デジタル通信では、ノイズのある通信路を通じてデータを正確に届ける必要があります。携帯電話の通話、Wi-Fiによるインターネット接続、人工衛星からの画像送信——いずれも通信路上で生じるビット誤りを自動的に検出・訂正する仕組みがなければ成り立ちません。では、シャノンの通信路符号化定理が示す理論限界にどこまで近づける符号が存在するのでしょうか。
その答えの一つがLDPC符号（Low-Density Parity-Check code、低密度パリティ検査符号）です。1962年にガラガー（Robert Gallager）が博士論文で提案したこの符号は、当時の計算能力では実用化できず、30年以上も忘れ去られていました。しかし1990年代後半に再発見されると、シャノン限界にきわめて近い性能を持つことが示され、通信技術に革命をもたらしました。
LDPC符号を理解すると、以下のような分野への応用が見えてきます。
- 5G/6G通信: 5G NRの制御チャネル（PBCH等）やデータチャネルでLDPC符号が標準採用されています
- 衛星通信: DVB-S2（デジタル衛星放送規格）でLDPC符号が使われ、限られた送信電力で高品質な通信を実現しています
- Wi-Fi: IEEE 802.11n/ac/ax（Wi-Fi 4/5/6）でLDPC符号がオプションまたは必須として導入されています
- 深宇宙通信: NASAの深宇宙探査ミッションでも、低SNR環境下での高信頼通信にLDPC符号が利用されています
本記事の内容
- LDPC符号の基本概念 — スパース性がもたらす利点
- パリティ検査行列とタナーグラフの対応関係
- LDPC符号の構成法 — 正則符号と不正則符号
- 確率伝搬法（Belief Propagation）による反復復号アルゴリズム
- 密度発展法による理論的性能解析
- PythonによるLDPC符号の実装と性能評価
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 線形符号の理論 — 生成行列と検査行列 — 線形符号の基礎、パリティ検査行列の定義と性質
- ハミング符号の理論と誤り訂正能力 — 古典的な誤り訂正符号の例
- ターボ符号の理論 — 反復復号と性能限界 — 反復復号の概念を理解する助けになります
- 交差エントロピーとKLダイバージェンスの関係 — 確率的な復号の背景にある情報理論
LDPC符号の基本概念 — スパース性の力
「低密度」とは何か
LDPC符号を理解するために、まず名前の意味を紐解きましょう。「低密度パリティ検査」とは、パリティ検査行列 $\bm{H}$ の中に含まれる1の割合が非常に少ない（すなわちスパースである）ことを意味しています。
線形符号の理論で学んだように、$[n, k]$ 線形符号はパリティ検査行列 $\bm{H}$（$(n-k) \times n$ 行列）で定義されます。符号語 $\bm{c}$ は $\bm{H}\bm{c}^T = \bm{0}$ を満たすベクトルです。
ハミング符号やリード・ソロモン符号のような古典的な符号では、パリティ検査行列の要素に1が比較的密に含まれています。一方、LDPC符号ではこの行列がスパース——各行や各列に含まれる1の個数が、行列のサイズ $n$ に比べて非常に少ない——という特徴があります。
たとえば、$n = 1000$ の符号を考えたとき、ハミング符号の検査行列の各行にはおよそ $n/2 = 500$ 個の1が含まれますが、LDPC符号では各行に含まれる1の個数は6個や8個といった定数オーダーにとどまります。
なぜスパースだと良いのか
スパース性がもたらす利点は、大きく3つあります。
第一に、効率的な復号アルゴリズムが使えます。 パリティ検査行列がスパースであるということは、各パリティ検査式が関与する変数（ビット）の数が少ないことを意味します。この構造を利用すると、各検査式で局所的な計算を行い、その結果をビット間で交換するメッセージパッシング（message passing）アルゴリズムが適用可能になります。復号の計算量は符号長 $n$ に対してほぼ線形 $O(n)$ であり、最尤復号の指数的な計算量 $O(2^n)$ と比べて圧倒的に効率的です。
第二に、長い符号長が実用的になります。 符号長を長くするほど誤り訂正能力は向上し、シャノン限界に近づくことがシャノンの符号化定理から知られています。しかし、復号の計算量が符号長に対して指数的に増大する符号では、長い符号を使うことは現実的ではありません。LDPC符号は線形計算量の復号器を持つため、$n = 10000$ や $n = 100000$ といった非常に長い符号を実用的に使えるのです。
第三に、シャノン限界に漸近的に到達できます。 ランダムに構成されたLDPC符号の性能は、符号長を大きくしていくとシャノン限界に任意に近づくことが理論的に証明されています。これは、スパースなグラフ構造を持つ符号が、ランダム符号化と同等の性能を持ちうることを意味しています。
このスパース性を体系的に理解するために、LDPC符号をグラフとして表現する方法を見ていきましょう。
タナーグラフ — LDPC符号のグラフ表現
二部グラフとしての表現
LDPC符号のスパースなパリティ検査行列は、タナーグラフ（Tanner graph）と呼ばれる二部グラフ（bipartite graph）で視覚的に表現できます。タナーグラフは1981年にタナー（R. Michael Tanner）が提案した表現方法で、LDPC符号の構造と復号アルゴリズムを理解する上で不可欠な道具です。
タナーグラフは2種類のノード（頂点）から構成されます。
- 変数ノード（variable node）: 符号語の各ビット $c_1, c_2, \dots, c_n$ に対応する $n$ 個のノード。丸で描かれます。
- 検査ノード（check node）: パリティ検査行列 $\bm{H}$ の各行（検査式）に対応する $m = n – k$ 個のノード。四角で描かれます。
変数ノード $j$ と検査ノード $i$ の間にエッジ（辺）が存在するのは、$H_{ij} = 1$ のとき——つまり、第 $i$ 番目のパリティ検査式に第 $j$ 番目のビットが関与しているとき——に限ります。パリティ検査行列がスパースであるということは、このグラフのエッジが少ない、すなわちグラフが疎であることを意味しています。
具体例で理解する
次のパリティ検査行列を考えましょう。
$$ \bm{H} = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix} $$
これは $[n=6, k=3]$ の符号で、3つの検査式があります。
- 検査式1: $c_1 \oplus c_2 \oplus c_4 = 0$
- 検査式2: $c_2 \oplus c_3 \oplus c_5 = 0$
- 検査式3: $c_1 \oplus c_3 \oplus c_6 = 0$
ここで $\oplus$ は排他的論理和（XOR）を表します。
この検査行列のタナーグラフでは、上段に6つの変数ノード（$c_1$ から $c_6$）、下段に3つの検査ノード（$f_1$ から $f_3$）が並びます。検査式1は $c_1, c_2, c_4$ に関与するので、$f_1$ からこれら3つの変数ノードにエッジが引かれます。同様に、$f_2$ は $c_2, c_3, c_5$ に、$f_3$ は $c_1, c_3, c_6$ にエッジが引かれます。
各変数ノードの次数（接続するエッジの数）は、$\bm{H}$ の対応する列の重み（1の個数）に等しくなります。この例では、$c_1$ と $c_3$ の次数は2、$c_2$ の次数も2、$c_4, c_5, c_6$ の次数は1です。各検査ノードの次数は、$\bm{H}$ の対応する行の重みに等しく、この例ではすべての検査ノードの次数が3です。
ループとグラフの性質
タナーグラフにおいて重要な概念がループ（cycle）の長さです。二部グラフにおけるループの最短長をガース（girth）と呼びます。二部グラフでは奇数長のループは存在しないため、ガースは偶数（最小値は4）です。
ガースが大きいほど、後述する確率伝搬法（BP）の復号性能が向上します。これは、BP復号がグラフが木構造である場合に最適であり、ガースが大きいほど局所的にグラフが木に近くなるためです。直感的には、ループが長ければ、メッセージが巡回して自分自身に戻るまでの反復回数が多くなり、メッセージの独立性がより良く保たれます。
実用的なLDPC符号では、ガースが6以上になるように設計されることが一般的です。ガースが4のグラフには、2つの変数ノードが2つの検査ノードを共有する構造が含まれ、復号性能を劣化させます。
グラフ構造としてLDPC符号を理解したところで、次にLDPC符号を体系的に構成する方法を見ていきましょう。
LDPC符号の構成法
正則LDPC符号
ガラガーが最初に提案したLDPC符号は正則（regular）LDPC符号と呼ばれます。正則LDPC符号では、すべての変数ノードの次数が $d_v$、すべての検査ノードの次数が $d_c$ で統一されています。パリティ検査行列 $\bm{H}$ で言えば、各列にちょうど $d_v$ 個の1が、各行にちょうど $d_c$ 個の1が含まれています。
このような符号を $(d_v, d_c)$-正則LDPC符号と呼びます。パリティ検査行列のサイズは $m \times n$ であり、1の総数は列から数えると $nd_v$、行から数えると $md_c$ となるため、以下の関係が成り立ちます。
$$ nd_v = md_c $$
符号化率 $R$ は $R = k/n = 1 – m/n$（$\bm{H}$ がフルランクの場合）であるため、次のように表されます。
$$ R = 1 – \frac{d_v}{d_c} $$
たとえば $(3, 6)$-正則LDPC符号の場合、符号化率は $R = 1 – 3/6 = 1/2$ です。各ビットは3つの検査式に関与し、各検査式は6つのビットを含みます。
ガラガーの構成法
ガラガーは、正則LDPC符号のパリティ検査行列を以下のように構成しました。$\bm{H}$ を $d_v$ 個のサブ行列 $\bm{H}_1, \bm{H}_2, \dots, \bm{H}_{d_v}$ に分割します。
$$ \bm{H} = \begin{pmatrix} \bm{H}_1 \\ \bm{H}_2 \\ \vdots \\ \bm{H}_{d_v} \end{pmatrix} $$
最初のサブ行列 $\bm{H}_1$ は、各行に連続する $d_c$ 個の1が並ぶ構造にします。
$$ \bm{H}_1 = \begin{pmatrix} 1 \cdots 1 & 0 \cdots 0 & \cdots & 0 \cdots 0 \\ 0 \cdots 0 & 1 \cdots 1 & \cdots & 0 \cdots 0 \\ \vdots & & \ddots & \vdots \\ 0 \cdots 0 & 0 \cdots 0 & \cdots & 1 \cdots 1 \end{pmatrix} $$
残りのサブ行列 $\bm{H}_2, \dots, \bm{H}_{d_v}$ は、$\bm{H}_1$ の列をランダムに並べ替え（列置換）して得ます。この構成により、各列にはちょうど $d_v$ 個の1が含まれ（各サブ行列から1つずつ）、各行にはちょうど $d_c$ 個の1が含まれます。
不正則LDPC符号
1990年代後半に、不正則（irregular）LDPC符号が正則LDPC符号よりもシャノン限界に近い性能を達成できることが発見されました。不正則LDPC符号では、変数ノードや検査ノードの次数が統一されておらず、次数の分布に自由度があります。
不正則LDPC符号の次数分布は、2つの多項式で特徴づけられます。変数ノード次数分布 $\lambda(x)$ と検査ノード次数分布 $\rho(x)$ です。
$$ \lambda(x) = \sum_{i=2}^{d_{v,\max}} \lambda_i x^{i-1}, \quad \rho(x) = \sum_{j=2}^{d_{c,\max}} \rho_j x^{j-1} $$
ここで $\lambda_i$ は次数 $i$ の変数ノードに接続するエッジの割合、$\rho_j$ は次数 $j$ の検査ノードに接続するエッジの割合を表します。$\lambda(1) = 1$、$\rho(1) = 1$ という正規化条件を満たします。
なぜ「エッジ」の割合なのかというと、復号アルゴリズムがメッセージをエッジ上で交換するため、エッジ視点での次数分布が復号性能の解析に自然に現れるからです。ノード視点での次数分布 $L(x) = \sum_i L_i x^i$、$R(x) = \sum_j R_j x^j$（$L_i$ は次数 $i$ の変数ノードの割合、$R_j$ は次数 $j$ の検査ノードの割合）とは次の関係で結ばれます。
$$ \lambda_i = \frac{i L_i}{\sum_k k L_k}, \quad \rho_j = \frac{j R_j}{\sum_k k R_k} $$
不正則LDPC符号の符号化率は次のように表されます。
$$ R = 1 – \frac{\sum_j \rho_j / j}{\sum_i \lambda_i / i} $$
最適な次数分布の設計は、後述する密度発展法（density evolution）を用いて行います。最適化された不正則LDPC符号は、シャノン限界から0.0045 dB以内の性能を達成することが報告されています。
PEG（Progressive Edge-Growth）アルゴリズム
実用的なLDPC符号の構成法として広く使われているのが、PEG（Progressive Edge-Growth）アルゴリズムです。PEGアルゴリズムは、与えられた次数分布に従いつつ、ガースをできるだけ大きくするようにエッジを一本ずつ追加していくグリーディ・アルゴリズムです。
アルゴリズムの手順は次のとおりです。
- 変数ノードを次数の昇順に並べる
- 各変数ノードについて、必要な次数に達するまでエッジを一本ずつ追加する
- エッジを追加する際、その変数ノードから幅優先探索（BFS）を行い、最も遠い検査ノード（最後に到達する検査ノード）を選んで接続する
- 同じ距離の検査ノードが複数ある場合は、現在の次数が最も小さいものを選ぶ
この方法により、短いループの生成が抑制され、与えられた符号長と次数分布に対して良好なグラフ構造を持つLDPC符号が効率的に構成されます。
LDPC符号の構成法を理解したところで、いよいよ復号アルゴリズムの核心——確率伝搬法——に進みましょう。
確率伝搬法（Belief Propagation）による復号
復号問題の定式化
通信路の出力として受信信号 $\bm{y} = (y_1, y_2, \dots, y_n)$ が得られたとき、送信された符号語 $\bm{c} = (c_1, c_2, \dots, c_n)$ を推定する問題を考えます。二元入力AWGN（加法的白色ガウス雑音）通信路を仮定すると、送信信号 $x_j = 1 – 2c_j$（BPSK変調: $c_j = 0 \to x_j = +1$、$c_j = 1 \to x_j = -1$）に対して受信信号は
$$ y_j = x_j + n_j $$
です。ここで $n_j \sim \mathcal{N}(0, \sigma^2)$ はガウス雑音です。$\mathrm{SNR} = E_b/N_0$ との関係は $\sigma^2 = 1/(2R \cdot E_b/N_0)$ です（$R$ は符号化率）。
最適な復号は、最大事後確率（MAP）推定
$$ \hat{c}_j = \arg\max_{c_j \in \{0,1\}} P(c_j \mid \bm{y}) $$
ですが、これは一般に計算量が指数的です。LDPC符号では、タナーグラフ上の確率伝搬法（BP: Belief Propagation）による近似が、非常に良い性能を発揮します。
対数尤度比（LLR）の導入
復号アルゴリズムの記述を簡潔にするため、対数尤度比（LLR: Log-Likelihood Ratio）を導入します。ビット $c_j$ に関するLLRは次のように定義されます。
$$ L(c_j) = \ln \frac{P(c_j = 0)}{P(c_j = 1)} $$
LLRが正であれば $c_j = 0$ が確からしく、負であれば $c_j = 1$ が確からしいことを意味します。LLRの絶対値が大きいほど、その判定の確信度が高いことを表しています。
通信路からの受信情報のLLR（通信路LLR）は、AWGN通信路の場合
$$ L_{\mathrm{ch}}(y_j) = \ln \frac{P(y_j \mid c_j = 0)}{P(y_j \mid c_j = 1)} = \ln \frac{P(y_j \mid x_j = +1)}{P(y_j \mid x_j = -1)} $$
と定義されます。ガウス雑音の確率密度関数を代入すると、
$$ L_{\mathrm{ch}}(y_j) = \ln \frac{\exp\left(-\frac{(y_j – 1)^2}{2\sigma^2}\right)}{\exp\left(-\frac{(y_j + 1)^2}{2\sigma^2}\right)} = \frac{2y_j}{\sigma^2} $$
となり、受信信号 $y_j$ に比例するシンプルな形になります。この結果は直感にも合います——受信値が大きな正の値であれば $x_j = +1$（$c_j = 0$）が送信されたと考えるのが自然であり、LLRも大きな正の値になります。
Sum-Product アルゴリズム
LDPC符号のBP復号で最も広く使われるのが、Sum-Productアルゴリズム（SPA）です。タナーグラフ上で変数ノードと検査ノードの間でLLRメッセージを繰り返し交換し、各ビットの事後LLRを徐々に精緻化していきます。
以下の記号を使います。
- $\mathcal{N}(j)$: 変数ノード $j$ に隣接する検査ノードの集合
- $\mathcal{M}(i)$: 検査ノード $i$ に隣接する変数ノードの集合
- $\mu_{j \to i}$: 変数ノード $j$ から検査ノード $i$ へのメッセージ（LLR）
- $\mu_{i \to j}$: 検査ノード $i$ から変数ノード $j$ へのメッセージ（LLR）
アルゴリズムは次の手順で進みます。
ステップ0（初期化）: 各変数ノード $j$ から隣接するすべての検査ノード $i \in \mathcal{N}(j)$ へ、通信路LLRをメッセージとして送ります。
$$ \mu_{j \to i}^{(0)} = L_{\mathrm{ch}}(y_j) $$
ステップ1（検査ノード更新）: 各検査ノード $i$ は、隣接する変数ノードから受け取ったメッセージを使って、変数ノード $j$ への返信メッセージを計算します。$j$ 以外の隣接変数ノードからのメッセージに基づく「$j$ のビットが0か1かの推定」です。
$$ \mu_{i \to j}^{(\ell)} = 2 \tanh^{-1} \left( \prod_{j’ \in \mathcal{M}(i) \setminus \{j\}} \tanh\left(\frac{\mu_{j’ \to i}^{(\ell-1)}}{2}\right) \right) $$
この式は、パリティ検査の制約（$\bigoplus_{j’ \in \mathcal{M}(i)} c_{j’} = 0$）を確率的に反映しています。$\tanh$ 関数が確率の積をLLR領域で効率的に扱うための数学的道具です。
直感的に理解すると、パリティ検査式は「関与するビットのXORが0」という制約です。検査ノード $i$ が変数ノード $j$ に送るメッセージは、「$j$ 以外のビットの推定値を総合すると、$j$ はこの値であるべきだ」という情報です。他のビットの確信度が高いほど、$j$ についての推定も確信度が高くなります。
$\tanh$ の積が使われる理由は次のとおりです。2つの独立な二元確率変数のXORの確率を計算するとき、LLR領域では $\tanh(L/2)$ の積を取ることが自然な演算になります。これは $\tanh(L/2) = (P(0) – P(1))/(P(0) + P(1))$ であり、独立なXORの $\tanh$ 値は各変数の $\tanh$ 値の積となるからです。
ステップ2（変数ノード更新）: 各変数ノード $j$ は、通信路LLRと隣接する検査ノード（$i$ 以外）からのメッセージを足し合わせて、検査ノード $i$ への返信メッセージを計算します。
$$ \mu_{j \to i}^{(\ell)} = L_{\mathrm{ch}}(y_j) + \sum_{i’ \in \mathcal{N}(j) \setminus \{i\}} \mu_{i’ \to j}^{(\ell)} $$
変数ノードの更新は単純な加算です。これは、独立な情報源からのLLRは加算で合成できるという性質に基づいています。通信路から得た情報と、各検査ノードからのパリティ制約に基づく情報を合わせて、より信頼性の高い推定を行います。
ただし、検査ノード $i$ に送るメッセージには $i$ からのメッセージを含めません（外因性情報の原則: extrinsic information）。もし $i$ からのメッセージを含めてしまうと、$i$ に自分自身の情報を送り返すことになり、情報の二重計上が起きてしまいます。
ステップ3（事後LLRの計算と判定）: 各反復の最後に、各ビットの事後LLR $L_j$ を計算します。
$$ L_j^{(\ell)} = L_{\mathrm{ch}}(y_j) + \sum_{i \in \mathcal{N}(j)} \mu_{i \to j}^{(\ell)} $$
ここでは（ステップ2と異なり）すべての隣接検査ノードからのメッセージを含めます。これが各ビットの最終的な推定値です。
硬判定で復号結果を得ます。
$$ \hat{c}_j = \begin{cases} 0 & \text{if } L_j^{(\ell)} \geq 0 \\ 1 & \text{if } L_j^{(\ell)} < 0 \end{cases} $$
復号語 $\hat{\bm{c}} = (\hat{c}_1, \dots, \hat{c}_n)$ がパリティ検査条件 $\bm{H}\hat{\bm{c}}^T = \bm{0}$ を満たせば復号成功とし、アルゴリズムを終了します。満たさない場合は、最大反復回数に達するまでステップ1とステップ2を繰り返します。
Min-Sum 近似
Sum-Productアルゴリズムの検査ノード更新には $\tanh$ と $\tanh^{-1}$ の計算が必要であり、ハードウェア実装では計算コストが問題になることがあります。Min-Sumアルゴリズムは、これを次のように近似します。
$$ \mu_{i \to j}^{(\ell)} \approx \left(\prod_{j’ \in \mathcal{M}(i) \setminus \{j\}} \mathrm{sign}\left(\mu_{j’ \to i}^{(\ell-1)}\right)\right) \cdot \min_{j’ \in \mathcal{M}(i) \setminus \{j\}} \left|\mu_{j’ \to i}^{(\ell-1)}\right| $$
この近似は、$\tanh$ の引数の絶対値が大きいとき $|\tanh(x)| \approx 1$ であることに基づいています。最も信頼性の低いメッセージ（絶対値が最小のもの）がボトルネックとなるため、最小値を取ります。符号（sign）の積はパリティ制約を反映します。
Min-Sum近似は性能が若干劣化しますが、正規化Min-Sum（Normalized Min-Sum）やオフセットMin-Sum（Offset Min-Sum）といった改良版では、性能劣化を小さく抑えつつ計算量を大幅に削減できます。正規化Min-Sumでは上記の最小値に正規化係数 $\alpha$（典型的には $\alpha = 0.75 \sim 0.85$）を乗じ、オフセットMin-Sumでは正の定数 $\beta$ を減じます。
BP復号の仕組みを理解したところで、次にこのアルゴリズムの理論的な性能限界を解析する方法を見ていきましょう。
密度発展法による性能解析
密度発展法とは
密度発展法（Density Evolution）は、符号長が無限大の極限においてBP復号の性能を厳密に追跡する理論的手法です。2001年にリチャードソン（Thomas Richardson）とウルバンケ（Rüdiger Urbanke）によって体系化されました。
密度発展法の基本的な考え方は次のとおりです。BP復号の各反復で、変数ノードから検査ノードへのメッセージの確率密度関数（または確率質量関数）がどのように変化するかを追跡します。符号長が無限大の場合、タナーグラフはサイクルフリー（木構造）に近づき、メッセージの独立性の仮定が正当化されるため、確率密度関数の発展を正確に記述できます。
二元対称通信路（BSC）での密度発展
密度発展法の考え方を、最も単純な二元対称通信路（BSC）で説明しましょう。BSCでは、各ビットが確率 $p$ で反転します。
BP復号の各反復 $\ell$ における、変数ノードから検査ノードへのメッセージの誤り確率を $x^{(\ell)}$ とします。密度発展の更新式は次のようになります。
検査ノード更新後のメッセージの誤り確率：
$$ y^{(\ell)} = \frac{1}{2}\left(1 – (1 – 2x^{(\ell-1)})^{d_c – 1}\right) $$
この式の意味を理解しましょう。検査ノードは $d_c – 1$ 個のメッセージを受け取り、それらのXORに基づいて返信します。各メッセージが独立に誤り確率 $x$ で間違っているとすると、XORの結果の誤り確率は上の式で与えられます。$(1 – 2x)^{d_c-1}$ は各メッセージの「正しさの度合い」$1 – 2x$ の積であり、$d_c – 1$ 個すべてが正しい場合にのみXORの結果が正しくなることを反映しています。
変数ノード更新後のメッセージの誤り確率：
$$ x^{(\ell)} = p \cdot \left(y^{(\ell)}\right)^{d_v – 1} $$
変数ノードは通信路からの情報（誤り確率 $p$）と $d_v – 1$ 個の検査ノードからのメッセージ（各々の誤り確率 $y$）を受け取ります。多数決的に判定するため、すべてが間違っている場合にのみ誤りが残ります。
これら2つの式を合成すると、$(d_v, d_c)$-正則LDPC符号の密度発展の再帰式が得られます。
$$ x^{(\ell)} = p \cdot \left[\frac{1}{2}\left(1 – (1 – 2x^{(\ell-1)})^{d_c – 1}\right)\right]^{d_v – 1} $$
初期値は $x^{(0)} = p$ です。反復を繰り返して $x^{(\ell)} \to 0$ であれば、復号が成功することを意味します。$x^{(\ell)} \to 0$ とならない最大の $p$ がしきい値 $p^*$ であり、BSCのビット反転確率がこのしきい値以下であれば、符号長を十分長くすることで誤り率を任意に小さくできます。
AWGN通信路での密度発展
AWGN通信路の場合、メッセージは連続値のLLRであるため、確率密度関数の発展を追跡する必要があります。正確な密度発展は数値積分を伴い計算が重くなりますが、重要な性質として対称性（symmetric）と一致性（consistency）があります。
対称ガウス近似（Gaussian Approximation）では、各反復でのメッセージのLLR分布をガウス分布 $\mathcal{N}(m, 2m)$ で近似します。ここで分散が平均の2倍であるという関係は、対称条件（symmetric condition）から導かれます。この近似により、密度発展はスカラーの再帰式に帰着します。
対称ガウス近似のもとで、$(d_v, d_c)$-正則LDPC符号の再帰式は次のようになります。変数ノードから検査ノードへのメッセージの平均LLR $m_v^{(\ell)}$ について、
$$ m_v^{(\ell)} = m_{\mathrm{ch}} + (d_v – 1) \cdot m_c^{(\ell-1)} $$
ここで $m_{\mathrm{ch}} = 2/\sigma^2$ は通信路LLRの平均です。検査ノード更新は対称ガウス近似のもとで
$$ m_c^{(\ell)} = \phi^{-1}\left(1 – \left[1 – \phi(m_v^{(\ell)})\right]^{d_c – 1}\right) $$
と書けます。ここで $\phi(x)$ は次で定義される関数です。
$$ \phi(x) = \begin{cases} 1 – \frac{1}{\sqrt{4\pi x}} \int_{-\infty}^{\infty} \tanh\left(\frac{u}{2}\right) e^{-\frac{(u-x)^2}{4x}} du & \text{if } x > 0 \\ 1 & \text{if } x = 0 \end{cases} $$
この関数は数値的にテーブル化して利用されます。
密度発展法により、しきい値 $\sigma^*$（等価的に $(E_b/N_0)^*$）が求まります。不正則LDPC符号の次数分布を最適化する問題は、密度発展のしきい値を最大化する（=必要なSNRを最小化する）最適化問題として定式化されます。
EXIT チャート
密度発展法の計算負荷を軽減するための実用的な手法として、EXITチャート（Extrinsic Information Transfer chart）があります。EXITチャートは、変数ノード復号器と検査ノード復号器のそれぞれについて、入力の相互情報量と出力の相互情報量の関係（伝達特性）を描画し、2つの曲線が交差しないこと（「トンネル」が開いていること）が復号成功の条件となります。
変数ノード復号器のEXIT関数 $I_E^{(v)}(I_A)$ は、事前情報の相互情報量 $I_A$ と外因性情報の相互情報量 $I_E$ の関係を表します。検査ノード復号器のEXIT関数 $I_E^{(c)}(I_A)$ も同様です。BP復号の反復は、これらの2つの関数を交互に適用する過程に対応し、EXITチャート上では階段状の軌跡として可視化できます。
この軌跡が右上の点 $(1, 1)$ に到達すれば復号成功、途中で2つの曲線に挟まれて停滞すれば復号失敗です。しきい値はちょうど2つの曲線が接する点で決まります。
密度発展法とEXITチャートによる理論的解析を理解したところで、ここまでの理論をPythonで実装して確認しましょう。
PythonによるLDPC符号の実装
LDPC符号の構成と復号の実装
まず、正則LDPC符号のパリティ検査行列をガラガーの方法で構成し、Sum-Product復号を実装します。
import numpy as np
import matplotlib.pyplot as plt
def gallager_ldpc(n, dv, dc):
"""ガラガーの方法で(dv, dc)-正則LDPC符号のパリティ検査行列を構成する"""
m = n * dv // dc # 検査行数
# 第1サブ行列: 連続するdc個の1を持つ行
H1 = np.zeros((m // dv, n), dtype=int)
for i in range(m // dv):
H1[i, i * dc:(i + 1) * dc] = 1
# 残りのサブ行列: H1の列をランダムに並べ替え
H = H1.copy()
for _ in range(dv - 1):
perm = np.random.permutation(n)
H = np.vstack([H, H1[:, perm]])
return H
def bp_decode(H, y, sigma, max_iter=50):
"""Sum-Productアルゴリズムによる復号"""
m, n = H.shape
# 通信路LLR
Lch = 2 * y / (sigma ** 2)
# 隣接関係の取得
check_neighbors = [np.where(H[i, :] == 1)[0] for i in range(m)]
var_neighbors = [np.where(H[:, j] == 1)[0] for j in range(n)]
# メッセージの初期化
# msg_v_to_c[i][j]: 変数ノードjから検査ノードiへのメッセージ
msg_v_to_c = {}
msg_c_to_v = {}
for i in range(m):
for j in check_neighbors[i]:
msg_v_to_c[(i, j)] = Lch[j]
msg_c_to_v[(i, j)] = 0.0
for iteration in range(max_iter):
# 検査ノード更新
for i in range(m):
neighbors = check_neighbors[i]
for j in neighbors:
# j以外の隣接変数ノードからのメッセージのtanhの積
product = 1.0
for j_prime in neighbors:
if j_prime != j:
val = msg_v_to_c[(i, j_prime)] / 2.0
product *= np.tanh(np.clip(val, -20, 20))
# 数値安定性のためにクリッピング
product = np.clip(product, -1 + 1e-15, 1 - 1e-15)
msg_c_to_v[(i, j)] = 2.0 * np.arctanh(product)
# 変数ノード更新 + 事後LLR計算
L_total = Lch.copy()
for j in range(n):
neighbors = var_neighbors[j]
for i in neighbors:
L_total[j] += msg_c_to_v[(i, j)]
# 硬判定
c_hat = (L_total < 0).astype(int)
# パリティ検査
syndrome = H @ c_hat % 2
if np.all(syndrome == 0):
return c_hat, iteration + 1, True
# 変数ノードから検査ノードへのメッセージ更新
for j in range(n):
neighbors = var_neighbors[j]
for i in neighbors:
msg_v_to_c[(i, j)] = Lch[j]
for i_prime in neighbors:
if i_prime != i:
msg_v_to_c[(i, j)] += msg_c_to_v[(i_prime, j)]
return c_hat, max_iter, False
上のコードでは、ガラガーの構成法で正則LDPC符号のパリティ検査行列を作成し、Sum-Productアルゴリズムで反復復号を行っています。bp_decode 関数の中で、検査ノード更新では $\tanh$ の積を取り、変数ノード更新ではLLRの加算を行うという、先に述べた理論がそのまま実装されています。数値的な安定性のために np.clip を使ってオーバーフローを防いでいる点にも注目してください。
BER性能のシミュレーション
AWGN通信路上でのビット誤り率（BER）をシミュレーションし、符号なし（未符号化）の場合と比較します。
np.random.seed(42)
# (3, 6)-正則LDPC符号, n=120
n = 120
dv = 3
dc = 6
H = gallager_ldpc(n, dv, dc)
k = n - H.shape[0] # 情報ビット数
R = k / n # 符号化率
# Eb/N0の範囲 (dB)
ebn0_db_range = np.arange(0, 7.5, 0.5)
ber_uncoded = []
ber_ldpc = []
num_frames = 500 # フレーム数
for ebn0_db in ebn0_db_range:
ebn0 = 10 ** (ebn0_db / 10)
sigma = np.sqrt(1 / (2 * R * ebn0))
# 未符号化BER (理論値)
from scipy.special import erfc
ber_uncoded.append(0.5 * erfc(np.sqrt(ebn0)))
# LDPC符号のBERシミュレーション
total_errors = 0
total_bits = 0
for _ in range(num_frames):
# 全ゼロ符号語を送信（対称性より一般性を失わない）
c = np.zeros(n, dtype=int)
x = 1 - 2 * c # BPSK: 0 -> +1, 1 -> -1
y = x + sigma * np.random.randn(n)
c_hat, iters, success = bp_decode(H, y, sigma, max_iter=50)
total_errors += np.sum(c_hat != c)
total_bits += n
ber_ldpc.append(total_errors / total_bits)
# プロット
plt.figure(figsize=(8, 5))
plt.semilogy(ebn0_db_range, ber_uncoded, 'b--', label='Uncoded (theory)')
plt.semilogy(ebn0_db_range, [max(b, 1e-7) for b in ber_ldpc],
'ro-', label=f'LDPC ({dv},{dc}), n={n}')
plt.xlabel('$E_b/N_0$ (dB)')
plt.ylabel('BER')
plt.title('LDPC Code BER Performance')
plt.legend()
plt.grid(True, which='both', alpha=0.3)
plt.ylim(1e-6, 1)
plt.tight_layout()
plt.show()
このシミュレーション結果から、いくつかの重要な特徴が読み取れます。
- 符号化利得: LDPC符号を使用することで、同じBERを達成するために必要な $E_b/N_0$ が大幅に低下します。たとえばBER = $10^{-4}$ では、未符号化の場合は約8.4 dBが必要ですが、LDPC符号ではそれよりも数dB低い値で達成できます。
- ウォーターフォール領域: LDPC符号のBER曲線には、ある $E_b/N_0$ を境にBERが急激に減少する「ウォーターフォール」（滝）と呼ばれる領域が現れます。この急峻な遷移は、密度発展法で予測されるしきい値の存在を反映しています。
- 符号長の影響: $n = 120$ という比較的短い符号長でも符号化利得が確認できますが、実用的なLDPC符号（$n = 10000$ 以上）ではさらに急峻なウォーターフォールが得られ、シャノン限界に近い性能が発揮されます。
密度発展法の数値計算
$(3, 6)$-正則LDPC符号の密度発展をBSCで計算し、しきい値を求めます。
def density_evolution_bsc(dv, dc, p, max_iter=200, tol=1e-10):
"""BSCに対する密度発展法"""
x = p # 初期誤り確率
trajectory = [x]
for _ in range(max_iter):
# 検査ノード更新
y = 0.5 * (1 - (1 - 2 * x) ** (dc - 1))
# 変数ノード更新
x_new = p * y ** (dv - 1)
trajectory.append(x_new)
if x_new < tol:
break
x = x_new
return trajectory
# しきい値の二分探索
def find_threshold_bsc(dv, dc, tol=1e-6):
"""BSCのしきい値を二分探索で求める"""
p_low, p_high = 0.0, 0.5
while p_high - p_low > tol:
p_mid = (p_low + p_high) / 2
traj = density_evolution_bsc(dv, dc, p_mid)
if traj[-1] < 1e-10:
p_low = p_mid
else:
p_high = p_mid
return (p_low + p_high) / 2
# (3,6)-正則LDPC符号のしきい値
threshold = find_threshold_bsc(3, 6)
print(f"(3,6)-正則LDPC符号のBSCしきい値: p* = {threshold:.6f}")
# シャノン限界: C = 1 - H(p) = R = 0.5 より H(p) = 0.5
from scipy.optimize import brentq
def shannon_eq(p):
if p <= 0 or p >= 1:
return 1.0
return -p * np.log2(p) - (1 - p) * np.log2(1 - p) - 0.5
p_shannon = brentq(shannon_eq, 0.01, 0.49)
print(f"シャノン限界 (R=0.5): p_Shannon = {p_shannon:.6f}")
print(f"しきい値のギャップ: {p_shannon - threshold:.6f}")
# 密度発展の軌跡を可視化
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# 左: しきい値付近での収束/発散
p_values = [0.06, 0.08, threshold, 0.10, 0.11]
for p in p_values:
traj = density_evolution_bsc(3, 6, p, max_iter=100)
label = f'p={p:.4f}'
if abs(p - threshold) < 1e-5:
label += ' (threshold)'
axes[0].semilogy(range(len(traj)), traj, '-o', markersize=3, label=label)
axes[0].set_xlabel('Iteration')
axes[0].set_ylabel('Error probability $x^{(\ell)}$')
axes[0].set_title('Density Evolution Trajectory (BSC)')
axes[0].legend(fontsize=9)
axes[0].grid(True, alpha=0.3)
axes[0].set_ylim(1e-15, 1)
# 右: 更新関数 f(x) = p * [0.5*(1-(1-2x)^(dc-1))]^(dv-1) のプロット
x_range = np.linspace(0, 0.15, 1000)
for p in [0.06, threshold, 0.11]:
y = 0.5 * (1 - (1 - 2 * x_range) ** 5)
fx = p * y ** 2
label = f'p={p:.4f}'
if abs(p - threshold) < 1e-5:
label += ' (threshold)'
axes[1].plot(x_range, fx, label=label)
axes[1].plot(x_range, x_range, 'k--', label='y = x', alpha=0.5)
axes[1].set_xlabel('$x^{(\ell)}$')
axes[1].set_ylabel('$x^{(\ell+1)}$')
axes[1].set_title('Fixed-point analysis')
axes[1].legend(fontsize=9)
axes[1].grid(True, alpha=0.3)
axes[1].set_xlim(0, 0.15)
axes[1].set_ylim(0, 0.15)
plt.tight_layout()
plt.show()
密度発展の結果から、以下のことが読み取れます。
-
しきい値の存在: $(3, 6)$-正則LDPC符号のBSCしきい値は約 $p^* \approx 0.0840$ です。通信路の反転確率がこの値より小さければ、反復を重ねるごとに誤り確率は指数的に0に収束します。しきい値を超えると、誤り確率は正の値に収束し、復号は失敗します。
-
シャノン限界との比較: 符号化率 $R = 0.5$ のシャノン限界は $p_{\text{Shannon}} \approx 0.1100$ です。しきい値とのギャップは約0.026であり、正則LDPC符号でもかなりシャノン限界に近いことがわかります。不正則LDPC符号では、このギャップをさらに小さくできます。
-
固定点解析: 右のグラフでは、密度発展の更新関数 $f(x)$ と直線 $y = x$ の交点が固定点を表しています。$p < p^*$ では $f(x) < x$ であり、反復により $x \to 0$ に収束します。$p > p^*$ では $f(x) > x$ となる領域が現れ、正の固定点が存在し、そこに収束してしまいます。しきい値ちょうどでは、$f(x)$ が $y = x$ に接します。
LDPC符号の実用面での考慮事項
符号化の課題
LDPC符号の符号化は、一般にはパリティ検査行列 $\bm{H}$ から生成行列 $\bm{G}$ を求めるガウス消去法で行えますが、計算量は $O(n^2)$ であり、長い符号では問題になります。
この課題に対する解決策として、以下のアプローチが使われています。
準巡回（QC: Quasi-Cyclic）LDPC符号: パリティ検査行列を巡回シフト行列のブロックで構成することで、符号化を線形時間 $O(n)$ で行えるようにします。5G NRやWi-Fiで採用されているLDPC符号はすべてQC構造を持っています。QC-LDPC符号の検査行列は次の形をしています。
$$ \bm{H} = \begin{pmatrix} \bm{P}_{0,0} & \bm{P}_{0,1} & \cdots & \bm{P}_{0,n_b-1} \\ \bm{P}_{1,0} & \bm{P}_{1,1} & \cdots & \bm{P}_{1,n_b-1} \\ \vdots & \vdots & \ddots & \vdots \\ \bm{P}_{m_b-1,0} & \bm{P}_{m_b-1,1} & \cdots & \bm{P}_{m_b-1,n_b-1} \end{pmatrix} $$
ここで $\bm{P}_{i,j}$ は $z \times z$ の巡回置換行列（または零行列）です。$z$ はリフティングサイズと呼ばれます。
RU（Richardson-Urbanke）の近似下三角（ALT）符号化: $\bm{H}$ の一部を下三角行列にする構造を導入し、後退代入で線形時間の符号化を可能にします。
エラーフロア
LDPC符号のBER曲線は、高SNR領域で傾きが緩やかになるエラーフロア（error floor）現象を示すことがあります。エラーフロアの原因は、タナーグラフ中のトラッピングセット（trapping set）と呼ばれる小規模な構造です。トラッピングセットは、BP復号が正しく収束できない変数ノードの小さな集合であり、少数のビット誤りが残存する原因となります。
エラーフロアを低減するための方法として、次のものがあります。
- グラフ構造の最適化: PEGアルゴリズムやACE（Approximate Cycle Extrinsic message degree）制約を用いて、有害なトラッピングセットを避ける
- ポストプロセッシング: BP復号後にOSD（Ordered Statistics Decoding）や Auxiliary Variable Nodeの追加で残存誤りを修正する
- 符号設計: 最小距離を大きくする設計や、ABP（Absorbing set Based Post-processing）の導入
ハードウェア実装
LDPC符号の復号器のハードウェア実装では、以下の点が重要です。
並列処理: タナーグラフの構造上、同じ層（変数ノード層または検査ノード層）内のノード更新は独立に行えるため、高度な並列化が可能です。
固定小数点化: LLRメッセージを固定小数点で表現することで、浮動小数点演算器を使わずに実装できます。Min-Sum近似は特にハードウェアフレンドリーで、乗算器なしで実装可能です。
レイヤード復号: QC-LDPC符号では、検査行列の各ブロック行を1つのレイヤーとして、レイヤーごとに順次更新するレイヤード復号（layered decoding）が広く使われています。標準的なフラッディング（flooding）方式に比べて収束が約2倍速く、必要な反復回数を半減できます。
LDPC符号とターボ符号の比較
LDPC符号とターボ符号はどちらもシャノン限界に近い性能を持つ符号ですが、いくつかの重要な違いがあります。
性能面: 短い符号長（$n < 1000$程度）ではターボ符号が優位ですが、長い符号長（$n > 10000$）ではLDPC符号が優位になる傾向があります。これは、LDPC符号のタナーグラフが木に近づくのに長い符号長が必要なためです。
エラーフロア: ターボ符号は比較的低いエラーフロアを持つ傾向がありますが、LDPC符号のエラーフロアは符号設計で制御可能です。
復号遅延: LDPC符号のBP復号は高度に並列化可能であるため、高スループットの実装ではLDPC符号が有利です。ターボ符号のMAP復号は本質的に逐次的な部分があり、並列化が制限されます。
標準化状況: 5G NRではデータチャネルにLDPC符号、制御チャネルにポーラー符号が採用され、ターボ符号は4G LTEまでの規格にとどまっています。これはLDPC符号の高スループット実装の容易さが評価された結果です。
まとめ
本記事では、LDPC符号の理論と実装について解説しました。
- スパース性の力: LDPC符号の本質は、パリティ検査行列がスパース（低密度）であることです。このスパース性が、線形計算量の復号アルゴリズム、長い符号長の実用化、シャノン限界への漸近を可能にします
- タナーグラフ: 二部グラフとしての表現が、符号の構造と復号アルゴリズムを統一的に理解する鍵です。ガースやトラッピングセットといったグラフの性質が直接的に復号性能に影響します
- 確率伝搬法: Sum-Productアルゴリズムは、タナーグラフ上のメッセージパッシングとして自然に定式化されます。LLR領域では、変数ノードの加算と検査ノードの $\tanh$ 積という2つの基本演算の繰り返しです
- 密度発展法: 符号長無限大の極限で、BP復号の性能を厳密に追跡する理論的枠組みです。しきい値の存在とその計算方法を理解することは、符号設計の基礎です
- 実用的設計: QC構造、不正則次数分布、PEGアルゴリズムなどの技術が、理論と実用のギャップを埋めています
LDPC符号は、シャノンの理論から60年後に実用的な形で「理論限界に手が届く符号」を実現した歴史的成果です。情報理論の基礎を学んだ上で、このような符号が実際に設計・実装される仕組みを理解することは、通信工学の深い理解につながります。
次のステップとして、以下の記事も参考にしてください。
- 線形符号の理論 — 生成行列と検査行列 — LDPC符号の数学的基盤
- ターボ符号の理論 — 反復復号と性能限界 — もう一つのシャノン限界級符号
- 交差エントロピーとKLダイバージェンスの関係 — 確率的復号の情報理論的背景