ハミング符号による誤り訂正を解説（数式付き）

Hamming(7,4) を符号化し、シンドロームを計算して各 1 ビット誤りを訂正し、SECDED へ拡張します。能力の限界を誇張せずにデコーダを検証する方法も説明します。

Denny

2026年5月7日読了まで約10分

Chalkboard feature illustration for “ハミング符号による誤り訂正を解説（数式付き）”

**要点：**Hamming(7,4) は 4 個のデータビットを 7 個の位置に配置します。3 つのパリティ検査により、各位置には一意なゼロ以外の 3 ビット列が割り当てられます。そのため 1 ビット反転が起こると、シンドロームはその位置の 2 進インデックスになります。デコーダはそのビットを反転して訂正できます。通常の Hamming(7,4) は 2 ビット誤りと一部の 1 ビット誤りを区別できませんが、全体パリティビットを加えれば、想定する誤り数の範囲内で SECDED に拡張できます。

パリティビットは奇数個の位置が変化したことを知らせられますが、どの位置かまでは特定できません。ハミングの構成では、複数のパリティ検査を重ね合わせます。失敗した検査のパターン、すなわち シンドローム がアドレスとして働きます。

この考え方が強力なのは、エンコーダ、検査器、訂正器のすべてを XOR ネットワークと復号論理で構成できるからです。同時に、厳格な境界もあります。拡張符号で検査を追加しない限り、よく知られた訂正規則は保護ブロック内の誤りが最大 1 個であることを仮定します。

ビット位置の割り当て

符号語の位置は 1 から番号付けし、2 のべき乗の位置にはパリティを置きます。

位置	1	2	3	4	5	6	7
役割	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
2 進インデックス	001	010	011	100	101	110	111

各パリティ検査は、位置の 2 進表現に含まれる 1 ビットに対応します。

$P_1$ はインデックスのビット 0 が 1 の位置、すなわち 1、3、5、7 をカバーします。
$P_2$ はインデックスのビット 1 が 1 の位置、すなわち 2、3、6、7 をカバーします。
$P_4$ はインデックスのビット 2 が 1 の位置、すなわち 4、5、6、7 をカバーします。

各位置には一意なゼロ以外の所属パターンがあります。たとえば位置 5 は $5=101_2$ なので、検査 1 と 4 に属します。

この 1 始まりの約束は便利なだけで、神秘的なものではありません。パリティ検査行列の列は、単に 1 から 7 の 2 進ラベルです。

偶数パリティによる符号化

各パリティビットは、その完全なカバー集合の XOR がゼロになるよう選びます。

P_1=D_1\oplus D_2\oplus D_4

P_2=D_1\oplus D_3\oplus D_4

P_4=D_2\oplus D_3\oplus D_4

この式により、符号は 組織符号 になります。元のデータは位置 3、5、6、7 に変わらず現れ、残りの位置をパリティが占めます。

期待する検査値を一貫して変えれば、奇数パリティも使えます。偶数パリティでは、すべての有効な符号語のシンドロームがゼロとなるため、線形代数による表現が特に直接的です。

符号化の例：データ 1011

次のように割り当てます。

D_1=1,\quad D_2=0,\quad D_3=1,\quad D_4=1

すると、次の通りです。

P_1=1\oplus0\oplus1=0

P_2=1\oplus1\oplus1=1

P_4=0\oplus1\oplus1=0

これらの値を 7 つの位置へ配置します。

位置	1	2	3	4	5	6	7
役割	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
ビット	0	1	1	0	0	1	1

位置 1 から位置 7 の順に読むと、符号語は次の通りです。

文献によっては、符号語を視覚的に逆方向で表記します。位置の約束を明示し、一貫して使う限り、計算は正しく保たれます。

シンドロームの計算

受信した位置を $R_1$ から $R_7$ とします。完全なパリティ検査を再計算します。

S_1=R_1\oplus R_3\oplus R_5\oplus R_7

S_2=R_2\oplus R_3\oplus R_6\oplus R_7

S_4=R_4\oplus R_5\oplus R_6\oplus R_7

シンドロームは次のように解釈します。

S=(S_4S_2S_1)_2

変化していない有効な符号語では $S=000$ です。ちょうど 1 つの位置 $i$ が反転すると、 $i$ をカバーする各検査が反転します。得られるシンドロームは、位置 $i$ に割り当てられた 2 進列です。

位置 5 の反転を訂正する

符号化した例の位置 5 を反転させます。

sent:     0 1 1 0 0 1 1
received: 0 1 1 0 1 1 1
position: 1 2 3 4 5 6 7

ここで、次のようになります。

S_1=0\oplus1\oplus1\oplus1=1

S_2=1\oplus1\oplus1\oplus1=0

S_4=0\oplus1\oplus1\oplus1=1

したがって、次の通りです。

S_4S_2S_1=101_2=5

1 誤りという仮定の下では、受信した位置 5 を反転します。訂正後の語は 0110011 に戻り、位置 3、5、6、7 からデータ 1011 が得られます。

パリティ位置の反転も同じように処理できます。位置 2 が変化した場合、シンドロームは 010 となり、訂正器は位置 2 を反転します。

行列表現

符号語ベクトルを

\mathbf r=[R_1\ R_2\ R_3\ R_4\ R_5\ R_6\ R_7]^T

とすると、パリティ検査行列の一例は次の通りです。

H= \begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}

シンドロームは次の通りです。

\mathbf s=H\mathbf r\pmod 2

H の列 $i$ は、 $i$ の 2 進表現であり、 $(S_1,S_2,S_4)^T$ の順に並べます。したがって、位置 $i$ にのみ 1 を持つ 1 ビット誤りベクトルは、正確に列 $i$ を返します。

この表現は、重なった円を暗記するよりもきれいに拡張できます。また、線形性も明確になります。有効な 2 つの符号語を XOR すると、別の有効な符号語になります。

通常のハミング符号が 2 ビット誤りを安全に訂正できない理由

Hamming(7,4) の最小ハミング距離は次の通りです。

d_{\min}=3

最小距離が $d_{\min}$ の符号は、次のことができます。

有効か無効かだけを判定するなら、最大 $d_{\min}-1$ 個の任意の誤りを検出する。
最も近い符号語を選ぶことで、最大 $\left\lfloor(d_{\min}-1)/2\right\rfloor$ 個の誤りを訂正する。

したがって Hamming(7,4) は 1 誤りを訂正できます。訂正を行わなければ、2 ビットの破損を「符号語ではない」として検出することもできます。しかし、ゼロ以外の 3 ビットシンドロームだけでは、それが 1 誤りによるものか、特定の 2 誤りによるものかを判断できません。

標準的な 1 誤りデコーダが 2 ビット誤りを受け取ると、2 つの誤り位置列の XOR は第 3 のゼロ以外の列になります。デコーダはその第 3 の位置を反転し、送信した符号語との差を 3 ビットにしてしまいます。これは 2 誤り訂正ではなく、誤訂正 です。

デコーダが仮定する誤りモデルは必ず明示してください。「シンドロームがゼロ以外ならその位置を反転する」という規則が有効なのは、システムが保護位置の誤りを最大 1 個と確立している場合だけです。

拡張ハミング符号と SECDED

7 ビットのハミング語全体にわたる全体パリティビット $P_0$ を追加します。8 ビットの拡張符号は $d_{\min}=4$ であり、符号語内の誤りが 2 個以下であると仮定すれば、1 誤り訂正・2 誤り検出（SECDED）をサポートします。

計算するものは次の通りです。

位置 1–7 から求める元の 3 ビットシンドローム S。
受信した 8 つの位置すべてに対する全体パリティ検査 P。

全体偶数パリティの場合は次のようになります。

シンドローム S	全体検査 P	0–2 誤りを仮定した解釈	操作
000	0	誤りなし	受理
nonzero	1	位置 1–7 の 1 誤り	位置 S を訂正
000	1	全体パリティ位置の誤り	パリティビット誤りを訂正または報告
nonzero	0	2 誤り	訂正不能として報告。1 誤り訂正を行わない

この限定は重要です。3 個以上の誤りは別の表の行をまねることがあります。SECDED は無制限の誤り検出器ではありません。

実際のメモリや通信システムでは、短縮ハミング符号、インターリーブ、シンボル指向符号、BCH 符号、Reed–Solomon 符号、低密度パリティ検査符号、積符号、または独自方式を使うことがあります。目に見えるデータ幅と検査ビット幅だけから、システムの ECC 能力を推測してはいけません。

一般的なハミング符号のサイズ

$m$ 個のデータビットと $r$ 個のハミングパリティビットでは、すべての符号語位置と誤りなしの場合に対するシンドロームパターンが十分に必要です。

2^r\ge m+r+1

完全長の 2 進ハミング符号族では、次の通りです。

n=2^r-1

k=n-r=2^r-r-1

パリティビット r	符号長 n	データビット k	完全符号
3	7	4	Hamming(7,4)
4	15	11	Hamming(15,11)
5	31	26	Hamming(31,26)
6	63	57	Hamming(63,57)

短縮版は検査構造を保ったまま選択したデータ位置を省きます。拡張版は全体パリティビットを追加し、距離を 3 から 4 に増やします。

オーバーヘッドは分母も明示する必要があります。Hamming(7,4) はデータ 4 ビットごとに検査ビットを 3 ビット追加します。これはペイロード比で 75% のオーバーヘッド、または送信語の 3/7 です。Hamming(63,57) は 6/57、すなわちペイロード比で約 10.5% を追加し、検査ビットは符号語の 6/63、約 9.5% を占めます。

ハードウェアアーキテクチャ

単純な組織符号の実装は、4 つの段階からなります。

data ─▶ parity generator ─▶ codeword
                              │
received word ─▶ check matrix ─▶ syndrome
                                      │
                       syndrome decoder ─▶ one-hot flip mask
received word ─────────────────────────── XOR ─▶ corrected word ─▶ extract data

Hamming(7,4) では次のようになります。

エンコーダは 3 つのパリティ式を計算します。
検査器は 3 つのシンドローム式を計算します。
3-to-8 デコーダは、0 番出力を訂正なしとして、ワンホット位置マスクを生成できます。
7 個の XOR ゲートがそのマスクを適用します。
配線が位置 3、5、6、7 を取り出します。

正確なゲート数とタイミングは、XOR ツリーの因数分解、共通項、セルライブラリ、FPGA へのマッピングに依存します。幅の広いデコーダでは、シンドローム計算と訂正をパイプライン化することがあります。「訂正済み」や「訂正不能」を示すフラグまたはステータスレジスタがある場合は、それらの信号を対応するデータのパイプライン段に整列させます。

検証計画

7 ビット符号の場合は、次の通りです。

16 通りすべてのデータ入力を符号化する。
符号化された各語のシンドロームがゼロであることを確認する。
各符号語について、7 個の位置をそれぞれ単独で反転する。
シンドロームが反転した位置と等しいことを確認する。
訂正を適用し、16×7 のすべてのケースで元のデータが復元されることを確認する。
代表的な 2 ビット誤りを注入し、通常の 1 誤りデコーダが誤訂正する理由を示す。

拡張 8 ビット版の場合は、次の通りです。

全体パリティ位置を含め、すべての単一位置テストを繰り返す。
各データ語に対し、すべての $\binom82=28$ 個の 2 位置パターンをテストする。
すべてのペアが訂正不能として報告され、1 誤りとして訂正されないことを確認する。
S != 0 かつ全体パリティ不一致の場合にのみ訂正が有効になるというアサーションを加える。

機能シミュレーションは、テストまたは網羅列挙したビットパターンに対して実装した真理値表を確認できます。しかし、物理的なソフトエラー率を与えたり、故障の独立性を確立したり、システムレベルの信頼性解析に取って代わったりはしません。

よくある設計ミス

位置を 0 から数えながら、シンドロームを 1 始まりのアドレスとして解釈する。
符号語を逆順で表記しているのに、その約束を記録しない。
偶数パリティの符号化と奇数パリティの検査を混在させる。
誤り数を制限せず、ゼロ以外のすべてのシンドロームを訂正する。
SECDED を重み 3 以上のすべての誤りを検出できるものとして扱う。
検査ビットと全体パリティビット自身も故障し得ることを忘れる。
分母が異なる「オーバーヘッド率」を比較する。
ECC と表示されたすべての製品が同じ符号を実装していると考える。

Hamming(7,4) が価値ある題材なのは、機構全体を見通せるからです。一意なパリティ検査列が 1 ビットの故障をアドレスに変えます。この点を理解すれば、通常のパリティは 1 行だけの検査行列に見え、より強力なブロック符号は同じ中心的な考え方を大きくしたものになります。すなわち、明示した故障モデルに構造化した冗長性を対応させるという考え方です。

参考文献

R. W. Hamming「Error Detecting and Error Correcting Codes」、Bell System Technical Journal、1950 年