LDPC 符号（ I ）
13.2 LDPC 符号による消失訂正
号化を行う方法である10）．また，検査行列に基づく符号化を行うこともできる．ただ し，ランダム構成法で検査行列が構成された場合には，必ずしも検査行列が必ずしも フルランクになるとは限らないことに注意が必要である．
13.2 LDPC符号による消失訂正
本節では，LDPC符号の復号法について議論する．一般の無記憶通信路での復号の 話に入る前に，メッセージパッシングに基づく復号のアイデアが掴みやすい無記憶2 元消失通信路におけるsum-product復号法をまず説明する．
13.2.1 2元消失通信路におけるsum-product復号法
ここでは，2元消失通信路（正確には2元定常無記憶消失通信路）における sum-product復号法の手順について説明する．2元消失通信路では，sum-product復号法は 非常に単純な処理となる．より一般的な無記憶通信路におけるsum-product復号法に ついては次章で述べる．
2元消失通信路のモデル図を図13.3に示す．図からわかるように，消失通信路では，
通信路に入力されるアルファベットは2元{0,1}であり，出力アルファベットは3元 {0,1, e}をとる．アルファベットeはシンボルの消失を表す．消失とは，そのシンボ ルが0,1のどちらかがわからない状況を意味している．入力アルファベットと出力ア ルファベットをつなぐ条件付確率は，図に示すとおりであり，確率1−pで送信記号 が正しく受信され，確率pで消失になる．なお，消失の発生は確率的に独立である．
この確率pは2元消失通信路の消失確率とよばれる．
次のようなシナリオを仮定する．2元m×n行列Hにより定義されるLDPC符号
図13.3 2元消失通信路
10）一般にはHが疎でもGが疎になるとは限らない．そのため，符号化の計算量はO(n2)となる．
Cを仮定する．送信側では，Cに含まれる符号語xが送信される．2元消失通信路か ら受信器が受け取る受信語をy= (y1, y2, . . . , yn)∈ {0,1, e}nとする．
以下では，チェックノードcに接続する変数ノードの集合をA(c)，変数ノードvに 接続するチェックノードの集合をB(v)と表記する．消失訂正sum-product復号法の 手順は以下のとおりである．
消失訂正sum-product復号法 入力：受信語，出力：推定語
ステップ1（初期設定） すべての変数ノードについて次の処理を実行する：変数ノード vに対応する受信値を変数ノード値N(v) =yiとして設定する．すべてのチェック ノードについて次の処理を実行する：チェックノードcからcに接続するすべての変 数ノードに対してeを送信する．
ステップ2（変数ノード処理） すべての変数ノードについて次の処理を実行する：変数 ノードvからチェックノードc∈B(v)へメッセージMv→cが送られる．メッセージ Mv→cを定めるルールは次のとおり．
• チェックノード群B(v)\cからのメッセージがすべて消失シンボルeであり，か つvに対応する変数ノード値N(v)がeならば，Mv→c=eとなる．
• それ以外の場合には，Mv→cはB(v)\cからのメッセージと変数ノード値の中に 含まれるe以外の値となる．
ステップ3（チェックノード処理）すべてのチェックノードについて次の処理を実行す る：チェックノードcから変数ノードv∈A(c)へメッセージMc→vが送られる．メッ セージMc→vを定めるルールは次のとおり．
• 変数ノード群A(c)\vからのメッセージの中に消失シンボルeが含まれていたな らば，Mc→v =eとする．
• もし，含まれていないのならばMc→vは，それらのメッセージの和（F2上の和）
とする（図13.4）．すなわち，
Mc→v=
v∈A(c)\v
Mv→c
である．
図13.4 消失訂正sum-product復号法のステップ3の処理
13.2 LDPC符号による消失訂正 167 ステップ4（変数ノード値の更新）変数ノードvが受け取るメッセージの中にe以外の シンボルb∈ {0,1}が含まれており，N(v) =eであるならば，N(v) =bと更新する．
ステップ2へ戻る．
以上の手続きではアルゴリズムの停止条件を明示していないが，変数ノード値の更 新が行われなくなる状態になればアルゴリズムを停止してよい．
以上の手続きを例を通して説明する．まず図13.5（a）に示すタナーグラフのLDPC 符号を利用するものと仮定する．送信側はオールゼロ符号語（0,0,0,0,0,0,0,0）を送 信し，受信側では受信語Y = (e, e, e, e,0,0,0,0)が受信されたものとする．すなわち，
通信路上で第1，2，3，4シンボルに消失が発生したとする．図において変数ノードを 左から順にv1, v2, . . . , v8，チェックノードを左から順にc1, . . . , c4とよぶ．
図（a）は復号プロセスの開始時における初期状態を表している．変数ノードに書き 込まれた値は変数ノード値N(v)である．
図（b）は，第1ラウンド（ステップ2，3，4の実行を1ラウンドと数える）終了後の 状態と第1ラウンドにおけるメッセージのやりとりの一部を示している．いま，右端 のチェックノードc4に注目する．チェックノードc4では，v6, v8からのメッセージ (Mv6→c4=Mv8→c4= 0)からv3に送るメッセージが
Mc4→v3=Mv6→c4+Mv8→c4 = 0
と計算される．この計算は，チェックノードにおけるパリティ検査条件，すなわち，
あるチェックノードに接続しているすべての変数ノード値の合計は必ず0になるとい う関係を利用したものである．変数ノードv3では，このメッセージからN(v3) = 0 として変数ノード値を更新する．このようにしていままで未知であった第3シンボル 目の送信シンボルが明らかとなった．
同様に，図（c）では，第1，第4シンボルの値が第2ラウンド終了後に定まることが 示されている．図（d）をみると，第3ラウンド終了時点ですべての未知シンボルがなく なり，正しく送信語が受信側で再現できている．以上の訂正手順からわかるように，
チェックノードにおける制約（パリティ条件）に基づき，局所的に推論（足して0とな るように未知シンボルを推定する）を繰り返しているものとみることができる．
この消失訂正アルゴリズムの計算量は，処理の反復数（ラウンド数）とグラフの枝数 の積に比例する．LDPC符号の場合，ノード数に比例して枝数が増加することから，
最大反復回数を固定すると復号時間は符号長について線形時間となる．このように，
グラフが疎であることは復号計算量の点からも非常に大きなメリットである．また，
sum-product復号法自身がもつ並列性も回路実装の観点からは重要である．
図13.5 メッセージパッシングに基づく消失訂正の過程例
13.2.2 密度発展法による復号器の振る舞いの解析
LDPC符号の復号特性を知るもっとも簡単な方法は，復号シミュレーション（第9 章参照）を行うことである．復号シミュレーションにより，復号後ビット誤り率などの 特性も含めて符号の特性の多くを知ることができる．しかし，より深くsum-product 復号法の振る舞いを理解し，符号と復号法の性質に関する洞察を得るには，密度発展 法（density evolution）とよばれる手法に頼る必要がある．
密度発展法は，sum-product復号法の実行中に交換されるメッセージの確率密度関 数の時間発展（復号1ラウンドを1単位時間とみなす）を追いかける手法であり，復号 器の平均的な振る舞いを知るために非常に有用な手法である．本節では，密度発展法 が単純になる2元消失通信路の場合を例にして，密度発展法の考え方を紹介する．
以下では，前節にて紹介した消失訂正sum-product復号法により，変数ノード次数
d，チェックノード次数kの正則符号を復号する場合を仮定する11）．また，解析対象
とする符号の符号長は無限大であると仮定する．確率piをラウンドiにおける変数 ノードからチェックノードへのメッセージが消失シンボルeである確率とし，qiをラ
11）正確には，一つの符号を仮定するのではなく，変数ノード次数d，チェックノード次数kの検査行列からな る検査行列アンサンブル（第15章参照）を仮定している．以下の説明で，「平均」と述べているのはこのアン サンブルにおける平均を意味している．
13.2 LDPC符号による消失訂正 169 ウンドiにおけるチェックノードから変数ノードへのメッセージがeである確率とす る．ただし，前節の消失訂正sum-product復号法のステップ2から4までを1ラウン ドと数えている．また，pを2元消失通信路における消失確率とする．
時点i+ 1において，変数ノードからチェックノードへのメッセージがeである確率 は，その変数シンボルに対応する受信値がeであり，かつその変数ノードに入るd−1 個のメッセージがすべてeである確率となるため12），
pi+1=pqid−1 (13.8)
となる．ここで，メッセージは独立した確率変数であるという性質を利用している．
この性質は，符号長が有限の場合には成り立たないことに注意が必要である．
一方，時点iにおいてチェックノードから変数ノードへのメッセージがeである確 率qiは，チェックノードに入るk−1個のメッセージのいずれかにe以外の値が含ま れる確率となるため13），
qi= 1−(1−pi)k−1 (13.9)
となる．
以上の式を組み合わせることにより，確率piに関する漸化式
pi+1=p(1−(1−pi)k−1)d−1 (13.10)
が得られる．ここで，初期条件はp0=pである．
2元消失通信路における消失訂正sum-product復号法の平均的な振る舞いを知るた めには，上記で定義された反復系pi+1=g(pi)の性質を初期条件p0=pのもとで調 べればよい．ここで，
g(x) =p(1−(1−x)k−1)d−1 である．
以下では，d= 3, k= 6の正則符号について，上記の反復系の振る舞いを図的手法 により調べてみよう．この場合の確率piの時間発展を図13.6に示す．図の横軸はx，
縦軸はyという変数に対応するものとする．図中には，関数y=xとy=g(x)が描か れており，消失確率p= 0.4のときのpiの時間発展が階段上の軌跡として示されてい る．時間発展の求め方は次のとおりである．
まず，p1=g(p0)として点(p0, p1)を求める（垂直線x= 0.4とy=g(x)の交点）．
次に，直線y=xを利用して折り返すことにより垂直線x=p1を求め，その垂直線と
12）消失訂正sum-product復号法（p.166）の変数ノード処理を参照のこと．
13）消失訂正sum-product復号法（p.166）のチェックノード処理を参照のこと．