ハミング符号をわかりやすく解説

1. home
2. others

: 2024年3月7日 : 2024年3月7日 ハミングコートチェックとは、情報の誤りを検出するのみではなく、誤りの訂正ができるという手法の一つである。ハミングコードにおいては排他的論理和というものが使用されており、この回路を用いると情報を完全に復元することができる。排他的論理和を用いて、入力がA、B、出力がYの表を書くと、 となる。この表をよく見ると一つの行において、二つの値が決まればもう一つの値も特定できるという特徴がある。つまり、二つのビット列を送信するとき、排他的論理和によって生成されたビット列を付加することで、どれか一つのビット列が破損していたとしてもデータを復元することができる。これに対し、例えば論理和などはその誤りを特定することができない。以下に論理和の入出力の関係を示すと、 となる。ビット列、0011と0101を送信することを考える。この時、論理和は0111となる。ここで、0101のビット列がすべて破損してしまったとする。つまり、 となり、Bの列がわからない状態である。b_3とb_4に関しては0と1の可能性が存在し、ビット列を完全に復元することができないとわかる。 一般にハミング符号は自然数$m$に対し \[ 符号長 : n = 2^m -1\\ 情報数 : k = n -m \] という値が設定される。ここで、符号長とは生成される符号のビット数であり、情報数は元のデータのビット数である。なので、元のデータのビット数が$k$のデータを送信するならば、 \[ k = 2^m -1 - m \] を満たすmをを求めればよい。今回の説明においては、m=3の時、つまりn=7,k=4 となるような(7,4)ハミング符号について取り扱う。以下、演算子+は排他的論理和を表すとする。 例えば、1+1 = 0であり、1+1+1=1となる。これは1が偶数個なら0、1が奇数個ならば1を返すと考えてもよい。
簡単に手順を先に述べると、

• 送信したいビット列\(\boldsymbol{x}\)の後ろにビットを追加し、ハミング符号\(\boldsymbol{w}\)を生成
• ハミング符号\(\boldsymbol{w}\)から生成行列\(\boldsymbol{G}\)を作成
• 生成行列\(\boldsymbol{G}\)から検査行列\(\boldsymbol{H}^T\)を作成 (検査行列を作成してから生成行列を作成することもできるが、今回は生成行列から検査行列を作成する方法を説明する)
• ハミング符号\(\boldsymbol{w}\)を送信 (どのように(\boldsymbol{w}\)を構成するかあらかじめ決めているのであれば、受信側でも\(\boldsymbol{H}^T\)は作成できるので送らなくてもよい)
• 受信側で誤りが存在すれば誤り訂正

今、送りたいビット列を\(\boldsymbol{x}=(x_1,x_2,x_3,x_4)\)とする。(7,4)符号の符号語\(\boldsymbol{w}\)を \[ \boldsymbol{w} = (x_1,x_2,x_3,x_4, x_1+x_2+x_3, x_1+x_2+x_4, x_2+x_3+x_4) \] とする。5列目以降のビット列の置き方には\((x_1,x_2,x_3,x_4)\)から3個の組み合わせを3通り選び、それぞれの和（繰り返しになるが、「和」は排他的論理和とする。）を追加する。この方法による選び方は(7,4)ハミング符合の時のみであり、一般的な形は後述する。生成行列\(\boldsymbol{G}\)は\(\boldsymbol{w}\) = \(\boldsymbol{xG}\)となる行列なので、\ \[ \boldsymbol{G}=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ \end{pmatrix} \] と書ける。つまり、\(\boldsymbol{x}\)対し、\(\boldsymbol{G}\)を右からかけることで、送信する符号語が生成されるような行列\(\boldsymbol{G}\)を生成行列と呼ぶ。 検査行列\(\boldsymbol{H}\)とは全ての列要素が0でなく、全ての列が異なり、生成行列\(\boldsymbol{G}\)に対し、\(\boldsymbol{GH}^T\)=\(\boldsymbol{0}\)となるような行列である。上述した\(\boldsymbol{G}\)に対応する\(\boldsymbol{H}^T\)は \[ \boldsymbol{H}^T=\begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \\ \end{pmatrix} \] となる。この検査行列は機械的に作成することができ、以下にその説明の画像を示す。 このとき、行列計算機などで\(\boldsymbol{GH}^T\)を計算すると、\(\boldsymbol{0}\)になることが確認できる。さらに、繰り返しとなるが、+演算は排他的論理和と考えるので、一般の行列計算機を使用すると結果は\(\boldsymbol{0}\)と表示されないこともあるが、結果の行列の要素は全て偶数になるはずであり、1を足す回数が偶数回であったということを意味するので、排他的論理をを考えれば結果は\(\boldsymbol{0}\)となる。 誤り訂正の方法を箇条書きで記述すると、

• \(\boldsymbol{wH}^T\)=\(\boldsymbol{0}\) となっているか確認する
• \(\boldsymbol{0}\)でなければ、\(\boldsymbol{H}^T\)と比較する
• 対応するビットを反転させる

\(\boldsymbol{G}\)と\(\boldsymbol{H}\)の定義より、\(\boldsymbol{wH}^T\)=\(\boldsymbol{xGH}^T\)=\(\boldsymbol{0}\)となるはずなので、そうでなければどこかに誤りが生じたと判断することができる。例えば、送信する側が\((1,1,0,1)\)を送信しようと考え、ハミング符合\((1,1,0,1,0,1,0)\)を送信したとする。しかし誤りが発生し、ハミング符合として\((1,1,1,1,0,1,0)\)を受信し、\(\boldsymbol{wH}^T\)=\((1,0,1)\)となったとする。この値が\(\boldsymbol{H}^T\)のうち、どの行と一致しているかを調べる \[ \boldsymbol{H}^T=\begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \\ \end{pmatrix} \] \((1,0,1)\)は\(\boldsymbol{H}^T\)の3行目に一致しているので送信された符号の3列目が間違っていると判断できる \[ \boldsymbol{w}= (1,1,1,1,0,1,0) \\ ↓ \quad \quad 3列目の0が1へ\\ \boldsymbol{w} = (1,1,0,1,0,1,0) \\ \] このように判定できる理由は、排他的論理和の性質を考えれば理解することができる。 \[ \boldsymbol{w} \boldsymbol{H}^T=(1,1,1,1,0,1,0) \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \\ \end{pmatrix}\\ =(1,0,1) \] 計算の結果、上述のようになるということは、\((1,0,1)\)の一列目と三列目は演算される1の数が1回分多い(少ない)ということがわかり、二列目が0ということは演算される1の回数が適切であるということである。この時、\((1,1,1,1,0,1,0)\)の三列目を0にし、\((1,1,0,1,0,1,0)\)\(\boldsymbol{H}^T\)を計算すると、一列目において演算される1の数が1増加し、二列目に関しては変化せず、三列目は演算される1の数が1増加する。また、0から1に反転させるときも演算回数が変化する。よって、計算結果が\(\boldsymbol{H}^T\)の何行目かを調べ、この行数に従って符号の中のあるビットを反転させることにより、誤りを検出、訂正することができる。 上述した話を任意のmに対して利用できるように一般化する。まず、送りたいビット列を \[ \boldsymbol{x} = (x_1,x_2,x_3, \cdots ,x_k) \] とし、ハミング符合を定める前に、\(\boldsymbol{G}\)を定める。符号長nは2^m-1、情報数kはn-mとなり、生成行列\(\boldsymbol{G}\)はk次単位行列E_kと(k,m)行列\(\boldsymbol{A}\)を用いて \[ \boldsymbol{G} = [\boldsymbol{E_k},\boldsymbol{A}] \] と定義する。この時、\(\boldsymbol{A}\)の定義の仕方はmビットで表せる数のうち、全てが0か、1が一つのみの場合を除いたものを行として行列を構成する。例えばmが3の時、 \[ \boldsymbol{A}=\begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1\\ \end{pmatrix} \] となり、mが4の時、 \[ \boldsymbol{A}=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix} \] などととれる。この\(\boldsymbol{A}\)の表し方は多義的であり、行を入れ替えても問題はない。そして、ここで\(\boldsymbol{w}\) = \(\boldsymbol{xG}\)としてハミング符号\(\boldsymbol{w}\)を定義する。(7,4)ハミング符号は説明の都合上先に\(\boldsymbol{w}\)を定義したが、\(\boldsymbol{G}\)を定義してから\(\boldsymbol{w}\)を生成する方が、任意のmに対して容易である。 生成行列は、m次単位行列をE_mをとすると、 \[ \boldsymbol{H}=[\boldsymbol{A^T},\boldsymbol{E_m}] \] と書ける。そして、受信側で受信したデータ\(\boldsymbol{w}\)に対し、\(\boldsymbol{wH}^T\)=\(\boldsymbol{0}\)となるかを確認し、上述した方法で誤りの検出、訂正を行えば良い。

• 講義「情報理論」第１２回通信路符号化法(1)
• 講義「情報理論」第１３回通信路符号化法(2)
• ハミング符合の生成行列と検査行列の意味の理解