変調・符号化#26

LDPC符号 — 疎な検査行列とメッセージパッシングでシャノン限界に迫る

パリティ検査行列Hをわざと疎にすることで、Tannerグラフ上のメッセージパッシング(Sum-Product/Belief Propagation)による並列・反復復号が可能になる。ターボ符号と並ぶもう一つのシャノン限界近傍符号、LDPC符号をチェックノード・変数ノード更新式まで導出する。

前提知識: shannon-capacity

LDPC誤り訂正符号TannerグラフBelief PropagationCCSDS

この回で学ぶこと

シャノン限界の回で、深宇宙通信は電力制限領域にあり、符号化研究の歴史は「 $E_b/N_0$ のシャノン限界 $-1.6$ dBにどこまで迫れるか」という壁への挑戦の歴史だったことを見ました。その回では、1993年のターボ符号がこの壁にわずか1dB程度まで迫る衝撃的な性能を示したことに触れました。しかし、シャノン限界近傍符号の歴史はターボ符号だけでは語れません。もう一つの、そしてある意味ではターボ符号以上に現代の深宇宙・近地球ミッションで存在感を増している符号が、この回で扱う LDPC符号 (Low-Density Parity-Check code, 低密度パリティ検査符号) です。

LDPC符号自体の発明は実はターボ符号よりずっと古く、1960年代前半にRobert G. Gallagerが博士論文の中で提案したものです。しかし当時の計算機では、その真価を発揮するために必要な反復復号を実用的な時間で実行することができず、長らく忘れられていました。1990年代半ば、ターボ符号の登場と歩調を合わせるように、David MacKayらによって再発見・再評価され、以来「反復復号でシャノン限界に迫る符号」のもう一つの柱として急速に研究が進みました。今日ではCCSDSの標準にも採用され、特に並列実装のしやすさという点でターボ符号を上回る特性を持つことから、近年の深宇宙・近地球ミッションの多くで標準的な誤り訂正符号として選ばれています。

この回では、LDPC符号を特徴づける「疎なパリティ検査行列」という定義から出発し、それをTannerグラフというグラフ構造として可視化し、そのグラフ上でメッセージ(対数尤度比)をやり取りしながら反復的に復号する**Sum-Product復号(Belief Propagation)**アルゴリズムを、チェックノード更新式・変数ノード更新式のレベルまで数式で導出します。そして、なぜこの構造がターボ符号よりも並列実装・高速復号に向いているのかを明らかにし、最後にCCSDS標準のLDPC符号(AR4JA符号など)が実際のミッションでどう使われているかを見ていきます。

直感的導入 — 疎な制約とローカルな合意形成

まず言葉で全体像を掴みましょう。線形符号は一般に、パリティ検査行列 $H$ (サイズ $(n-k)\times n$ )を使って、長さ $n$ の符号語 $\mathbf{c}=(c_1,\dots,c_n)$ が満たすべき条件

H\mathbf{c}^{\mathsf T} = \mathbf{0}

として定義されます。 $H$ の各行は「これらのビットのXORはゼロでなければならない」という1本のパリティ検査制約を表します。

ここでLDPC符号の定義そのものはただ一つ、「 $H$ が疎(sparse)である」ということだけです。つまり、 $H$ の各行・各列に含まれる1の個数(行重み・列重み)が、符号長 $n$ に対して非常に少ない(典型的には定数、あるいは $\log n$ 程度)ということです。密な $H$ (たとえば各行の重みが $n/2$ 程度もある)を持つ符号と比べ、疎な $H$ を持つ符号は、各パリティ検査が「ごく少数のビットだけに関与する、局所的な制約」になります。

この「疎性」がなぜそんなに重要なのでしょうか。直感的にはこう理解できます。もし各パリティ検査が数百・数千個のビットに関与する密な制約だったら、「この検査が満たされているか」を確かめるだけでも大量の計算が要り、しかも「どのビットが怪しいか」という情報を的確に分配することも難しくなります。一方、各検査がたった数個(たとえば3〜6個)のビットだけに関与する疎な制約であれば、個々の検査は単純な「多数決に近い」局所的な処理で済みます。そして、たくさんの単純な局所的検査をネットワーク状につなぎ、互いに情報(この後「メッセージ」と呼びます)を交換させながら反復的に磨き上げていくと、驚くほど正確な全体としての復号推定に収束する。これがLDPC符号の基本アイデアです。まるで、それぞれは断片的な情報しか持たない多数の人間が、隣人とだけ噂話(メッセージ)を交換し合っているうちに、やがて全員が正しい「真相」に近い認識へと収束していく——そんな分散的な合意形成のプロセスに似ています。

以下ではこの直感を、まずグラフ表現、次に数式的なメッセージパッシングのアルゴリズムへと具体化していきます。

Tannerグラフ — 符号を二部グラフとして描く

パリティ検査行列 $H$ は、Tannerグラフと呼ばれる二部グラフ(bipartite graph)として視覚化できます。

変数ノード (variable node) $v_1,\dots,v_n$ : 符号語の各ビット $c_1,\dots,c_n$ に対応する。
チェックノード (check node) $u_1,\dots,u_{n-k}$ : $H$ の各行(各パリティ検査制約)に対応する。
エッジ: $H$ の $(j,i)$ 成分が $H_{ji}=1$ であるとき、かつそのときに限り、チェックノード $u_j$ と変数ノード $v_i$ の間にエッジを引く。

このグラフ上で、変数ノード $v_i$ の次数(接続するエッジの本数)は $H$ の第 $i$ 列の重み(列重み $d_v$ )に、チェックノード $u_j$ の次数は $H$ の第 $j$ 行の重み(行重み $d_c$ )に、それぞれ等しくなります。すべての変数ノードの次数が同じ $d_v$ 、すべてのチェックノードの次数が同じ $d_c$ であるとき、その符号を $(d_v, d_c)$ -正則LDPC符号 と呼びます(実務上はチェックノード次数を意図的に不揃いにする不規則(irregular)LDPC符号の方が、密度発展(density evolution)という解析手法によって最適化されており、性能が優れていることが多いのですが、この回では基本形である正則符号を中心に扱います)。

疎性の条件は、このグラフの言葉で言えば「グラフ全体のエッジ数が $n$ に対して線形( $n d_v$ 本、 $d_v$ は定数)にとどまり、 $n^2$ のオーダーにはならない」ということです。この線形性が、後述する復号の計算量が符号長に対して線形にとどまることの直接の理由になります。

以降のSum-Product復号は、まさにこのTannerグラフの上で、変数ノードとチェックノードが交互にメッセージを送り合う反復アルゴリズムとして定式化されます。

対数尤度比によるビットの表現

反復復号の道具として、各ビットの確からしさを 対数尤度比(Log-Likelihood Ratio, LLR)

L(c_i) \equiv \ln\frac{P(c_i = 0)}{P(c_i = 1)}

という1つの実数で表すことにします。 $L>0$ ならビットは0らしい、 $L<0$ なら1らしい、 $|L|$ が大きいほど確信度が高いという直感的な意味を持ちます。

BPSK変調・AWGN通信路(ビット $c_i\in\{0,1\}$ を振幅 $a_i = (-1)^{c_i}\sqrt{E_s}$ に写像し、受信サンプル $y_i = a_i + n_i$ 、 $n_i \sim \mathcal N(0,\sigma^2)$ )を仮定すると、受信サンプルだけから計算できる通信路LLRは、ガウス尤度比を計算することで

L_{\mathrm{ch},i} \equiv \ln\frac{P(y_i \mid c_i=0)}{P(y_i \mid c_i=1)} = \frac{2\sqrt{E_s}}{\sigma^2}\, y_i

という、受信サンプル $y_i$ に単純に比例する形になります。これが復号アルゴリズムへの入力です。

LLRのもう一つ重要な性質は、 $t \equiv \tanh(L/2)$ と置くと

\tanh\!\left(\frac{L}{2}\right) = P(c=0) - P(c=1)

が成り立つことです(2値確率変数のLLRの定義から直接導けます)。この $t$ を「バイアス(bias)」と呼ぶことにします。 $t=+1$ なら確実に0、 $t=-1$ なら確実に1、 $t=0$ ならまったくの五分五分です。次節のチェックノード更新式は、このバイアス表現を使うと驚くほどきれいに書けます。

チェックノード更新式の導出 — XORのバイアスは積で伝わる

チェックノード $u_j$ に接続する変数ノードの集合を $N(j)$ と書きます。パリティ検査制約は「 $N(j)$ に属するビットのXORがゼロ」という条件でした。ここで考えたい問いは、「 $N(j)\setminus\{i\}$ (検査対象からビット $i$ 自身を除いた残りのビットたち)の(独立と仮定した)LLRが分かっているとき、パリティ制約を満たすためにビット $i$ が0であるべきという確信度(これを外部情報, extrinsic informationと呼びます)はどれだけか」ということです。

まず、独立な2つの2値変数 $c_1, c_2$ のXOR $c_1\oplus c_2$ のバイアスを考えます。 $t_1 = P(c_1=0)-P(c_1=1)$ 、 $t_2$ も同様として、

\begin{aligned} P(c_1\oplus c_2=0) - P(c_1\oplus c_2=1) &= \big[P(c_1{=}0)P(c_2{=}0) + P(c_1{=}1)P(c_2{=}1)\big] \\ &\quad - \big[P(c_1{=}0)P(c_2{=}1) + P(c_1{=}1)P(c_2{=}0)\big] \\ &= \big[P(c_1{=}0)-P(c_1{=}1)\big]\big[P(c_2{=}0)-P(c_2{=}1)\big] = t_1 t_2 \end{aligned}

つまり、独立な2ビットのXORのバイアスは、それぞれのバイアスの単純な積になります。 この結果は帰納法により、3個以上のビットのXORにもそのまま拡張できます。

\text{bias}\big(c_{i_1}\oplus c_{i_2}\oplus\cdots\oplus c_{i_m}\big) = \prod_{k=1}^{m} t_{i_k} = \prod_{k=1}^m \tanh\!\left(\frac{L_{i_k}}{2}\right)

したがって、チェックノード $u_j$ から変数ノード $i\in N(j)$ へ送る外部情報メッセージ(「 $N(j)\setminus\{i\}$ のビットのXORが0であってほしい」というバイアスをLLRに戻したもの)は、

\tanh\!\left(\frac{L_{j\to i}}{2}\right) = \prod_{i'\in N(j)\setminus\{i\}} \tanh\!\left(\frac{L_{i'\to j}}{2}\right)

すなわち

\boxed{L_{j\to i} = 2\tanh^{-1}\!\left(\prod_{i'\in N(j)\setminus\{i\}} \tanh\!\left(\frac{L_{i'\to j}}{2}\right)\right)}

これがチェックノード更新式です。積の中に自分自身( $i$ )を含めない(すなわち $i$ 以外の情報だけを使う)のがポイントで、これにより「自分が言ったことがそのまま自分に返ってくる」という自己参照的な情報の水増しを避けています。

変数ノード更新式 — 独立な証拠の単純な足し算

次に、変数ノード側を考えます。あるビット $c_i$ について得られる証拠は、通信路から得た $L_{\mathrm{ch},i}$ と、接続する各チェックノードから送られてくる外部情報 $L_{j\to i}$ ( $j\in N(i)$ )です。これらの証拠が(局所的な木構造の仮定のもとで)互いに独立であるとみなせるなら、対数尤度比の性質「独立な証拠のLLRは単純に加算できる」(ベイズ則を対数領域で書いたときの自然な帰結)により、ビット $i$ から特定のチェックノード $j$ へ送る外部情報メッセージは、そのチェックノード自身からの情報を除いた残り全部の和として、

\boxed{L_{i\to j} = L_{\mathrm{ch},i} + \sum_{j'\in N(i)\setminus\{j\}} L_{j'\to i}}

と書けます。これが変数ノード更新式です。ここでも「 $j$ 自身からの情報を除く」ことで、同じ自己参照の問題を避けています。

そして、最終的な(すべての証拠を使った)ビット $i$ の推定LLRは、全チェックノードからの情報を(除外なしで)すべて足し合わせた

L_i = L_{\mathrm{ch},i} + \sum_{j\in N(i)} L_{j\to i}

で与えられ、判定は符号だけを見て

\hat c_i = \begin{cases} 0 & L_i \ge 0 \\ 1 & L_i < 0 \end{cases}

とします。

Sum-Product復号アルゴリズムのまとめ

以上の2つの更新式を、Tannerグラフ全体で反復的に適用するのがSum-Product復号(Belief Propagation, BP)です。

初期化: すべての $i,j$ ( $i\in N(j)$ )について $L_{i\to j}^{(0)} = L_{\mathrm{ch},i}$ とする。
チェックノード更新: 各チェックノード $j$ とその近傍の各 $i\in N(j)$ について、 $L_{j\to i} = 2\tanh^{-1}\!\left(\prod_{i'\in N(j)\setminus\{i\}} \tanh\!\left(\tfrac{L_{i'\to j}}{2}\right)\right)$
変数ノード更新: 各変数ノード $i$ とその近傍の各 $j\in N(i)$ について、 $L_{i\to j} = L_{\mathrm{ch},i} + \sum_{j'\in N(i)\setminus\{j\}} L_{j'\to i}$
暫定判定: $L_i = L_{\mathrm{ch},i} + \sum_{j\in N(i)} L_{j\to i}$ から $\hat{\mathbf c}$ を決定し、 $H\hat{\mathbf c}^{\mathsf T}=\mathbf 0$ が成り立つか確認する。成り立てば復号成功として終了。
成り立たなければ、あらかじめ定めた最大反復回数に達するまでステップ2に戻る。

この手順は、Tannerグラフに閉路(サイクル)が存在しない木構造であれば、有限回の反復で厳密な事後確率(周辺分布)に一致することが情報理論的に保証されます。実際のLDPC符号のTannerグラフには短いサイクルが存在しますが(完全な木にはできません)、サイクルの長さ(girth)を十分大きく設計すれば、この「木構造での厳密性」が近似的に成り立ち、経験的に非常に良い復号性能が得られることが知られています。

なぜLDPC符号はターボ符号より並列実装・高速復号に向いているのか

ターボ符号の復号(BCJR/MAPアルゴリズムに基づく反復復号)と比較すると、LDPC符号の復号には決定的な構造上の違いがあります。

ターボ復号の中核であるBCJRアルゴリズムは、各構成符号(畳み込み符号)のトレリス上で、時刻 $1$ から $N$ へ向かう前向き再帰(状態確率 $\alpha_t$ を $\alpha_{t-1}$ から計算)と、時刻 $N$ から $1$ へ向かう後ろ向き再帰(状態確率 $\beta_t$ を $\beta_{t+1}$ から計算)を実行します。 $\alpha_t$ は $\alpha_{t-1}$ に依存し、 $\alpha_{t-1}$ は $\alpha_{t-2}$ に依存し……という具合に、この再帰は本質的に**逐次的(シーケンシャル)**であり、トレリスの長さ $N$ に比例した長さの依存関係の鎖(計算の「深さ」)を持ちます(スライディングウィンドウ法などである程度並列化・パイプライン化はできますが、鎖状の依存関係そのものは解消できません)。さらに2つの構成符号のBCJR復号器は、インターリーバを介して外部情報を交互に交換しながら動作するため、全体として反復ごとに直列的な処理段階を踏む構造になっています。

これに対し、LDPC符号のSum-Product復号では、あるチェックノードの更新は、直前の反復で得られた近傍の変数ノードからのメッセージだけに依存し、他のチェックノードの更新結果には一切依存しません(ステップ2で全チェックノードが使うのは、1つ前の反復で確定した $L_{i\to j}$ の値だけです)。したがって、1回の反復の中で、すべてのチェックノード更新を完全に同時並行して計算でき、同様にすべての変数ノード更新も完全に同時並行して計算できます。計算の「深さ」は近傍ノードの次数( $d_c$ や $d_v$ 、いずれも符号長 $n$ に依存しない定数)だけで決まり、符号長 $n$ には依存しません。

この「更新の局所性(locality)」こそが、LDPC符号がFPGAやASICによる完全並列・パイプライン化されたハードウェア復号器に向いている本質的な理由です。符号長が数千〜数万ビットに及ぶ現代の高速リンクでも、すべてのノードの更新を並列演算器に割り当てて同時に処理できるため、ターボ復号よりも高いスループット(ビット/秒)を、より低い復号遅延で実現できます。また、疎行列であることから1回の反復あたりの演算量も総エッジ数 $nd_v$ (すなわち $O(n)$ )にとどまり、密な行列を扱う場合の $O(n^2)$ と比べて大きな計算量削減にもなっています。

CCSDS標準LDPC符号 — AR4JA符号

CCSDS勧告書 CCSDS 131.0-B (TM Synchronization and Channel Coding) には、LDPC符号の具体的な符号構成として AR4JA (Accumulate–Repeat–4–JAgged–accumulate) と呼ばれる符号族が規定されています。名前が示す通り、情報ビット列を繰り返し(repeat)、疎な並べ替え(jagged accumulate)を経て、アキュムレータ(積分器的な構造を持つ簡単な畳み込み演算)に通すことで、系統的かつ疎な $H$ 行列を効率よく生成する構造的な設計になっており、符号化・復号双方をハードウェアに実装しやすいという特徴を持ちます。

AR4JA符号族は、符号化率 $R=1/2,\ 2/3,\ 4/5$ と、情報ブロック長 $k=1024,\ 4096,\ 16384$ ビットの組み合わせが標準として定義されており、ミッションの要求データレートや許容遅延に応じて選択されます。長いブロック長(たとえば $k=16384$ )の符号では、目標ビット誤り率 $10^{-6}$ 程度においてシャノン限界からのギャップが1dB未満にまで達することが報告されており、これはターボ符号に匹敵する、あるいは条件によってはそれを上回る性能です。加えてCCSDSは、深宇宙リンクに特化してさらに低い誤り率フロア(error floor、反復復号特有の「ある誤り率以下で性能改善が頭打ちになる」現象)を狙った符号構成(C2 LDPC符号)も別途規定しており、再送がほぼ不可能な深宇宙リンクの信頼性要求に応えています。

実務での使われ方

LDPC符号がターボ符号と並ぶ、あるいはそれ以上に近年のミッションで選ばれる理由は、前節までで見た2点に集約されます。(1) 十分長い符号語であればシャノン限界に1dB程度まで迫れる高い符号化利得、(2) チェックノード・変数ノードの更新が局所的で独立なため完全並列なハードウェア復号器を組みやすく、高スループット・低遅延の復号が可能であること。

具体的には、NASAのルナー・リコネサンス・オービター(LRO)は、月から地球へのKaバンド高速ダウンリンクにCCSDS標準のAR4JA LDPC符号を採用し、限られた送信電力の中で高いデータレートを実現しました。また、近年の多くの近地球ミッションやCubeSatクラスの小型衛星でも、比較的短いブロック長( $k=1024$ )のLDPC符号がFPGAベースのソフトウェア無線受信機に実装しやすいという理由から広く採用されています。深宇宙ミッションにおいても、JPLをはじめとする機関がAR4JA符号やC2符号の採用・評価を進めており、ターボ符号(CCSDS 131.0-Bにも並記されている符号化率1/2, 1/3, 1/6のターボ符号)と並んで、ミッションの通信システム設計者が符号化利得・復号遅延・実装コストのバランスを見ながら選択する、現代の深宇宙・近地球通信における標準的な選択肢の一つとなっています。

DSN Telecommunications Link Design Handbook (810-005) のリンクバジェット設計モジュールにも、採用する符号ごとの所要 $E_b/N_0$ とそのシャノン限界からのギャップが一覧化されており、LDPC符号はそこで「高スループット・低遅延を要求されるリンクにおける第一候補」として位置づけられています。

演習問題

符号長 $n=6$ 、検査数 $n-k=3$ の次のパリティ検査行列を考えます。
$H = \begin{pmatrix} 1&1&0&1&0&0 \\ 0&1&1&0&1&0 \\ 1&0&1&0&0&1 \end{pmatrix}$
この $H$ に対応するTannerグラフを、変数ノード $v_1,\dots,v_6$ とチェックノード $u_1,u_2,u_3$ の接続関係として書き下し、各変数ノードの次数(列重み)と各チェックノードの次数(行重み)を求めてください。また、符号語候補 $\mathbf c=(1,1,0,0,0,1)$ が $H\mathbf c^{\mathsf T}=\mathbf 0$ を満たすかどうかを検算してください。
あるチェックノード $u_j$ に3本のエッジがあり、そのうち2本から届いた変数ノードLLRが $L_{1\to j}=1.5$ 、 $L_{2\to j}=-2.0$ であったとします。残る1本のエッジ(変数ノード $i$ )へチェックノードから送られる外部情報 $L_{j\to i} = 2\tanh^{-1}\!\big(\tanh(L_{1\to j}/2)\tanh(L_{2\to j}/2)\big)$ を数値計算してください(電卓・数値計算ツール使用可)。符号が反転していること(片方が正、片方が負)が、結果のLLRの符号にどう影響するか、 $\tanh$ の奇関数性から説明してください。
変数ノード更新式 $L_{i\to j} = L_{\mathrm{ch},i} + \sum_{j'\in N(i)\setminus\{j\}} L_{j'\to i}$ が、なぜ単純な「足し算」で書けるのか、対数尤度比の定義に立ち返って説明してください。またチェックノード更新式が足し算ではなく $\tanh$ を介した積になる理由を、XORという演算の性質(この回で導いたバイアスの積公式)と対比しながら論じてください。
列重み $d_v$ 、行重み $d_c$ の $(d_v,d_c)$ -正則LDPC符号(符号長 $n$ )において、1回の反復あたりの総メッセージ計算量が $O(n)$ にとどまる理由を、Tannerグラフの総エッジ数から説明してください。さらに、ターボ符号のBCJR復号におけるトレリス上の前向き・後ろ向き再帰が本質的に逐次的である理由と対比し、なぜLDPC符号のメッセージパッシングが完全並列なハードウェア実装に向いているのかを、この回で学んだ更新式の依存関係をもとに自分の言葉で説明してください。

まとめと次回予告

この回では、ターボ符号と並んでシャノン限界に迫る現代符号のもう一つの柱であるLDPC符号を扱いました。疎なパリティ検査行列 $H$ が定義するTannerグラフの上で、チェックノード更新式(XORのバイアスが積で伝わる性質から導かれる $\tanh$ を介した式)と変数ノード更新式(独立な証拠のLLRの単純な加算)を交互に適用するSum-Product復号(Belief Propagation)は、各ノードの更新が近傍だけに依存する局所的な計算であるがゆえに、ターボ復号のBCJRトレリス再帰のような逐次的な依存関係を持たず、完全並列なハードウェア実装に向いているという点が、この符号の大きな強みでした。CCSDS標準のAR4JA符号は、十分な符号語長のもとでシャノン限界から1dB未満まで迫る性能を持ち、LRO をはじめとする実ミッションで採用されています。

次回は、この2つの符号(ターボ符号・LDPC符号)を含め、CCSDSの誤り訂正符号化標準がリード・ソロモン+畳み込み符号の連接符号から、いつ、どのような経緯でターボ符号・LDPC符号へと移行してきたのか、CCSDS符号化標準の変遷を概観します。

参考文献

R. G. Gallager, Low-Density Parity-Check Codes, MIT Press, 1963(および “Low-density parity-check codes,” IRE Transactions on Information Theory, vol. 8, 1962)
D. J. C. MacKay, R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electronics Letters, vol. 32, 1996
T. J. Richardson, R. L. Urbanke, Modern Coding Theory, Cambridge University Press, 2008
R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Transactions on Information Theory, vol. 27, 1981
CCSDS 131.0-B, TM Synchronization and Channel Coding
DSN Telecommunications Link Design Handbook, DSN No. 810-005
J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76