人工衛星から届く画像、スマートフォンが受け取る音声、SSDから読み出される1ビット——これらはすべて、途中で雑音にさらされた「汚れた信号」です。受け取った側は、汚れたビット列だけを手がかりに、元の正しいビット列を推定しなければなりません。素朴に考えれば「すべてのありうる符号語を試して、いちばん近いものを選ぶ」のが正解ですが、符号長が1000ビットもあれば候補は $2^{1000}$ 通りにもなり、宇宙の年齢を費やしても計算は終わりません。
では、現実の通信機器はどうやってリアルタイムに復号しているのでしょうか。その答えの中心にあるのが、Tannerグラフ（タナーグラフ）という符号の絵と、その上を情報が伝わっていくメッセージパッシング復号です。符号を一枚のグラフとして描くと、グローバルで手に負えない「最尤推定問題」が、各ノードでの小さなローカル計算と、隣どうしの「うわさ話（メッセージ）」の交換に分解されます。ノードたちが互いに「君のビットはたぶん0だよ」「いや、僕の検査式から見ると1のはずだ」と何度も意見を交わすうちに、全体として正しい符号語へと収束していく——これがメッセージパッシングの直感です。
この仕組みを理解すると、次のような応用が見えてきます。
- 衛星・深宇宙通信: DVB-S2やNASAの深宇宙ミッションでは、限られた送信電力でシャノン限界近くの通信を実現するためにLDPC符号のメッセージパッシング復号が使われています
- 5G/6Gとストレージ: 5G NRのデータチャネルやSSD/フラッシュメモリの誤り訂正で、Tannerグラフ上の和積（Sum-Product）復号が大規模に並列実装されています
本記事の内容
- パリティ検査行列 $\bm{H}$ をTannerグラフ（変数ノード・チェックノードの二部グラフ）に対応づける方法
- ガース（最短閉路の長さ）が復号性能に与える影響の直感的・理論的な理解
- 和積アルゴリズムの変数→チェック、チェック→変数のメッセージ更新式をベイズ的に省略なく導出
- LLR（対数尤度比）領域での実装が数値的に安定である理由
- 小さな $\bm{H}$ のTannerグラフをPythonで構築し、反復復号でビット誤りが減衰する様子を可視化
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — LDPC符号とパリティ検査行列の全体像
- 線形ブロック符号の理論 — 生成行列・検査行列・シンドロームの基礎
- Min-Sum復号によるLDPC復号の近似 — 和積の簡易版である最小和復号
- 確率的グラフィカルモデル入門 — メッセージパッシングの一般論（因子グラフ・確率伝搬）
本記事は、LDPC符号の全体像を扱ったLDPC符号の理論の「Tannerグラフ」と「復号」の部分を、グラフの組み立て方とメッセージ更新式の導出という一点に絞って、より深く掘り下げる位置づけです。
Tannerグラフとは — 検査行列を「絵」にする
検査行列が表す「制約のネットワーク」
線形ブロック符号では、符号語 $\bm{c} = (c_1, c_2, \dots, c_n)$ は、パリティ検査行列 $\bm{H}$（サイズ $m \times n$、要素は0か1）に対して次を満たすビット列です。
$$ \bm{H}\bm{c}^{\mathsf{T}} = \bm{0} \pmod 2 $$
この一本の行列方程式は、実は $m$ 個の独立な「XOR制約」の束です。$\bm{H}$ の第 $i$ 行を見ると、1が立っている列の番号に対応するビットだけがその制約に参加します。たとえば第 $i$ 行が $c_1, c_3, c_4$ に1を持つなら、その制約は
$$ c_1 \oplus c_3 \oplus c_4 = 0 $$
という「これら3ビットのXORは偶数（=0）でなければならない」というルールです。つまり符号とは、「どのビットたちが、どんなパリティ制約で互いに縛り合っているか」というネットワークそのものなのです。このネットワークを目に見える形にしたのがTannerグラフです。
二部グラフによる表現
ここで素朴な疑問が生まれます——ビットと制約は別種のものなのに、どうやって一枚の図に描くのでしょうか。答えは「二部グラフ（bipartite graph）」です。グラフの頂点を2つのグループに分け、グループ内には辺を引かず、グループ間にだけ辺を引きます。
- 変数ノード（variable node）: 符号語の各ビット $c_1, \dots, c_n$ に対応する $n$ 個のノード。慣例として丸 $\bigcirc$ で描きます。
- チェックノード（check node）: パリティ検査行列の各行（=各XOR制約）に対応する $m$ 個のノード。慣例として四角 $\square$ で描きます。
そして辺の引き方は、検査行列の中身そのものです。
$$ \text{変数ノード } j \text{ とチェックノード } i \text{ を辺で結ぶ} \iff H_{ij} = 1 $$
言い換えれば、$\bm{H}$ という0/1行列は、二部グラフの隣接行列にほかなりません。$\bm{H}$ がスパース（1が少ない）であれば、グラフの辺も少なく、各ノードの次数（つながっている辺の数）は小さくなります。これがLDPC符号の「低密度（Low-Density）」の幾何学的な意味です。
ここで重要なのは、Tannerグラフが単なるお絵描きではないという点です。後で見るように、復号アルゴリズムは「このグラフの辺の上を、ビットの確からしさという数値が行き来する」という形で定義されます。グラフは符号の構造であると同時に、復号という計算の配線図でもあるのです。
具体例で組み立てる
抽象論だけでは掴みにくいので、小さな $[n=7, k=3]$ 符号を例にとります。検査行列を次のように置きましょう（$m = 4$ 行、$n = 7$ 列）。
$$ \bm{H} = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 \end{pmatrix} $$
各行を読み下すと、4つの制約が得られます。
- チェック $f_1$: $c_1 \oplus c_2 \oplus c_4 = 0$
- チェック $f_2$: $c_2 \oplus c_3 \oplus c_5 = 0$
- チェック $f_3$: $c_3 \oplus c_4 \oplus c_6 = 0$
- チェック $f_4$: $c_1 \oplus c_5 \oplus c_7 = 0$
このグラフでは、上段に7個の変数ノード $c_1, \dots, c_7$、下段に4個のチェックノード $f_1, \dots, f_4$ が並びます。$f_1$ からは $c_1, c_2, c_4$ へ辺が伸び、$f_2$ からは $c_2, c_3, c_5$ へ、というように、各行の1の位置に辺が引かれます。
ノードの次数も行列から直読できます。変数ノード $j$ の次数は $\bm{H}$ の第 $j$ 列の1の個数（列重み）、チェックノード $i$ の次数は第 $i$ 行の1の個数（行重み）に等しくなります。この例ではすべてのチェックノードの次数が3で、変数ノードの次数は2のものと1のものが混在しています。次数が辺の本数を、行重み・列重みが行列の1の個数を、という対応関係を頭に入れておくと、グラフと行列を自由に行き来できるようになります。
ここまでで、符号という抽象物をグラフという具体物に翻訳できました。次に、このグラフの「形」、とくに閉路の長さが復号にどう効くのかを見ていきます。
ガース — グラフの閉路が復号を左右する
閉路とガースの定義
Tannerグラフをたどっていくと、同じノードに戻ってくる経路、すなわち閉路（cycle）が見つかることがあります。たとえば「$c_2 \to f_1 \to c_4 \to f_3 \to c_3 \to f_2 \to c_2$」のように、変数ノードとチェックノードを交互に通って出発点に戻る道です。
二部グラフでは変数ノードとチェックノードを交互にしか通れないため、閉路に含まれる辺の数（=閉路長）は必ず偶数になります。最も短い閉路でも長さ4です。このグラフ全体の中で最短の閉路の長さをガース（girth）と呼びます。ガースが大きいほど、グラフは局所的に「枝分かれだけで閉じない木（tree）」に近づきます。
なぜ木構造だと嬉しいのか
ここで「閉路の有無が復号とどう関係するのか」という疑問が当然湧きます。これを理解する鍵が、メッセージパッシング復号の前提にある独立性の仮定です。
後で詳しく導出しますが、メッセージパッシング復号では、あるノードに入ってくる複数のメッセージが「互いに独立な証拠」であると仮定して、それらを掛け合わせたり足し合わせたりします。グラフが完全な木であれば、この仮定は厳密に正しく、復号は最適な事後確率を計算します。各メッセージは異なる枝（部分木）からやってきた、共通の原因を持たない独立な情報だからです。
ところが閉路があると話が変わります。閉路に沿ってメッセージが一周すると、あるノードが過去に送り出した情報が、形を変えて自分のところに戻ってきます。これは「自分の意見を、別の人の意見であるかのように聞かされて、確信を強めてしまう」エコーチェンバー現象です。独立だと思って掛け合わせた証拠が、実は同じ情報源から来ていた——この相関が復号性能を劣化させます。
ガースが大きいほど良い理由
閉路が一周するのにかかる反復回数は、閉路長に比例します。ガースが4なら、わずか2反復でエコーが戻ってきますが、ガースが8なら4反復、ガースが10なら5反復は独立性が保たれます。
$$ \text{エコーが戻るまでの反復回数} \approx \frac{\text{閉路長}}{2} $$
つまりガースが大きいほど、復号の序盤で「証拠が独立である」という仮定が長く成り立ち、メッセージが正しい方向へ素直に育っていきます。実用的なLDPC符号でガース6以上が好まれ、ガース4が避けられるのはこのためです。とくにガース4は、2つの変数ノードが2つの同じチェックノードを共有する $4$-閉路を意味し、これらのビットの間で情報が即座に往復してしまうため、性能を強く損ないます。
ガース4の有無は行列から簡単に判定できます。$\bm{H}$ の任意の2列が、2つ以上の共通の行で同時に1を持てば、その2変数ノードと2チェックノードがガース4の閉路をなします。設計の段階で列ペアの「内積」を調べ、2以上になる組を排除することで、ガースを6以上に保てます。
グラフの形が復号の質を決めることが分かりました。では肝心の「メッセージ」とは具体的に何で、どんな式で更新されるのか。ここからが本記事の核心です。
メッセージとは何か — LLRという共通言語
ビットの確からしさを一つの数で表す
復号で行き来する「メッセージ」とは、結局のところ「このビットは0か1か、そしてどれくらい自信があるか」という情報です。これを確率 $P(c_j=0)$ と $P(c_j=1)$ の2つで持ち歩くこともできますが、足して1になる冗長性があり、しかも確率の掛け算はアンダーフローしやすく扱いにくいものです。
そこで導入するのが対数尤度比（LLR: Log-Likelihood Ratio）です。ビット $c_j$ についてのLLRを次で定義します。
$$ L(c_j) = \ln \frac{P(c_j = 0)}{P(c_j = 1)} $$
この1つの実数に、判定（符号）と確信度（絶対値）の両方が詰まっています。$L > 0$ なら0が優勢、$L < 0$ なら1が優勢、$|L|$ が大きいほど確信が強く、$L = 0$ は「全く分からない」状態です。確率の積が対数では和になるため、後で見るように独立な証拠の合成が「足し算」という最も安定な演算に化けます。これがLLRを使う最大の理由です。
通信路から得る最初のメッセージ
復号の出発点となるのは、通信路を通って受信した信号から計算される通信路LLRです。BPSK変調（$c_j = 0 \to x_j = +1$、$c_j = 1 \to x_j = -1$）でAWGN通信路 $y_j = x_j + n_j$、$n_j \sim \mathcal{N}(0, \sigma^2)$ を仮定します。受信値 $y_j$ を見たときのLLRは、ベイズの定理と事前確率が等しい（$P(c_j=0)=P(c_j=1)$）という仮定のもとで尤度比に帰着します。
$$ L_{\mathrm{ch}}(y_j) = \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(-\dfrac{(y_j – 1)^2}{2\sigma^2}\right)}{\exp\!\left(-\dfrac{(y_j + 1)^2}{2\sigma^2}\right)} = -\frac{(y_j-1)^2}{2\sigma^2} + \frac{(y_j+1)^2}{2\sigma^2} $$
分子側の指数から分母側の指数を引く形になりました。ここで $(y_j+1)^2 – (y_j-1)^2 = 4y_j$ を使うと、二次の項が打ち消し合い、
$$ L_{\mathrm{ch}}(y_j) = \frac{(y_j+1)^2 – (y_j-1)^2}{2\sigma^2} = \frac{4y_j}{2\sigma^2} = \frac{2 y_j}{\sigma^2} $$
きれいに受信値に比例した形になります。受信値が大きな正なら $x_j=+1$（$c_j=0$）が確からしく、LLRも大きな正——直感と完全に一致します。この値が、各変数ノードが最初に手にする「自分のビットについての通信路からの証言」です。
メッセージの正体がLLRだと分かったので、次はこれをグラフ上でどう更新していくか、ベイズの観点から組み立てます。
和積アルゴリズムの導出 — ベイズで組み立てる
復号問題の分解
私たちが本当に知りたいのは、受信ベクトル $\bm{y}$ が与えられたときの各ビットの事後確率 $P(c_j \mid \bm{y})$ です。符号語の事後分布は、ベイズの定理より
$$ P(\bm{c} \mid \bm{y}) \propto P(\bm{y} \mid \bm{c}) \, P(\bm{c}) $$
と書けます。AWGN通信路ではビットごとに雑音が独立なので尤度は積に分解でき $P(\bm{y}\mid\bm{c}) = \prod_j P(y_j \mid c_j)$、また事前分布 $P(\bm{c})$ は「すべてのパリティ制約を満たすかどうか」を表す指示関数の積です。
$$ P(\bm{c} \mid \bm{y}) \propto \left[\prod_{j=1}^{n} P(y_j \mid c_j)\right] \left[\prod_{i=1}^{m} \mathbb{1}\!\left(\bigoplus_{j’ \in \mathcal{M}(i)} c_{j’} = 0\right)\right] $$
ここで $\mathcal{M}(i)$ はチェックノード $i$ に隣接する変数ノードの集合（=第 $i$ 行で1が立つ列）、$\mathbb{1}(\cdot)$ は条件が真なら1、偽なら0をとる指示関数です。この式の右辺は「ローカルな因子（各 $P(y_j\mid c_j)$ と各パリティ指示関数）の積」になっており、まさにTannerグラフの構造そのものです。変数ノードは尤度因子を、チェックノードはパリティ因子を担っています。
この因子分解された分布の周辺化（各 $c_j$ について他を足し上げる）を、グラフ上のメッセージ交換で効率的に近似計算するのが和積アルゴリズムです。以下では2種類のメッセージを記号で定義します。
- $\mu_{j \to i}$: 変数ノード $j$ からチェックノード $i$ へ送るLLRメッセージ
- $\mu_{i \to j}$: チェックノード $i$ から変数ノード $j$ へ送るLLRメッセージ
- $\mathcal{N}(j)$: 変数ノード $j$ に隣接するチェックノードの集合（=第 $j$ 列で1が立つ行）
チェックノード更新の導出
まずチェックノード $i$ が変数ノード $j$ へ送るメッセージを導きます。チェックノード $i$ は「自分に繋がるビットのXORは0でなければならない」という制約を持っています。$j$ への返信は、「$j$ 以外の隣接ビットの推定値を総合すると、$j$ はどうあるべきか」を伝えるものです。
パリティ制約 $\bigoplus_{j’ \in \mathcal{M}(i)} c_{j’} = 0$ を $c_j$ について解くと、
$$ c_j = \bigoplus_{j’ \in \mathcal{M}(i)\setminus\{j\}} c_{j’} $$
つまり「$j$ 以外のビットのXOR」が $c_j$ の推定になります。問題は、各 $c_{j’}$ が確率的にしか分からないとき、そのXORの確率をどう計算するかです。ここで威力を発揮するのが次のXORの恒等式です。あるビット $b$ について $P(b=0) – P(b=1)$ を「偏り」と呼ぶと、独立な2ビット $b_1, b_2$ のXORの偏りは、各偏りの積になります。
$$ P(b_1\oplus b_2 = 0) – P(b_1\oplus b_2 = 1) = \big(P(b_1=0)-P(b_1=1)\big)\big(P(b_2=0)-P(b_2=1)\big) $$
これは $b_1\oplus b_2=0$ となるのが「両方0」か「両方1」のとき、という場合分けを書き下して整理すれば確かめられます。複数ビットへ拡張すれば、XORの偏りは各偏りの総積です。
ここで偏りとLLRの橋渡しをするのが $\tanh$ です。$P(b=0)+P(b=1)=1$ と $L=\ln\frac{P(b=0)}{P(b=1)}$ から、
$$ P(b=0)-P(b=1) = \frac{e^{L}-1}{e^{L}+1} = \tanh\!\left(\frac{L}{2}\right) $$
が成り立ちます。これは双曲線正接の定義 $\tanh(x)=\frac{e^{x}-e^{-x}}{e^{x}+e^{-x}}$ で $x=L/2$ とおき、分子分母を $e^{L/2}$ で整理すれば得られます。したがって「偏りの積」は「$\tanh(L/2)$ の積」になり、$j$ へのメッセージ $\mu_{i\to j}$ の偏りは
$$ \tanh\!\left(\frac{\mu_{i\to j}}{2}\right) = \prod_{j’ \in \mathcal{M}(i)\setminus\{j\}} \tanh\!\left(\frac{\mu_{j’\to i}}{2}\right) $$
両辺を $\tanh$ の逆関数で戻し、2倍すれば、チェックノード更新式が得られます。
$$ \boxed{\;\mu_{i \to j} = 2\,\tanh^{-1}\!\left( \prod_{j’ \in \mathcal{M}(i)\setminus\{j\}} \tanh\!\left(\frac{\mu_{j’\to i}}{2}\right)\right)\;} $$
この式の気持ちを言葉にすれば、「$j$ 以外のビットがどれも確信を持って(=$|\mu|$ が大きく $\tanh\approx\pm1$)決まっていれば、それらのXORから $j$ も確信を持って決まる。だが一つでも曖昧なビット($\tanh\approx0$)があれば、積が0に引きずられ、$j$ への助言も弱くなる」となります。最も曖昧なビットが助言の強さのボトルネックになる、という性質は、後のMin-Sum復号の近似の出発点でもあります。
変数ノード更新の導出
次に、変数ノード $j$ がチェックノード $i$ へ送るメッセージです。変数ノード $j$ は複数の証拠を持っています——通信路からの証言 $L_{\mathrm{ch}}(y_j)$ と、隣接する各チェックノードからの助言 $\mu_{i’\to j}$ です。
これらが互いに独立な証拠であれば（ガースが大きく木に近いとき、その仮定は良く成り立ちます）、ベイズ的にはそれぞれの尤度比を掛け合わせるのが正しい合成です。LLRは尤度比の対数ですから、積は和になります。
$$ L_j = \ln\frac{P(c_j=0\mid\text{全証拠})}{P(c_j=1\mid\text{全証拠})} = L_{\mathrm{ch}}(y_j) + \sum_{i’ \in \mathcal{N}(j)} \mu_{i’\to j} $$
ただし、チェックノード $i$ へ送り返すメッセージには、$i$ 自身からもらった助言 $\mu_{i\to j}$ を含めてはいけません。もし含めると、$i$ が自分の送った情報を自分のものとして再び受け取り、同じ証拠を二重に数えてしまうからです。この「自分以外（extrinsic）」の原則に従い、$i$ からの寄与だけを除いた和を送ります。
$$ \boxed{\;\mu_{j \to i} = L_{\mathrm{ch}}(y_j) + \sum_{i’ \in \mathcal{N}(j)\setminus\{i\}} \mu_{i’\to j}\;} $$
変数ノード更新が単なる足し算なのは、LLR領域で独立な証拠を合成しているからにほかなりません。チェックノードの $\tanh$ 積と変数ノードの加算——この2つの基本演算の往復が、和積アルゴリズムの全てです。
事後LLRと判定
各反復の終わりに、各ビットの最終判定に使う事後LLRを計算します。ここでは送信用メッセージと違い、自分以外の原則は不要で、すべての証拠を合わせます。
$$ L_j^{\text{post}} = L_{\mathrm{ch}}(y_j) + \sum_{i \in \mathcal{N}(j)} \mu_{i\to j} $$
硬判定は符号を見るだけです。
$$ \hat{c}_j = \begin{cases} 0 & (L_j^{\text{post}} \ge 0) \\ 1 & (L_j^{\text{post}} < 0) \end{cases} $$
得られた $\hat{\bm{c}}$ がパリティ検査 $\bm{H}\hat{\bm{c}}^{\mathsf{T}} = \bm{0}$ を満たせば復号成功として打ち切り、満たさなければ最大反復回数までメッセージ交換を続けます。これで復号アルゴリズムの全体像が出揃いました。
導出は確率（偏り）の世界で行いましたが、実装は対数（LLR）の世界で行うのが定石です。なぜそうするのか、数値計算の観点から見ておきましょう。
なぜLLR領域が数値的に安定なのか
確率そのものを使った実装には、深刻な弱点があります。変数ノード更新は確率の積 $\prod P(y_j\mid c_j)\cdots$ を含み、符号長が伸びると掛け合わせる確率の個数が増えます。0と1の間の数を何十個も掛ければ、値はあっという間に $10^{-30}$ といった極小値に達し、倍精度浮動小数点でもアンダーフローして0に丸められます。一度0になった確率は、比をとっても意味のある情報を失っています。
LLR領域はこの問題を根本から回避します。確率の積が対数では和になるため、
$$ \ln\prod_k p_k = \sum_k \ln p_k $$
掛け算で指数的に小さくなっていた量が、足し算で線形にしか増減しなくなります。$10^{-30}$ という値は対数では $-69$ 程度の穏やかな数であり、桁あふれの心配がありません。確信度が極端に高いビットでも、LLRは大きいながらも有限の実数として安全に表現できます。
唯一注意すべきはチェックノード更新の $\tanh$ と $\tanh^{-1}$ です。$\tanh(x)$ は $|x|$ が大きいと $\pm1$ に飽和し、$\tanh^{-1}$ の引数が $\pm1$ ちょうどになると発散します。実装では引数を $\pm(1-\varepsilon)$ にクリップして無限大を防ぎます。逆に $\tanh(L/2)$ の引数 $L/2$ が大きすぎてもオーバーフローしうるので、$L$ 自体も適度な範囲にクリップします。こうした軽微なガードを入れるだけで、和積アルゴリズムは広いSNR範囲で安定に動作します。
なお、$\tanh$・$\tanh^{-1}$ の計算をハードウェアで嫌う場合は、$\tanh$ 積を「符号の積 × 絶対値の最小値」で近似するMin-Sum復号が使われます。これは前節で触れた「最も曖昧なビットがボトルネック」という性質をそのまま近似に落とし込んだものです。
理論と数値の道具立てが揃いました。いよいよPythonでTannerグラフを組み、メッセージが反復のたびに育って誤りが消えていく様子を観察します。
PythonによるTannerグラフと反復復号の実装
Tannerグラフの構築と可視化
まず、先ほどの $[7,4]$ 的な検査行列からTannerグラフを組み立て、二部グラフとして描いてみます。隣接関係は検査行列の1の位置から直接読み取れます。
import numpy as np
import matplotlib.pyplot as plt
# パリティ検査行列 H (m=4 x n=7)
H = np.array([
[1, 1, 0, 1, 0, 0, 0],
[0, 1, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0, 1],
], dtype=int)
m, n = H.shape
# 隣接リスト: チェックiに繋がる変数, 変数jに繋がるチェック
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)]
print("各チェックノードの隣接変数:")
for i, nb in enumerate(check_neighbors):
print(f" f{i+1}: {[f'c{j+1}' for j in nb]}")
print("各変数ノードの次数(列重み):", [len(v) for v in var_neighbors])
このコードは検査行列をそのまま隣接リストに変換しています。出力される各チェックノードの隣接変数は、本文で書き下した4つのXOR制約とぴったり対応し、変数ノードの次数（列重み）も2と1が混在することが確認できます。行列の1の配置がグラフの配線にそのまま写されている、というTannerグラフの本質がコードレベルで見て取れます。
次に、二部グラフとして座標を与えて描画します。
fig, ax = plt.subplots(figsize=(9, 5))
# 変数ノードを上段, チェックノードを下段に配置
var_x = np.linspace(0, 1, n)
chk_x = np.linspace(0.15, 0.85, m)
var_y, chk_y = 1.0, 0.0
# 辺を描く
for i in range(m):
for j in check_neighbors[i]:
ax.plot([var_x[j], chk_x[i]], [var_y, chk_y],
color="gray", lw=1, zorder=1)
# ノードを描く (変数=丸, チェック=四角)
ax.scatter(var_x, [var_y]*n, s=600, c="#4dd0e1",
edgecolors="k", zorder=2)
ax.scatter(chk_x, [chk_y]*m, s=600, c="#ffb74d",
marker="s", edgecolors="k", zorder=2)
for j in range(n):
ax.text(var_x[j], var_y, f"$c_{{{j+1}}}$", ha="center", va="center")
for i in range(m):
ax.text(chk_x[i], chk_y, f"$f_{{{i+1}}}$", ha="center", va="center")
ax.set_title("Tanner graph of H")
ax.axis("off")
plt.tight_layout()
plt.show()
描画されたグラフでは、上段の丸い変数ノードと下段の四角いチェックノードが灰色の辺で結ばれています。$f_1$ が $c_1, c_2, c_4$ に、$f_2$ が $c_2, c_3, c_5$ に繋がる様子が一目で分かり、辺の混み具合（=次数の大小）が符号の構造を視覚的に語っています。同じ種類のノード同士には辺がなく、変数とチェックの間だけに辺がある「二部性」も確認できます。
ガース4の有無を検査行列から判定する
ガース4は「2つの列が2つ以上の共通行で1を持つ」と同値でした。列ペアごとに共通行数を数えれば、4-閉路の有無を機械的に調べられます。
def has_girth4(H):
"""検査行列に4-閉路(ガース4)が存在するか判定する"""
n = H.shape[1]
for j1 in range(n):
for j2 in range(j1 + 1, n):
# 2列が共通して1を持つ行の数
common = np.sum((H[:, j1] == 1) & (H[:, j2] == 1))
if common >= 2:
return True, (j1, j2, common)
return False, None
print("元のH:", has_girth4(H))
# わざとガース4を作った行列 (列0と列1が行0,行1で共通)
H_bad = np.array([
[1, 1, 0, 0],
[1, 1, 0, 0],
[0, 0, 1, 1],
], dtype=int)
print("悪いH:", has_girth4(H_bad))
実行すると、元の行列ではガース4が検出されず、わざと列0と列1を2行で重ねた行列ではガース4（共通行数2）が検出されます。これは設計時に「列ペアの共通行数が2以上の組を排除する」だけでガース6以上を保証できることを、そのまま手続きにしたものです。グラフを描かずとも行列の演算だけで閉路構造を診断できる点に注目してください。
和積（Sum-Product）復号の実装
いよいよLLR領域の和積アルゴリズムを実装します。導出したチェックノード更新（$\tanh$ 積）と変数ノード更新（加算）を、自分以外の原則とともにそのまま書き下します。
def sum_product_decode(H, y, sigma, max_iter=20):
"""LLR領域の和積復号。各反復の事後LLRとシンドローム重みを記録して返す"""
m, n = H.shape
cn = [np.where(H[i] == 1)[0] for i in range(m)] # チェック隣接変数
vn = [np.where(H[:, j] == 1)[0] for j in range(n)] # 変数隣接チェック
Lch = 2.0 * y / sigma**2 # 通信路LLR
mu_v2c = {(i, j): Lch[j] for i in range(m) for j in cn[i]} # 初期化
mu_c2v = {(i, j): 0.0 for i in range(m) for j in cn[i]}
history = [] # 各反復の(事後LLR, シンドローム重み, 推定語)
for it in range(max_iter):
# --- チェックノード更新: tanhの積 ---
for i in range(m):
for j in cn[i]:
prod = 1.0
for jp in cn[i]:
if jp != j:
prod *= np.tanh(np.clip(mu_v2c[(i, jp)] / 2.0, -15, 15))
prod = np.clip(prod, -1 + 1e-12, 1 - 1e-12) # arctanhの発散防止
mu_c2v[(i, j)] = 2.0 * np.arctanh(prod)
# --- 事後LLRと硬判定 ---
L_post = Lch.copy()
for j in range(n):
for i in vn[j]:
L_post[j] += mu_c2v[(i, j)]
c_hat = (L_post < 0).astype(int)
syndrome_weight = int(np.sum((H @ c_hat) % 2))
history.append((L_post.copy(), syndrome_weight, c_hat.copy()))
if syndrome_weight == 0:
break # 全パリティ充足で成功
# --- 変数ノード更新: 自分以外のチェックからのLLRを加算 ---
for j in range(n):
for i in vn[j]:
s = Lch[j]
for ip in vn[j]:
if ip != i:
s += mu_c2v[(ip, j)]
mu_v2c[(i, j)] = s
return c_hat, history
この実装は導出した式の逐語訳です。mu_c2v の計算では tanh の積をとり arctanh で戻す部分が、mu_v2c の計算では自分以外のチェックからのLLRを足す部分が、それぞれチェックノード更新・変数ノード更新に対応します。np.clip を2か所に入れているのは、前節で述べた $\tanh^{-1}$ の発散と $\tanh$ の引数のオーバーフローを防ぐためで、これがLLR実装を安定させる要です。
誤りが反復とともに減衰する様子を観察する
雑音を加えた受信信号を復号し、反復ごとに「まだ満たされていないパリティ制約の数（シンドローム重み）」と「事後LLRの確信度」がどう変化するかを追います。全ゼロ符号語を送り、いくつかのビットを雑音で大きく揺らした状況を作ります。
rng = np.random.default_rng(7)
# 全ゼロ符号語を送信 (BPSK: 0 -> +1)
c = np.zeros(n, dtype=int)
x = 1 - 2 * c
sigma = 0.9
y = x + sigma * rng.standard_normal(n)
# わざと数ビットを強く反転させて誤りを仕込む
y[1] = -2.0 # c2 を 1 寄りに
y[4] = -1.6 # c5 を 1 寄りに
c_hat, history = sum_product_decode(H, y, sigma, max_iter=20)
print("受信硬判定:", (y < 0).astype(int)) # 復号前の素朴な判定
print("復号結果 :", c_hat)
print("正解 :", c)
print("各反復のシンドローム重み:",
[h[1] for h in history])
出力を見ると、復号前の素朴な硬判定（受信値の符号だけで決める判定）では $c_2, c_5$ が1に化けて誤っているのに対し、和積復号後の結果は全ゼロの正解に一致します。各反復のシンドローム重みのリストは、満たされないパリティ制約の数が反復のたびに減り、やがて0（全制約充足=復号成功）に達する様子を数値で示しています。チェックノードからの助言が変数ノードの誤った確信を覆していく過程が、ここに表れています。
最後に、この収束をグラフで可視化します。左にシンドローム重みの推移を、右に誤りビットの事後LLRの推移を描きます。
synd = [h[1] for h in history]
# 誤りを仕込んだビット c2(index1), c5(index4) の事後LLRの推移
llr_c2 = [h[0][1] for h in history]
llr_c5 = [h[0][4] for h in history]
iters = range(1, len(history) + 1)
fig, axes = plt.subplots(1, 2, figsize=(13, 4.5))
axes[0].plot(iters, synd, "o-", color="#e57373")
axes[0].set_xlabel("Iteration")
axes[0].set_ylabel("Unsatisfied checks (syndrome weight)")
axes[0].set_title("Errors decay over iterations")
axes[0].grid(alpha=0.3)
axes[1].axhline(0, color="k", lw=0.8)
axes[1].plot(iters, llr_c2, "s-", label="$L_{post}(c_2)$")
axes[1].plot(iters, llr_c5, "^-", label="$L_{post}(c_5)$")
axes[1].set_xlabel("Iteration")
axes[1].set_ylabel("Posterior LLR")
axes[1].set_title("Confidence of flipped bits recovers")
axes[1].legend()
axes[1].grid(alpha=0.3)
plt.tight_layout()
plt.show()
左のグラフからは、満たされないパリティ制約の数が反復とともに階段状に減り、最終的に0へ落ちて復号が成功することが読み取れます。右のグラフがより本質的です——雑音で1側（負のLLR）に引きずられていた $c_2, c_5$ の事後LLRが、反復を経るごとに上昇し、ついには正に転じて正しい0判定へと回復しています。チェックノードからの「君のビットは0のはずだ」という助言が、通信路の誤った証言を上書きしていく様子が、LLRの符号反転として目に見える形で現れているのです。
この小さな例で観察した「誤りが反復で減衰する」挙動こそ、符号長を伸ばし反復を重ねたときにシャノン限界近くまで誤り率を下げられるLDPC符号の威力の源です。実用符号では数千〜数万ビットの巨大なTannerグラフ上で同じメッセージ交換が並列に走り、ウォーターフォール領域で急峻に誤り率が落ちます。
まとめ
本記事では、Tannerグラフとメッセージパッシング復号の理論と実装を、グラフの組み立てとメッセージ更新式の導出に絞って解説しました。
- Tannerグラフ: パリティ検査行列 $\bm{H}$ は変数ノード（ビット）とチェックノード（XOR制約）からなる二部グラフの隣接行列であり、$H_{ij}=1$ が一本の辺に対応します。符号の構造が、そのまま復号計算の配線図になります
- ガース: 最短閉路の長さガースが大きいほど、メッセージの独立性の仮定が長く保たれ復号性能が向上します。ガース4は2列の共通行数が2以上で判定でき、設計段階で排除できます
- 和積アルゴリズム: チェックノード更新は「偏りの積=$\tanh(L/2)$ の積」というXORの恒等式から導かれ、変数ノード更新は独立な証拠のLLRを足し合わせる加算です。自分以外（extrinsic）の原則が二重計上を防ぎます
- LLR領域の安定性: 確率の積が対数では和になるため、長い符号でもアンダーフローせず、$\tanh^{-1}$ のクリップだけで安定に動作します
- 収束の観察: 小さな符号でも、反復のたびに満たされないパリティ制約が減り、雑音で化けたビットの事後LLRが符号を反転して正しい判定へ回復する様子を確認しました
Tannerグラフという一枚の絵が、手に負えない最尤推定を、ローカルな計算とメッセージ交換の積み重ねへと分解する——この発想は誤り訂正符号にとどまらず、確率推論一般に通じる強力な考え方です。
次のステップとして、以下の記事も参考にしてください。
- LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — 符号構成法・密度発展法・BER性能まで含めた全体像
- Min-Sum復号によるLDPC復号の近似 — 本記事の $\tanh$ 積をハードウェア向けに近似する手法
- 確率的グラフィカルモデル入門 — メッセージパッシングを因子グラフ上の一般論として捉える