LDPCとTurbo符号 — 5Gと宇宙探査を支える誤り訂正

シャノンが1948年に「存在する」と証明し、45年間だれも作れなかった符号。軟判定・対数尤度比・信念伝播という3つの道具で、なぜ理論限界の目前まで届いたのかを前提知識ゼロから解き、5G NRと深宇宙通信で実際に何が動いているかまでつなげます。

45年間、宙に浮いていた約束

1948年、クロード・シャノンは通信路には容量という上限があり、それより遅く送るかぎり誤り率をいくらでも0に近づける符号が「存在する」と証明しました。

$$C = B\log_2\!\left(1 + \frac{S}{N}\right)$$

$C$ は1秒に運べるビット数、$B$ は周波数の幅、$S/N$ は信号と雑音の電力比。つまり「帯域と信号の強さが決まれば、流せる情報量の天井も決まる」——導出は情報理論とAIにあります。

問題は証明の仕方でした。シャノンはでたらめな符号の集団の平均が良いと示しただけで、作り方は言っていない。しかもでたらめな符号を復号するには、受信信号を $2^k$ 個の候補全部と突き合わせるしかありません（$k$ は情報ビット数）。そこで技術者は反対から攻めます。誤り訂正を1からのハミング符号やリード・ソロモン符号のように代数的な構造を入れ、復号を軽くする。復号はできるが容量には数dB届かず、この差が45年埋まりませんでした。

1993年、Berrou・Glavieux・Thitimajshima の3人が「Turbo符号」を発表します。符号化率1/2、Eb/N0 = 0.7 dB でビット誤り率 $10^{-5}$ を下回った、と。信じがたい主張でしたが追試が通りました。1996年に MacKay と Neal が示した同等の符号は新発明ですらなく、1962年に Robert Gallager が提案した LDPC符号（低密度パリティ検査符号）が、復号を回せる計算機がないまま忘れられていただけでした。

硬判定という、もったいなさ

アンテナに届くのは0と1ではなく電圧です。しきい値0.5Vとして0.51Vなら「1」と丸める。ここで「かろうじて1だった」という事実が捨てられています。0.51Vも0.99Vも次の段では同じ「1」ですが、前者は雑音がもう少し大きければ裏返っていた危うい1です。

硬判定を軟判定に変える——0か1かではなく、0らしさの度合いをそのまま渡す。これがTurboとLDPCの出発点で、軟判定は硬判定に対しておよそ2dB分の余裕を生むとされます。45年ぶんの停滞の多くは、この捨てていた情報の中にありました。

確信度を1つの数にする — 対数尤度比

読み方は2つだけ。符号がどちら寄りかを、絶対値がどれだけ自信があるかを表す。大きな正なら「ほぼ確実に0」、小さな負なら「たぶん1、でも自信はない」、0なら五分五分です。$y_i$ は $i$ 番目のビットの受信信号、$x_i$ は本当に送られたビット。これをLLR（対数尤度比）と呼びます。

白色ガウス雑音の通信路でBPSK（+1と−1で0と1を送る方式）を使うと、式(1)は驚くほど簡単になります。

$$L_i = \frac{2 y_i}{\sigma^2}$$

$\sigma^2$ は雑音の分散です。要するに受信電圧を雑音の大きさで割るだけ。雑音の多い環境では同じ電圧でも確信を小さく見積もる、という当たり前のことを式にしています。

確率そのものではなく比の対数なのには理由があります。独立な証拠が2つあるとき確率は掛け算で合流し、対数を取れば足し算になる。つまりLLRなら別の場所から来た証拠を足すだけで統合できる。ベイズの定理をAIで使うの事後分布の更新と同じ構図です。

「全部試す」がなぜ無理か

正しい符号語のうちLLRといちばん整合するものを選べば最良です（最尤復号）。しかし候補は $2^k$ 個。5G NRのLDPCが扱う情報ビットは最大8448ビット（3GPP TS 38.212 の base graph 1）なので $2^{8448}$ 通りあり、1秒に1兆個試せる装置を宇宙の年齢だけ回しても足りません。

必要なのは全候補を数えずに各ビットの「0らしさ」だけを求める方法です。TurboとLDPCは見た目がまるで違いながら、どちらもそれをやります。

LDPC — 検査式を「疎」にする

LDPCは名前がそのまま設計図です。パリティ検査行列 $H$ を用意し、送る語 $\mathbf{c}$ が次を満たすようにする。

$$H\mathbf{c}^\top = \mathbf{0} \pmod 2$$

要するに「$H$ の各行が1本のパリティ式で、参加するビットのXORは必ず0」。ここまでは普通の線形符号と同じで、LDPCが特別なのは$H$ がすかすかであることだけです。行の長さが数千ビットあるのに、1は数個から20個程度しか立っていません。

$H$ は絵に描き直せます。ビット1個につき変数ノード、パリティ式1本につき検査ノードを置き、参加していれば線でつなぐ。これがTannerグラフです。疎でなければならない理由は2つ。復号の手間が線の本数に比例すること、そして線が少ないほど短い閉路（短い経路で同じノードに戻る輪）ができにくく、閉路はアルゴリズムを騙すことです。