ハミング符号とは - 理数の散策路

ハミング符号とは、データの誤りを検出・訂正できる線型誤り訂正符号です。

ハミング距離

ハミング距離とは、２つの $n$ 桁の信号の差異を、$n$ 次元の超立方体の頂点間の距離として表したものです。 $n$ 桁（$n$ 次元）の信号を以下で表すと、

$${\bf x}=(x_1,x_2,\cdots,x_n)　,　x_i=1\,\mathrm{or}\,0$$

２つの信号 ${\bf x},{\bf y}$ のハミング距離 $d$ は以下で定義されます。

$$d({\bf x},{\bf y})=\sum_{i=1}^n|x_i-y_i|$$

このハミング距離は次のような性質を持ちます。

- $d({\bf x},{\bf y})\ge0$ 、$d({\bf x},{\bf x})=0$
- $d({\bf x},{\bf y})=d({\bf y},{\bf x})$
- $d({\bf x},{\bf y})+d({\bf y},{\bf z})\ge d({\bf x},{\bf z})$

送信信号 ${\bf x}$ に対し、受信信号 ${\bf x}’$ が最大 $r$ ビットでエラーが発生する場合、両者のハミング距離は、

$$d({\bf x},{\bf x}’)\le r$$

従って、任意の送信信号 ${\bf x},{\bf y}$ のハミング距離が①であれば、仮に $r$ ビットのエラーが発生しても元の受信信号を特定することができます。

$$d({\bf x},{\bf y})\ge 2r+1　　-①$$

ハミング符号では、$r=1$（エラーが１ビット）の場合を前提としています。

ハミング符号では、信号の桁数を $n$ 、情報信号の桁数を $m$ 、検査信号の桁数を $k$ とすると以下の関係があります。

$$n=2^k-1$$$$m=n-k$$

このとき、送信信号を $n$ 次元の列行列 ${\bf x}$ 、$1\sim2^k-1$ の値を表す $k$ 次元の列行列を $h_i$ とすると、ハミング符号の検査信号は以下の式が成り立つように定義されます。ここで $H$ は $k\times n$ の行列です。

$$H{\bf x}=0　　-②$$$$H\equiv(h_1\cdots h_i\cdots h_n)$$

$k=3$ の場合は、$n=7$ 、$m=4$ となります。$h_1=1,\cdots,h_7=7$ であるから、行列 $H$（３×７行列）は、

$$H=\left(\begin{array}{ccc}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array}\right)　　-③$$

４ビットの情報信号 $x_1\sim x_4$ と３ビットの検査信号 $c_1\sim c_3$ を以下のように並べて送信信号 ${\bf x}$ を定義し、

$${\bf x}=(c_1,c_2,x_1,c_3,x_2,x_3,x_4)^t$$

②を計算すると以下になります。これにより、情報信号から検査信号が求められます。

$$c_1=x_1+x_2+x_4$$$$c_2=x_1+x_3+x_4$$$$c_3=x_2+x_3+x_4$$

尚、このときの演算は、偶数を０、奇数を１で表すような以下の規則に従います。

これより、正と負、加算と減算は同じことになります。

$$1=-1$$$$x+x=0$$

受信信号でエラーが発生した場合は②が成り立たないこと、そしてエラーが起こったビットが特定（訂正）できることを示します。

任意の送信信号 ${\bf x},{\bf y}$ で②が成り立つ場合、

$$d({\bf x},{\bf y})\ge3$$

となることを示します。ハミング距離は平行移動しても変わらないため、${\bf x}+{\bf y}={\bf z}$ とすると、

$$d({\bf x},{\bf y})=d({\bf x}+{\bf x},{\bf y}+{\bf x})=d(0,{\bf z})\ge3　　-④$$

任意の送信信号 ${\bf z}$ に対し、④が成り立つことを示します。

$d(0,{\bf z})=1$ の場合
${\bf z}$ の１つのビットが１であるため、それを $i$ 番目として②を計算すると、③より、$$H{\bf z}=h_i\ne0$$
$d(0,{\bf z})=2$ の場合
${\bf z}$ の２つのビットが１であるため、それを $i$ 番目と $j$ 番目として②を計算すると、③と$h_i\ne h_j$ より、$$H{\bf z}=h_i+h_j\ne0$$

以上より、②が成り立つためには、ハミング距離が３以上である必要があります。