こんにちは、ぽたです。今回は情報理論の生成行列と検査行列について、そしてそれを用いての誤り訂正のやり方をわかりやすく説明してみようと思います！
ハミング符号とは
ハミング符号とは、ある整数ｍに対して、
で表されるものである。wikipedia参照
これだとわかりにくいので、よく聞く(7.4)ハミング符号にしてみましょう。m=3、を代入すると、n=7、k=4になる。この時を(7.4)ハミング符号といいます。もちろんm=4のときもあります。
この時の符号語を、
と表します。ｘは情報ビット、Cは検査ビットと呼ばれます。
何故これが利用されるかというと、
検査行列と生成行列を利用して間違いの訂正ができる
この１点に尽きると思います。間違いの訂正ができるというのは、データを送信する際に、誤って送ったり受け取ったりすることがあると思います。そういった場合に元のデータに戻すことができるということです。
検査行列と生成行列についてはのちに説明いたします。
検査行列とは
検査行列とは、基本的にHとして表される、ｍ行の行列をｎ列並べたもので、すべての列要素がゼロではなく、かつすべての列が違う行列です。
このままだとわかりにくいと思うので、例を表します。
先ほどの(7.4)ハミング符号のときを考えてみましょう。m=3、n=7なので、ベクトルがかぶらず、ゼロベクトルを入れないように考えると、
このようになります。この列ベクトルの順番に関しては様々なものがあります。今後出てくる生成行列を簡単に出したい場合は、検査行列の列を並び替えた、
このような形で考えるのをお勧めします。何が変わったかというと、ベクトルが右側に単位行列みたいなものを集めた形にしました。
また、これは、先ほどのハミング符号語と合わせると、
という式が成り立ちます。これを利用すると、先ほどCと置いていたハミング符号語がわかるようになります。最初の式、
こちらの行列を用いて、ハミング符号語のCを求めていきます。Hとｗに代入すると、
これを解くと、=０なので、方程式が出ます。
このように方程式がでてくるので、これをCについてとくと、この式は、2進数で考えるので、
となるので、ハミング符号語ｗは、
このようになることがわかります。したがって、ある検査行列と、xという情報ビットが与えられると、検査ビットも求まり、ハミング符号語もわかるということが理解できたと思います。
また、後ほど書きますが、検査行列というのは名前通り、検査するために利用する行列です。
生成行列とは
生成行列とは、符号理論における線形符号の基底であり、すべての符号語を生成する。wikipedia参照
これだと意味が分からないので、かみ砕きながら言うと、
先ほど説明したハミング符号語のすべてのパターンを、生成行列を利用すると作れる
ということです。先ほど作ったハミング符号語を利用して説明します。式にあらわすと、
これが成立するということです。ｘは列ベクトルで(7.4)ハミング符号の場合、長さが４です。長さは情報ビットの数に依存します。これの例として、先ほど求めたハミング符号語、
を利用して考えてみましょう。生成行列の式にｗとｘを代入すると、
Gは、４行×７列の行列です。このように置くと計算できそうに思えませんか？
ｗとｘの一行目は両方ともx1なので、x2の要素などはありません。したがって、Ｇの一列目一行目は「１」になりますよね。このように考えてみると、Ｇは、
となります。ｗの横とＧの縦の列の関係性が、下の図から見て取れると思います。
つまりハミング符号語というのは，Ｇとｘが決まれば一意に決めることができます。逆もしかりです。
また、検査行列Ｈがわかるとそこから生成行列を求めることもできます。
検査行列と生成行列の特殊な場合の関係性
特殊な場合の検査行列と生成行列の関係についてです。検査行列で簡単な形、
これを利用するのをお勧めすると書きましたが、これには訳があります。このように置くと生成行列を簡単に求めることができます。検査行列を、単位行列の部分とそうでない部分に分けます。それらをEとKとすると、
このように考えることができます。ここから生成行列を求めると、
このようになることが知られています。
Kの転置で考えることができる場合は、検査行列Hの右部分が単位行列の形になっていることが条件です。Gの単位行列の部分はKの転置の大きさに合わせましょう。
このように考えるのがわざわざ計算もせずに楽です。
もし、最初に検査行列が与えられていて、それが簡単にできる形ではない場合は、上の生成行列とは、の部分を参考にしてください。
ハミング符号における誤り訂正の仕方
それではハミング符号語の誤り訂正の仕方について説明します。
まず、ハミング符号の誤り訂正ができる数というのは、先に決まっています。(7 4)ハミング符号については、１ビットまでの誤りなら検出し、訂正することが可能です。
これに関しては別の記事で書こうと思うのでお待ちください。
それでは１ビットの誤りを含んでいるハミング符号語の訂正を行いたいと思います。やり方は、
①wHTを計算する。
②それをHTと比較する。
③ｗを誤り訂正する。
この順序です。一緒にやっていきましょう。
① wHTを計算する
一番最初に、検査行列
が与えられて、
の符号語訂正を行ってください、と問題があった場合、まずは先ほど言ったように、 wHT を計算します。もし間違っていなければ計算結果は０になるはずですよね。計算してみると、
最後の答えはもちろん２進数で答えてください。つまり１が奇数個だったら１、偶数個だったら0という形です。求まりましたね。それでは次のステップへ行きます。
②HTと比較する
HTと比較します。検査行列には面白い特徴があります。先ほど求めたベクトルｗHTとHTの行を比較すると、どこが間違っているかがわかるという特徴があります。文字だとわかりにくいと思うので、実際にやってみます。
上の通りです。①で計算したところ、wHT=(1,1,0)でしたよね。よって、ｗの２行目が間違っていることがわかります。それでは次が最後のステップです。
③ｗを誤り訂正する
誤り訂正を行います。今回は２行目が間違っていると②からわかったので、
間違っているハミング符号語
の２行目を訂正して、
となります。２行目が１→０になっています。これが最終的に求めたかった正しいハミング符号語です。
このように３ステップを踏むことによってハミング符号語を訂正することができます。
最後に
今回は、情報理論を勉強していると絶対に出てくるハミング符号の生成行列、検査行列に加えハミング符号語の訂正方法について説明しました。これでわかる人が一人でもいてくれると嬉しいです。
行列は少し難しい概念だと思いますが、頑張って乗り越えましょう！やっていることは結構簡単なことが多いです。情報理論に関しては、ほかにも記事にしているものがあります。ぜひ参考にしてみてください。
それではまた、ぽたでした。