LDPC符号

同義語:LDPC codelow-density parity-check codeGallager code

概要

LDPC符号(low-density parity-check code)とは、検査行列の各行・各列の 1 の個数が符号長によらず一定以下である 2 元線形符号の族である。検査行列を Tanner グラフという二部グラフで表し、復号はグラフの上の局所的な計算の反復で行う。各ビットの次数がそろった Tanner グラフで、小さいビットの集合が十分多くの検査とつながる(展開的である)とき、最小距離が大きく、展開がより強ければビット反転復号が誤りを線形時間で直す。消失通信路では剥がし復号の結果が停止集合で決まり、密度発展で閾値を計算する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 線形符号, 誤り訂正符号, 二部グラフ

LDPC 符号(low-density parity-check code)は、検査行列の各行・各列に $1$ が少ししかない 2 元の 線形符号 である。検査行列を「ビット」と「検査」の 2 種類の頂点をもつ 二部グラフ(Tanner グラフ)で表すと、辺の本数が符号長に比例する疎なグラフになる。復号はこのグラフの上で局所的な計算を繰り返して行い、1 回の反復の手間は辺の本数に比例する。
LDPC 符号は Gallager が 1962 年に導入した。疎であることだけでは良い符号にならない。この記事の要点は、Tanner グラフの展開性(小さなビットの集合が多くの検査とつながること)が、最小距離と速い復号の両方を保証することである。
この記事では、展開性から最小距離が出ること、ビット反転復号が誤りを直すこと(Sipser–Spielman の定理)、消失通信路の剥がし復号を停止集合で特徴づける定理を証明し、密度発展で閾値を求める。

定義と使える条件

以下、$\mathbb{F}_2=\{0,1\}$ とし、ベクトル $x\in\mathbb{F}_2^n$ の重み($1$ の個数)を $\operatorname{wt}(x)$ と書く。

検査行列と Tanner グラフ

$H$ を $\mathbb{F}_2$ 上の $m\times n$ 行列とする。$H$ の Tanner グラフ は、ビットの節 $v_1,\dots,v_n$ と検査の節 $c_1,\dots,c_m$ を頂点とし、$H_{ij}=1$ のとき $c_i$ と $v_j$ を辺で結んだ二部グラフである。$C(H)=\{x\in\mathbb{F}_2^n: Hx=0\}$ を $H$ の定める符号という。ビットの節の集合 $S$ について、$S$ のどれかと隣接する検査の節の全体を $N(S)$ と書く。

$x\in C(H)$ とは、各検査 $c_i$ について、$c_i$ に隣接するビットの値の和が $0$ であることである。和が $1$ の検査を 満たされない検査 という。

LDPC 符号

正の整数 $c,d$ を固定する。各行の $1$ の個数が $d$ 以下、各列の $1$ の個数が $c$ 以下の検査行列 $H_n$ で定まる符号の族 $C(H_n)$($n\to\infty$)を LDPC 符号 という。各列の $1$ の個数がちょうど $c$、各行がちょうど $d$ のとき $(c,d)$ 正則 という。

「疎」は $n$ によらず $c,d$ が一定であることで、族の性質である。Tanner グラフは符号ではなく行列について決まる。$(c,d)$ 正則なら辺は $nc=md$ 本で、$m=nc/d$ である。
定理を使える条件は次の 3 種類に分かれる。

  1. 次数:各ビットの節の次数がちょうど $c$(左 $c$ 正則)。
  2. 展開性:下の def-ldpc-expansion の $(a,\varepsilon)$ の条件。
  3. 通信路:誤りの位置が分からない 2 元対称通信路 型の誤り(thm-ldpc-flip)か、位置の分かる 消失(thm-ldpc-peeling)か。
展開性と一意な隣接

Tanner グラフの各ビットの節の次数が $c$ であるとする。正の整数 $a$ と $0\le\varepsilon<1$ について、
$$ 1\le\lvert S\rvert\le a\ \Longrightarrow\ \lvert N(S)\rvert\ge(1-\varepsilon)c\lvert S\rvert $$
がすべてのビットの節の集合 $S$ について成り立つとき、グラフは $(a,\varepsilon)$ 展開的 であるという。検査 $r\in N(S)$ が $S$ のちょうど 1 つの節と隣接するとき、$r$ を $S$ の 一意な隣接 といい、その全体を $U(S)$ と書く。

$\lvert N(S)\rvert\le c\lvert S\rvert$ は常に成り立つので、$\varepsilon$ が小さいほど展開性は強い。

停止集合

ビットの節の集合 $S$ が 停止集合 であるとは、$N(S)$ のどの検査も $S$ の節と 2 つ以上隣接することをいう(空集合も停止集合とする)。

停止集合の和集合は停止集合である($N(S\cup T)$ の検査は $S$ か $T$ の一方の隣接で、その中に 2 つ以上の節をもつ)。したがって、任意のビットの集合 $E$ に対して、$E$ に含まれる最大の停止集合がただ 1 つある。非零の符号語 $x$ の台 $\{j:x_j=1\}$ は停止集合である:台に隣接する検査は台の偶数個の節と隣接し、その個数は $1$ 以上なので $2$ 以上である。

公式の表

$G$ は Tanner グラフ、$c$ は左の次数、$d$ は右の次数である。

量公式・結果使える条件根拠
次元$\dim C(H)\ge n-m$、$(c,d)$ 正則なら符号化率 $\ge1-c/d$なし(等号は $H$ の行が 1 次独立のとき)prop-ldpc-rate
一意な隣接$\lvert U(S)\rvert\ge(1-2\varepsilon)c\lvert S\rvert$$(a,\varepsilon)$ 展開的、$1\le\lvert S\rvert\le a$lem-ldpc-unique
最小距離$d_{\min}\ge a+1$$(a,\varepsilon)$ 展開的、$\varepsilon<1/2$thm-ldpc-distance
ビット反転復号重み $\le a/2$ の誤りを $c\cdot(\text{誤りの重み})$ 回以下の反転で直す$(a,\varepsilon)$ 展開的、$\varepsilon<1/4$thm-ldpc-flip
剥がし復号残る消失 $=$ 消失の集合に含まれる最大の停止集合消失通信路thm-ldpc-peeling
密度発展$x_0=\varepsilon$、$x_\ell=\varepsilon\bigl(1-(1-x_{\ell-1})^{d-1}\bigr)^{c-1}$深さ $2\ell$ の近傍が木prop-ldpc-tree
閾値$\varepsilon^*=\min_{0< x\le1}\dfrac{x}{(1-(1-x)^{d-1})^{c-1}}$、$(3,6)$ で $\approx0.42944$同上、$c\ge3$($c=2$ では下限 $1/(d-1)$ が閾値)rem-ldpc-threshold(計算)
$c=2$ の距離$d_{\min}=$ 検査のグラフの内周 $\le2\log_{d-1}m+2$$c=2$、$d\ge3$prop-ldpc-cycle

符号化率と最小距離

符号化率の下界

$H$ が $m\times n$ 行列なら $\dim C(H)=n-\operatorname{rank}H\ge n-m$ である。特に $(c,d)$ 正則なら、符号化率 $\dim C(H)/n$ は 設計の符号化率 $1-c/d$ 以上である。

階数の定理

$C(H)$ は線形写像 $x\mapsto Hx$ の核なので、階数・退化次数の定理 により $\dim C(H)=n-\operatorname{rank}H$ である。$\operatorname{rank}H$ は行の本数 $m$ 以下である。$(c,d)$ 正則なら $m=nc/d$ なので $\dim C(H)/n\ge1-c/d$ である。$\square$

$(c,d)$ 正則の行列では、全部の行の和は各列で $c$ 個の $1$ を足したものだから、$c$ が偶数なら零ベクトルになる。このとき行は 1 次従属で、符号化率は $1-c/d$ より真に大きい(ex-ldpc-k4)。

一意な隣接の個数

各ビットの節の次数が $c$ で、ビットの節の集合 $S$ が $\lvert N(S)\rvert\ge(1-\varepsilon)c\lvert S\rvert$ を満たすなら、$\lvert U(S)\rvert\ge(1-2\varepsilon)c\lvert S\rvert$ である。

辺を数える

$S$ から出る辺は $c\lvert S\rvert$ 本で、各辺の他端は $N(S)$ にある。$r\in N(S)$ が $S$ と結ぶ辺の本数を $k_r$ とすると、$r\in U(S)$ なら $k_r=1$、そうでなければ $k_r\ge2$ である。よって
$$ c\lvert S\rvert=\sum_{r\in N(S)}k_r\ge\lvert U(S)\rvert+2\bigl(\lvert N(S)\rvert-\lvert U(S)\rvert\bigr)=2\lvert N(S)\rvert-\lvert U(S)\rvert $$
であり、$\lvert U(S)\rvert\ge2\lvert N(S)\rvert-c\lvert S\rvert\ge2(1-\varepsilon)c\lvert S\rvert-c\lvert S\rvert=(1-2\varepsilon)c\lvert S\rvert$ を得る。$\square$

一意な隣接は、$S$ のビットだけを反転したとき必ず満たされなくなる検査である。$S$ の中でちょうど 1 つのビットだけが $r\in U(S)$ に入るからである。これが以下の 2 つの定理の鍵になる。

展開性と最小距離

Tanner グラフの各ビットの節の次数が $c\ge1$ で、グラフが $(a,\varepsilon)$ 展開的、$\varepsilon<1/2$ とする。すると $C(H)$ の非零の符号語の重みはすべて $a+1$ 以上であり、最小距離は $a+1$ 以上である。

一意な隣接が符号語を拒む

非零の $x\in C(H)$ で $\operatorname{wt}(x)\le a$ のものがあったとし、その台を $S$ とする。$1\le\lvert S\rvert\le a$ なので、lem-ldpc-unique により $\lvert U(S)\rvert\ge(1-2\varepsilon)c\lvert S\rvert>0$ である。$r\in U(S)$ をとると、$r$ に隣接するビットのうち値が $1$ のものは $S$ の中のちょうど 1 つだけなので、検査 $r$ の和は $1$ であり、$Hx\ne0$ となって矛盾する。線形符号の最小距離は非零の符号語の最小の重みに等しい(線形符号 の命題「最小距離と最小の重み」)ので、最小距離は $a+1$ 以上である。$\square$

展開性の条件 $\varepsilon<1/2$ は外せない(ex-ldpc-k4 と反例の表)。$\varepsilon<1/2$ と $a\ge\alpha n$($\alpha>0$ は一定)を満たす左 $c$ 正則のグラフの族が存在し、$m/n<1$ にとれば、符号化率と相対距離がともに $0$ から離れた符号の族が得られる。この存在はこの記事では証明しない。確率的な存在は GRS25 Theorem 11.2.3(p. 205)、明示的な構成は Theorem 11.2.5(p. 205)、最小距離の結論は Theorem 11.3.6(p. 213)にある。
ビットの節の次数 $c$ が $2$ の場合(各ビットがちょうど 2 つの検査に入る場合)は、展開性がちょうど境目で失われる。

$c=2$ の LDPC 符号

各ビットの節の次数が $2$ とし、検査の節を頂点、ビットの節を「隣接する 2 つの検査を結ぶ辺」とする多重グラフを $\Gamma$ とする。$x\in\mathbb{F}_2^n$ が符号語であることは、台の辺の集合がどの頂点でも偶数本の辺をもつことと同値である。$\Gamma$ が閉路をもつなら、最小距離は $\Gamma$ の内周(最短の閉路の長さ)$g$ に等しい。さらに $\Gamma$ が $d$ 正則($d\ge3$)で頂点が $m$ 個なら $g\le2\log_{d-1}m+2$ である。

閉路と Moore の数え上げ
証明を開く

検査 $c_i$ の和は、頂点 $c_i$ に接する台の辺の本数を $2$ で割った余りなので、前半が従う。閉路の辺の集合は各頂点で $0$ 本か $2$ 本の辺をもつので符号語であり、最小距離は $g$ 以下である。逆に非零の符号語の台の辺だけを見ると、辺をもつ頂点の次数は $2$ 以上なので、その部分グラフは閉路を含む(最長の道の端点を考えればよい)。よって重みは $g$ 以上である。

後半:$g\le2$ なら明らかなので $g\ge3$ とし、$r=\lfloor(g-1)/2\rfloor$ とおくと $g\le2r+2$ である。1 つの頂点 $o$ から距離 $r$ 以下の頂点への最短の道が 2 本あれば、その和は長さ $2r\le g-1$ 以下の閉路を含み、内周の定義に反する。距離 $k< r$ の 2 頂点を結ぶ辺があっても、$o$ からの 2 本の最短の道とその辺が長さ $2k+1\le g-2$ 以下の閉路を含み、同じく反する($g\ge3$ なので多重辺もない)。よって距離 $r$ 以下の頂点は $o$ を根とする木をなし、$1+d+d(d-1)+\dots+d(d-1)^{r-1}\ge(d-1)^r$ 個以上ある。$(d-1)^r\le m$、すなわち $r\le\log_{d-1}m$ である。$\square$

$m=2n/d$ なので、$c=2$ の正則な族の最小距離は符号長の対数の程度にとどまる。台が長さ $g$ の閉路 $S$ では $\lvert N(S)\rvert=\lvert S\rvert=\tfrac12c\lvert S\rvert$ で、$\varepsilon=1/2$ になる。一方、列の重み $c\ge3$ のランダムな正則の族は、符号長に比例する最小距離をもつことが Gallager と MacKay によって示されている(Mac03 §47.1、p. 557。この記事では証明しない)。

ビット反転復号

符号語 $x$ を送り、いくつかのビットが反転した語 $y$ を受け取ったとする。誤りの位置は分からない。ビット反転復号 は次の手順である。

  1. $y$ について各検査の和を計算し、満たされない検査を記録する。
  2. 満たされない検査と 半分より多く($c/2$ より多く)隣接するビットの節があれば、その 1 つを選んで値を反転し、その節に隣接する検査の状態を更新する。
  3. そのようなビットがなくなったら止め、そのときの語を出力する。
    選ぶ順番は任意で、次の定理はどの順番でも成り立つ。
ビット反転復号(Sipser–Spielman)

Tanner グラフの各ビットの節の次数が $c\ge1$ で、グラフが $(a,\varepsilon)$ 展開的、$\varepsilon<1/4$ とする。符号語 $x$ と語 $y$ が $\operatorname{wt}(y-x)\le a/2$ を満たすなら、$y$ から始めたビット反転復号は、高々 $c\cdot\operatorname{wt}(y-x)$ 回の反転のあとで止まり、$x$ を出力する。

SS96 Theorem 10(p. 1714)は、$(c,d)$ 正則のグラフで満たされない検査の最も多いビットから反転する場合について、展開の係数を $3c/4$ より大きいとして同じ結論を述べている。$\varepsilon<1/4$ は $\lvert N(S)\rvert\ge(1-\varepsilon)c\lvert S\rvert>\tfrac34c\lvert S\rvert$ を与える。

満たされない検査の個数を位置エネルギーにする

$t$ 回の反転のあとの語を $y_t$($y_0=y$)とし、$S_t=\{j:(y_t)_j\ne x_j\}$、$u_t$ を $y_t$ について満たされない検査の個数とする。$Hy_t=H(y_t-x)$ なので、満たされない検査は誤りの位置 $S_t$ だけで決まる。
(1) $u_t$ は反転のたびに $1$ 以上減る。 反転するビットの節は $k>c/2$ 個の満たされない検査と隣接する。反転すると、その $k$ 個は満たされ、残りの $c-k$ 個は状態が逆になる。ほかの検査は変わらない。よって $u_{t+1}-u_t\le(c-k)-k<0$ で、$u$ は整数なので $1$ 以上減る。特に反転の回数は $u_0$ 以下であり、$u_0$ 個の満たされない検査はどれも $S_0$ に隣接するので $u_0\le c\lvert S_0\rvert$ である。これが回数の上界である。
(2) $1\le\lvert S_t\rvert\le a$ なら、反転できるビットがある。 lem-ldpc-unique により $\lvert U(S_t)\rvert\ge(1-2\varepsilon)c\lvert S_t\rvert>\tfrac12c\lvert S_t\rvert$ である($\varepsilon<1/4$ を使った)。$U(S_t)$ の検査は $S_t$ のちょうど 1 つの節と隣接し、満たされない(lem-ldpc-unique のあとの観察)。$v\in S_t$ ごとに「$v$ と隣接する満たされない検査の個数」を足すと、$U(S_t)$ の各検査が 1 回ずつ数えられるので、和は $\lvert U(S_t)\rvert>\tfrac12c\lvert S_t\rvert$ 以上である。よってある $v\in S_t$ は $c/2$ より多くの満たされない検査と隣接する。
(3) いつも $\lvert S_t\rvert< a$ である。 $S_0=\emptyset$ なら $u_0=0$ で、反転は起きない。$S_0\neq\emptyset$ とし、$\lvert S_t\rvert\ge a$ となる $t$ があったとする。$\lvert S_0\rvert\le a/2< a$ で、1 回の反転で $\lvert S_t\rvert$ はちょうど $1$ 変わるので、$\lvert S_t\rvert=a$ となる最初の $t\ge1$ がある。このとき (2) の計算と同じく
$$ u_t\ge\lvert U(S_t)\rvert\ge(1-2\varepsilon)ca>\tfrac12ca\ge c\lvert S_0\rvert\ge u_0 $$
となる。一方 (1) により $u_t< u_0$ であり、矛盾する。
結論。 (1) により手順は有限回で止まる。止まった時刻 $T$ で $S_T\ne\emptyset$ なら、(3) により $1\le\lvert S_T\rvert< a$ で、(2) により反転できるビットがあり、止まったことに反する。よって $S_T=\emptyset$、すなわち出力は $x$ である。$\square$

証明の (1) は展開性を使わず、「半分より多く」の厳密な不等号だけで手順が止まることを示している。
各反復の手間は反転したビットの近傍の大きさ($c$ と $d$ で決まる定数)で済むので、全体の手間は符号長に比例する。$\varepsilon<1/4$ と $a\ge\alpha n$ を満たす族があれば、符号長に比例する個数の誤りを線形時間で直せる。

消失通信路と剥がし復号

消失通信路(erasure channel)では、各ビットが確率 $\varepsilon$ で独立に「?」に置き換わり、それ以外は正しく届く。受信者は消えた位置を知っている。符号化率 $R$ の符号でこの通信路の誤りを任意に小さくできるのは $R<1-\varepsilon$ のときに限られ、$1-\varepsilon$ が通信路容量である(Elias。LMSS01 p. 569 の紹介による。この記事では証明しない)。
剥がし復号 は次の手順である。$E$ を消えたビットの集合とする。

  1. 消えたビットとちょうど 1 つだけ隣接する検査を探す。
  2. あれば、その検査に隣接するほかのビット(すべて既知)の和を、消えたビットの値とし、$E$ から除く。1 に戻る。
  3. なければ止め、残った $E$ を出力する(空なら復号の成功)。
剥がし復号と停止集合

送った語を符号語 $x$、消えたビットの集合を $E$ とする。剥がし復号で復元した値はすべて正しく、止まったときに残る消失の集合は、$E$ に含まれる最大の停止集合 $S^*$ に等しい。特に、復号が成功することと、$E$ が空でない停止集合を含まないことは同値であり、結果は手順 1 の検査の選び方によらない。

停止集合は剥がれず、残りは停止集合

値の正しさ。 手順 2 で使う検査 $r$ について、$x$ は符号語なので $r$ に隣接するビットの $x$ の値の和は $0$ である。消えたビット $v$ 以外の値は正しく分かっているので、それらの和は $x_v$ に等しい。帰納的に、既知の値はすべて $x$ の値と一致する。
$S^*$ は最後まで残る。 手順のある時点で $S^*$ のすべての節がまだ消えているとする。$S^*$ の節 $v$ を復元するには、$v$ に隣接し、消えたビットとちょうど 1 つだけ隣接する検査 $r$ が要る。ところが $r\in N(S^*)$ は停止集合の定義により $S^*$ の節と 2 つ以上隣接し、それらはまだ消えている。よって $S^*$ の節は復元されず、帰納法により最後まで残る。
残りは停止集合。 止まったときの集合 $E_T$ について、$N(E_T)$ の検査が $E_T$ の節とちょうど 1 つだけ隣接すれば手順 1 が続くので、そのような検査はない。よって $E_T$ は停止集合で、$E_T\subseteq E$ だから $E_T\subseteq S^*$ である。前段と合わせて $E_T=S^*$ である。$S^*$ は $E$ だけで決まるので、結果は選び方によらない。$\square$

符号語の台は停止集合なので、$E$ が非零の符号語の台を含むと、どんな復号でも $x$ と $x+$(その符号語)を区別できない。逆に停止集合であって符号語の台を含まないものもあり、そのときは連立 1 次方程式を解けば復元できるのに剥がし復号は止まる(よくある誤りの表)。

密度発展と閾値

剥がし復号を並列に行う形が メッセージ伝達復号 である。反復 $t=1,2,\dots$ で、各辺の両向きに「値が分かった/まだ消えている」のメッセージを送る。

  • ビット $v$ から検査 $r$ へ:$v$ が通信路で届いていたか、$r$ 以外の隣接する検査から前の反復で「分かった」が来ていれば「分かった」。
  • 検査 $r$ からビット $v$ へ:$v$ 以外の隣接するビットからこの反復で「分かった」が来ていれば「分かった」。
    反復 $\ell$ のあと、$v$ が通信路で届いたか、隣接する検査のどれかから「分かった」が来ていれば、$v$ は復元される。復元された値は剥がし復号と同じ理由で正しい。
木の上の消失確率

Tanner グラフは $(c,d)$ 正則とし、各ビットは確率 $\varepsilon$ で独立に消えるとする。ビットの節 $v$ から距離 $2\ell$ 以内の節と辺がなす部分グラフが木なら、反復 $\ell$ のあとに $v$ が消えたままである確率は
$$ \varepsilon\bigl(1-(1-x_{\ell-1})^{d-1}\bigr)^{c},\qquad x_0=\varepsilon,\quad x_t=\varepsilon\bigl(1-(1-x_{t-1})^{d-1}\bigr)^{c-1} $$
である。$x_t$ は、反復 $t+1$ に根以外のビットから親の検査へ送られる「まだ消えている」のメッセージの確率である。

交わらない部分木は独立
証明を開く

近傍が木なので、$v$ を根とする木で考える。根以外のビットの節 $w$ は、親の検査のほかに $c-1$ 個の子の検査をもち、各検査は親のビットのほかに $d-1$ 個の子のビットをもつ。反復 $t$ に $w$ から親へ送るメッセージは、$w$ を根とする深さ $2(t-1)$ の部分木の中の消失だけで決まる($t$ についての帰納法)。

$t$ についての帰納法で、反復 $t$ に根以外のビットから親の検査へ「まだ消えている」が送られる確率が $x_{t-1}$ であることを示す。反復 $1$ では、それは $w$ が消えている確率 $\varepsilon=x_0$ である。反復 $t$ に検査 $r'$ から親のビット $w$ へ「分かった」が送られるのは、$r'$ の $d-1$ 個の子のビットがすべて反復 $t$ に「分かった」を送るときである。子の部分木は互いに交わらないので、これらの事象は独立で、確率は $(1-x_{t-1})^{d-1}$ である。$w$ が反復 $t+1$ に「まだ消えている」を送るのは、$w$ が消え、かつ $c-1$ 個の子の検査がすべて「消えている」を送るときである。$w$ 自身の消失と子の部分木は互いに交わらない消失で決まるので、確率は $\varepsilon(1-(1-x_{t-1})^{d-1})^{c-1}=x_t$ である。根 $v$ は子の検査を $c$ 個もち、反復 $\ell$ のあとに消えたままなのは $v$ が消え、$c$ 個の検査がすべて反復 $\ell$ に「消えている」を送るときなので、主張の式を得る。$\square$

閾値

$f_\varepsilon(x)=\varepsilon(1-(1-x)^{d-1})^{c-1}$ は $x$ について増加なので、$x_t$ は単調に減って、$f_\varepsilon(x)=x$ の $[0,\varepsilon]$ の最大の解に収束する。$x_t\to0$ となることは、$0< x\le\varepsilon$ で $f_\varepsilon(x)< x$ であることと同値で、その上限
$$ \varepsilon^*=\min_{0< x\le1}\frac{x}{\bigl(1-(1-x)^{d-1}\bigr)^{c-1}} $$
を 閾値 という($c\ge3$ のとき。最小値は数値計算による。$c=2$ では最小値はなく、下限 $1/(d-1)$ が閾値になる)。$(3,6)$ では $\varepsilon^*\approx0.42944$(最小点 $x\approx0.26057$)で、設計の符号化率 $1/2$ の容量の限界 $0.5$ より小さい。

木の計算は 1 つの節の周りの話であり、グラフ全体で復号が成功するかは別の問題である。LMSS01 は、辺の次数分布を $\lambda(x)=\sum_i\lambda_ix^{i-1}$、$\rho(x)=\sum_i\rho_ix^{i-1}$($\lambda_i,\rho_i$ は次数 $i$ の節に入る辺の割合)とするランダムな二部グラフで、$\lambda_1=\lambda_2=0$ かつ
$$ \delta\lambda\bigl(1-\rho(y)\bigr)<1-y\qquad(0\le y<1) $$
なら、割合 $\delta$ の独立な消失から、次数 1 の検査で 1 つずつ復元する過程が高い確率ですべてを復元することを示した(Proposition 2 と Lemma 1、p. 575。条件の形は p. 576 の (8)。この記事では証明しない)。$(c,d)$ 正則では $\lambda(x)=x^{c-1}$、$\rho(x)=x^{d-1}$ で、$y=1-x$ と置くとこの条件は $f_\delta(x)< x$($0< x\le1$)に一致する。ランダムな $(3,6)$ 正則のグラフでは、消失の割合が閾値未満なら、符号長が大きいとき剥がし復号がほぼ確実に成功する。
図: (3,6) 正則の密度発展の写像 f(x)=ε(1-(1-x)^5)^2 のグラフを、ε=0.40、0.4294、0.45 の 3 本と対角線 y=x で描いたもの。横軸は x、縦軸は f(x)。ε=0.40 の曲線は 0<x≤ε で対角線より下にあり、ε=0.45 の曲線は x≈0.2 の近くで対角線の上に出て、最大の交点 x≈0.355 で対角線と交わる(反復はこの点に収束する)。ε=0.4294 の曲線は x≈0.26 で対角線に接する。 図: (3,6) 正則の密度発展の写像 f(x)=ε(1-(1-x)^5)^2 のグラフを、ε=0.40、0.4294、0.45 の 3 本と対角線 y=x で描いたもの。横軸は x、縦軸は f(x)。ε=0.40 の曲線は 0<x≤ε で対角線より下にあり、ε=0.45 の曲線は x≈0.2 の近くで対角線の上に出て、最大の交点 x≈0.355 で対角線と交わる(反復はこの点に収束する)。ε=0.4294 の曲線は x≈0.26 で対角線に接する。

計算の手順

LDPC 符号を設計して性能を見積もる手順をまとめる。

  1. 次数を決める:$(c,d)$ を選ぶ。設計の符号化率は $1-c/d$(prop-ldpc-rate)。実際の次元は $H$ の階数を $\mathbb{F}_2$ 上の掃き出しで求める。
  2. グラフを作る:各ビットに $c$ 本、各検査に $d$ 本の辺が出るように結ぶ。短い閉路(特に長さ 4 の閉路、すなわち $H$ の 2 行が 2 列で共に $1$ をもつこと)を避ける。
  3. 距離を確かめる:小さい集合の展開性 $(a,\varepsilon)$ を確かめられれば、$\varepsilon<1/2$ で $d_{\min}\ge a+1$(thm-ldpc-distance)。$c=2$ なら距離は検査のグラフの内周(prop-ldpc-cycle)。
  4. 復号を選ぶ:位置の分からない誤りにはビット反転復号($\varepsilon<1/4$ で $a/2$ 個まで保証、thm-ldpc-flip)。消失には剥がし復号(thm-ldpc-peeling)。止める判定は「反転できるビットがない」「次数 1 の検査がない」で、反復の回数はそれぞれ $u_0$ 以下、消失の個数以下である。
  5. 閾値を計算する:消失通信路では $x_t=f_\varepsilon(x_{t-1})$ を反復し、$x_t\to0$ となる $\varepsilon$ の上限を二分法で求めるか、$\min_x x/(1-(1-x)^{d-1})^{c-1}$ を数値で求める(rem-ldpc-threshold)。容量 $1-R$ と比べる。

例題

完全グラフ $K_4$ の辺の符号

検査を $K_4$ の頂点 $1,2,3,4$、ビットを 6 本の辺 $12,13,14,23,24,34$ とする($c=2$、$d=3$)。
$$ H=\begin{pmatrix}1&1&1&0&0&0\\1&0&0&1&1&0\\0&1&0&1&0&1\\0&0&1&0&1&1\end{pmatrix} $$
使う公式:prop-ldpc-rate、lem-ldpc-unique、thm-ldpc-distance、prop-ldpc-cycle。
答え:$\operatorname{rank}H=3$(4 行の和が $0$)、$\dim C(H)=3$、符号化率 $1/2$(設計の符号化率 $1/3$ より大きい)。符号語は空集合・4 つの三角形・3 つの長さ 4 の閉路で、重みは $0,3,3,3,3,4,4,4$、最小距離は内周 $3$。

展開性の計算を開く

$\min\lvert N(S)\rvert/(2\lvert S\rvert)$ は、$\lvert S\rvert=1$ で $1$(端点 2 つ)、$\lvert S\rvert=2$ で $3/4$(端点を共有する 2 辺)、$\lvert S\rvert=3$ で $1/2$(三角形)である。よってグラフは $(2,1/4)$ 展開的で、$\varepsilon=1/4<1/2$ だから thm-ldpc-distance により $d_{\min}\ge3$ であり、三角形で等号になる。$(3,1/2)$ 展開的でもあるが、$\varepsilon=1/2$ では定理は使えない。

ビット反転復号の 1 歩

ex-ldpc-k4 の符号で $x=0$ を送り、辺 $12$ のビットだけが反転した $y=(1,0,0,0,0,0)$ を受け取った。
使う公式:ビット反転復号の手順。
答え:満たされない検査は頂点 $1,2$ の 2 つ。辺 $12$ は 2 つの満たされない検査と隣接し、$2>c/2=1$ なので反転され、$\boxed{y\mapsto0}$ で止まる。反転は 1 回。

定理との関係を開く

このグラフは $(1,0)$ 展開的だが、thm-ldpc-flip が保証するのは重み $a/2=1/2$ 以下、すなわち誤りなしだけである。$(2,1/4)$ 展開的でもあるが $\varepsilon<1/4$ を満たさない。1 個の誤りが直ったのは定理の保証の外の成り行きである。2 個の誤りでは直らない(反例の表)。

剥がし復号

ex-ldpc-k4 の符号で、閉路 $1\text{–}2\text{–}4\text{–}3\text{–}1$ の符号語 $x=(1,1,0,0,1,1)$(座標の順は $12,13,14,23,24,34$)を送り、辺 $12,13,14$ のビットが消えた。
使う公式:thm-ldpc-peeling。
答え:頂点 $2$ の検査で $x_{12}=x_{23}+x_{24}=1$、頂点 $3$ の検査で $x_{13}=x_{23}+x_{34}=1$、最後に頂点 $1$ の検査で $x_{14}=x_{12}+x_{13}=0$。すべて復元され、$x$ に一致する。

止まる場合を開く

消えたのが三角形 $12,13,23$ なら、頂点 $1,2,3$ の検査はどれも消えたビットを 2 つずつもち、頂点 $4$ の検査は消えたビットをもたない。三角形は停止集合なので何も復元されない。三角形は符号語でもあるので、どんな復号でも区別できない。

$(3,6)$ の密度発展

$(c,d)=(3,6)$、$f_\varepsilon(x)=\varepsilon(1-(1-x)^5)^2$ とする。
使う公式:prop-ldpc-tree、rem-ldpc-threshold。
答え:$\varepsilon=0.40$ では $x_1\approx0.340211$、$x_2\approx0.306227$、$x_3\approx0.281752$ と減り、$x_t\to0$。根が反復 1、2 のあとに消えたままの確率は $\approx0.31376$、$\approx0.26794$。$\varepsilon=0.45$ では $x_t$ は固定点 $\approx0.355443$ に収束して $0$ にならない。閾値は $\varepsilon^*\approx0.42944$。

ほかの次数の閾値を開く
$(c,d)$設計の符号化率閾値 $\varepsilon^*$容量の限界 $c/d$
$(3,4)$$1/4$$\approx0.64743$$0.75$
$(3,5)$$2/5$$\approx0.51757$$0.6$
$(3,6)$$1/2$$\approx0.42944$$0.5$
$(4,8)$$1/2$$\approx0.38345$$0.5$

同じ符号化率 $1/2$ でも、次数を上げた $(4,8)$ のほうが閾値は低い。正則の符号では閾値は容量の限界に届かない。

Petersen グラフの辺の符号

検査を Petersen グラフの 10 頂点、ビットを 15 本の辺とする($c=2$、$d=3$)。
使う公式:prop-ldpc-rate、prop-ldpc-cycle。
答え:$\operatorname{rank}H=9$、次元 $6$(符号化率 $2/5$、設計の符号化率 $1/3$)、最小距離は内周の $5$。prop-ldpc-cycle の上界は $2\log_2 10+2\approx8.64$。

階数の理由を開く

連結なグラフの接続行列の $\mathbb{F}_2$ 上の階数は「頂点の数 $-1$」である(行の集合 $T$ の和が $0$ なら、どの辺も $T$ の頂点を偶数個もつので、$T$ と補集合の間に辺がない。連結なので $T$ は空か全体であり、1 次関係は全部の行の和だけである)。よって $15-9=6$。

使える条件と反例

外す条件反例成り立たなくなること
thm-ldpc-distance の $\varepsilon<1/2$($\varepsilon=1/2$ にする)$K_4$ の符号は $(3,1/2)$ 展開的重み $3\le a$ の符号語(三角形)がある
thm-ldpc-flip の誤りの重み $\le a/2$$K_4$ の符号($(1,0)$ 展開的)で辺 $12,23$ の 2 個の誤り辺 $13$ が反転され、三角形の符号語に誤って復号される
手順が有限回で止まること(thm-ldpc-flip の証明の (1)。展開性によらない)に要る「半分より多く」の厳密な不等号(「半分以上」にする)$K_4$ の符号で辺 $12$ の 1 個の誤り辺 $13$ を反転・再反転でき、満たされない検査の個数が $2$ のまま往復して止まらないことがある
thm-ldpc-peeling の「$E$ が空でない停止集合を含まない」$K_4$ の符号で三角形 $12,13,23$ が消える何も復元されない
prop-ldpc-rate の等号に要る「行が 1 次独立」$K_4$ の符号(4 行の和が $0$)符号化率は $1/2$ で、$1-c/d=1/3$ に等しくない
prop-ldpc-tree の「近傍が木」$K_4$ の符号(Tanner グラフに長さ 6 の閉路)$\varepsilon=0.4$ で、ビット $12$ が反復 2 のあとに消えたままの確率は $0.136192$ だが、式は $\approx0.079732$(反復 1 では近傍が木で、どちらも $0.16384$)
反例の確認を開く

2 行目:$y=(1,0,0,1,0,0)$ で満たされない検査は頂点 $1,3$。辺 $13$ だけが 2 つの満たされない検査と隣接して反転され、$(1,1,0,1,0,0)$(三角形)で止まる。3 行目:$y=(1,0,0,0,0,0)$ で辺 $13$ は満たされない検査 $1$ と満たされた検査 $3$ に隣接し、ちょうど半分なので「半分以上」の規則では反転できる。反転後 $(1,1,0,0,0,0)$ は頂点 $2,3$ が満たされず、辺 $13$ はまた半分なので戻せる。満たされない検査の個数は $2,2,2,\dots$ のままである。

よくある誤り

誤り正しくはなぜ
符号化率は $1-c/d$ に等しい$1-c/d$ 以上。行が従属なら大きいprop-ldpc-rate、ex-ldpc-k4
検査行列が疎なら最小距離は大きい展開性が要る。$c=2$ では対数の程度prop-ldpc-cycle
剥がし復号が止まれば、消えたビットは決められない停止集合が符号語の台を含まなければ、1 次方程式で決まる下の例
閾値 $0.4294$ は容量 $0.5$ と同じ意味閾値はこの復号の限界、容量はどの符号・復号でも越えられない限界rem-ldpc-threshold
直せる誤りの数は最小距離の半分まで保証されるthm-ldpc-flip は $\varepsilon<1/4$ で $a/2$ 個まで。距離の保証($\varepsilon<1/2$)より強い展開性が要るthm-ldpc-flip
3 行目の例を開く

$H$ の行を $\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$ とする 3 ビットの符号は $\{0\}$ だけである(最初の 3 行から $x_1=x_2=x_3$、4 行目から $x_1=0$)。3 ビットすべてが消えても答えは $0$ と決まるが、どの検査も消えたビットを 2 つ以上もつので剥がし復号は 1 歩も進まない。

補足

  • 確率伝搬(sum–product):2 元対称通信路や Gauss 通信路では、メッセージを「消えた/分かった」から各ビットの事後確率に替える。Tanner グラフが木なら周辺の事後確率を正確に計算し、閉路があっても近似として使う(Mac03 §47.3、p. 559)。最尤復号そのものは一般に計算が難しい(同 §47.1、p. 557)。
  • 非正則の符号:次数の分布 $\lambda,\rho$ を選ぶと、消失通信路で閾値を容量 $1-R$ にいくらでも近づけられる(LMSS01 §IV、p. 576 以降。この記事では証明しない)。
  • Tanner 符号:各検査を単一のパリティでなく短い符号で置き換えると、より弱い展開性で良い符号が作れる(GRS25 §11.4)。

関連項目

参考文献

[1]
David J. C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003, §47.1 Theoretical properties(p. 557、列の重み 3 以上の Gallager 符号の距離、最尤復号の困難さ)、§47.3 Decoding with the sum–product algorithm(p. 559)
[3]
Michael Sipser, Daniel A. Spielman, Expander Codes, IEEE Transactions on Information Theory 42 (6) (1996), 1710–1722, 1996, Theorem 10(p. 1714、単純な逐次復号)
[4]
Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman, Efficient Erasure Correcting Codes, IEEE Transactions on Information Theory 47 (2) (2001), 569–584, 2001, p. 569(消失通信路の容量)、Proposition 2・Lemma 1(p. 575)、Theorem 2 と条件 (7)・(8)(p. 576)、§IV(p. 576 以降)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する