LDPC(Low-Density Parity-Check)符号は、1960年代にGallagerによって発見されました。この符号が注目されるようになったのは30年以上後のMackayによる再発見(1990年代)から¹ですが、この再発見により符号理論界にブレイクスルーを起こしました。現在では、LDPC符号はイーサネットや衛星通信、LTEやWiFiにおける誤り訂正方式として標準化されています。

これほど注目されるようになった大きな理由は、その復号方式によります。 LDPC符号の復号方式は、そのタナ―グラフ(Tanner Graph)が疎であることを活用してsum-product復号法²と呼ばれる方法を使って復号します。それによって、非常に良いパフォーマンスで復号することが可能になります。また、適切に符号を設定するとシャノン限界に迫る特性を達成することも大きな理由の一つとして挙げられます。

LDPC符号の定義

まずは本題のLDPC符号の定義を紹介します。

定義 1.1. LDPC符号(Low-Density Parity-Check Codes)

$H$ を ${\mathbb F}_2$ 上の行列とする。 $H$ の成分に1が少ないとき、 $H$ を疎行列(sparse matrix)といい、疎行列 $H$ をパリティ検査行列にもつ線形符号 $C$ と疎行列 $H$ のペア $(C, H)$ をLDPC符号(Low-Density Parity-Check Codes)という。

$(C, H)$ を単に $C$ と書くこともありますが、符号 $C$ から得られた $H$ が疎行列であることは必ずしも言えないため、 $C$ だけを指してLDPC符号と呼ぶのは好ましくないとされています。

定義 1.2. 正則・非正則LDPC符号(Regular/Irregular LDPC Codes)

LDPC符号 $(C, H)$ の行列 $H$ において、全ての列のハミング重みが等しく全ての行のハミング重みが等しいとき、正則LDPC符号(Regular LDPC Codes)といい、そうでないとき非正則LDPC符号(Irregular LDPC Codes)という。

正則LDPC符号は構築しやすく、非正則LDPC符号はパフォーマンスがよりよいといった特徴があります。

タナ―グラフ

LDPC符号の復号法で重要な役割を持っているタナ―グラフを見ていきます。タナ―グラフは行列 $H$ から表される二部グラフのことで、次のように定義されます。

定義 2.1. タナ―グラフ(Tanner Graph)

$H=(h_{i,j})$ をサイズが $m\times n$ の ${\mathbb F}_2$ 上の行列として、集合 $V_c,V_v$ をそれぞれ $V_c := \{c_1, c_2, \dots, c_m\}, V_v := \{v_1, v_2, \dots, v_n\}$ とする。

集合 $V,E$ をそれぞれ

$\begin{eqnarray} V &:=& V_c \cup V_v\\ E &:=& \{(c_i, v_j)\in V_c\times V_v\ |\ h_{i,j}=1\} \end{eqnarray}$

としたとき、二部グラフ $G=(V,E)$ をタナ―グラフ(Tanner Graph)という。また、 $V_c$ の元を検査ノード(check nodes)、 $V_v$ の元を変数ノード(variable nodes)という。

例 2.2.

パリティ検査行列 $H$ を以下とします:

$H = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 0 & 1 & 0 & 1 & 1\\ \end{pmatrix}.$

このとき、 $H$ から表されるタナ―グラフは次のようになります。

tanner_graph

パリティ検査行列とタナ―グラフの関係

序論で説明していますが、LDPC符号の復号法はそのタナ―グラフを用いて表されることがほとんどです。パリティ検査行列(行列での表現)とタナ―グラフ(グラフでの表現)にはどのような関係があるのでしょうか。

例2.2.を参考にしながら進めていくと、行列と比べてタナ―グラフはある列(行)に関係している行(列)がわかりやすくなっていることがわかります。例えば、この $H$ を用いて生成された符号語 ${\textbf c}$ は $H\cdot {\textbf c}^{\rm T}={\textbf 0}$ と表すことができますが、検査ノード $c_i(i\in\{1, 2, 3\})$ と接続している変数ノードの集合を $V(c_i)$ と表すとすると、次のように表すことができます:

$\prod_{c_i\in V_c} \delta\left[\sum_{v_j\in V(c_i)} c_{v_j} = 0 \right].$

ここで、 $\delta[p]$ は、 $p$ が真のときのみ $1$ 、それ以外は $0$ となる関数とします。

また、変数ノード $v_j(j\in\{1,2,\dots,7\})$ と接続している検査ノードの集合を $C(v_j)$ と表すとすると、定義1.2.は次のように言い換えることができます:

定義1.2.の言い換え

任意の $i, j(i\in\{1, 2,\dots, m\}, j\in\{1,2,\dots,n\})$ において、 $|V(c_i)|$ と $|C(v_j)|$ がそれぞれ等しいとき正則、そうでないとき非正則という。

このように、LDPC符号のパリティ検査行列 $H$ で定義されていた概念をタナ―グラフを用いて言い換えることが可能であることがわかったと思います。復号法のみでなく、パリティ検査行列で説明される概念はパリティ検査行列 $H$ とタナ―グラフの両方の表現で考えることが重要になります。

符号化について

定義1.2.の後に述べていますが、LDPC符号が正則のとき構成するのは簡単ですが、非正則かつ擬巡回(quasi-cyclic)の性質を持っていないときは複雑になります。その場合の符号化手法の一つである下三角行列(lower-trianglar matrix)での後退代入(back substitution)については参考文献3.で紹介されています。非正則で擬巡回の場合は、(恐らく)QC-LDPC符号で紹介していると思います。

以上の理由から、ここでの符号化についての説明は割愛します。

復号化の概要

復号化についても、ここから説明していくと非常に長くなると考えられるため簡単に説明します。

復号化において、LDPC符号が優れている理由は、復号法であるsum-product復号法は確率伝播によるものであり、この確率がパリティ検査行列 $H$ が疎であるほど良いパフォーマンスで求まるということにあります。具体的に言うと、 $H$ のタナ―グラフにサイクルがない、もしくは少ないほうが好まれる傾向にあります。

まずは、sum-product復号法を定義していきます:

定義 4.1 (確率領域)sum-product 復号法

入力: ${\mathbb F}_2$ 上の $m\times n$ 行列 $H$ 、 $y\in {\mathbb F}_2^{n}$ 、整数 $l_{\rm max}$

出力: $H$ が与える線形符号 $C$ の符号語 $c$ あるいは記号 $?$

1. 初期化：

$h_{i,j} = 1$ を満たす全ての組 $(i,j)$ に対して、 $\beta_{i,j}(x)\in {\mathbb R}$ を以下で定義する:

$\beta_{i,j}(x) := P(y_j|x).$

ただし、 $x\in \{0,1\}$ であり、 $P(a|b)$ は $b$ のとき $a$ となる確率とする。また、反復回数のカウンタとして $l:=1$ とする。

2. 行処理：

$h_{i,j} = 1$ を満たす全ての組 $(i,j)$ に対して、 $\alpha_{i,j}(x)\in {\mathbb R}$ を以下で定義する:

$\alpha_{i,j}(x) := K \sum_{c_{\ V(i)\setminus \{j\}}} \delta\left[\sum_{v\in V(i)\setminus \{j\}}c_v = x\right] \times \prod_{j'\in V(i)\setminus \{j\}} \beta_{i,j'}(c_{j'})$

ここで、定数 $K$ は $\alpha_{i,j}(0)+\alpha_{i,j}(1)=1$ を満たすように定める。また、

$\sum_{c_{\{1, 2, \dots, m\}}} := \sum_{c_{1}\in {\mathbb F}_2}\sum_{c_{2}\in {\mathbb F}_2}\cdots \sum_{c_{m}\in {\mathbb F}_2}$

とする。

3. 列処理：

$h_{i,j} = 1$ を満たす全ての組 $(i,j)$ に対して、 $\beta_{i,j}(x)\in {\mathbb R}$ を以下のように更新する:

$\beta_{i,j}(x) := K'P(y_j|x)\prod_{i'\in C(j)\setminus \{i\}}\alpha_{i',j}(x).$

同様に、定数 $K'$ は $\beta_{i,j}(0)+\beta_{i,j}(1)=1$ を満たすように定める。

4. 一時推定：

$j\in \{1, 2, \dots, n\}$ に対して、 $\gamma_{j}(x)\in {\mathbb R}$ を以下のように求める:

$\gamma_{j}(x) := P(y_j|x)\prod_{i\in C(j)}\alpha_{i,j}(x).$

そして、 $\gamma_{j}(0) \geq \gamma_{j}(1)$ のとき、 $\hat{c}_{j}:=0$ 、そうでないときは $\hat{c}_{j}:=1$ とする。

5. パリティ検査：

$H\cdot (\hat{c}_{1}, \hat{c}_{2}, \dots, \hat{c}_{n})^{\rm T}={\textbf 0}$ を満たすならば、 $c:=(\hat{c}_{1}, \hat{c}_{2}, \dots, \hat{c}_{n})$ を出力する。そうでないときは6.へ

6.

$l \geq l_{\rm max}$ ならば、 $?$ を出力する。そうでないときは、 $l = l+1$ として3.へ

例 4.2

定義4.1.で説明されたsum-product復号法の例をあげていきます。まず最初に、パリティ検査行列 $H$ を次のように設定します:

$H= \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ \end{pmatrix}.$

また、 $y = (0, 0, 1, 1, 0, 1, 0, 0)$ 、 $l_{\rm max}=5$ として、任意の $a, b\in {\mathbb F}_2$ において $P(a|b)=\frac{3}{4} (a = b), \frac{1}{4} (a \neq b)$ とします。

初期化

$\beta(x):=(\beta_{i,j}(x)), x\in \{0, 1\}$ は次のようになります:

$\beta(0) = \begin{pmatrix} 0 & 0 & 0 & 1/4 & 3/4 & 1/4 & 0 & 0 \\ 3/4 & 0 & 0 & 1/4 & 0 & 0 & 0 & 3/4 \\ 3/4 & 3/4 & 1/4 & 0 & 3/4 & 0 & 3/4 & 3/4 \\ \end{pmatrix},$

$\beta(1) = \begin{pmatrix} 0 & 0 & 0 & 3/4 & 1/4 & 3/4 & 0 & 0 \\ 1/4 & 0 & 0 & 3/4 & 0 & 0 & 0 & 1/4 \\ 1/4 & 1/4 & 3/4 & 0 & 1/4 & 0 & 1/4 & 1/4 \\ \end{pmatrix}.$

行処理

手順2.より、 $\alpha_{i,j}(x)$ を求めていきます。

例えば、 $\alpha_{1,5}(x)$ を考えていくとしましょう。 $H$ のタナ―グラフの検査ノード $c_i$ に隣接している変数ノードは $V(i)=\{4,5,6\}$ の三つですね。よって、 $\alpha_{1,5}(x)$ を書き直すと次のようになります:

$\alpha_{1,5}(x) = K\left(\sum_{c_4\in {\mathbb F}_2}\sum_{c_6\in {\mathbb F}_2} \delta\left[\sum_{v\in \{4,6\}} c_{v} = x \right]\times \prod_{j'\in \{4,6\}} \beta_{i, j'}(c_{j'}) \right)$

ここから $x = 0$ の場合と $x = 1$ の場合に分けて見ていきましょう。 $x=0$ のとき、 $\delta[\dots]$ が $1$ になるのは、 $c_4, c_6 = 0\ {\rm or}\ 1$ のときですね。よって、

$\alpha_{1,5}(0) = K \left(\frac{1}{4}\cdot \frac{1}{4}+\frac{3}{4}\cdot \frac{3}{4}\right) = K\cdot \frac{5}{8}$

同様にして、 $x=1$ のときは、 $c_4, c_6 = 0, 1 \ {\rm or}\ 1, 0$ のときであり、

$\alpha_{1,5}(1) = K \left(\frac{1}{4}\cdot \frac{3}{4}+\frac{3}{4}\cdot \frac{1}{4}\right) = K\cdot \frac{3}{8}$

したがって、 $\alpha_{1,5}(0) = \frac{5}{8}$ $,\alpha_{1,5}(1) = \frac{3}{8}$ となります。同様に進めていくと、 $\alpha(x)=(\alpha_{i,j}(x))$ は次のようになります:

$\alpha(0) = \begin{pmatrix} 0 & 0 & 0 & 3/8 & 5/8 & 3/8 & 0 & 0 \\ 3/8 & 0 & 0 & 5/8 & 0 & 0 & 0 & 3/8 \\ 31/64 & 31/64 & 33/64 & 0 & 31/64 & 0 & 31/64 & 31/64 \\ \end{pmatrix},$

$\alpha(1) = \begin{pmatrix} 0 & 0 & 0 & 5/8 & 3/8 & 5/8 & 0 & 0 \\ 5/8 & 0 & 0 & 3/8 & 0 & 0 & 0 & 5/8 \\ 33/64 & 33/64 & 31/64 & 0 & 33/64 & 0 & 33/64 & 33/64 \\ \end{pmatrix}.$

列処理

次に手順3.にいきます。先ほどの列バージョンになっています。最終的に $\beta(x)$ は次のようになります:

$\beta(0) = \begin{pmatrix} 0 & 0 & 0 & 5/14 & 31/42 & 1/4 & 0 & 0 \\ 31/42 & 0 & 0 & 1/6 & 0 & 0 & 0 & 31/42 \\ 9/14 & 3/4 & 1/4 & 0 & 5/6 & 0 & 3/4 & 9/14 \\ \end{pmatrix},$

$\beta(1) = \begin{pmatrix} 0 & 0 & 0 & 9/14 & 11/42 & 3/4 & 0 & 0 \\ 11/42 & 0 & 0 & 5/6 & 0 & 0 & 0 & 11/42 \\ 5/14 & 1/4 & 3/4 & 0 & 1/6 & 0 & 1/4 & 5/14 \\ \end{pmatrix}.$

一時推定

手順4.に移ります。一ビットずつ列ベクトルから符号語の予想を出していきます。最終的な $\hat{c}$ は次のようになります:

$\hat{c} = (0, 0, 1, 1, 0, 1, 0, 0 ).$

まだ初期の $y$ と同じですね。もちろんパリティ検査行列とかけても ${\textbf 0}$ とはならないので、 $l$ を増やしてループします。

という風な感じで復号が進んでいきます。最終的にどうなるか気になったら、ぜひ手を動かして見てください。めちゃくちゃ大変です。😇(ちなみに自分は $l=2$ で諦めました)

今回は、一般的なsum-product復号法を紹介しましたが、対数を使ったsum-product復号法もあり、こちらの方がコンピュータなどで計算する際に都合がよくなります。

参考文献

井坂元彦,「知識の森」6章ターボ符号・LDPC符号, 電子情報通信学会, 2012
萩原学, 「符号理論」, 日本評論社, 2012
Marco Baldi, QC-LDPC Code-Based Cryptography, Springer, 2014
IEEE, Enhancing the error-correcting performance of LDPC codes for LTE and WiFi, https://ieeexplore.ieee.org/abstract/document/7148600, 2015

当時では、符号長が大きいと計算量が莫大になるなどの理由によって影を潜めていたそうです ↩
sum-productアルゴリズム(SPA)に基づく反復復号法(iterative decoding)のこと。ターボ符号(1993~, turbo codes)もこの復号法を使うことができるため注目されています。 ↩