情報理論:ハミングコード

§1-2 of “Information Theory, Inference and Learning Algorithms”/David Mackay

ハードディスクの限界の続き

もしかして、繰り返しコーディングの欠点は、1ビットずつエンコードしていることではないだろうか?今度は、一度に複数のコードをエンコードする方法を考える。

(7,4)ハミングコード

このコーディングは、4次元から7次元への線型写像である。但し体はmod 2である。

$\mathbf{t}=\begin{pmatrix}1 0 0 0 \\0 1 0 0 \\0 0 1 0 \\0 0 0 1 \\1 1 1 0 \\0 1 1 1 \\1 0 1 1 \\\end{pmatrix}\mathbf{s}$

エンコード後、転送中(transmitted)にFlipが起こり、ノイズベクトルとの和が最終的に受け取られる(received)ベクトルである。

$\mathbf{r}=\mathbf{t}+\mathbf{n}$

(7,4)ハミングコードのメリットは、転送レートが良いことである。

4bitの情報を7bitで送れるので、効率は4/7=57%で、繰り返しコードより遥かに良い。

1bitだけFlipされている場合

では、(7,4)ハミングコードをデコードするにはどうすれば良いのだろうか?

それには、「今回Flipされたbitは1個以下である」という前提を置く必要がある。Flipレートfが<<1の場合はこれはほぼ正しい。このような過程を置くデコーダーを、「Maximum Likelihood Decoder」と呼ぶ。

もしFlipされたbitが1個であれば、7bitのうちどれがFlipされたのかを特定できれば、nが1通りに決まるから、rとnからtが求められる。

$\mathbf{t}=\mathbf{r}-\mathbf{n}=\mathbf{r} \oplus \mathbf{n}$

さらに、tからsへの写像は射影であるから、そのままで良い。

$s_i=t_i \quad (1 \leq i \leq 4)$

Flipされたbitを特定するには、以下のような写像を構成すれば良い。3次元空間zをsyndromeといい、7次元空間の基底uはunit vectorである。

$\mathbf{r} \to \mathbf{z} \to \mathbf{u}$

この操作z->uは、定義域を拡大して行列表現ができる。これなら容易にプログラミング可能になる。まずu->zは簡単に求められ、

$(1,0,0,0,0,0,0)^t \to (0,0,1)^t \\(0,1,0,0,0,0,0)^t \to (0,1,0)^t \\(0,0,1,0,0,0,0)^t \to (0,1,1)^t \\(0,0,0,1,0,0,0)^t \to (1,0,0)^t \\(0,0,0,0,1,0,0)^t \to (1,0,1)^t \\(0,0,0,0,0,1,0)^t \to (1,1,0)^t \\(0,0,0,0,0,0,1)^t \to (1,1,1)^t$

$\mathbf{z}=\begin{pmatrix}0 0 0 1 1 1 1 \\0 1 1 0 0 1 1 \\1 0 1 0 1 0 1 \\\end{pmatrix}\mathbf{u}$

この行列の行は、好きに並び替えても値域が変わらないから、恒等行列を前に出す形で定義するのが良い。

$\mathbf{z}=\begin{pmatrix}1 0 0 1 1 1 0 \\0 1 0 1 0 1 1 \\0 0 1 1 1 0 1 \\\end{pmatrix}\mathbf{u} = \mathbf{H} \mathbf{u}$

逆写像は存在しないが、単射であるから、zを与えられればuの元を一意に対応させられる。よって

$\mathbf{r} \to \mathbf{z} \to \mathbf{u}$

が構成できた。これがデコード写像である。

2bitだけFlipされている場合

この場合は、前提から漏れているだけでなく、「必ずエラー」になる。
最も被害が大きいのは、1bit目と2bit目がFlipされていた場合で、4番目がFlipしたと診断されてしまい、結果として1,2,4の3つのbitが反転されたベクトルにデコードされてしまう。
逆に、5,6がFlipされていた場合は2がFlipしたと診断され、1ビットの被害で済む場合もある。

線形写像であるので、2つのノイズベクトルn,mに対し、

$\mathbf{A}(\mathbf{n}+\mathbf{m})=\mathbf{An} + \mathbf{Am}$

体がmod2なので、An+Am(syndrome)のバリエーションは8種類しかない。対応表を作ると以下のようになり、直感に反して、「元信号ビット」と「パリティビット」に対して完全に対象であることがわかる。(0,0,1),(0,1,0),(0,1,1),(1,0,0)が元信号ビット、(1,0,1),(1,1,0),(1,1,1)がパリティビットである。

Am+An	例	条件を満たす2BitFlipの方法

$\begin{pmatrix}0 \\0 \\0 \\\end{pmatrix}=$

最低1つは一致しない要素が存在するため不可能

0通り

$\begin{pmatrix}0 \\0 \\1 \\\end{pmatrix}=$

$\begin{pmatrix}1 \\0 \\0 \\\end{pmatrix}\oplus\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}$

3通り

$\begin{pmatrix}0 \\1 \\0 \\\end{pmatrix}=$

$\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}\oplus\begin{pmatrix}1 \\1 \\1 \\\end{pmatrix}$

3通り

$\begin{pmatrix}1 \\0 \\0 \\\end{pmatrix}=$

$\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}\oplus\begin{pmatrix}0 \\0 \\1 \\\end{pmatrix}$

3通り

$\begin{pmatrix}0 \\1 \\1 \\\end{pmatrix}=$

$\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}\oplus\begin{pmatrix}1 \\1 \\0 \\\end{pmatrix}$

3通り

$\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}=$

$\begin{pmatrix}1 \\0 \\0 \\\end{pmatrix}\oplus\begin{pmatrix}0 \\0 \\1 \\\end{pmatrix}$

3通り

$\begin{pmatrix}1 \\1 \\0 \\\end{pmatrix}=$

$\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}\oplus\begin{pmatrix}0 \\1 \\1 \\\end{pmatrix}$

3通り

$\begin{pmatrix}1 \\1 \\1 \\\end{pmatrix}=$

$\begin{pmatrix}1 \\0 \\1 \\\end{pmatrix}\oplus\begin{pmatrix}0 \\1 \\0 \\\end{pmatrix}$

3通り

エラーレートの計算

転送レートは良いとしても、パフォーマンスはどうなのだろうか。エラーレートが高くなってしまっていては、転送レートが良くなっていても、パフォーマンスが高いとは限らない。

エラーレートには「ブロックエラー」と「ビットエラー」2種の評価方法がある。

Exercise 1.6.1

ブロックエラーは元信号の4bitのうち一つでも間違っていたらダメという考え方であり、2bit以上が同時に反転された場合は全てブロックエラーになる。よって、上記の表全てがアウトであり、

$\displaystyle\binom 7 2 f^2=21 f^2$

がleading termになる。

Exercise 1.6.2

ビットエラーはビット単位での正確さを表す。パリティビットは間違っていても正常にデコードできるので、s1,s2,s3,s4のエラー率を4で割って平均した数値である。hatは回帰などでも、伝統的に予測値(この場合はデコード値)を表す。

$\frac{1}{4} \displaystyle \sum_{i=1}^{4} P(s_1 \neq \hat{s_1})$

この値のleading termもまた、2bitが同時に反転された場合について計算すれば良い。21通り全てについて、エラーbit数を計算すれば良い。最大被害は先ほど書いた通り3bit、最小被害は1bitである。

実際に計算すると36bitとなり、これを4で割ってLeading Termは

$9 f^2$

である。しかし、上の表の対称性を利用して、単純に以下の式で求めることもできる。

$21 f^2 \cdot \displaystyle \frac{3}{7} = 9 f^2$