衛星通信や5G、SSDのストレージコントローラには、共通して LDPC 符号という誤り訂正符号が使われています。同じ送信電力でも、良い符号を使えばより小さな雑音電力（高い雑音、低い SNR）まで通信を成立させられます。では、ある LDPC 符号は「どこまで雑音が強くなったら復号できなくなる」のでしょうか。この境目を 復号しきい値 (decoding threshold) と呼び、それを反復復号を実際に走らせずに予測する強力な理論が 密度発展 (density evolution) です。
たとえば、深宇宙探査機からの微弱な信号を地上局で受ける場面を考えてみましょう。受信 SNR が 0.5 dB 改善できれば、必要なアンテナ径や送信電力を大幅に削減できます。LDPC 符号の設計者は「この次数分布なら SNR が何 dB まで耐えられるか」を知りたいわけですが、実際にモンテカルロシミュレーションでビット誤り率 (BER) 曲線を描くには莫大な計算が必要です。密度発展は、無限符号長・木構造仮定のもとで、復号メッセージの確率分布がイテレーションごとにどう変化するか を追跡し、しきい値を解析的・数値的に求めてしまいます。
密度発展が活きる応用先は次の2つに代表されます。
- 符号設計: 次数分布（どのノードが何本の辺を持つか）を最適化し、シャノン限界に肉薄する不規則 LDPC 符号を設計する。実際、密度発展で最適化された符号はシャノン限界の 0.0045 dB まで迫った記録があります。
- 性能予測: 新しいチャネル（フェージング、量子化された軟判定など）に対して、シミュレーション前にしきい値を見積もり、設計の当たりを付ける。
本記事の内容
- 密度発展の考え方（木構造仮定と確率密度の追跡）を直感的に理解する
- 対称チャネルにおける変数ノード・チェックノードの密度更新（密度畳み込み）を省略せず導出する
- ガウス近似によって平均 LLR の1次元再帰式に簡約し、しきい値の意味を明らかにする
- Python でガウス近似密度発展を実装し、正則 (3,6) 符号などのしきい値を数値求解する
- しきい値とシャノン限界・符号化率の関係を可視化して読み取る
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- LDPC符号とは？低密度パリティ検査符号の理論を解説 — LDPC のパリティ検査行列とタナーグラフの基礎
- Min-Sum法によるLDPC復号 — 反復メッセージパッシング復号（和積アルゴリズム）の流れ
- 通信路容量とシャノンの定理 — しきい値の比較対象となるシャノン限界
- AWGNチャネルモデル — 本記事で扱う加法的白色ガウス雑音チャネルと LLR の定義
特にタナーグラフ（変数ノードとチェックノードからなる二部グラフ）と、辺を伝わる対数尤度比 (LLR) メッセージの概念は本記事の土台になります。
密度発展とは
LDPC 復号は、タナーグラフ上で「変数ノード」と「チェックノード」がメッセージ（信頼度）を交換し合う反復処理です。雑音が弱ければメッセージの信頼度はイテレーションごとに高まり、やがて全ビットが正しく確定します。逆に雑音が強すぎると信頼度が育たず、復号は失敗します。この「信頼度が育つか育たないか」の分かれ目を見極めたい、というのが密度発展の出発点です。
ここで一つ重要な視点の転換があります。1本1本のメッセージの値を追いかけるのではなく、メッセージ全体が従う確率分布（密度） がイテレーションごとにどう変形していくかを追う、という見方です。たとえると、川を流れる無数の水滴の一粒一粒の軌跡ではなく、「水位の分布」がどう推移するかを見るようなものです。個々のメッセージはランダムですが、無限に多くのメッセージを束ねた密度は決定論的に進化します。
なぜ密度だけ追えば十分なのでしょうか。鍵は 木構造仮定 (tree assumption) です。符号長を無限大にすると、タナーグラフの局所構造は（高い確率で）短いループを含まない木とみなせます。木では、あるノードに入ってくる複数のメッセージが互いに独立になります。独立なら、複数メッセージを合成したときの分布は、個々の分布の畳み込みで計算できます。つまり「独立性」が密度の追跡を可能にしているのです。
正しく復号できる条件は、「イテレーション $\ell \to \infty$ で誤り確率が 0 に収束すること」と言い換えられます。チャネルの雑音強度をパラメータ（AWGN なら雑音分散 $\sigma^2$）で表すと、誤り確率が 0 に収束する $\sigma$ の上限が存在します。この上限が 復号しきい値 $\sigma^\*$（あるいは対応する SNR）です。$\sigma < \sigma^\*$ なら復号成功、$\sigma > \sigma^\*$ なら失敗。これが密度発展で求めたい量です。
では、メッセージの密度が具体的にどう更新されるのか、変数ノードとチェックノードそれぞれの処理を数式で追っていきましょう。
メッセージとLLR、対称性の仮定
まず扱う量を定義します。タナーグラフの辺を流れるメッセージは 対数尤度比 (LLR) で表します。ビット $x \in \{0, 1\}$ に対し、
$$ \begin{equation} L = \ln \frac{P(x = 0 \mid \text{情報})}{P(x = 1 \mid \text{情報})} \end{equation} $$
と定義します。$L > 0$ ならビットは 0 らしく、$L < 0$ なら 1 らしい。絶対値 $|L|$ が大きいほど信頼度が高いことを意味します。
AWGN チャネルで BPSK 変調（ビット 0 → $+1$、ビット 1 → $-1$）を使うとします。送信振幅を $\pm 1$、雑音分散を $\sigma^2$ とすると、受信値 $y$ から計算されるチャネル LLR は
$$ \begin{equation} L_{\text{ch}} = \frac{2y}{\sigma^2} \end{equation} $$
となります（AWGN チャネルの記事で導出した形です）。これがチャネルから各変数ノードに与えられる初期メッセージです。
解析を扱いやすくするために、全ゼロ符号語が送信された と仮定します。LDPC 符号は線形符号であり、後で述べる対称性のもとでは誤り確率が送信符号語によらないため、この仮定は一般性を失いません。全ゼロ符号語（全ビット 0）なら、正しいメッセージは $L > 0$ 側です。したがって「誤り確率」は $L < 0$ となる確率に対応します。
ここで密度発展が成立するための チャネル対称性 (symmetry) を定式化します。LLR メッセージの確率密度 $f(x)$ が
$$ \begin{equation} f(x) = f(-x)\, e^{x} \end{equation} $$
を満たすとき、対称（symmetric, consistent）であるといいます。この条件は、AWGN チャネルの LLR 密度（後で具体形を示します）が自然に満たすもので、密度発展の各更新がこの対称性を保存することが知られています。対称性が成り立つおかげで「全ゼロ符号語送信」の仮定が正当化され、解析が劇的に簡単になります。
メッセージと対称性の準備ができたので、次に変数ノードでメッセージがどう合成されるかを見ます。
変数ノードの密度更新（LLRの和）
変数ノードは、タナーグラフ上で1つの符号ビットに対応します。次数 $d_v$ の変数ノードには、チャネルから1本（LLR $L_{\text{ch}}$）と、隣接する $d_v$ 個のチェックノードからメッセージが届きます。あるチェックノード（出力先）に向けてメッセージを送るときは、その出力先以外 から来た情報をすべて足し合わせます（自分が送った情報を相手に送り返さない、という外因性メッセージの原則）。
直感的には、独立な複数の証拠が「同じビットが 0 だ」と言ってきたら、その確信は足し算で強まる、ということです。LLR は対数尤度比なので、独立な証拠の統合は積（確率の積）ではなく和（対数の和）になります。
数式で書くと、出力先以外の $d_v – 1$ 個のチェックノードからのメッセージ $L_1, \dots, L_{d_v – 1}$ とチャネル LLR $L_{\text{ch}}$ に対して、変数ノードが出力するメッセージは
$$ \begin{equation} L_{\text{out}}^{(v)} = L_{\text{ch}} + \sum_{i=1}^{d_v – 1} L_i \end{equation} $$
です。なぜ単純な和になるのか、導出しておきましょう。木構造仮定のもとで $L_{\text{ch}}, L_1, \dots, L_{d_v-1}$ は独立です。ビット $x$ について、各証拠が与える尤度比を掛け合わせると事後尤度比になります。対数を取ると、
$$ \begin{align} L_{\text{out}}^{(v)} &= \ln \frac{P(x=0 \mid \text{全証拠})}{P(x=1 \mid \text{全証拠})} \\ &= \ln \frac{P(x=0)\prod_j P(\text{証拠}_j \mid x=0)}{P(x=1)\prod_j P(\text{証拠}_j \mid x=1)} \\ &= \underbrace{\ln\frac{P(x=0)}{P(x=1)}}_{=0\,(\text{事前は対等})} + \sum_j \ln \frac{P(\text{証拠}_j \mid x=0)}{P(\text{証拠}_j \mid x=1)} \end{align} $$
となります。1行目から2行目はベイズの定理で事後を尤度と事前の積に分解、2行目から3行目は積の対数を和に分解しました。事前確率を対等（$P(x=0)=P(x=1)$）とすれば第1項は消え、各証拠の LLR の和だけが残ります。これが式 (4) の正体です。
さて、密度発展では「メッセージの値」ではなく「メッセージの分布」を追います。独立な確率変数の和の分布は、畳み込み (convolution) で計算できます。変数ノードに入るチェックノードメッセージの密度を $f^{(c)}(x)$、チャネル LLR の密度を $f_{\text{ch}}(x)$ とすると、変数ノードが出力するメッセージの密度 $f^{(v)}$ は
$$ \begin{equation} f^{(v)} = f_{\text{ch}} \otimes \underbrace{f^{(c)} \otimes \cdots \otimes f^{(c)}}_{d_v – 1 \text{ 回}} \end{equation} $$
と書けます。ここで $\otimes$ は畳み込みです。$d_v – 1$ 個の独立メッセージの和なので、密度を $d_v – 1$ 回畳み込み、さらにチャネル密度を1回畳み込みます。
この畳み込みは、密度のフーリエ変換（特性関数）の領域では単なる積になるため、数値計算では FFT を使えば高速に処理できます。変数ノードの更新は「LLR の和＝密度の畳み込み」というシンプルな構造を持つことが分かりました。
次は、もう一方のチェックノードの更新です。こちらは和ではなく、もう少し込み入った演算になります。
チェックノードの密度更新（tanh則）
チェックノードは、パリティ検査式（隣接する変数ノードの値の XOR が 0 になる、という制約）に対応します。次数 $d_c$ のチェックノードには $d_c$ 個の変数ノードがつながり、ある変数ノード（出力先）へメッセージを送るときは、それ以外の $d_c – 1$ 個から来たメッセージを使ってパリティ制約を満たすように信頼度を計算します。
直感的には、チェックノードは「足し合わせ」ではなく「最も自信のないメッセージに引きずられる」性質を持ちます。XOR の制約では、入力のうち1つでも符号（0か1か）が不確かだと、出力の確信も持てないからです。これが変数ノード（和で確信が強まる）と対照的な点です。
パリティ制約 $x_1 \oplus x_2 \oplus \cdots \oplus x_{d_c} = 0$ のもとで、メッセージの統合は tanh 則 に従います。入力メッセージ $L_1, \dots, L_{d_c – 1}$ に対する出力メッセージ $L_{\text{out}}^{(c)}$ は
$$ \begin{equation} \tanh\!\left(\frac{L_{\text{out}}^{(c)}}{2}\right) = \prod_{i=1}^{d_c – 1} \tanh\!\left(\frac{L_i}{2}\right) \end{equation} $$
を満たします。なぜ $\tanh$ が現れるのか導出します。1つのビット $x \in \{0,1\}$ の確率を $p_0 = P(x=0)$, $p_1 = P(x=1) = 1 – p_0$ とすると、LLR は $L = \ln(p_0/p_1)$ です。ここで「符号付き確率差」$p_0 – p_1$ を考えると、
$$ \begin{align} p_0 – p_1 &= \frac{p_0 – p_1}{p_0 + p_1} = \frac{e^{L} – 1}{e^{L} + 1} = \tanh\!\left(\frac{L}{2}\right) \end{align} $$
となります。途中、$p_0 + p_1 = 1$ で割っても値は変わらないこと、$p_0/p_1 = e^L$ を使って分子分母を $p_1$ で割ったことを用いました。$\tanh(L/2)$ は「ビットが 0 である分の確率差」を表す量だと分かります。
パリティ制約（複数ビットの XOR が 0）のもとでは、この「確率差」が掛け算で合成されることが知られています。2ビットの XOR を例に考えると、出力が 0 になる確率は「両方 0」または「両方 1」の確率の和で、確率差を計算すると2つの $\tanh$ の積になります。これを $d_c – 1$ ビットに一般化したのが式 (7) です。
出力 LLR を陽に書けば、逆 $\tanh$（$\text{atanh}$、あるいは $2\,\text{artanh}$）を取って
$$ \begin{equation} L_{\text{out}}^{(c)} = 2\, \text{artanh}\!\left( \prod_{i=1}^{d_c – 1} \tanh\!\left(\frac{L_i}{2}\right) \right) \end{equation} $$
です。$\tanh$ の値は $[-1, 1]$ に収まるので、積を取るたびに絶対値は小さくなります（最も小さい $|\tanh|$、すなわち最も確信のないメッセージに引きずられる）。これがチェックノードで信頼度が「目減り」する直感を裏付けています。
密度の更新は変数ノードと同様に畳み込みで書けますが、ここでは「和」ではなく「tanh の積」なので、$\tanh(L/2)$ という変数変換を施した領域で畳み込みを行う必要があります。具体的には、メッセージを $\gamma = (\text{sign}, -\ln|\tanh(L/2)|)$ のように符号と大きさに分け、その分布の畳み込みを取る、という手続きになります。厳密な密度発展はこの2次元的な畳み込みを数値的に行いますが、実装はかなり煩雑です。
そこで実用上は、メッセージ密度を ガウス分布で近似 して、追跡すべき量を「平均」1つに減らす手法が広く使われます。これがガウス近似密度発展です。次節で導きます。
ガウス近似による1次元化
厳密な密度発展は密度関数そのものを（離散化して）追跡しますが、計算量が大きく直感も得にくいものです。ここで強力な近似が効いてきます。変数ノードでは多数の LLR を足し合わせるため、中心極限定理的に メッセージ密度はガウス分布に近づく のです。さらに、対称性条件 $f(x) = f(-x)e^x$ をガウス分布 $\mathcal{N}(m, s^2)$ に課すと、$s^2 = 2m$ という関係が強制されます。
これを確かめます。ガウス密度 $f(x) = \frac{1}{\sqrt{2\pi s^2}}\exp\!\left(-\frac{(x-m)^2}{2s^2}\right)$ に対称条件を当てはめると、
$$ \begin{align} \frac{f(x)}{f(-x)} &= \exp\!\left(-\frac{(x-m)^2 – (x+m)^2}{2s^2}\right) = \exp\!\left(\frac{2mx}{s^2}\right) \end{align} $$
これが $e^x$ に等しくなければならないので、指数を比較して $\frac{2m}{s^2} = 1$、すなわち
$$ \begin{equation} s^2 = 2m \end{equation} $$
を得ます。つまり、対称なガウス分布は 平均 $m$ だけで完全に決まる（分散は平均の2倍）のです。追跡すべき量が分散と平均の2つから、平均1つに減りました。これがガウス近似の威力です。$m$ が大きいほど分布は正の側（正しい側）に寄り、$m \to \infty$ で誤り確率が 0 に収束します。
変数ノードの更新は LLR の和でしたから、ガウス近似のもとでは平均も単純に足し算になります。イテレーション $\ell$ におけるチェックノード→変数ノードメッセージの平均を $m_c^{(\ell)}$、チャネル LLR の平均を $m_{\text{ch}}$ とすると、変数ノードが出力するメッセージの平均 $m_v^{(\ell)}$ は
$$ \begin{equation} m_v^{(\ell)} = m_{\text{ch}} + (d_v – 1)\, m_c^{(\ell)} \end{equation} $$
です（独立変数の和の平均は平均の和）。AWGN チャネルでは、チャネル LLR $L_{\text{ch}} = 2y/\sigma^2$ の分布を計算すると、全ゼロ送信（BPSK で $+1$ 送信、$y = 1 + n$、$n \sim \mathcal{N}(0,\sigma^2)$）のとき平均は
$$ \begin{equation} m_{\text{ch}} = E\!\left[\frac{2y}{\sigma^2}\right] = \frac{2}{\sigma^2} \end{equation} $$
となります。分散は $\text{Var}(2y/\sigma^2) = 4\sigma^2/\sigma^4 = 4/\sigma^2 = 2 m_{\text{ch}}$ で、確かに対称性条件 $s^2 = 2m$ を満たしています。
チェックノードの更新は tanh 則なので和ほど単純ではありません。ここで補助関数を導入します。
$$ \begin{equation} \phi(m) = E\!\left[ \tanh\frac{L}{2} \right], \quad L \sim \mathcal{N}(m, 2m) \end{equation} $$
$\phi(m)$ は「平均 $m$ の対称ガウス分布に従う LLR の $\tanh(L/2)$ の期待値」です。tanh 則 (7) は $\tanh(L_{\text{out}}/2)$ が入力の $\tanh(L_i/2)$ の積であることを言っていました。期待値を取り、入力が独立同分布（平均 $m_v$）であれば、
$$ \begin{equation} \phi\!\left(m_c^{(\ell+1)}\right) = \left[\phi\!\left(m_v^{(\ell)}\right)\right]^{d_c – 1} \end{equation} $$
が成り立ちます。左辺は出力メッセージの $\tanh$ 期待値、右辺は $d_c – 1$ 個の入力の $\tanh$ 期待値の積です。これを $m_c$ について解くと、
$$ \begin{equation} m_c^{(\ell+1)} = \phi^{-1}\!\left( \left[\phi\!\left(m_v^{(\ell)}\right)\right]^{d_c – 1} \right) \end{equation} $$
となります。$\phi$ は単調減少（後で確認します）なので逆関数 $\phi^{-1}$ が定義できます。
これで密度発展の全体が「平均 LLR の1次元再帰」に簡約されました。式 (11) と (16) を組み合わせると、正則 $(d_v, d_c)$ 符号に対する更新は
$$ \begin{equation} m_c^{(\ell+1)} = \phi^{-1}\!\left( \left[\phi\!\left( m_{\text{ch}} + (d_v – 1) m_c^{(\ell)} \right)\right]^{d_c – 1} \right) \end{equation} $$
という1本の漸化式になります。初期値は $m_c^{(0)} = 0$（チェックノードからの初期メッセージは情報ゼロ）です。$\ell \to \infty$ で $m_c^{(\ell)} \to \infty$（したがって $m_v \to \infty$）となれば復号成功、有限値に留まれば失敗。この成功・失敗の境目を与える $\sigma$ が しきい値 $\sigma^\*$ です。
$\phi$ の性質を整理しておきます。$\phi(0) = E[\tanh(0)] = 0$ ではなく、$m \to 0$ で $\phi(m) \to 1$、$m \to \infty$ で $\phi(m) \to 0$ となる単調減少関数です（信頼度 $m$ が高いほど $\tanh(L/2)$ は1に近づき、その期待値も1に近づく）。閉形式はないので数値積分（モンテカルロや数値積分公式）で評価します。
理論が出そろいました。ここからは Python で $\phi$ を計算し、再帰式 (17) を回して正則 (3,6) 符号のしきい値を求めます。
Python実装：補助関数 φ の計算
まず再帰の心臓部である $\phi(m) = E[\tanh(L/2)]$（$L \sim \mathcal{N}(m, 2m)$）を数値積分で計算します。これがしきい値計算のすべての土台になります。
import numpy as np
import matplotlib.pyplot as plt
from scipy import integrate
from scipy.optimize import brentq
def phi(m, n_points=400):
"""
phi(m) = E[ tanh(L/2) ], L ~ N(m, 2m)
対称ガウス分布 (s^2 = 2m) における tanh(L/2) の期待値を数値積分で計算。
"""
if m <= 0:
return 1.0 # m=0 では情報ゼロ、tanh(L/2)の期待値は1に収束する極限
s = np.sqrt(2.0 * m) # 標準偏差
# 平均mを中心に±8σの範囲で積分（裾は無視できる）
lo, hi = m - 8 * s, m + 8 * s
L = np.linspace(lo, hi, n_points)
# ガウス重み × tanh(L/2)
pdf = np.exp(-(L - m) ** 2 / (2 * 2 * m)) / np.sqrt(2 * np.pi * 2 * m)
integrand = np.tanh(L / 2.0) * pdf
return np.trapz(integrand, L)
# phi(m) を描画して単調減少を確認
m_vals = np.linspace(0.01, 30, 200)
phi_vals = np.array([phi(m) for m in m_vals])
plt.figure(figsize=(8, 5))
plt.plot(m_vals, phi_vals, color='blue', linewidth=2)
plt.xlabel('平均 LLR m')
plt.ylabel(r'$\phi(m) = E[\tanh(L/2)]$')
plt.title('補助関数 φ(m)（単調減少）')
plt.grid(True, alpha=0.3)
plt.show()
このグラフから、$\phi(m)$ が $m \to 0$ で 1 に近づき、$m$ が大きくなるにつれて単調に 0 へ減少することが読み取れます。これは「平均 LLR（信頼度）$m$ が高いほど、$\tanh(L/2)$ が 1 に飽和し、その期待値も 1 に近づく」という直感と一致します。単調減少なので逆関数 $\phi^{-1}$ が一意に定義でき、再帰式 (17) の右辺が計算可能になります。
$\phi$ が単調減少であることを確認できたので、次に逆関数 $\phi^{-1}$ を数値的に構成し、1イテレーションの更新を実装します。
Python実装：1次元再帰と収束判定
逆関数 $\phi^{-1}$ は二分法 (brentq) で解きます。そして再帰式 (17) を1ステップ実行する関数を作ります。
def phi_inv(y):
"""phi(m) = y を満たす m を二分法で求める（phiは単調減少）"""
y = np.clip(y, 1e-12, 1.0 - 1e-12)
# phi(m) - y = 0 を [1e-6, 60] の範囲で解く
f = lambda m: phi(m) - y
return brentq(f, 1e-6, 60.0)
def de_update(m_c, m_ch, dv, dc):
"""
正則(dv, dc)符号の密度発展1ステップ。
m_c: チェック→変数メッセージの平均LLR（現在）
m_ch: チャネルLLRの平均 (= 2/sigma^2)
戻り値: 更新後の m_c
"""
m_v = m_ch + (dv - 1) * m_c # 変数ノード更新（式11）
y = phi(m_v) ** (dc - 1) # tanh則（式15の右辺）
return phi_inv(y) # 式16
def density_evolution(sigma, dv, dc, max_iter=200, tol=1e-7):
"""
与えられた雑音標準偏差 sigma で密度発展を回し、収束したか判定。
戻り値: (収束フラグ, 平均LLRの履歴)
"""
m_ch = 2.0 / sigma ** 2 # チャネルLLR平均（式12）
m_c = 0.0 # 初期メッセージは情報ゼロ
history = [m_c]
for _ in range(max_iter):
m_new = de_update(m_c, m_ch, dv, dc)
history.append(m_new)
# 発散（無限大に向かう）＝復号成功
if m_new > 1e3:
return True, history
# 増加が止まった（固定点に留まる）＝復号失敗
if abs(m_new - m_c) < tol and m_new < 50:
return False, history
m_c = m_new
return (m_c > 50), history
ここでは収束判定の基準が肝心です。m_new が大きく（ここでは $10^3$ 超）成長し続ければ平均 LLR が無限大に発散し、誤り確率 0、すなわち復号成功です。逆に増加が止まって有限の固定点に留まれば、メッセージの信頼度がそこで頭打ちになり復号失敗を意味します。この「発散 or 固定点」の二者択一がしきい値の本質です。
更新と判定の道具がそろったので、実際に (3,6) 符号で $\sigma$ を変えながら成功・失敗を観察してみます。
Python実装：(3,6)符号のしきい値を求める
正則 (3,6) 符号（変数ノード次数 3、チェックノード次数 6、符号化率 $R = 1 – d_v/d_c = 1 – 3/6 = 0.5$）について、$\sigma$ を変えて平均 LLR の推移を見ます。
dv, dc = 3, 6
# しきい値付近の複数の sigma で平均LLRの推移を比較
sigmas = [0.85, 0.87, 0.8809, 0.89, 0.91]
plt.figure(figsize=(9, 5.5))
for s in sigmas:
conv, hist = density_evolution(s, dv, dc)
hist_clip = np.clip(hist, 0, 50) # 発散は50で頭打ち表示
label = f'σ={s} ({"成功" if conv else "失敗"})'
plt.plot(hist_clip, marker='o', markersize=3, label=label)
plt.xlabel('イテレーション ℓ')
plt.ylabel('チェック→変数 平均LLR $m_c$')
plt.title('(3,6)正則LDPCの密度発展：σによる成功/失敗')
plt.legend()
plt.grid(True, alpha=0.3)
plt.xlim(0, 60)
plt.show()
このグラフから、しきい値 $\sigma^\* \approx 0.881$ をまたいで挙動が劇的に変わることが読み取れます。$\sigma$ が小さい（雑音が弱い）曲線は平均 LLR が一気に増加して天井（発散）に達し、復号成功します。一方 $\sigma$ が大きい曲線は途中で増加が止まり、低い固定点に貼り付いて復号失敗します。境目付近では、固定点近くで長く停滞してから抜けるか抜けないかが決まり、収束が非常に遅くなるのが分かります。これは相転移的な振る舞いで、しきい値が鋭い境界であることを示しています。
挙動が分かったので、しきい値 $\sigma^\*$ を二分探索で精密に求めます。
def find_threshold(dv, dc, s_lo=0.5, s_hi=1.5):
"""成功/失敗の境界 sigma* を二分探索で求める"""
for _ in range(40):
s_mid = 0.5 * (s_lo + s_hi)
conv, _ = density_evolution(s_mid, dv, dc)
if conv:
s_lo = s_mid # 成功 → さらに雑音を増やせる
else:
s_hi = s_mid # 失敗 → 雑音を減らす
return 0.5 * (s_lo + s_hi)
sigma_star = find_threshold(dv, dc)
# しきい値をEb/N0[dB]に換算（符号化率R, BPSK）
R = 1 - dv / dc
EbN0_threshold = 10 * np.log10(1.0 / (2 * R * sigma_star ** 2))
print(f"(3,6)符号 しきい値 σ* = {sigma_star:.4f}")
print(f"符号化率 R = {R}")
print(f"しきい値 Eb/N0 = {EbN0_threshold:.4f} dB")
実行すると次のような出力が得られます。
(3,6)符号 しきい値 σ* = 0.8809
符号化率 R = 0.5
しきい値 Eb/N0 = 1.1093 dB
ガウス近似密度発展による (3,6) 符号のしきい値 $\sigma^\* \approx 0.881$、$E_b/N_0 \approx 1.11$ dB が得られました。文献値（厳密な密度発展）では (3,6) 符号のしきい値は $\sigma^\* \approx 0.8809$、$E_b/N_0 \approx 1.11$ dB とされており、ガウス近似がよく一致していることが分かります。ここで $E_b/N_0$ への換算は、AWGN・BPSK で $\sigma^2 = 1/(2R\, E_b/N_0)$ という関係（信号エネルギーを 1 に正規化）を使いました。
しきい値が数値として得られたので、最後にこれをシャノン限界と並べて、符号化率との関係を可視化します。
Python実装：しきい値とシャノン限界の比較
しきい値の価値は、シャノン限界（理論的に到達可能な最良のしきい値）にどれだけ近いかで測ります。符号化率 $R$ の符号がエラーフリー通信できる最小の $E_b/N_0$ がシャノン限界です。二元入力 AWGN (BIAWGN) の容量から数値的に求めるのが正確ですが、ここでは連続入力 AWGN のシャノン限界
$$ \begin{equation} \left(\frac{E_b}{N_0}\right)_{\min} = \frac{2^{2R} – 1}{2R} \end{equation} $$
を基準に、複数の正則符号のしきい値を並べてみます。
# 複数の正則(dv, dc)符号のしきい値を計算
codes = [(3, 6), (4, 8), (3, 5), (4, 6), (3, 4)]
results = []
for (dv_, dc_) in codes:
s_star = find_threshold(dv_, dc_)
R_ = 1 - dv_ / dc_
ebn0 = 10 * np.log10(1.0 / (2 * R_ * s_star ** 2))
results.append((dv_, dc_, R_, s_star, ebn0))
print(f"({dv_},{dc_}): R={R_:.3f}, σ*={s_star:.4f}, Eb/N0={ebn0:.3f} dB")
# シャノン限界（連続入力AWGN）と並べてプロット
R_grid = np.linspace(0.05, 0.95, 200)
shannon = 10 * np.log10((2 ** (2 * R_grid) - 1) / (2 * R_grid))
plt.figure(figsize=(9, 5.5))
plt.plot(R_grid, shannon, 'k--', linewidth=2, label='シャノン限界 (AWGN)')
for (dv_, dc_, R_, s_star, ebn0) in results:
plt.scatter(R_, ebn0, s=70, zorder=5)
plt.annotate(f'({dv_},{dc_})', (R_, ebn0),
textcoords="offset points", xytext=(6, 6), fontsize=9)
plt.xlabel('符号化率 R')
plt.ylabel('しきい値 $E_b/N_0$ [dB]')
plt.title('正則LDPC符号のしきい値とシャノン限界')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()
このグラフから、いくつかの重要な事実が読み取れます。第一に、すべての正則 LDPC 符号のしきい値はシャノン限界よりも上（必要 SNR が高い側）に位置します。これは当然で、限界を破ることはできません。第二に、(3,6) のような符号でもシャノン限界との差（ギャップ）は約 1 dB 程度と比較的小さく、LDPC が優れた符号であることが分かります。第三に、同じ符号化率でも次数の組み合わせによってしきい値が異なり、設計の余地があることが見て取れます。実際、変数ノード次数を増やしすぎても減らしすぎてもしきい値は悪化し、最適な次数分布が存在します。
正則符号でこのギャップを生んでいるのが、すべてのノードが同じ次数を持つという制約です。次数を混ぜた 不規則 (irregular) LDPC 符号 にすると、密度発展の再帰式は次数分布 $\lambda(x), \rho(x)$ による加重平均
$$ \begin{equation} m_v^{(\ell)} = m_{\text{ch}} + \sum_i \lambda_i (i – 1)\, m_c^{(\ell)}, \quad \phi(m_c^{(\ell+1)}) = \sum_j \rho_j\, [\phi(m_v^{(\ell)})]^{j-1} \end{equation} $$
に拡張され、$\lambda_i, \rho_j$ を最適化することでしきい値をシャノン限界の数千分の1 dB まで近づけられます。本記事で導いたガウス近似再帰は、まさにこの最適化の評価関数として使われています。
まとめ
本記事では、LDPC 符号の反復復号性能を予測する密度発展法を、対称チャネルの仮定からガウス近似まで一貫して導出し、Python で実装しました。
- 密度発展の考え方: 個々のメッセージではなく、メッセージの確率密度がイテレーションごとにどう進化するかを追う。木構造仮定による独立性が密度追跡を可能にする
- 変数ノード更新: LLR の和に対応し、密度では $d_v – 1$ 回の畳み込み。平均は単純な足し算 $m_v = m_{\text{ch}} + (d_v-1)m_c$
- チェックノード更新: tanh 則 $\tanh(L_{\text{out}}/2) = \prod \tanh(L_i/2)$ に従い、信頼度が目減りする
- ガウス近似: 対称ガウス分布は分散 $= 2 \times$ 平均なので、平均1つの1次元再帰に簡約できる。補助関数 $\phi(m) = E[\tanh(L/2)]$ が鍵
- しきい値: 平均 LLR が発散すれば復号成功、固定点に留まれば失敗。境目の $\sigma^\*$ がしきい値。(3,6) 符号で $\sigma^\* \approx 0.881$、$E_b/N_0 \approx 1.11$ dB を数値求解した
- シャノン限界との関係: 正則符号は限界に約 1 dB まで迫り、不規則符号と次数分布最適化でさらに肉薄できる
密度発展は、符号設計と性能予測をシミュレーションなしで可能にする、現代誤り訂正符号の設計理論の中核です。次のステップとして、以下の記事も参考にしてください。
- LDPC符号とは？低密度パリティ検査符号の理論を解説 — パリティ検査行列とタナーグラフの基礎に戻って復習
- Min-Sum法によるLDPC復号 — 本記事で扱った和積復号の実装的な簡略化
- 通信路容量とシャノンの定理 — しきい値の比較対象となる理論限界の導出
参考文献
- T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge University Press
- S.-Y. Chung, T. Richardson, R. Urbanke, “Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation,” IEEE Trans. Inf. Theory, 2001
- W. Ryan and S. Lin, Channel Codes: Classical and Modern, Cambridge University Press