Hamming, CRC, and Huffman

デジタル通信で送ったデータが途中でビット反転したらどうする？ 答えは「冗長ビットを足して、壊れたことを検出して、できれば直す」。ハミング符号とCRCはそのための技術。 ハフマン符号は逆に冗長性を削って圧縮する技術。やってることは正反対だけど、どっちも「ビット列をどう設計するか」の話。

ハミング距離

2つの符号語のうち、異なるビットの個数がハミング距離 $d$。

なぜこれが大事かというと、符号の最小ハミング距離が誤り訂正能力を決めるから。最小距離が $d$ のとき、訂正可能なビット誤りの数 $b$ は、

$$b = \left\lfloor \frac{d - 1}{2} \right\rfloor$$

$d = 3$ なら $b = 1$（1ビット誤り訂正可能）。直感的には、符号語 000 と 111 の距離が3なら、000 から1ビット壊れた 001 や 010 や 100 は 000 のほうが近い（距離1）から、元が 000 だったと復元できる。011 だと 000 からも 111 からも距離2で、どっちに訂正すればいいかわからない。だから $d = 3$ で訂正できるのは1ビットまで。

$d = 2$ だと $b = 0$ で、誤りの検出はできるけど訂正はできない。偶数パリティがまさにこれ。「壊れた」ことはわかるけど「どこが壊れた」かはわからない。

実用上のポイントとして、誤り訂正には距離が必要でそのぶん冗長ビットが増える。通信路の品質と冗長度のトレードオフがある。光ファイバーみたいに誤り率が低いチャネルではCRC（検出のみ、再送で対処）が合理的で、衛星通信や宇宙探査みたいに再送コストが高いチャネルでは誤り訂正符号が必須になる。

(7,4) ハミング符号

4ビットの情報ビット $x_1 x_2 x_3 x_4$ に3ビットのパリティ $C_1 C_2 C_3$ を付加して、7ビットの符号語を作る。

パリティビットの生成はmod 2演算（XOR）で、

$$C_1 = x_2 \oplus x_3 \oplus x_4, \qquad C_2 = x_1 \oplus x_3 \oplus x_4, \qquad C_3 = x_1 \oplus x_2 \oplus x_4$$

ここで重要なのは、各パリティビットがカバーする情報ビットの組み合わせが異なること。$C_1$ は $x_2, x_3, x_4$、$C_2$ は $x_1, x_3, x_4$、$C_3$ は $x_1, x_2, x_4$。$x_4$ は全部のパリティに含まれていて、$x_1$ は $C_2, C_3$ だけ、$x_2$ は $C_1, C_3$ だけ、$x_3$ は $C_1, C_2$ だけに含まれる。

この「どのパリティがどの情報ビットをカバーするか」のパターンが、実は2進数の1, 2, 3, ..., 7の列に対応している。$x_1$ の位置は3 (011)、$x_2$ は5 (101)、$x_3$ は6 (110)、$x_4$ は7 (111)。$C_1$ は位置1 (001)、$C_2$ は位置2 (010)、$C_3$ は位置4 (100)。各パリティビットは、自分の位置の2進表現でビットが立っている位置を全部XORする。ハミング符号がエレガントだと言われるのはこの構造のおかげ。

具体例をやってみよう。情報ビットが $x_1 x_2 x_3 x_4 = 1001$ のとき、

$$C_1 = 0 \oplus 0 \oplus 1 = 1, \quad C_2 = 1 \oplus 0 \oplus 1 = 0, \quad C_3 = 1 \oplus 0 \oplus 1 = 0$$

送信する符号語は 1001100。

これが伝送中に 1011010 になったとする（$x_3$ が 0 → 1 に反転）。受信側でシンドローム $S_1, S_2, S_3$ を計算する。

$$S_1 = x_2 \oplus x_3 \oplus x_4 \oplus C_1, \quad S_2 = x_1 \oplus x_3 \oplus x_4 \oplus C_2, \quad S_3 = x_1 \oplus x_2 \oplus x_4 \oplus C_3$$

受信データ 1011010 で計算すると、

$$S_1 = 0 \oplus 1 \oplus 1 \oplus 0 = 0, \quad S_2 = 1 \oplus 1 \oplus 1 \oplus 1 = 0, \quad S_3 = 1 \oplus 0 \oplus 1 \oplus 0 = 0$$

あれ、全部0？ これだとエラーなしの判定になる。例を見直すと……

ハミング距離が3ということは3箇所反転している。(7,4)ハミング符号は1ビット誤りしか訂正できないから、3ビット誤りだと訂正不能。1ビット誤りの例で再計算してみよう。

送信 1001100 の $x_3$ だけ反転して 1001100 → 1011100 になった場合、

$$S_1 = 0 \oplus 1 \oplus 1 \oplus 1 = 1, \quad S_2 = 1 \oplus 1 \oplus 1 \oplus 0 = 1, \quad S_3 = 1 \oplus 0 \oplus 1 \oplus 0 = 0$$

シンドロームは $(S_1, S_2, S_3) = (1, 1, 0)$。これを2進数として読むと 110 = 6。(7,4)ハミング符号の位置番号6は $x_3$。ビンゴ。$x_3$ を反転すれば訂正完了。

シンドロームが全部0なら誤りなし。1つ以上が1なら、シンドロームの2進値がエラー位置をそのまま指す。これが(7,4)ハミング符号の仕組み。デコードにAND/XORゲート数個で済むからハードウェア実装が極めて軽い。ECCメモリ（Error-Correcting Code memory）は(72,64)ハミング符号の拡張版で、64ビットのデータに8ビットのパリティを付加して1ビット誤り訂正・2ビット誤り検出（SECDED）を実現している。サーバのメモリに載ってるのがまさにこれ。

巡回冗長検査（CRC）

CRCはハミング符号より広く使われている誤り検出方式。データを多項式として扱って、生成多項式 $G(x)$ で割った余りを付加する。受信側で同じ割り算をして余りが0なら正常、0じゃなければ誤り。

情報信号 $I(x)$、生成多項式 $G(x)$（$n$ 次の既約多項式）として、送信信号 $W(x)$ は、

$$\hat{I}(x) = x^n \cdot I(x), \qquad R(x) = \hat{I}(x) \bmod G(x), \qquad W(x) = \hat{I}(x) + R(x)$$

$W(x)$ は $G(x)$ で割り切れるように設計されている。$x^n$ を掛けるのは、余り $R(x)$ を入れるスペースを末尾に確保するため。

具体例として $I(x) = x^2 + 1$（ビット列 101）、$G(x) = x^4 + x^2 + 1$（ビット列 10101）のとき、$\hat{I}(x) = x^6 + x^4$（1010000）。$R(x) = \hat{I}(x) \bmod G(x)$ をGF(2)上の多項式除算で計算して、

$$W(x) = x^6 + x^5 + x^4 + x^3 + x + 1$$

受信側で $Y(x) = W(x) / G(x)$ の余りが0なら正常。ビットが反転したら余りが変わるから検出できる。CRCは検出のみで訂正はしない。誤りを検出したら再送を要求する（ARQ: Automatic Repeat reQuest）。

CRC-32はEthernet、ZIP、PNGで使われていて、$G(x)$ は32次の多項式。バースト誤り（連続するビット誤り）の検出に強いのが特徴で、ランダム誤りだけじゃなくて通信路のノイズで起きやすいパターンの誤りにも対応できる。

ハフマン符号

ハフマン符号は出現頻度に基づく可変長符号。頻度の高いシンボルに短い符号を、低いシンボルに長い符号を割り当てる。アルゴリズムは、シンボルを生起確率の順に並べて、最も確率の小さい2つを結合して、結合したノードに0と1を割り当てる。これを繰り返す。

4種類のシンボルで確率が $P_S = 8/23$、$P_M = 7/23$、$P_L = 5/23$、$P_B = 3/23$ のとき、ハフマン木を構築すると $S \to$ 1（1ビット）、$M \to$ 01（2ビット）、$L \to$ 000（3ビット）、$B \to$ 001（3ビット）。

平均符号長は、

$$\bar{L} = 1 \times \frac{8}{23} + 2 \times \frac{7}{23} + 3 \times \frac{5}{23} + 3 \times \frac{3}{23} = \frac{8 + 14 + 15 + 9}{23} = \frac{46}{23} \approx 2.0$$

固定長だと $\lceil\log_2 4\rceil = 2$ ビット必要だから、この例ではほぼ同じ。でもシンボル数が多くて確率の偏りが大きいほど圧縮効率は上がる。理論的な下限はシャノンの情報エントロピー $H = -\sum p_i \log_2 p_i$ で、ハフマン符号はこの下限に最も近い瞬時復号可能な符号。JPEGのエントロピー符号化にも使われているし、ZIPもDeflateアルゴリズムの中でハフマン符号を使っている。