これはなに
次の論文について、個人的な関心領域の話題を加えて勉強したことをメモしました。
https://www.jstage.jst.go.jp/article/essfr/14/3/14_217/_article/-char/ja/
(DOI https://doi.org/10.1587/essfr.14.3_217)
低密度パリティ検査符号（LDPC符号）
１．まえがき
特になし。
２．通信システムモデルと誤り訂正符号
原文では通信路のモデルをシンボルごとに独立同分布に従い（i.i.d.：independent and identically distributed）、通信路誤り率 p の確率でビット誤りが起こる２元対称通信路（BSC：Binary symmetric channel）として議論を進めているが、自習のために適宜AWGN通信路として受信信号から尤度を計算できるように準備する。
AWGN通信路では、送信信号（符号語を変調した信号）に対して正規分布に従う白色雑音が印加されて受信信号となる。受信信号を復調する時に信号の値とSNR(Signal-to-Noise Ratio)から計算できる尤度を復号器に入力し、復号アルゴリズムの中で利用する方法を軟判定と呼ぶ。一方、いったん受信語をビット判定してしまって、それを復号器に入力する方法を硬判定と呼ぶ。
1ビット( 0 / 1 )を2値の信号( +1 / -1 )に変調するBPSK(Binary Phase-Shift Keying)方式において、受信信号のシンボル y_i は次の条件付き確率に従った値をとる。
\begin{aligned}
\Pr[y_i|x_i=0] = \frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{(y_i-(+1))^2}{2\sigma^2}} \\
\Pr[y_i|x_i=1] = \frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{(y_i-(-1))^2}{2\sigma^2}}
\end{aligned}
受信信号のシンボル y_i と雑音の分散 \sigma^2 が得られた時、符号語のビット x_i=0 と x_i=1 との対数尤度比 L_i を求めることができる。
自分の勉強用に、 0 である尤度のほうが大きいとき正の値をとることを明示するために、特に L_i(0) と表記する。（以後も付記や省略を適宜行う）
\begin{aligned}
L_i(0) &= \log\frac{\Pr[y_i|x_i=0]}{\Pr[y_i|x_i=1]} \\
&= \frac{2y_i}{\sigma^2}
\end{aligned}
３．確率推論による復号とLDPC符号
３．１ 確率推論による復号
符号語の事前確率 P_{\mathbf{X}}(\mathbf{x}) について、メッセージ \mathbf{m} の長さ k に対して \lvert \mathcal{C} \rvert = 2^k 通りの符号語が均等に現れる。
\begin{aligned}
P_{\mathbf{X}}(\mathbf{x}) = \begin{dcases}
1 / \lvert \mathcal{C} \rvert & (\mathbf{x} \in \mathcal{C}) \\
0 & (\mathrm{otherwise})
\end{dcases} = \frac{1}{\lvert \mathcal{C} \rvert}\mathbb{I}[\mathbf{x} \in \mathcal{C}]
\end{aligned}
例えば1ビットのメッセージに対して3回繰り返す符号化では、 \mathcal{C} = \{000, 111\} であり、 \lvert \mathcal{C} \rvert = 2 である。
このとき、指示関数 \mathbb{I}[\mathbf{x} \in \mathcal{C}] は「 x_1=0 かつ x_2=0 かつ x_3=0 、または x_1=1 かつ x_2=1 かつ x_3=1 のときには 1 を返し、そうでない場合は 0 を返す」関数であり、ブール代数の真理値表で表すことができる。
\begin{aligned}
\begin{array}{c|c|c||c} \hline
x_1 & x_2 & x_3 & \mathbb{I}[\mathbf{x} \in \mathcal{C}] \\ \hline
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 \\ \hline
\end{array}
\end{aligned}
そのため、指示関数を加法標準形の論理式に書き換えることができる。
\begin{aligned}
\mathbb{I}[\mathbf{x} \in \mathcal{C}] = f(\mathbf{x}) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} + x_1 \cdot x_2 \cdot x_3
\end{aligned}
繰り返し符号はどの符号語のシンボルを推定（復号）しても結果は同じで、 \hat{x}_1 に代表できる。
原文の P_{Y|X}(y_i|x_i=b) を便宜的に l_{i}(x_i=b) と省略して表す。
\begin{aligned}
\hat{x}_1 &= \mathop{\mathrm{argmax}}\limits_{x_1 \in \{0, 1\}} P_{X|\mathbf{Y}}(x_1|\mathbf{y}) \\
&= \mathop{\mathrm{argmax}}\limits_{x_1 \in \{0, 1\}} \displaystyle \sum_{\sim x_1} \left( \displaystyle \prod_{j=1}^{3} P_{Y|X}(y_j|x_j) \right) \mathbb{I}[\mathbf{x} \in \mathcal{C}] \\
&= \mathop{\mathrm{argmax}}\limits_{x_1 \in \{0, 1\}} \displaystyle \sum_{x_2 x_3} f(\mathbf{x}) \displaystyle \left( \displaystyle \prod_{j=1}^{3} l_{j}(x_j) \right) \\
&= \mathop{\mathrm{argmax}}\limits_{x_1 \in \{0, 1\}} \displaystyle \sum_{x_2 x_3} \left( \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} + x_1 \cdot x_2 \cdot x_3 \right) \displaystyle \prod_{j=1}^{3} l_{j}(x_j) \\
&= \mathop{\mathrm{argmax}}\limits_{x_1 \in \{0, 1\}} \begin{dcases}
l_1(0) \cdot l_2(0) \cdot l_3(0) & (x_1 = 0) \\
l_1(1) \cdot l_2(1) \cdot l_3(1) & (x_1 = 1)
\end{dcases}
\end{aligned}
３．２ 分配則による演算数の削減
小さなパリティ検査行列を使って、分配則の確認をする。
\begin{aligned}
\mathbf{H} = \begin{bmatrix}
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1
\end{bmatrix}
\end{aligned}
\begin{aligned}
\mathcal{C} &= \set{\mathbf{x} \mid \mathbf{H}\mathbf{x}^\mathrm{T}=\mathbf{0}} \\
&= \set{\mathbf{x} \mid x_1 \oplus x_3=0 \ \ \mathrm{and} \ \ x_1 \oplus x_2 \oplus x_4=0}
\end{aligned}
\begin{aligned}
\begin{array}{c|c|c|c||c} \hline
x_1 & x_2 & x_3 & x_4 & \mathbb{I}[\mathbf{x} \in \mathcal{C}] \\ \hline
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 \\ \hline
\end{array}
\quad
\begin{array}{c|c|c|c||c} \hline
x_1 & x_2 & x_3 & x_4 & \mathbb{I}[\mathbf{x} \in \mathcal{C}] \\ \hline
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 0 \\ \hline
\end{array}
\end{aligned}
\begin{aligned}
\mathbb{I}[\mathbf{x} \in \mathcal{C}] = f(\mathbf{x}) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot \overline{x_4} + \overline{x_1} \cdot x_2 \cdot \overline{x_3} \cdot x_4 + x_1 \cdot \overline{x_2} \cdot x_3 \cdot x_4 + x_1 \cdot x_2 \cdot x_3 \cdot \overline{x_4}
\end{aligned}
この送信シンボル x_1 に対する事後確率（正規化定数を追記）を全ての積和が確認できるように表記する。
すると、乗算の数が12、加算の数が2必要であることが分かる。
\begin{aligned}
\frac{P_{X|\mathbf{Y}}(x_1|\mathbf{y})}{1/Z}
= {} & \displaystyle \sum_{\sim x_1} f(\mathbf{x}) \displaystyle \prod_{j=1}^{4} l_{j}(x_j) \\
= {} & \begin{dcases}
l_{1}(0) \cdot l_{2}(0) \cdot l_{3}(0) \cdot l_{4}(0)
+ l_{1}(0) \cdot l_{2}(1) \cdot l_{3}(0) \cdot l_{4}(1) & (x_1 = 0) \\
l_{1}(1) \cdot l_{2}(0) \cdot l_{3}(1) \cdot l_{4}(1)
+ l_{1}(1) \cdot l_{2}(1) \cdot l_{3}(1) \cdot l_{4}(0) & (x_1 = 1)
\end{dcases}
\end{aligned}
ここから共通因子をまとめるには、 \mathcal{C} が \mathcal{C}_1 = \set{\mathbf{x} \mid x_1 \oplus x_3=0} と \mathcal{C}_2 = \set{\mathbf{x} \mid x_1 \oplus x_2 \oplus x_4=0} に分解できることを考えれば良い。
\begin{aligned}
\mathbb{I}[\mathbf{x} \in \mathcal{C}] = \mathbb{I}_1 \cdot \mathbb{I}_2 = f_1(x_1,x_3) \cdot f_2(x_1,x_2,x_4) = \mathbb{I}[\mathbf{x} \in \mathcal{C}_1] \cdot \mathbb{I}[\mathbf{x} \in \mathcal{C}_2]
\end{aligned}
\begin{aligned}
\begin{array}{c}
\begin{array}{c|c||c} \hline
x_1 & x_3 & \mathbb{I}_1 \\ \hline
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\ \hline
\end{array} \\
\\
\\
\\
\\
\end{array}
\quad
\begin{array}{c|c|c||c} \hline
x_1 & x_2 & x_4 & \mathbb{I}_2 \\ \hline
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 \\ \hline
\end{array}
\end{aligned}
\begin{aligned}
\begin{array}{c|c|c|c||c|c|c} \hline
x_1 & x_2 & x_3 & x_4 & \mathbb{I}_1 & \mathbb{I}_2 & \mathbb{I}_1 \cdot \mathbb{I}_1 \\ \hline
0 & 0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 & 0 \\ \hline
\end{array}
\quad
\begin{array}{c|c|c|c||c|c|c} \hline
x_1 & x_2 & x_3 & x_4 & \mathbb{I}_1 & \mathbb{I}_2 & \mathbb{I}_1 \cdot \mathbb{I}_1 \\ \hline
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline
\end{array}
\end{aligned}
同じように送信シンボル x_1 に対する事後確率を全ての積和が確認できるように表記する。
すると、乗算の数が8、加算の数が2となり、演算数の少ない計算式を得ていることが分かる。
\begin{aligned}
\frac{P_{X|\mathbf{Y}}(x_1|\mathbf{y})}{1/Z}
= {} & \displaystyle \sum_{\sim x_1} \mathbb{I}_1 \mathbb{I}_2 \displaystyle \prod_{j=1}^{4} l_{j}(x_j) \\
= {} & l_{1}(x_1) \displaystyle \sum_{x_2 x_3 x_4} f_1(x_1,x_3) f_2(x_1,x_2,x_4) l_2(x_2) l_3(x_3) l_4(x_4) \\
= {} & l_{1}(x_1) \displaystyle \sum_{x_3} f_1(x_1,x_3) l_3(x_3) \sum_{x_2 x_4} f_2(x_1,x_2,x_4) l_2(x_2) l_4(x_4) \\
= {} & \begin{dcases}
l_{1}(0) \cdot l_{3}(0) \cdot \{l_{2}(0) \cdot l_{4}(0) + l_{2}(1) \cdot l_{4}(1)\} & (x_1 = 0) \\
l_{1}(1) \cdot l_{3}(1) \cdot \{l_{2}(0) \cdot l_{4}(1) + l_{2}(1) \cdot l_{4}(0)\} & (x_1 = 1)
\end{dcases}
\end{aligned}
３．３ 木とsum-productアルゴリズム
sum-productアルゴリズムの導入の準備として、検査行列が \mathbf{H} である符号で符号化した通信の事後分布 P_{\mathbf{X}|\mathbf{Y}}(\mathbf{x}|\mathbf{y}) について考える。
まず、生成行列 \mathbf{G} から、独立して通信できるメッセージは2変数である。
\begin{aligned}
\mathbf{G} = \begin{bmatrix}
1 & 0 & 1 & 1 \\
0 & 1 & 0 & 1
\end{bmatrix}
\end{aligned}
次に、事後分布を P_{\mathbf{X}|\mathbf{Y}}(\mathbf{x}|\mathbf{y}) P_{\mathbf{Y}}(\mathbf{y}) = P_{\mathbf{Y}|\mathbf{X}}(\mathbf{y}|\mathbf{x}) P_{\mathbf{X}}(\mathbf{x}) で変形した \mathbf{x} の同時確率分布の部分を、条件付き確率を用いて4つの積に因数分解する。便宜的に p がそれぞれの変数の確率分布を表す関数であるとする。（ P_{\mathbf{X}}(\mathbf{x})=p(\mathbf{x}) ）
\begin{aligned}
p(\mathbf{x})
&= p(x_1) p(x_2,x_3,x_4|x_1) \\
&= p(x_1) p(x_2|x_1) p(x_3,x_4|x_1,x_2) \\
&= p(x_1) p(x_2|x_1) p(x_3|x_1,x_2) p(x_4|x_1,x_2,x_3) \\
\end{aligned}
この中で条件として有効ではない場合がある。例えば、 x_2 と x_1 は独立であるし、 x_3 と x_2 は x_1 の元で条件付き独立である。
\begin{aligned}
p(\mathbf{x})
&= p(x_1) p(x_2|x_1) p(x_3|x_1,x_2) p(x_4|x_1,x_2,x_3) \\
&= p(x_1) p(x_2) p(x_3|x_1) p(x_4|x_1,x_2) \\
\end{aligned}
すると、送信シンボル x_1 に対する事後確率を求める際に、 \mathbf{x} の同時確率分布の因数分解によって、符号 \mathcal{C}を \mathcal{C}_1 と \mathcal{C}_2 に分解したときと同様の分配則による演算数の削減ができる。
\begin{aligned}
\frac{P_{X|\mathbf{Y}}(x_1|\mathbf{y})}{1/p(\mathbf{y})}
= {} & \displaystyle \sum_{\sim x_1} \left( \displaystyle \prod_{j=1}^{4} l_{j}(x_j) \right) p(\mathbf{x}) \\
= {} & \displaystyle \sum_{x_2 x_3 x_4} l_1(x_1) l_2(x_2) l_3(x_3) l_4(x_4) p(x_1) p(x_2) p(x_3|x_1) p(x_4|x_1,x_2) \\
= {} & p(x_1) l_{1}(x_1) \displaystyle \sum_{x_3} p(x_3|x_1) l_3(x_3) \sum_{x_2 x_4} p(x_2) p(x_4|x_1,x_2) l_2(x_2) l_4(x_4) \\
\end{aligned}
（ここまでの内容は、次の論文の5章を参考にしました。）
https://kazunorihayashi.github.io/paper/mika2018.pdf
https://kazunorihayashi.github.io/publication.html#02
上記の共通因子をくくることは、人間が目で見てもどうにかできそうである。では、もっと複雑な場合に、ある確率変数に対して効率的に周辺化するにはどうしたらよいのだろうか。
そのためには、ファクターグラフと呼ばれる変数ノードとファクター（因子）ノードの2種類のノードを持つグラフで事後分布を表す。
もう少し複雑な事後分布でファクターグラフを確認する。
ファクターグラフにおいて、同時確率分布の因数分解はファクターノードで表される因数の積となり、ファクターノード f_i に隣接する（Neighbours）変数ノード {\rm ne}(f_i) がそれぞれの因数に含まれる変数となる。
6変数ノード、4ファクターノードのファクターグラフでは、6変数が4つの因数に分配される。
\begin{aligned}
p(\mathbf{x})
&= f_1(x_1,x_2) f_2(x_2,x_3,x_5) f_3(x_4,x_5) f_4(x_5,x_6) \\
&= \displaystyle \prod_{i=1}^{4} f_i({\rm ne}(f_i))
\end{aligned}
このファクターグラフを検査行列に適用すると、4行6列の検査行列となる。
\begin{aligned}
\mathbf{H} = \begin{bmatrix}
1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 1
\end{bmatrix}
\end{aligned}
\begin{aligned}
p(\mathbf{x}) = \frac{1}{\lvert \mathcal{C} \rvert} \mathbb{I}[x_1 \oplus x_2 = 0] \cdot \mathbb{I}[x_2 \oplus x_3 \oplus x_5 = 0] \cdot \mathbb{I}[x_4 \oplus x_5 = 0] \cdot \mathbb{I}[x_5 \oplus x_6 = 0]
\end{aligned}
全ての送信シンボルに対する事後確率を求める。
\begin{aligned}
\frac{P_{X|\mathbf{Y}}(x_i|\mathbf{y})}{1/p(\mathbf{y})}
&= \displaystyle \sum_{\sim x_i} \left( \displaystyle \prod_{j=1}^{6} l_{j}(x_j) \right) p(\mathbf{x}) \\
\frac{P_{X|\mathbf{Y}}(x_1|\mathbf{y})}{1/p(\mathbf{y})}
&= l_1(x_1) \left[ \sum_{x_2}
f_1(x_1,x_2) l_2(x_2) \left\{ \sum_{x_3 x_5}
f_2(x_2,x_3,x_5) \underline{l_3(x_3)} \left(
l_5(x_5) \sum_{x_4} f_3(x_4,x_5) \underline{l_4(x_4)} \sum_{x_6} f_4(x_5,x_6) \underline{l_6(x_6)}
\right)
\right\}
\right] \\
\frac{P_{X|\mathbf{Y}}(x_2|\mathbf{y})}{1/p(\mathbf{y})}
&= l_2(x_2) \sum_{x_1} f_1(x_1,x_2) \underline{l_1(x_1)} \left\{ \sum_{x_3 x_5}
f_2(x_2,x_3,x_5) \underline{l_3(x_3)} \left(
l_5(x_5) \sum_{x_4} f_3(x_4,x_5) \underline{l_4(x_4)} \sum_{x_6} f_4(x_5,x_6) \underline{l_6(x_6)}
\right)
\right\} \\
\frac{P_{X|\mathbf{Y}}(x_3|\mathbf{y})}{1/p(\mathbf{y})}
&= l_3(x_3) \left\{ \sum_{x_2 x_5}
f_2(x_2,x_3,x_5) l_2(x_2) \sum_{x_1} f_1(x_1,x_2) \underline{l_1(x_1)} \left(
l_5(x_5) \sum_{x_4} f_3(x_4,x_5) \underline{l_4(x_4)} \sum_{x_6} f_4(x_5,x_6) \underline{l_6(x_6)}
\right)
\right\} \\
\frac{P_{X|\mathbf{Y}}(x_4|\mathbf{y})}{1/p(\mathbf{y})}
&= l_4(x_4) \left[ \sum_{x_5}
f_3(x_4,x_5) l_5(x_5) \left\{ \sum_{x_2 x_3}
f_2(x_2,x_3,x_5) \left(
l_2(x_2) \sum_{x_1} f_1(x_1,x_2) \underline{l_1(x_1)}
\right) \underline{l_3(x_3)}
\right\} \sum_{x_6} f_4(x_5,x_6) \underline{l_6(x_6)}
\right] \\
\frac{P_{X|\mathbf{Y}}(x_5|\mathbf{y})}{1/p(\mathbf{y})}
&= l_5(x_5) \left\{ \sum_{x_2 x_3}
f_2(x_2,x_3,x_5) \left(
l_2(x_2) \sum_{x_1} f_1(x_1,x_2) \underline{l_1(x_1)}
\right) \underline{l_3(x_3)}
\right\} \sum_{x_4} f_3(x_4,x_5) \underline{l_4(x_4)} \sum_{x_6} f_4(x_5,x_6) \underline{l_6(x_6)} \\
\frac{P_{X|\mathbf{Y}}(x_6|\mathbf{y})}{1/p(\mathbf{y})}
&= l_6(x_6) \left[ \sum_{x_5}
f_4(x_5,x_6) l_5(x_5) \left\{ \sum_{x_2 x_3}
f_2(x_2,x_3,x_5) \left(
l_2(x_2) \sum_{x_1} f_1(x_1,x_2) \underline{l_1(x_1)}
\right) \underline{l_3(x_3)}
\right\} \sum_{x_4} f_3(x_4,x_5) \underline{l_4(x_4)}
\right] \\
\end{aligned}
このように、計算式からも葉ノード（下線付き変数）からルートノードに向かって変数ノード処理と検査ノード処理が入れ子状に行われていることがわかる。
そのため、sum-productアルゴリズムを用いた確率伝搬法により事後確率が求まり、符号語について確率推論による復号を行うことができる。
（グラフィカルモデル上で伝搬する確率メッセージについて、詳細はPRMLの8章にあります。）
https://www.microsoft.com/en-us/research/wp-content/uploads/2006/01/Bishop-Pattern-Recognition-and-Machine-Learning-2006.pdf
https://www.microsoft.com/en-us/research/people/cmbishop/prml-book/
https://olj611.hatenablog.com/archive/category/グラフィカルモデル
通信分野において、LDPCの復号は対数尤度比を用いて行われることが多い。
変数ノード処理 q_{ij} と検査ノード処理 r_{ij} で、x_j=0 と x_j=1 のときに q_{ij}(0)+q_{ij}(1)=1 、 r_{ij}(0)+r_{ij}(1)=1 となる確率メッセージが伝搬するように規格化定数を掛ける。
\begin{aligned}
q_{ij}(x_j)
&= K \cdot M_{x_j \to f_i}(x_j)
= K \cdot l_j(x_j) \displaystyle \prod_{f_{i^{'}} \in {\rm ne}(x_j) \backslash f_i} M_{f_{i^{'}} \to x_j}(x_j) \\
r_{ij}(x_j)
&= K' \cdot M_{f_i \to x_j}(x_j)
= K' \cdot \displaystyle \sum_{x_{j^{'}} \in {\rm ne}(f_i) \backslash x_j} f_i({\rm ne}(f_i)) \prod_{x_{j^{'}} \in {\rm ne}(f_i) \backslash x_j} M_{x_{j^{'}} \to f_i}(x_{j^{'}}) \\
f_i({\rm ne}(f_i))
&= \mathbb{I}[x_1 \oplus x_2 \oplus \dotsb \oplus x_j \oplus \dotsb \oplus x_n = 0]
\end{aligned}
確率変数なので、対数尤度比を求めることができる。
\begin{aligned}
q_{ij}(0)
&= K \cdot l_j(0) \displaystyle \prod_{i^{'} \in {\rm ne}(x_j) \backslash f_i} r_{i^{'}j}(0) \\
q_{ij}(1)
&= K \cdot l_j(1) \displaystyle \prod_{i^{'} \in {\rm ne}(x_j) \backslash f_i} r_{i^{'}j}(1) \\
r_{ij}(0)
&= K' \cdot \displaystyle \sum_{x_{j^{'}} \in {\rm ne}(f_i) \backslash x_j} f_i({\rm ne}(f_i) | x_j=0) \prod_{j^{'} \in {\rm ne}(f_i) \backslash x_j} q_{ij^{'}}(x_{j^{'}}) \\
r_{ij}(1)
&= K' \cdot \displaystyle \sum_{x_{j^{'}} \in {\rm ne}(f_i) \backslash x_j} f_i({\rm ne}(f_i) | x_j=1) \prod_{j^{'} \in {\rm ne}(f_i) \backslash x_j} q_{ij^{'}}(x_{j^{'}}) \\
\beta_{ij}
&= \log \left( \frac{q_{ij}(0)}{q_{ij}(1)} \right) \\
\alpha_{ij}
&= \log \left( \frac{r_{ij}(0)}{r_{ij}(1)} \right)
\end{aligned}
ここで以降の議論を補助するために、 0 と 1 で表現されるバイナリ文字列 \mathbf{b}_{1\times n} の j 文字目が 1 である確率を p_j とすると（ただし、互いに独立とする）、文字列のパリティが偶または奇となる確率に関して以下の等式が成立する。
\begin{aligned}
\Pr[b_1 \oplus b_2 \oplus \dotsb \oplus b_n = 0] = \dfrac{1}{2} + \dfrac{1}{2} \displaystyle \prod_{j=1}^{n} (1 - 2 p_j) \\
\Pr[b_1 \oplus b_2 \oplus \dotsb \oplus b_n = 1] = \dfrac{1}{2} - \dfrac{1}{2} \displaystyle \prod_{j=1}^{n} (1 - 2 p_j)
\end{aligned}
簡単な説明
n = 1 の場合、以下の通り成立する。
\begin{aligned}
{\rm Prob}[b_1 = 0] &= 1 - p_1 &= \dfrac{1}{2} + \dfrac{1}{2} (1 - 2 p_1) \\
{\rm Prob}[b_1 = 1] &= p_1 &= \dfrac{1}{2} - \dfrac{1}{2} (1 - 2 p_1)
\end{aligned}
次に、 n = k の場合、以下が成り立つと仮定する。
\begin{aligned}
{\rm Prob}[b_1 \oplus b_2 \oplus \dotsb \oplus b_k = 0] = \dfrac{1}{2} + \dfrac{1}{2} \displaystyle \prod_{j=1}^{k} (1 - 2 p_j) \\
{\rm Prob}[b_1 \oplus b_2 \oplus \dotsb \oplus b_k = 1] = \dfrac{1}{2} - \dfrac{1}{2} \displaystyle \prod_{j=1}^{k} (1 - 2 p_j)
\end{aligned}
また、 n=k + 1 のパリティは以下のように計算できる。
\begin{aligned}
b_1 \oplus b_2 \oplus \dotsb \oplus b_{k + 1} = 0 \iff
\begin{dcases}
b_1 \oplus b_2 \oplus \dotsb \oplus b_k = 0 \ \ {\rm and} \ \ b_{k + 1} = 0, & {\rm or} \\
b_1 \oplus b_2 \oplus \dotsb \oplus b_k = 1 \ \ {\rm and} \ \ b_{k + 1} = 1
\end{dcases} \\
b_1 \oplus b_2 \oplus \dotsb \oplus b_{k + 1} = 1 \iff
\begin{dcases}
b_1 \oplus b_2 \oplus \dotsb \oplus b_k = 0 \ \ {\rm and} \ \ b_{k + 1} = 1, & {\rm or} \\
b_1 \oplus b_2 \oplus \dotsb \oplus b_k = 1 \ \ {\rm and} \ \ b_{k + 1} = 0
\end{dcases}
\end{aligned}
よって、それぞれの確率は以下の通り。
\begin{aligned}
& \begin{split}
{\rm Prob}[b_1 \oplus b_2 \oplus \dotsb \oplus b_{k + 1} = 0] = {} & \biggl\{ \dfrac{1}{2} + \dfrac{1}{2} \displaystyle \prod_{j=1}^{k} (1 - 2 p_j) \biggr\} \cdot (1 - p_{k + 1}) \\
& + \biggl\{ \dfrac{1}{2} - \dfrac{1}{2} \displaystyle \prod_{j=1}^{k} (1 - 2 p_j) \biggr\} \cdot p_{k + 1}
\end{split} \\
& \begin{split}
{\rm Prob}[b_1 \oplus b_2 \oplus \dotsb \oplus b_{k + 1} = 1] = {} & \biggl\{ \dfrac{1}{2} + \dfrac{1}{2} \displaystyle \prod_{j=1}^{k} (1 - 2 p_j) \biggr\} \cdot p_{k + 1} \\
& + \biggl\{ \dfrac{1}{2} - \dfrac{1}{2} \displaystyle \prod_{j=1}^{k} (1 - 2 p_j) \biggr\} \cdot (1 - p_{k + 1})
\end{split}
\end{aligned}
上式を整理すると、 n=k が成り立つとき n=k + 1 でも成立することがわかる。以上のことから、どのような n に対しても成立する。 \blacksquare
検査ノード処理の議論に戻り、 f_i を x_j に関する各条件を満たすパリティチェックの式に展開する。
すると、検査ノード処理 r_{ij}(0) の計算は、 {\rm ne}(f_i) \backslash x_j のパリティが偶のときの積和計算になっている。同様に、 r_{ij}(1) の計算は、 {\rm ne}(f_i) \backslash x_j のパリティが奇のときの積和計算になっている。
式の整理のために確率 S_j を S_j = q_{ij}(x_j=1) として導入すると、先ほどの等式が使える。
\begin{aligned}
r_{ij}(0)
&= K' \cdot \displaystyle \sum_{x_{j^{'}} \in {\rm ne}(f_i) \backslash x_j} \mathbb{I}[x_1 \oplus \dotsb \oplus x_{j-1} \oplus x_{j+1} \oplus \dotsb \oplus x_n = 0] \prod_{j^{'} \in {\rm ne}(f_i) \backslash x_j} q_{ij^{'}}(x_{j^{'}}) \\
&= \Pr[x_1 \oplus \dotsb \oplus x_{j-1} \oplus x_{j+1} \oplus \dotsb \oplus x_n = 0] \\
&= \dfrac{1}{2} + \dfrac{1}{2} \displaystyle \prod_{j^{'} \in {\rm ne}(f_i) \backslash x_j}(1-2 S_{j^{'}}) \\
r_{ij}(1)
&= K' \cdot \displaystyle \sum_{x_{j^{'}} \in {\rm ne}(f_i) \backslash x_j} \mathbb{I}[x_1 \oplus \dotsb \oplus x_{j-1} \oplus x_{j+1} \oplus \dotsb \oplus x_n = 1] \prod_{j^{'} \in {\rm ne}(f_i) \backslash x_j} q_{ij^{'}}(x_{j^{'}}) \\
&= \Pr[x_1 \oplus \dotsb \oplus x_{j-1} \oplus x_{j+1} \oplus \dotsb \oplus x_n = 1] \\
&= \dfrac{1}{2} - \dfrac{1}{2} \displaystyle \prod_{j^{'} \in {\rm ne}(f_i) \backslash x_j}(1-2 S_{j^{'}})
\end{aligned}
さらに、確率 0 \le p \le 1 と \tanh 関数に関する以下の関係式がある。
\begin{aligned}
\tanh \biggl(\dfrac{1}{2}\log \dfrac{1 - p}{p} \biggr) = 1 - 2p
\end{aligned}
簡単な説明
まず、 x \ge 0 について以下が成立する。
\begin{aligned}
\begin{split}
\tanh \biggl(\dfrac{1}{2}\log x \biggr) &= \dfrac{e^{\log \sqrt{x}} - e^{-\log \sqrt{x}}}{e^{\log \sqrt{x}} + e^{-\log \sqrt{x}}} \\
&= \dfrac{\sqrt{x} - \dfrac{1}{\sqrt{x}}}{\sqrt{x} + \dfrac{1}{\sqrt{x}}} \\
&= \dfrac{x - 1}{x + 1}
\end{split}
\end{aligned}
よって、
\begin{aligned}
\begin{split}
\tanh \biggl(\dfrac{1}{2}\log \dfrac{1 - p}{p} \biggr) &= \dfrac{\dfrac{1 - p}{p} - 1}{\dfrac{1 - p}{p} + 1} \\
&= 1 - 2p
\end{split}
\end{aligned}
これを用いて、 r_{ij}(1) について整理すると、対数ドメインのsum-product復号法となる。
\begin{aligned}
1 - 2 r_{ij}(1)
&= \displaystyle \prod_{j^{'} \in {\rm ne}(f_i) \backslash x_j}(1-2 S_{j^{'}}) \\
\tanh \biggl(\dfrac{1}{2}\log \dfrac{r_{ij}(0)}{r_{ij}(1)} \biggr)
&= \displaystyle \prod_{j^{'} \in {\rm ne}(f_i) \backslash x_j}\tanh \biggl(\dfrac{1}{2}\log \dfrac{q_{ij^{'}}(0)}{q_{ij^{'}}(1)} \biggr)
\end{aligned}
\begin{aligned}
\alpha_{ij}
&= 2 \tanh^{-1} \left[
\displaystyle \prod_{j^{'} \in {\rm ne}(f_i) \backslash x_j}\tanh \biggl(\dfrac{1}{2} \beta_{ij^{'}} \biggr)
\right] \\
\beta_{ij}
&= \log \frac{l_j(0) \displaystyle \prod_{i^{'} \in {\rm ne}(x_j) \backslash f_i} r_{i^{'}j}(0)}{l_j(1) \displaystyle \prod_{i^{'} \in {\rm ne}(x_j) \backslash f_i} r_{i^{'}j}(1)} \\
&= L_j(0) + \displaystyle \sum_{i^{'} \in {\rm ne}(x_j) \backslash f_i} \alpha_{i^{'}j}
\end{aligned}
（ここまでの内容は、次の論文を参考にしました。）
https://www.jstage.jst.go.jp/article/itetr/25.81/0/25.81_39/_article/-char/ja/
(DOI https://doi.org/10.11485/itetr.25.81.0_39)
今回の勉強範囲はここまで。
３．４ 同時更新型sum-product復号
３．５ LDPC符号のパリティ検査行列
４．実用的なLDPC符号の設計
５．２元対称通信路での復号誤り率特性
６．むすび
Discussion