LDPC 符号（ I ）
13.1 LDPC 符号に関する基礎事項
159
号とよばれる．
この定義では，検査行列が必ずしもフルランクであることを条件付けていないこと から，Cの次元はn−m以上となる．したがって，Cの符号化率Rは，R≥1−m/n を満たす．
典型的なLDPC符号の例を以下に示す．m= 5000, n= 10000の2元行列Hにお いて，任意の行の行重み（行に含まれる1の個数）がwr= 6，任意の列の列重み（列に 含まれる1の個数）がwc= 3であるような行列は疎行列であり，CはLDPC符号と
なる（図13.1）．実際には，検査行列内に含まれる1の個数が符号長の定数倍（3〜8程
度）に抑えられるような行列がLDPC符号の構成に用いられることが多い．
図13.1 疎な検査行列の例
上で述べた定義では，疎行列について明確に定義していない．もう少し行列が疎で ある，という意味を明確にしておこう．そのためには，一つの行列で考えるのではな く，行列の系列を導入する必要がある．2元行列の系列{H1, H2, . . . , Hn, . . .}を考え る．ここで，Hn (n= 1,2, . . .)は列数n，行数αnの行列である（αは0≤α≤1を 満たす実数）．この系列において，列重み（または，行重み）がインデックスnに依存 しない定数で上から抑えられる場合，この行列の系列は疎行列系列であるという．
たとえば，Hnのサイズが0.5n ×nであり，列重みがnにかかわらず3であるよ うな行列の系列を考える．このとき，Hnに含まれる1の個数は3nであり，行列内に 含まれる1の個数はnに比例して増加する．一方，密な行列の系列では，1の個数が 列数nについてn2に比例して増加していくことになる．
疎な行列を検査行列として用いる理由は大きく分けて二つある．第一の理由は，
LDPC符号の復号特性に関係する．LDPC符号の復号には，sum-productアルゴリ
13.1 LDPC符号に関する基礎事項 161 ズムが利用される．ただし，LDPC符号の復号問題においては，復号に利用される ファクターグラフが一般にはループを含むため，sum-productアルゴリズムでは厳 密には周辺化計算ができる保証はない．すなわち，近似周辺化アルゴリズムとして
sum-productアルゴリズムを利用することになる．この場合，ファクターグラフが疎
であることが近似精度の点で望ましいことが知られている．後に述べるように，疎行 列に対応するファクターグラフは疎なグラフとなるため，復号の観点からは疎行列が 望ましいことになる3）．
第二の理由は，復号にかかる計算量に関係する．sum-productアルゴリズムに基づ く復号法の計算量は，検査行列内に含まれる1の個数に比例する4）．LDPC符号は，
検査行列内にO(n)個の1を含むため，その計算量もO(n)となる．このように，復号 の計算量の観点からも疎行列の利用が望ましい．
13.1.2 タナーグラフ
タナーグラフは，検査行列から導かれる2部グラフであり，LDPC符号の性質を議 論する場合の一つの土台となる．タナーグラフの定義を与える．
タナーグラフ（Tanner graph）
2元m×n検査行列Hのi行j列成分をhijと書く．この検査行列をもとに2部グラ フ5）G(H) = (V, E)を次のように定める．ノード集合V =V1∪V2の要素を
V1={v1, v2, . . . , vn}, V2={c1, c2, . . . , cm} (13.1) と名前をつけておく．ここで，V1に含まれるノードを変数ノード，V2に含まれるノード をチェックノードとよぶ．hij= 1 (i∈[1, m], j∈[1, n])を満たす(i, j)について，viと cjをつなぐエッジeij∈Eが存在する．hij= 0 (i∈[1, m], j∈[1, n])ならば，viとcj をつなぐエッジは存在しない．このように定義される2部グラフG(H)をHのタナー グラフとよぶ．
タナーグラフの定義においては，検査行列の第i行がチェックノードciに，第j列 が変数ノードvjに対応し，hij = 1の場合に限りciとvjを結ぶエッジが存在する．
検査行列Hと対応するタナーグラフを図13.2に示す．上側の白色ノード群が変 数ノードであり，下側の黒色ノード群がチェックノードである．変数ノードの上に
3）いくらでも疎にすればよいかというと，検査行列内の1の数が少なすぎると今度はLDPC符号の最小距離 が小さくなってしまい，復号性能が劣化することになる．
4）最大反復回数（後述）をnに依存しない定数にとった場合．
5）2部グラフとは，ノード集合V が二つの互いに排反な集合V1, V2に分割されており，エッジがV1とV2
間のみに存在するグラフのことである．
図13.2 タナーグラフの例
書かれた記号v1, . . . , v5は符号語のシンボルを表し，それぞれ0または1の値をと る．左端のチェックノードc1は，v1, v2, v3の変数ノードに接続しているが，これは v1+v2+v3= 0という拘束条件を表している．すなわち，チェックノードはパリティ 検査条件に対応し，変数ノードは符号語の各シンボルに対応している．
LDPC符号の場合，疎な検査行列が利用されるため，対応するタナーグラフも疎な 2部グラフとなっている．ノード数に対してエッジの本数がきわめて少ない場合，す なわち，ノード数nに対してエッジ数がO(n)となる場合，そのグラフ（またはグラフ の系列）は疎であるという．
LDPC符号の性質は，グラフ理論の言葉で述べるほうが自然な場合も多い．たとえ ば，ある変数ノードから出発し，同じノードへ戻ってくるパスをループ（またはサイ クル）とよぶ．タナーグラフに短いループが含まれる場合には，sum-productアルゴリ ズムによる復号性能が劣化する場合が多い．図13.2のタナーグラフの場合には，変数 ノードv2, v3，チェックノードc1, c2が長さ4のループを構成している．とくに，こ のような長さ4のループは復号特性に影響が大きいため，可能な限りこのような短い ループが生じないように検査行列を構成することが望ましい．
13.1.3 正則LDPC符号・非正則LDPC符号
LDPC符号には，大きくわけて正則LDPC符号と非正則LDPC符号の二つのタイ プがある．それらの定義は次のとおりである．
正則LDPC符号・非正則LDPC符号
すべての列重みが等しくwcであり，すべての行重みが等しくwrである検査行列によ り定義されるLDPC符号を正則LDPC符号（または，レギュラーLDPC符号）とよぶ．
正則LDPC符号の場合，列重み，行重みを並べて（wc, wr）正則LDPC符号と表記する 場合もある．正則LDPC符号でないLDPC符号は，非正則LDPC符号（または，イレ ギュラーLDPC符号）とよぶ．
13.1 LDPC符号に関する基礎事項 163 以下では，簡単のため，この両者を正則符号，非正則符号とよぶことにする．タ ナーグラフの観点から述べると正則符号は，すべての変数ノードが同じ次数wcをも ち，同様にすべてのチェックノードも同じ次数wrをもつタナーグラフが対応する．
正則符号，非正則符号では，その復号特性の特徴が異なっている．一般に，LDPC 符号の誤り率カーブ（図9.4参照）は，ウォーターフォール領域とよばれる急峻に誤り 率が落ちていく部分と，エラーフロア領域とよばれる誤り率カーブが比較的平坦にな る部分に分かれる．適切に設計されたLDPC符号の場合，正則符号はエラーフロア領 域の特性が優れており，非正則符号はウォーターフォール領域の特性が良い．
非正則符号の重要なパラメータとして次数分布がある．変数ノード次数分布とは，
変数ノードにおいて次数k 6）のノードがすべての変数ノードの何割を占めるかを表す 指標であり，
Lk= |{i∈[1, n] : deg(vi) =k}|
n (13.2)
と定義できる．ここで，deg(v)はノードvの次数を表す．チェックノード次数分布も 同様に定義できる．また，すべての枝数に対して次数kの枝が何%を占めるかを表す タイプの次数分布の表示法もしばしば利用される．
LDPC符号は，後に述べるsum-product復号法により復号されるのが一般的であ る．sum-product復号法を利用する場合，その復号特性は上で定義された次数分布に 強く依存することが知られている．優れた非正則符号を構成するためには，この次数 分布を最適化する必要がある7）．
13.1.4 疎行列の構成
LDPC符号を構成するためには，まず疎な検査行列を生成する必要がある．疎な検 査行列の構成法は，ランダム構成法と確定的構成法の2種に大別できる．ランダム構 成法では，乱数を利用して確率的に検査行列を構成する方法である．もう一つの確定 的構成法は，何らかの数学的ルールに基づいて検査行列を構成する方法の総称である．
検査行列の確定的構造を利用することにより，符号化器・復号器の構造が簡単になる ことが多い．
まずランダム構成法の一つとして，ギャラガーの構成法を符号構成の具体例を挙げ て紹介する．ここでは，列重みwc = 2，行重みwr = 4の正則符号の構成を考える．
いま，行列H1を
6）あるノードの次数とは，そのノードに接続するエッジの本数を意味する．
7）次数分布の最適化は，密度発展法（13.2.2項参照）により求まる反復しきい値を目的関数として最適化を行う．
H1=
⎛
⎝ 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1
⎞
⎠ (13.3)
と定義する．また，H1の列ベクトルにランダム置換することにより8）得られた行列を H2=
⎛
⎝ 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1
⎞
⎠ (13.4)
とする．行列H1とH2を結合して得られる行列
H=
⎛
⎜⎜
⎜⎜
⎜⎝
1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1
⎞
⎟⎟
⎟⎟
⎟⎠
(13.5)
は，（2,4）正則符号の検査行列となる．他のパラメータの場合にも同様に構成すること
ができる．先頭のwr個の要素が1で残りが0であるような長さnのベクトルをh1 とする．行列H1を
H1=
⎛
⎜⎜
⎜⎜
⎜⎜
⎜⎜
⎜⎝
h1 s(h1) s2(h1)
... sn/wr−1(h1)
⎞
⎟⎟
⎟⎟
⎟⎟
⎟⎟
⎟⎠
(13.6)
とおく．ここで，s(·)はベクトルを右方向にwrシンボルシフトさせる巡回置換を表 している．あとは（4,2）正則符号の場合と同様に，この行列をランダムに列置換して得 られる行列をH2, . . . , Hwcとするとき，それらを縦方向に結合することにより，
H=
⎛
⎜⎜
⎜⎜
⎜⎜
⎝ H1 H2 ... Hwc
⎞
⎟⎟
⎟⎟
⎟⎟
⎠
(13.7)
として（wc, wr）正則行列の検査行列Hが得られる9）．
13.1.5 LDPC符号の符号化
LDPC符号の符号化は，第6章で述べられた一般の線形符号の符号化が利用でき る．ひとつの方法は，疎行列であるHから生成行列Gを導き，生成行列Gにより符
8）8!通りの列置換に等確率を割り当て，その確率に従った乱数により置換を選択するものと考えればよい．
9）このように構成された行列は，必ずしもフルランクになるとは限らない．