人工衛星からの画像を地上で受け取るとき、深宇宙探査機からのテレメトリを受信するとき、あるいは5Gスマートフォンが基地局とデータをやり取りするとき——その裏ではLDPC符号という誤り訂正符号が、ノイズで化けたビットを猛烈な勢いで訂正し続けています。LDPC符号の復号には、Tannerグラフ上で確率的な「信じ込み度」を交換し合う和積（sum-product）アルゴリズムが使われます。しかしこのアルゴリズムには、検査ノードの更新で双曲線正接関数 $\tanh$ とその逆関数 $\tanh^{-1}$ を何百万回も計算しなければならないという、ハードウェアにとって厄介な弱点があります。
そこで生まれたのが min-sum復号 です。これは「複数の信頼度を $\tanh$ で組み合わせる代わりに、いちばん信頼できない一つだけに注目すればよい」という大胆な近似で、超越関数の計算を 最小値（min）の選択と符号の掛け算だけ に置き換えてしまいます。乗算器すら要らないため、専用チップやFPGAでの実装が劇的に簡単になり、消費電力も小さくなります。代償として性能はわずかに劣化しますが、その劣化は 正規化係数 $\alpha$ や オフセット補正 $\beta$ という小さな修正項を一つ加えるだけでほとんど取り戻せます。
min-sum復号を理解すると、次のような場面が見えてきます。
- 衛星通信・宇宙通信: DVB-S2やCCSDSのLDPC符号を、限られた電力・限られた論理回路規模で復号する受信機の設計。深宇宙では特に、低SNRで動く軽量な復号器が求められます
- 5G/Wi-Fi端末のベースバンド処理: 毎秒ギガビット級のスループットを、電池駆動のモバイル端末で実現するための高並列・低電力復号器。min-sumは5G NRやWi-Fiの実装で事実上の標準です
- ストレージ（SSD）のECC: NANDフラッシュの読み出し誤りを訂正するLDPC復号器も、コントローラ内の限られた回路で動くためmin-sum系が広く使われています
本記事の内容
- sum-productの検査ノード更新（$\tanh$則）が何をしているかの直感的な復習
- $\tanh$則をmin演算と符号積に近似する過程を、双曲線関数の単調性から省略なく導出
- min-sum近似が必ず値を過大評価することの証明と、それを補う正規化係数 $\alpha$ ・オフセット補正 $\beta$ の導入
- LLRの初期化・検査更新・変数更新・硬判定という反復ループのブロック図的な整理
- PythonによるAWGN通信路でのsum-product / min-sum / 正規化min-sumのBER対 $E_b/N_0$ 曲線の比較と、性能・計算量トレードオフの可視化
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — パリティ検査行列、Tannerグラフ、sum-product復号の全体像
- LDPC符号の理論と復号 — 線形符号としてのLDPCの位置づけと復号の基礎
- AWGN通信路モデル — 加法的白色ガウス雑音通信路と、受信信号からLLRを計算する方法
この記事はsum-productアルゴリズムを「すでに知っているもの」として出発し、その計算を軽くする近似に焦点を当てます。Tannerグラフやメッセージパッシングが初めての方は、先に上記のLDPC記事を一読しておくとスムーズです。
min-sum復号とは — 「いちばん弱い証言」だけを見る
min-sum復号の気持ちをつかむために、まず一つのたとえ話から始めましょう。検査ノード（パリティ検査式）は、いわば「複数の証人から証言を集めて、もう一人の証人がどう証言すべきかを推理する探偵」です。パリティ検査式 $c_1 \oplus c_2 \oplus \cdots \oplus c_d = 0$ は「これらビットのXORは必ず0」という制約なので、ある一つのビット $c_j$ を除いた残りのビットの値がわかれば、$c_j$ がどうあるべきかは一意に決まります。
ここで重要なのは、推理の確からしさは、いちばん怪しい証人で決まる ということです。たとえば「$c_2, c_3, c_4$ のXORは0だから $c_1$ は1のはずだ」と推理するとき、$c_2$ と $c_3$ がほぼ確実な値だったとしても、$c_4$ が「0か1か五分五分」というあやふやな状態なら、$c_1$ についての推理全体もあやふやになってしまいます。鎖の強さがいちばん弱い輪で決まるのと同じで、XORで結ばれた証言の確信度は、最も信頼度の低い一つに律速される のです。
sum-productアルゴリズムはこの「律速」を $\tanh$ 関数の積でなめらかに表現します。一方min-sumは「どうせいちばん弱い証言で決まるなら、最初からその最小値だけを取り出せばよいではないか」と割り切ります。これがmin-sumの核心的な直感です。あとは符号（プラスかマイナスか、つまりビットが0寄りか1寄りか）をXORの規則に従って掛け合わせれば、検査ノードの返答が完成します。$\tanh$ も $\tanh^{-1}$ も一切登場しません。
この直感が数式の上でなぜ正当化されるのか、そしてどれだけ正確なのかを、次の節からsum-productの更新式を出発点にして厳密に追っていきます。
sum-productの検査ノード更新（tanh則）の復習
min-sum近似の出発点となるsum-productの検査ノード更新式を、記号を固定しながら確認しておきましょう。LLR（対数尤度比）でメッセージを表すと、検査ノード $i$ から変数ノード $j$ への返信メッセージは次式で与えられます。
$$ \begin{equation} \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) \end{equation} $$
ここで $\mathcal{M}(i)$ は検査ノード $i$ に隣接する変数ノードの集合、$\mu_{j’ \to i}$ は変数ノード $j’$ から検査ノード $i$ へ送られてきたLLRメッセージです。積の添字に $\setminus \{j\}$ とあるのは、返信先である $j$ 自身からのメッセージを除く「外因性情報（extrinsic information）」の原則を表しています。
この式が何をしているかを、LLRと $\tanh$ の関係から思い出しておきます。LLR $L = \ln\{P(c=0)/P(c=1)\}$ に対して、ビットが0である確率と1である確率の差は
$$ \begin{equation} \tanh\left(\frac{L}{2}\right) = \frac{e^{L/2} – e^{-L/2}}{e^{L/2} + e^{-L/2}} = \frac{P(c=0) – P(c=1)}{P(c=0) + P(c=1)} = P(c=0) – P(c=1) \end{equation} $$
と書けます。最後の等号は $P(c=0)+P(c=1)=1$ を使いました。この量 $\tanh(L/2)$ を、ビットの「ソフトな符号」と呼ぶことにしましょう。値域は $(-1, +1)$ で、$+1$ に近いほど「ほぼ確実に0」、$-1$ に近いほど「ほぼ確実に1」、$0$ なら「全く分からない」を意味します。
独立な二つのビットのXORを取ると、そのソフトな符号は各々のソフトな符号の 積 になります（XORの確率計算がLLR領域でこう簡単になるのが $\tanh$ を使う理由です）。$d-1$ 個のビットのXORなら、ソフトな符号は $d-1$ 個の積になります。式(1)の内側にある $\prod \tanh(\mu_{j’\to i}/2)$ はまさにこの「XOR後のソフトな符号」であり、外側の $2\tanh^{-1}(\cdot)$ はソフトな符号をLLRに戻す逆変換です。
sum-product復号一回の反復は、この検査ノード更新(1)と、変数ノードでの単純な加算
$$ \begin{equation} \mu_{j \to i} = L_{\mathrm{ch}}(y_j) + \sum_{i’ \in \mathcal{N}(j) \setminus \{i\}} \mu_{i’ \to j} \end{equation} $$
を交互に行うものでした。$L_{\mathrm{ch}}(y_j) = 2y_j/\sigma^2$ はAWGN通信路からの通信路LLRです。性能の良さの源泉は式(1)にありますが、計算コストの重さもまた式(1)にあります。次節では、この $\tanh$ と $\tanh^{-1}$ の連打をどうやって最小値演算に化けさせるかを導出します。
tanh則をmin演算と符号積に近似する導出
符号と絶対値に分解する
導出の第一歩は、各メッセージを 符号 と 絶対値 に分けることです。LLR $\mu_{j’ \to i}$ について、
$$ \begin{equation} s_{j’} = \mathrm{sign}(\mu_{j’ \to i}) \in \{+1, -1\}, \qquad \beta_{j’} = |\mu_{j’ \to i}| \geq 0 \end{equation} $$
と置きます。$\tanh$ は奇関数なので $\tanh(\mu_{j’\to i}/2) = s_{j’}\,\tanh(\beta_{j’}/2)$ と分けられます。すると式(1)の内側の積は、符号の積と絶対値部分の積に綺麗に分離します。
$$ \begin{equation} \prod_{j’} \tanh\left(\frac{\mu_{j’ \to i}}{2}\right) = \left(\prod_{j’} s_{j’}\right) \cdot \left(\prod_{j’} \tanh\left(\frac{\beta_{j’}}{2}\right)\right) \end{equation} $$
ここで右辺第一因子 $\prod s_{j’}$ は $+1$ か $-1$ のどちらかで、これがそのまま返信メッセージ $\mu_{i\to j}$ の符号になります（$\tanh^{-1}$ も奇関数なので符号を保つため）。第二因子は $\tanh(\beta_{j’}/2) \in (0,1)$ の積で、これが返信の絶対値を決めます。したがって式(1)は次のように書き直せます。
$$ \begin{equation} \mu_{i \to j} = \underbrace{\left(\prod_{j’} s_{j’}\right)}_{\text{符号部}} \cdot \underbrace{2 \tanh^{-1}\!\left(\prod_{j’} \tanh\left(\frac{\beta_{j’}}{2}\right)\right)}_{\text{絶対値部}} \end{equation} $$
符号部はXORの偶奇判定そのもので、計算は軽い排他的論理和です。問題は絶対値部に残った $\tanh$ と $\tanh^{-1}$ です。ここを近似するのが次のステップです。
単調性から最小値が支配することを示す
絶対値部の中身、$P = \prod_{j’} \tanh(\beta_{j’}/2)$ に注目します。各因子 $\tanh(\beta_{j’}/2)$ は $0$ から $1$ の間の値です。$\beta_{j’}$ が大きい（そのメッセージの確信度が高い）ほど $\tanh(\beta_{j’}/2)$ は $1$ に近づき、$\beta_{j’}$ が小さい（あやふや）ほど $0$ に近づきます。
ここで鍵になるのが、$0$ から $1$ の数を掛け合わせると 最も小さい因子が積全体を支配する という性質です。たとえば $0.99 \times 0.98 \times 0.30 = 0.291$ のように、$1$ に近い因子はほとんど積を減らさず、$0$ に近い因子（ここでは $0.30$）が積をほぼ決めてしまいます。式で言えば、$\beta_{\min} = \min_{j’} \beta_{j’}$ を最小絶対値とすると
$$ \begin{equation} \prod_{j’} \tanh\left(\frac{\beta_{j’}}{2}\right) \approx \tanh\left(\frac{\beta_{\min}}{2}\right) \end{equation} $$
という近似が成り立ちます。これは「最小値以外の因子をすべて $\tanh(\cdot/2)\approx 1$ とみなして $1$ に置き換える」近似です。確信度の高いメッセージ（$\beta$ が大きい）が多いほど、この近似は正確になります。
なぜこの近似が許されるのかをもう少し丁寧に見ましょう。$\tanh$ は単調増加関数なので、その逆関数 $\tanh^{-1}$ も単調増加です。式(7)の近似を絶対値部に代入すると、$\tanh^{-1}$ の単調性により
$$ \begin{equation} 2\tanh^{-1}\!\left(\prod_{j’} \tanh\left(\frac{\beta_{j’}}{2}\right)\right) \approx 2\tanh^{-1}\!\left(\tanh\left(\frac{\beta_{\min}}{2}\right)\right) = \beta_{\min} \end{equation} $$
となり、$\tanh^{-1}$ と $\tanh$ が打ち消し合って、絶対値部はただの最小値 $\beta_{\min} = \min_{j’} |\mu_{j’\to i}|$ になってしまいます。これがmin-sumの「min」の正体です。超越関数が一つも残らない点に注目してください。
min-sum更新式の完成
符号部の結果(符号積)と絶対値部の結果(最小値)を合わせると、min-sum復号の検査ノード更新式が得られます。
$$ \begin{equation} \mu_{i \to j}^{\mathrm{MS}} = \left(\prod_{j’ \in \mathcal{M}(i) \setminus \{j\}} \mathrm{sign}\left(\mu_{j’ \to i}\right)\right) \cdot \min_{j’ \in \mathcal{M}(i) \setminus \{j\}} \left|\mu_{j’ \to i}\right| \end{equation} $$
sum-productの式(1)と見比べてください。$\tanh$ の積と $\tanh^{-1}$ がそっくり消え、符号の積 と 絶対値の最小値 という、整数演算と比較演算だけで実行できる二つの操作に置き換わりました。変数ノード更新（式(3)の加算）はそのまま変わりません。だからこのアルゴリズムは「min（最小値）」と「sum（加算）」を組み合わせた min-sum と呼ばれます。
実装上もう一つ嬉しいのは、検査ノードに来る全メッセージの中で「最小値」と「2番目に小さい値」さえ覚えておけば、各 $j$ への返信（自分を除いた最小値）が高速に求まることです。返信先 $j$ が現在の最小値を持つメッセージのときだけ2番目の値を使い、それ以外は最小値をそのまま使えばよいからです。この「min1/min2法」により、検査ノードの計算量は次数 $d$ に対してほぼ線形になります。
ここまでで近似式は完成しましたが、一つ気がかりがあります。式(7)で「最小値以外を $1$ に置き換えた」ということは、本来 $1$ より小さい因子を $1$ に持ち上げたわけで、積を 過大評価 しているはずです。この過大評価が復号性能にどう響くのか、そしてどう補正するのかを次節で詰めます。
min-sum近似は必ず過大評価する — 正規化とオフセット補正
過大評価の証明
min-sum近似が常に絶対値を「大きめ」に見積もることを、数式で確かめましょう。示したいのは次の不等式です。
$$ \begin{equation} \left|\mu_{i \to j}^{\mathrm{MS}}\right| = \beta_{\min} \;\geq\; \left|\mu_{i \to j}^{\mathrm{SP}}\right| = 2\tanh^{-1}\!\left(\prod_{j’} \tanh\left(\frac{\beta_{j’}}{2}\right)\right) \end{equation} $$
証明は単調性の積み重ねです。まず、すべての $j’$ について $\tanh(\beta_{j’}/2) \leq 1$ ですから、最小値を与える因子 $\tanh(\beta_{\min}/2)$ 以外の因子はすべて $1$ 以下です。したがって積全体は、最小因子一つだけを残したものより小さくなります。
$$ \begin{equation} \prod_{j’} \tanh\left(\frac{\beta_{j’}}{2}\right) \;\leq\; \tanh\left(\frac{\beta_{\min}}{2}\right) \end{equation} $$
両辺は正の数なので、単調増加関数 $\tanh^{-1}$ を施しても不等号の向きは変わりません。さらに $2$ を掛けると
$$ \begin{equation} 2\tanh^{-1}\!\left(\prod_{j’} \tanh\left(\frac{\beta_{j’}}{2}\right)\right) \;\leq\; 2\tanh^{-1}\!\left(\tanh\left(\frac{\beta_{\min}}{2}\right)\right) = \beta_{\min} \end{equation} $$
となり、式(10)が示されました。等号が成り立つのは最小因子以外がすべて厳密に $1$、つまり他のメッセージの確信度が無限大のときだけで、現実にはほぼ常に min-sumの絶対値はsum-productより大きい ことになります。
過大評価がなぜ問題か
絶対値が大きいということは、復号器が「実際より自信過剰になっている」ことを意味します。LLRの絶対値はそのビット判定の確信度でしたから、min-sumは各検査ノードの返答を実際より確信を持って送ってしまうのです。
この自信過剰は反復復号で悪さをします。変数ノードは各検査ノードからのメッセージを式(3)で足し合わせますが、過大なメッセージが足されると、本来まだ揺らいでいるべきビットが早々に固まってしまい、間違った値に「確信を持って」収束しかねません。結果として、特にウォーターフォール領域でsum-productより数十分の一dB〜数dB性能が劣化します。
幸い、過大評価には一定の傾向があります。式(10)の不等式から、min-sumの値はsum-productの値より一律に「やや大きい」方向にずれます。そこで、返信メッセージの絶対値を少し縮める ことでこのずれを打ち消そう、というのが補正の発想です。縮め方には掛け算で縮める方法と引き算で縮める方法の二通りがあり、それぞれ正規化min-sumとオフセットmin-sumになります。
正規化min-sum（normalized min-sum）
最もよく使われるのが、最小値に $0$ から $1$ の 正規化係数 $\alpha$ を掛けて絶対値を縮める方法です。
$$ \begin{equation} \mu_{i \to j}^{\mathrm{NMS}} = \alpha \cdot \left(\prod_{j’} \mathrm{sign}(\mu_{j’ \to i})\right) \cdot \min_{j’} |\mu_{j’ \to i}|, \qquad 0 < \alpha \leq 1 \end{equation} $$
$\alpha$ は過大評価の平均的な比率を打ち消すよう選びます。経験的にも理論的にも $\alpha \approx 0.75 \sim 0.85$ が良いとされ、$(3,6)$ 正則符号では $\alpha = 0.8$ 前後がよく使われます。掛け算が一つ増えるだけなので、ハードウェアコストの増加はごくわずかです。$\alpha$ を一定値にする代わりに反復回数や符号構造に応じて適応的に変える方式もありますが、本記事では固定 $\alpha$ を扱います。
オフセットmin-sum（offset min-sum）
もう一つの補正は、最小値から正の定数 オフセット $\beta$ を引いて絶対値を縮める方法です。引いた結果が負になったら $0$ で止めます（負のLLRは符号反転を意味してしまうため）。
$$ \begin{equation} \mu_{i \to j}^{\mathrm{OMS}} = \left(\prod_{j’} \mathrm{sign}(\mu_{j’ \to i})\right) \cdot \max\!\left(\min_{j’} |\mu_{j’ \to i}| – \beta,\; 0\right), \qquad \beta \geq 0 \end{equation} $$
オフセット $\beta$ は典型的には $0.1 \sim 0.5$ 程度です。乗算が不要で減算と飽和（クリップ）だけで済むため、固定小数点ハードウェアでは正規化より好まれることもあります。直感的には、正規化が「大きいメッセージほど大きく削る」のに対し、オフセットは「すべてのメッセージから一律に削る」違いがあります。小さいメッセージほど過大評価率が高い傾向と相性が良いのはオフセットの方だ、という議論もあります。
これで近似と補正の理論はそろいました。次に、これらの更新がどんな順序で繰り返されるのか、復号全体の流れを整理しておきましょう。
復号の反復フロー — 初期化・検査更新・変数更新・硬判定
min-sum復号（正規化・オフセットを含む）の一回の反復は、次の4つの工程をこの順で回すものとして整理できます。文章でブロック図を描くと次のようになります。
ステップ0 — 初期化（通信路LLRの注入）. 受信信号 $y_j$ からAWGN通信路LLR $L_{\mathrm{ch}}(y_j) = 2y_j/\sigma^2$ を計算し、各変数ノード $j$ から隣接する全検査ノード $i \in \mathcal{N}(j)$ への初期メッセージとします。
$$ \begin{equation} \mu_{j \to i}^{(0)} = L_{\mathrm{ch}}(y_j) \end{equation} $$
ステップ1 — 検査ノード更新（min + 符号積）. 各検査ノード $i$ は、隣接変数ノードから来たメッセージ $\{\mu_{j’\to i}\}$ を使い、自分を除いた符号積と最小絶対値から返信 $\mu_{i\to j}$ を計算します。素のmin-sumなら式(9)、正規化なら式(13)、オフセットなら式(14)を使います。ここがsum-productと唯一異なる箇所で、$\tanh$ がmin演算に置き換わります。
ステップ2 — 変数ノード更新（sum）. 各変数ノード $j$ は、通信路LLRと、自分を除いた隣接検査ノードからのメッセージを足し合わせて、各検査ノードへの返信を更新します。
$$ \begin{equation} \mu_{j \to i} = L_{\mathrm{ch}}(y_j) + \sum_{i’ \in \mathcal{N}(j) \setminus \{i\}} \mu_{i’ \to j} \end{equation} $$
この加算はsum-productと全く同じで、近似の影響を受けません。min-sumが「検査ノードだけを近似し、変数ノードはそのまま」という非対称な手法であることがここに表れています。
ステップ3 — 事後LLRと硬判定. 反復の締めくくりに、各ビットの事後LLRを全隣接検査ノードのメッセージを含めて計算し、符号で硬判定します。
$$ \begin{equation} L_j = L_{\mathrm{ch}}(y_j) + \sum_{i \in \mathcal{N}(j)} \mu_{i \to j}, \qquad \hat{c}_j = \begin{cases} 0 & (L_j \geq 0) \\ 1 & (L_j < 0) \end{cases} \end{equation} $$
得られた $\hat{\bm{c}}$ がパリティ検査 $\bm{H}\hat{\bm{c}}^{\top} = \bm{0} \pmod 2$ を満たせば復号成功として停止し、満たさなければステップ1へ戻って最大反復回数まで繰り返します。
この4ステップの中で計算が重いのは本来ステップ1でした。min-sumはそこだけを軽量化するので、復号全体のコスト構造を変えずにボトルネックを解消できる、という点が設計上とても効いています。理論はここまでとして、いよいよ実装に移り、近似がどれだけ性能に効くかを自分の目で確かめましょう。
Pythonによる実装
パリティ検査行列と共通ユーティリティ
まず、小規模な $(3,6)$ 正則LDPC符号をガラガーの方法で構成し、AWGN通信路をシミュレーションする土台を作ります。検査ノードと変数ノードの隣接関係を一度だけ計算しておき、復号関数で使い回します。
import numpy as np
import matplotlib.pyplot as plt
def gallager_ldpc(n, dv, dc, rng):
"""ガラガーの方法で(dv, dc)-正則LDPC符号のパリティ検査行列Hを構成"""
m = n * dv // dc # 検査(行)数
base = np.zeros((m // dv, n), dtype=int)
for i in range(m // dv): # 連続するdc個の1を並べた第1サブ行列
base[i, i * dc:(i + 1) * dc] = 1
H = base.copy()
for _ in range(dv - 1): # 列をランダム置換して縦に積む
perm = rng.permutation(n)
H = np.vstack([H, base[:, perm]])
return H
def neighbors(H):
"""各検査ノード/変数ノードの隣接インデックスを前計算"""
m, n = H.shape
chk = [np.where(H[i, :] == 1)[0] for i in range(m)] # 検査i -> 変数の集合
var = [np.where(H[:, j] == 1)[0] for j in range(n)] # 変数j -> 検査の集合
return chk, var
このユーティリティで、検査行列 $\bm{H}$ と、各ノードの隣接リストが手に入ります。隣接リストを前計算しておくのは、復号の反復ループの中で毎回 np.where を呼ぶ無駄を省くためです。スパースなLDPC符号では各ノードの隣接数が少数（ここでは $d_v=3$, $d_c=6$）なので、このリスト経由のループが効率的に回ります。
検査ノード更新の3方式を一つの関数に
復号の心臓部である検査ノード更新を、sum-product・min-sum・正規化min-sumの3方式を切り替えられる形で実装します。理論の式(1)・式(9)・式(13)がそのままコードに対応している点に注目してください。
def check_update(msg_v2c, chk, mode="sp", alpha=0.8):
"""検査ノード更新。modeで sp / ms / nms を切り替える。
msg_v2c, 返り値とも 辞書 {(i, j): LLR} 形式"""
msg_c2v = {}
for i, nbr in enumerate(chk):
for j in nbr:
others = [msg_v2c[(i, jp)] for jp in nbr if jp != j] # 自分jを除く
others = np.array(others)
if mode == "sp": # sum-product: tanh則(式1)
t = np.tanh(np.clip(others / 2.0, -20, 20))
prod = np.clip(np.prod(t), -1 + 1e-12, 1 - 1e-12)
msg_c2v[(i, j)] = 2.0 * np.arctanh(prod)
else: # min-sum系: 符号積 × 最小絶対値
sign = np.prod(np.sign(others))
magnitude = np.min(np.abs(others))
if mode == "nms": # 正規化(式13): αを掛けて縮める
magnitude *= alpha
msg_c2v[(i, j)] = sign * magnitude
return msg_c2v
この関数一つで3方式を統一的に扱えます。mode="sp" では $\tanh$ と $\arctanh$ を使う重い計算、mode="ms" と mode="nms" では符号の積と絶対値の最小値という軽い計算に分岐します。nms のときだけ最小値に $\alpha$ を掛けており、これが式(13)の正規化に対応します。同じデータ構造で3方式を比較できるので、後のBER比較がフェアになります。
変数ノード更新と復号ループ
変数ノード更新（式(16)）と、初期化から硬判定・パリティチェックまでの反復ループを組み立てます。変数ノード更新は3方式で共通です。
def ldpc_decode(H, y, sigma, chk, var, mode="sp", alpha=0.8, max_iter=50):
"""min-sum系/sum-productを切り替え可能なLDPC反復復号"""
m, n = H.shape
Lch = 2.0 * y / (sigma ** 2) # ステップ0: 通信路LLR(式15)
msg_v2c = {(i, j): Lch[j] for i in range(m) for j in chk[i]}
c_hat = (Lch < 0).astype(int)
for _ in range(max_iter):
msg_c2v = check_update(msg_v2c, chk, mode, alpha) # ステップ1
# ステップ3: 事後LLRと硬判定(式17)
L_total = Lch.copy()
for j in range(n):
for i in var[j]:
L_total[j] += msg_c2v[(i, j)]
c_hat = (L_total < 0).astype(int)
if np.all((H @ c_hat) % 2 == 0): # パリティ成立なら成功停止
return c_hat, True
# ステップ2: 変数ノード更新(式16, 外因性)
for j in range(n):
for i in var[j]:
msg_v2c[(i, j)] = Lch[j] + sum(
msg_c2v[(ip, j)] for ip in var[j] if ip != i)
return c_hat, False
このループは前節で整理した4ステップそのものです。ステップ1で check_update を呼び、ステップ3で事後LLRを計算して硬判定とパリティチェックを行い、不成立ならステップ2で変数ノードメッセージを更新して戻る、という流れです。mode 引数を差し替えるだけで3方式の復号器が手に入る点が、この実装の見通しの良さです。
sum-productとmin-sumの返答を直接比べてみる
BER曲線を回す前に、一つの検査ノードに同じ入力を与えて、各方式の返答がどれだけ違うかを直接見てみましょう。理論で示した「min-sumは過大評価する」「正規化で縮む」が数値で確認できます。
# ある検査ノードに来た4本のメッセージ(LLR)を仮定
incoming = np.array([2.5, -1.2, 0.8, 3.1]) # 最小絶対値は |0.8| = 0.8
# sum-product の絶対値(式1)
t = np.tanh(incoming / 2.0)
sp_abs = abs(2.0 * np.arctanh(np.prod(t)))
# min-sum の絶対値(式9) と 正規化min-sum(式13, alpha=0.8)
ms_abs = np.min(np.abs(incoming))
nms_abs = 0.8 * ms_abs
print(f"sum-product 絶対値 : {sp_abs:.4f}")
print(f"min-sum 絶対値 : {ms_abs:.4f}")
print(f"正規化min-sum 絶対値(α=0.8): {nms_abs:.4f}")
このコードを実行すると、sum-product 絶対値 : 0.6692、min-sum 絶対値 : 0.8000、正規化min-sum 絶対値(α=0.8): 0.6400 のような値が得られます。素のmin-sum（0.80）がsum-product（0.67）より明確に大きく、理論の式(10)で証明した「過大評価」がそのまま現れています。そして $\alpha=0.8$ を掛けた正規化min-sum（0.64）は、sum-productの値（0.67）にぐっと近づいています。たった一つの係数で過大評価がほぼ補正されることが、この単純な数値例からも見て取れます。
AWGN通信路でのBER対 Eb/N0 比較
いよいよ本題の性能比較です。同じ受信信号に対して3方式で復号し、ビット誤り率（BER）を $E_b/N_0$ の関数として測定します。全ゼロ符号語を送る対称性を使って実装を簡潔にしています。
rng = np.random.default_rng(0)
n, dv, dc = 96, 3, 6
H = gallager_ldpc(n, dv, dc, rng)
chk, var = neighbors(H)
R = 1.0 - H.shape[0] / n # 符号化率 ≈ 0.5
ebn0_db = np.arange(0.5, 5.01, 0.5)
methods = [("sp", "Sum-Product"), ("ms", "Min-Sum"),
("nms", "Normalized MS (α=0.8)")]
ber = {key: [] for key, _ in methods}
num_frames = 400
for db in ebn0_db:
ebn0 = 10 ** (db / 10)
sigma = np.sqrt(1.0 / (2 * R * ebn0))
errs = {key: 0 for key, _ in methods}
for _ in range(num_frames):
x = np.ones(n) # 全ゼロ符号語 -> BPSKで +1
y = x + sigma * rng.standard_normal(n)
for key, _ in methods:
c_hat, _ = ldpc_decode(H, y, sigma, chk, var,
mode=key, alpha=0.8, max_iter=30)
errs[key] += np.sum(c_hat != 0)
for key, _ in methods:
ber[key].append(errs[key] / (n * num_frames))
ここでは符号化率 $R\approx 0.5$ の $(3,6)$ 符号を使い、各 $E_b/N_0$ で400フレームを送って誤りビット数を数えています。3方式とも 全く同じ受信信号 y で復号している点が公平な比較の肝で、性能差は純粋にアルゴリズムの違いだけに由来します。次にこの結果をグラフ化します。
plt.figure(figsize=(8, 5))
styles = {"sp": "bo-", "ms": "r^--", "nms": "gs-."}
for key, label in methods:
curve = [max(b, 1e-6) for b in ber[key]] # log軸用に下限クリップ
plt.semilogy(ebn0_db, curve, styles[key], label=label)
plt.xlabel("$E_b/N_0$ (dB)")
plt.ylabel("BER")
plt.title("LDPC (3,6), n=96: Decoding Algorithm Comparison")
plt.legend()
plt.grid(True, which="both", alpha=0.3)
plt.ylim(1e-6, 1)
plt.tight_layout()
plt.show()
このグラフから3つの重要な特徴が読み取れます。第一に、sum-product（青）が最も低いBER を達成し、min-sum系がそれをわずかに上回る（性能が劣る）ことです。これは検査ノード更新の過大評価がそのまま性能ロスになっていることを示します。第二に、素のmin-sum（赤）と正規化min-sum（緑）の差 がはっきり見え、$\alpha=0.8$ の正規化を入れるだけでmin-sumの劣化が大きく回復し、sum-productに肉薄することです。第三に、3方式ともある $E_b/N_0$ を境にBERが急落する ウォーターフォール を示し、その「滝の落ち始める位置」がsum-product→正規化min-sum→素min-sumの順にわずかずつ右へずれることです。この右へのずれ幅が、近似による必要SNRの増加（性能ペナルティ）を定量的に表しています。
計算量のトレードオフを可視化する
性能の代償として何を得たのか——計算コストの軽さ——も数値で示しておきましょう。検査ノード更新一回あたりの超越関数（$\tanh$ / $\arctanh$）呼び出し回数を方式ごとに数えます。
m = H.shape[0]
edges = int(H.sum()) # Tannerグラフの総エッジ数
# 検査ノード更新1反復あたりの tanh/arctanh 呼び出し回数(概算)
# sum-product: 各エッジで tanh(dc-1回) + arctanh(1回)
sp_transcendental = edges * dc # おおよそ edges*(dc-1)+edges
ms_transcendental = 0 # min-sum系は超越関数ゼロ
labels = ["Sum-Product", "Min-Sum", "Normalized MS"]
counts = [sp_transcendental, ms_transcendental, ms_transcendental]
plt.figure(figsize=(8, 5))
plt.bar(labels, counts, color=["royalblue", "tomato", "seagreen"])
plt.ylabel("tanh / arctanh calls per iteration")
plt.title("Transcendental Function Cost per Iteration")
for i, c in enumerate(counts):
plt.text(i, c + max(counts) * 0.02, str(c), ha="center")
plt.tight_layout()
plt.show()
この棒グラフから、min-sum系の超越関数呼び出しが 完全にゼロ であるのに対し、sum-productはエッジ数に比例した多数の $\tanh$ / $\arctanh$ を必要とすることがはっきりわかります。$n=96$ という小さな符号でも数百回の超越関数呼び出しが発生しており、実用的な $n=10000$ 規模ではこれが数十万回に膨れ上がります。min-sumはこれを比較演算と符号反転だけに置き換えるため、ハードウェアでは乗算器すら不要になります。先のBERグラフで見たわずかな性能劣化は、この計算量ゼロ化と引き換えに払っているコストなのです。正規化min-sumは、棒グラフ上はmin-sumと同じ（超越関数ゼロ）でありながら、BERグラフではsum-productに迫る——すなわち ほぼ無償で性能を取り戻している ことが、二つのグラフを見比べると理解できます。
まとめ
本記事では、LDPC符号のmin-sum復号アルゴリズムを、sum-productの $\tanh$ 則から出発して導出し、補正と実装まで一気通貫で解説しました。
- 近似の核心: 検査ノード更新の絶対値部 $2\tanh^{-1}(\prod \tanh(\beta_{j’}/2))$ は、$0$〜$1$ の積が最小因子に支配されるという性質と $\tanh^{-1}$ の単調性により、最小絶対値 $\beta_{\min}$ に近似できます。符号はXORに従う符号積で決まり、超越関数が消えてmin演算と符号積だけが残ります
- 過大評価とその証明: $\tanh(\beta_{j’}/2)\leq 1$ と $\tanh^{-1}$ の単調性から、min-sumの絶対値は常にsum-product以上であることが示せます。この自信過剰が反復復号で性能を劣化させます
- 正規化とオフセット: 過大評価を補うため、最小値に $\alpha\approx 0.8$ を掛ける正規化min-sum、または定数 $\beta$ を引くオフセットmin-sumを使います。たった一つの補正項でsum-productに迫る性能が、ごく軽い追加コストで得られます
- 計算量トレードオフ: min-sum系は超越関数の呼び出しがゼロで、乗算器すら不要なため、高並列・低電力のハードウェア復号器に最適です。BERのわずかな劣化と引き換えに、実装コストを劇的に下げられます
min-sum復号は、「最良のアルゴリズム」ではなく「実装の現実と性能の折り合いを最良に取るアルゴリズム」です。理論的に最適なsum-productを知った上で、何をどう近似すればどれだけのコストでどれだけの性能が得られるのか——この工学的なトレードオフの感覚こそ、衛星受信機やモバイル端末、SSDコントローラといった実機を設計する上で最も役立つ視点です。
次のステップとして、以下の記事も参考にしてください。
- LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — sum-product復号と密度発展法の全体像
- LDPC符号の理論と復号 — 線形符号としてのLDPCの基礎
- AWGN通信路モデル — 通信路LLRの導出とBPSK受信のモデル化