マエカワの備忘録的な何か

思い立ったが吉日

情報通信システム 其の十一 20170629

(7,4)ハミング符号の続き、いきます.

  \displaystyle \begin{cases}c_1&=&&i_1&+&i_2&+&i_3&&&\\c_2&=&&&&i_2&+&i_3&+&i_4&\\c_3&=&&i_1&+&i_2&+&&+&i_4&\end{cases}

こんな規則で検査記号が付加されることを思い出しとく.

シンドローム

 上の式を右辺を0にするように変形しましょう.

   \displaystyle \begin{cases}&i_1&+&i_2&+&i_3&&&+&c_1&&&&&&=&0\\&&&i_2&+&i_3&+&i_4&&&+&c_2&&&&=&0\\&i_1&+&i_2&+&&+&i_4&&&&&+&c_3&&=&0\end{cases}

  \displaystyle iとか \displaystyle cとかややこしいので、全部 \displaystyle x_jでおいてしまいましょう.

   \displaystyle \begin{cases}&x_1&+&x_2&+&x_3&&&+&x_5&&&&&&=&0\\&&&x_2&+&x_3&+&x_4&&&+&x_6&&&&=&0\\&x_1&+&x_2&+&&+&x_4&&&&&+&x_7&&=&0\end{cases}

 ここで、入力を \displaystyle \vec{y}=(x_1,x_2,x_3,x_4,x_5,x_6,x_7)、誤り率を \displaystyle \vec{e}=(e_1,e_2,e_3,e_4,e_5,e_6,e_7)とすると、誤りを持った入力符号は \displaystyle (x_1+e_1,x_2+e_2,x_3+e_3,x_4+e_4,x_5+e_5,x_6+e_6,x_7+e_7)となる.これを上に書いてある規則に代入すると、 \displaystyle x_jの和の部分は \displaystyle 0になるので

   \displaystyle \begin{cases}&e_1&+&e_2&+&e_3&&&+&e_5&&&&&&=&s_1\\&&&e_2&+&e_3&+&e_4&&&+&e_6&&&&=&s_2\\&e_1&+&e_2&+&&+&e_4&&&&&+&e_7&&=&s_3\end{cases}

 になる.この時の \displaystyle (s_1,s_2,s_3)のことをシンドロームといい、(7,4)ハミング符号では誤りが一つの時、この組み合わせが一意に決まることから、どこが誤っているのかが100%わかる.

生成行列

 単位行列と検査符号を決めるための規則

   \displaystyle \begin{cases}c_1&=&&i_1&+&i_2&+&i_3&&&\\c_2&=&&&&i_2&+&i_3&+&i_4&\\c_3&=&&i_1&+&i_2&+&&+&i_4&\end{cases}

 の転置行列(これを \displaystyle A^tとする)を横につなげたもの.(7,4)ハミング符号の生成行列は

   \displaystyle G=\left(\begin{array}{rrrrrrr}1&0&0&0&1&0&1\\0&1&0&0&1&1&1\\0&0&1&0&1&1&0\\0&0&0&1&0&1&1\end{array}\right)

 になる.次のように書いたほうがわかりやすい.

   \displaystyle \begin{eqnarray}G&=&\left(\begin{array}{rrrrrrrr}1&0&0&0&\vdots&1&0&1\\0&1&0&0&\vdots&1&1&1\\0&0&1&0&\vdots&1&1&0\\0&0&0&1&\vdots&0&1&1\end{array}\right)\\&=&\left(\begin{array}{rrr}E&\vdots& A^t\end{array}\right)\end{eqnarray}

検査行列

 結論からいきましょう.検査行列 \displaystyle H

   \displaystyle H=\left(\begin{array}{rrr}A&\vdots&E\end{array}\right)

 になる.(7,4)ハミング符号だと、

   \displaystyle H=\left(\begin{array}{rrrrrrrr}1&1&1&0&\vdots&1&0&0\\0&1&1&1&\vdots&0&1&0\\1&1&0&1&\vdots&0&0&1\end{array}\right)

ハミング距離

 同符号長の符号どうしを見比べ、値が違っているものの数のことを言う.例えば、 \displaystyle \vec{v}=(1,0,0,0,1,1) \displaystyle \vec{u}=(1,1,0,0,1,0)は第2要素と第6要素の値が違っているので、ハミング距離 \displaystyle d_H(\vec{v},\vec{u}) 2ということになる.

ハミング重み

 これは零ベクトルとのハミング距離のことをいう.つまり、符号に含まれる 1の数がそのままハミング重みになっている.例えば、 \displaystyle \vec{v}=(0,1,1,0,0,1,1)のハミング重み \displaystyle w_H(\vec{v}) 4ということになる.

符号の最小距離

 これはハミング距離の最小値 \displaystyle d_{min}のことをいう.符号語全体に対して計算する必要があるため、ちょっとめんどくさいかも….

線形符号の最小距離

 これは馬鹿正直に計算していくと大変なので、裏技を使う. \displaystyle \vec{0}以外の符号語のハミング重みの最小値と一致する.(7,4)ハミング符号を例に挙げるならば、この値は 3になる.


今回はここまで.用語の意味とかは覚えておく.

次回は符号間の距離を視覚的に見ていくことから始めていきます.