LDPCでDVC(2) - タンタン的思考

検査行列Hに対して，G Ht=0になるGを生成行列と言います．ただし，Htは検査行列Hの転地行列，GF(2)とします（要は足し算がXORとか，2で割った余りにだけ注目とか，0か1しかないとか）．このGの求め方がいまいち分からないのですが，ガウスの消去法でできます．

$H=\left(\begin{matrix}1&1&1&0&0\\1&0&1&1&0\\0&1&0&1&1\end{matrix}\right)$
とします．次に，(Ht E)を作ります．Eは単位行列です．
$HtE_0=\left(\begin{matrix}1&1&0&1&0&0&0&0\\1&0&1&0&1&0&0&0\\1&1&0&0&0&1&0&0\\0&1&1&0&0&0&1&0\\0&0&1&0&0&0&0&1\end{matrix}\right)$
となります．これをガウスの消去法で順番に整理していきます．まずは，1行1列目の1を残して，2行目以降の1を消します．このとき，GF(2)であることに注意．
$HtE_1=\left(\begin{matrix}1&1&0&1&0&0&0&0\\0&1&1&1&1&0&0&0\\0&0&0&1&0&1&0&0\\0&1&1&0&0&0&1&0\\0&0&1&0&0&0&0&1\end{matrix}\right)$
こうなります．次は2行2列目の1を残して，他の行にある2列目の1を消します．
$HtE_2=\left(\begin{matrix}1&0&1&0&1&0&0&0\\0&1&1&1&1&0&0&0\\0&0&0&1&0&1&0&0\\0&0&0&1&1&0&1&0\\0&0&1&0&0&0&0&1\end{matrix}\right)$
3行3列目は0ですので，行の交換を行います．3行3列目から下に見ていくと5行目に1があります．そこで，3行目と5行目を入れ替えます．
$HtE_3=\left(\begin{matrix}1&0&1&0&1&0&0&0\\0&1&1&1&1&0&0&0\\0&0&1&0&0&0&0&1\\0&0&0&1&1&0&1&0\\0&0&0&1&0&1&0&0\end{matrix}\right)$
3行3列目の1を残して，他の行にある3列目の1を消します．
$HtE_4=\left(\begin{matrix}1&0&0&0&1&0&0&1\\0&1&0&1&1&0&0&1\\0&0&1&0&0&0&0&1\\0&0&0&1&1&0&1&0\\0&0&0&1&0&1&0&0\end{matrix}\right)$
Htが3列しかないので，ここで終了です．行列のランクが実は3しかないことが分かります．そして，生成行列は4行目以下の右側に出来ています．
$G=\left(\begin{matrix}1&1&0&1&0\\1&0&1&0&0\end{matrix}\right)$
ですね．

これは，いわゆる基底行列だと思われます．また，上記の手順によってはことなる行列が生成されますが，どれも基底にかわりありません．なんでこんなまどろっこしい手順で説明したかと言いますと，上記の手順で実装すると出来た生成行列がキレイだからです．具体的には先日の図のようになります．

メッセージ列mに対して，mGを計算して符号語cを生成します．受信側でc'を受信したとします．面倒なのでc'=cとします．H ct（cの転地行列）を計算すると，H(mG)t=H Gt mt=G Ht mt=0となるはずです．c'をHc't=0になるように変更すれば正しいであろうcが得られます．Gの右側は単位行列になっているので，cが分かればmも自ずと分かります．

プログラムはこちら．例えば，

$ ldpc 15 3 2

と実行すれば，検査行列と生成行列が標準出力に出力されます．詳しくはソースを読んでください．構造体が面倒だったので，malloc後に変なことをしてます．

ところで，先日のレターの符号化率間違ってませんかね．生成行列の次元を考えると，もうちょっと符号化率が高いと思うんですけど．どうも，レターに出ているのはGFを考慮していないとき感じがします．生成行列なんて求めなくても，性能評価は出来ますからね．もうちょっと確信が持てればメールしてみようかしら．

というわけで，次回はsum-productアルゴリズムの理解です．これは論文通りに実装すれば良いだけかな・・・．

追記：和田山先生のウェブサイトが復活しているorz 1週間前は見られなかったので，自作していたのに．んー，理解が激しく深まるのは良いのですが，なんだか無駄なことをしているなぁ，私．