1950年、ベル研究所の研究者リチャード・ハミング（Richard Hamming）は、ある苛立ちから歴史的な発明を生み出しました。当時のコンピュータはパンチカードで動いており、週末にリレー式計算機を走らせると、月曜日にはカードの読み取りエラーで計算が止まっていることがしばしばでした。「マシンはエラーを検出できるのに、なぜ自分で直せないのか？」——この素朴な問いが、ハミング符号（Hamming code）の発明につながりました。
ハミング符号は1ビットのエラーを自動的に訂正できる最も効率的な線形符号であり、完全符号（perfect code）という特別な性質を持っています。「完全」とは、エラー訂正のための冗長性に一切の無駄がなく、理論的な限界（ハミング限界）をぴったり達成するという意味です。数学的な美しさと実用性を兼ね備えた、符号理論の金字塔です。
ハミング符号を理解すると、以下のような分野に直結する知識が得られます。
- コンピュータメモリ: ECCメモリ（Error-Correcting Code memory）はハミング符号に基づいており、宇宙放射線（ソフトエラー）からデータを守っています
- 通信プロトコル: USB、イーサネット、Bluetoothのフレームチェックシーケンスはハミング符号の考え方の延長にあります
- 符号理論の基礎: ハミング符号は線形符号の構造を学ぶための最良の具体例であり、BCH符号やリード・ソロモン符号への橋渡しとなります
- 情報理論: 完全符号の存在（と非存在）は、球充填問題という深い数学的問題と結びついています
本記事の内容
- ハミング符号の構成原理 — 検査行列の驚くべき構造
- $[2^r – 1, 2^r – 1 – r, 3]$ ハミング符号のパラメータ
- シンドロームによるエラー位置の自動特定
- 完全符号とハミング限界の証明
- 拡大ハミング符号 — 2ビット検出への拡張
- 双対符号としてのシンプレックス符号
- Pythonによる実装と性能評価
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 線形符号の理論 — 生成行列と検査行列 — 線形符号の基本概念、生成行列、検査行列、シンドローム
- 交差エントロピーとKLダイバージェンスの関係 — 情報理論の基礎
ハミング符号の構成 — エレガントな検査行列
構成の核心的アイデア
ハミング符号の構成は驚くほどシンプルです。線形符号の理論で学んだように、線形符号は検査行列 $\bm{H}$ で定義されます。ハミング符号では、検査行列の列として $\mathbb{F}_2^r$ のゼロでないすべてのベクトルを並べるのです。
パラメータ $r \geq 2$ を固定します。$r$ ビットのゼロでないベクトルはちょうど $2^r – 1$ 個あります。これらを $\bm{H}$ の列として（適当な順序で）並べると、$r \times (2^r – 1)$ の検査行列が得られます。
$$ \bm{H} \in \mathbb{F}_2^{r \times (2^r – 1)} $$
この検査行列から定まる線形符号が$[n, k, d]$ ハミング符号です。パラメータは、
$$ n = 2^r – 1, \quad k = n – r = 2^r – 1 – r, \quad d_{\min} = 3 $$
符号長 $n$（符号語のビット数）は $2^r – 1$ 、情報ビット数 $k$ は $2^r – 1 – r$、最小距離は3です。
なぜ最小距離が3なのか
線形符号の理論で学んだ定理を思い出しましょう。「最小距離 $d_{\min}$ は、検査行列 $\bm{H}$ の中で線形従属となる列の最小個数に等しい」。
$\bm{H}$ の列は $\mathbb{F}_2^r$ のすべてのゼロでないベクトルです。
- 任意の1列はゼロでない: よって $d_{\min} \geq 2$
- 任意の2列は線形独立: もし $\bm{h}_i = \bm{h}_j$ なら同じベクトルが2回現れることになりますが、すべて異なるベクトルなので $\bm{h}_i \neq \bm{h}_j$。$\mathbb{F}_2$ では $\bm{h}_i + \bm{h}_j \neq \bm{0}$ であり線形独立です。よって $d_{\min} \geq 3$
- 線形従属な3列が存在する: 任意の2つの列 $\bm{h}_i, \bm{h}_j$ に対して、$\bm{h}_i + \bm{h}_j$ もゼロでないベクトルであるため、$\bm{H}$ のどこかの列 $\bm{h}_l$ に等しい。したがって $\bm{h}_i + \bm{h}_j + \bm{h}_l = \bm{0}$ であり、3列が線形従属です。よって $d_{\min} = 3$
最小距離 $d_{\min} = 3$ であるため、ハミング符号は $t = \lfloor (3-1)/2 \rfloor = 1$ ビットのエラーを訂正でき、$s = 3 – 1 = 2$ ビットのエラーを検出できます（ただし訂正と検出を同時に行うことはできません）。
代表的なパラメータ
| $r$ | $n = 2^r – 1$ | $k = n – r$ | 符号化率 $R = k/n$ | 訂正能力 |
|---|---|---|---|---|
| 2 | 3 | 1 | 0.333 | 1ビット |
| 3 | 7 | 4 | 0.571 | 1ビット |
| 4 | 15 | 11 | 0.733 | 1ビット |
| 5 | 31 | 26 | 0.839 | 1ビット |
| 6 | 63 | 57 | 0.905 | 1ビット |
| 7 | 127 | 120 | 0.945 | 1ビット |
$r$ が大きくなるほど符号化率 $R$ は1に近づきますが、訂正能力は常に1ビットです。符号長が長くなると「1ビットエラーの確率」自体は変わらないので、エラー密度に対する耐性は相対的に低下します。しかし、各7ビット（$r = 3$の場合）ごとに1ビットのエラーを確実に訂正できるという保証は実用上十分に有用です。
ハミング符号の構成を理解したところで、復号の仕組み——シンドロームによるエラー位置の自動特定——を見ていきましょう。
シンドロームによるエラー位置の特定
$[7, 4, 3]$ ハミング符号の具体例
最も小さな非自明なハミング符号である $[7, 4, 3]$ 符号（$r = 3$）を詳しく見ましょう。検査行列の列として、1から7までの整数の2進表現を並べます。
$$ \bm{H} = \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} $$
各列を確認しましょう。第1列は $(0, 0, 1)^T = 1_{10}$、第2列は $(0, 1, 0)^T = 2_{10}$、第3列は $(0, 1, 1)^T = 3_{10}$、…、第7列は $(1, 1, 1)^T = 7_{10}$ です。
この配置が復号において驚くべき効果を発揮します。
シンドロームの意味
受信語 $\bm{r} = \bm{c} + \bm{e}$ のシンドロームは $\bm{s} = \bm{r}\bm{H}^T = \bm{e}\bm{H}^T$ です（線形符号の理論参照）。
エラーなし（$\bm{e} = \bm{0}$）の場合: $\bm{s} = \bm{0}\bm{H}^T = \bm{0}$。シンドロームはゼロベクトルです。
$i$ 番目のビットに1ビットエラーがある場合: $\bm{e}$ は $i$ 番目の位置だけが1のベクトルなので、$\bm{s} = \bm{e}\bm{H}^T$ は $\bm{H}$ の $i$ 番目の列に等しくなります。
ここがハミング符号の最も巧妙な点です。$\bm{H}$ の各列が1から $n$ までの2進表現であるため、シンドロームの値（2進表現を10進数に変換したもの）がそのままエラー位置を示します。
具体例で確認しましょう。符号語 $\bm{c} = (1, 0, 1, 1, 0, 0, 0)$ を送信し、第5ビットにエラーが発生して $\bm{r} = (1, 0, 1, 1, 1, 0, 0)$ を受信したとします。
$$ \bm{s} = \bm{r}\bm{H}^T = (1, 0, 1)^T $$
$(1, 0, 1)_2 = 5_{10}$ なので、第5ビットにエラーがあると判定されます。第5ビットを反転させて $\hat{\bm{c}} = (1, 0, 1, 1, 0, 0, 0)$ を得ます。元の符号語が正しく復元されました。
この「シンドロームの値 = エラー位置」という性質は、$\bm{H}$ の列を1から $n$ の2進表現として配置したことの直接的な帰結であり、ハミング符号の復号が非常に単純かつ高速に行える理由です。
2ビットエラーの場合
$i$ 番目と $j$ 番目のビットにエラーがある場合、$\bm{s} = \bm{h}_i + \bm{h}_j$ です。この場合、シンドロームはゼロでも単一列でもない値を取ります。
$d_{\min} = 3$ のハミング符号は1ビットエラーしか訂正できないため、2ビットエラーが発生すると誤訂正が起こる可能性があります。シンドロームが $\bm{h}_l = \bm{h}_i + \bm{h}_j$ に一致するため、$l$ 番目のビットにエラーがあると誤って判定し、かえってエラーを増やしてしまいます。
この問題を解決するために、後述する拡大ハミング符号が使われます。
生成行列の構成
検査行列 $\bm{H}$ から生成行列 $\bm{G}$ を構成しましょう。$\bm{H}$ の列を並べ替えて $\bm{H} = [\bm{P}^T \mid \bm{I}_r]$ の形にすると（列の並べ替えは符号語のビットの順序を変えるだけ）、組織形式の生成行列は $\bm{G} = [\bm{I}_k \mid \bm{P}]$ で得られます。
$[7, 4, 3]$ 符号の場合、
$$ \bm{G} = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} $$
情報ビット $\bm{u} = (u_1, u_2, u_3, u_4)$ に対して、パリティビットは
$$ \begin{aligned} p_1 &= u_1 \oplus u_2 \oplus u_4 \\ p_2 &= u_1 \oplus u_3 \oplus u_4 \\ p_3 &= u_2 \oplus u_3 \oplus u_4 \end{aligned} $$
各パリティビットは、情報ビットの特定の組み合わせのXORです。これは偶数パリティ検査に他なりません。
シンドローム復号の仕組みを理解したところで、ハミング符号がなぜ「完全」なのかを厳密に証明しましょう。
完全符号とハミング限界
ハミング限界（球充填限界）
$\mathbb{F}_2^n$ の中に $M = 2^k$ 個の符号語を配置し、$t$ ビットのエラーを訂正したいとします。各符号語 $\bm{c}$ を中心とするハミング球
$$ B(\bm{c}, t) = \{\bm{v} \in \mathbb{F}_2^n : d(\bm{v}, \bm{c}) \leq t\} $$
は、$\bm{c}$ から距離 $t$ 以内のすべてのベクトルの集合です。$t$ ビットのエラーを訂正するためには、異なる符号語のハミング球が重なってはなりません。
ハミング球のサイズ（含まれるベクトルの個数）は、
$$ |B(\bm{c}, t)| = \sum_{i=0}^{t} \binom{n}{i} $$
距離がちょうど $i$ のベクトルは $\binom{n}{i}$ 個あります（$n$ ビットのうち $i$ ビットを反転させる選び方の数）。
$2^k$ 個の符号語のハミング球が重ならないための必要条件は、ハミング球の総サイズが空間全体 $2^n$ を超えないことです。
$$ 2^k \sum_{i=0}^{t} \binom{n}{i} \leq 2^n $$
これがハミング限界（Hamming bound）または球充填限界（sphere packing bound）です。
ハミング符号が完全符号である証明
ハミング限界で等号が成り立つ符号を完全符号（perfect code）と呼びます。ハミング符号が完全符号であることを証明しましょう。
ハミング符号のパラメータは $n = 2^r – 1$、$k = 2^r – 1 – r$、$t = 1$（1ビット訂正）です。ハミング限界の左辺を計算します。
$$ 2^k \sum_{i=0}^{1} \binom{n}{i} = 2^k (1 + n) = 2^{2^r – 1 – r} \cdot 2^r = 2^{2^r – 1} = 2^n $$
ここで $k + r = 2^r – 1 = n$ であること、および $1 + n = 1 + 2^r – 1 = 2^r$ を使いました。
$$ 2^k (1 + n) = 2^{n – r} \cdot 2^r = 2^n $$
ハミング限界で等号が成立しているため、ハミング符号は完全符号です。
完全符号の意味
完全符号であることの幾何学的な意味は深いです。$\mathbb{F}_2^n$ の全空間 $2^n$ 個のベクトルが、$2^k$ 個のハミング球によって隙間なく、重なりなく覆われることを意味します。すべてのベクトルは、ちょうど一つの符号語から距離1以内に位置しています。
換言すると、任意の $n$ ビットのベクトル $\bm{v}$ に対して、$d(\bm{v}, \bm{c}) \leq 1$ を満たす符号語 $\bm{c}$ がちょうど1つ存在します。1ビットのエラーは常に一意的かつ正確に訂正でき、余分な冗長性は一切ありません。
完全符号の分類定理
完全符号は非常に稀です。二元（$\mathbb{F}_2$）の完全符号は、以下のものに限られることが知られています（ティエットヴァイネンの定理、1973年）。
- 反復符号: $[n, 1, n]$（$n$ 奇数）。全ビットを繰り返すだけの自明な符号
- ハミング符号: $[2^r – 1, 2^r – 1 – r, 3]$（$r \geq 2$）
- ゴレイ符号: $[23, 12, 7]$。3ビットのエラーを訂正できる唯一の非自明な完全符号
この分類定理は、完全符号が数学的にいかに特殊な存在であるかを示しています。ハミング符号は「最も自然な」完全符号の無限族であり、符号理論において特別な位置を占めています。
完全符号の理論を理解したところで、実用上重要な拡張——拡大ハミング符号——を見ていきましょう。
拡大ハミング符号
2ビットエラー検出への拡張
先述のとおり、$[7, 4, 3]$ ハミング符号は1ビットエラーを訂正できますが、2ビットエラーを検出することはできません（2ビットエラーを1ビットエラーと誤認して誤訂正する）。
この問題を解決するのが拡大ハミング符号（extended Hamming code）です。ハミング符号語の末尾に全体パリティビットを追加します。全体パリティビットは、符号語のすべてのビットのXOR（偶数パリティ）です。
$$ c_{n+1} = c_1 \oplus c_2 \oplus \cdots \oplus c_n $$
これにより、パラメータは次のようになります。
$$ [n+1, k, 4] = [2^r, 2^r – 1 – r, 4] $$
最小距離が3から4に増加します。$d_{\min} = 4$ であるため、
- 1ビットのエラーを訂正し、かつ2ビットのエラーを検出（SECDED: Single Error Correction, Double Error Detection）
この動作を理解しましょう。
1ビットエラー: シンドローム $\bm{s} \neq \bm{0}$ かつ全体パリティが奇数（エラーあり）。シンドロームからエラー位置を特定して訂正。
2ビットエラー: シンドローム $\bm{s} \neq \bm{0}$ かつ全体パリティが偶数（ビットの反転が偶数個なので全体パリティは保存）。2ビットエラーが検出されるが、訂正は行わない。
エラーなし: シンドローム $\bm{s} = \bm{0}$ かつ全体パリティが偶数。
全体パリティビットが「1ビットエラーか2ビットエラーか」の区別を可能にしているのです。この追加コストは1ビットだけであり、実用上非常に価値のある拡張です。
ECCメモリでの応用
拡大ハミング符号の最も身近な応用がECCメモリ（Error-Correcting Code memory）です。
サーバーやワークステーションで使われるECC DDRメモリは、64ビットのデータに8ビットのECCビットを追加して72ビットとして格納します。これは $[72, 64, 4]$ 拡大ハミング符号（$r = 8$ に基づく）に対応しています。
宇宙放射線などによるソフトエラー（メモリセルの一時的なビット反転）は1ビットエラーとして現れることが多く、ECCメモリはこれを自動的に訂正します。2ビットの同時エラーは検出されてシステムに報告されます。
ECCメモリなしのPCでは、ソフトエラーは検出されずにデータ破損を引き起こす可能性があります。サーバーでECCメモリが必須とされる理由がここにあります。
双対符号 — シンプレックス符号
ハミング符号の双対
線形符号の理論で学んだように、$[n, k]$ 線形符号の双対符号は $[n, n-k]$ 線形符号です。ハミング符号 $[2^r – 1, 2^r – 1 – r]$ の双対符号は $[2^r – 1, r]$ 符号であり、シンプレックス符号（simplex code）と呼ばれます。
シンプレックス符号の生成行列は、ハミング符号の検査行列 $\bm{H}$ です。したがって、シンプレックス符号の符号語は $\bm{H}$ の行の全線形結合です。
シンプレックス符号の重要な性質は、すべての非ゼロ符号語のハミング重みが $2^{r-1}$ で等しいことです。このような符号を等重み符号（equidistant code, constant weight code）と呼びます。
等重み符号は符号分割多元接続（CDMA）やスプレッドスペクトラム通信で使われる拡散符号の設計に関連しています。シンプレックス符号から得られるウォルシュ・アダマール行列は、CDMAの直交拡散符号として広く使われています。
リード・マラー符号との関係
ハミング符号はリード・マラー符号（Reed-Muller code）とも密接に関連しています。$r$-次リード・マラー符号 $\mathrm{RM}(r, m)$ は、$m$ 変数の $r$ 次以下のブール多項式を符号語とする符号です。
1次リード・マラー符号 $\mathrm{RM}(1, m)$ はシンプレックス符号の拡大版であり、ハミング符号の双対の拡大版です。この関係は、符号理論における異なる構成法の間の深いつながりを示しています。
Pythonによる実装と性能評価
ハミング符号の構成と全パターンテスト
import numpy as np
import matplotlib.pyplot as plt
from scipy.special import comb
np.random.seed(42)
class HammingCode:
"""ハミング符号 [2^r - 1, 2^r - 1 - r, 3]"""
def __init__(self, r):
self.r = r
self.n = 2**r - 1
self.k = self.n - r
# 検査行列: 列は1からnの2進表現
self.H = np.zeros((r, self.n), dtype=int)
for i in range(1, self.n + 1):
for j in range(r):
self.H[j, i - 1] = (i >> j) & 1
# 組織形式への変換（ガウス消去法）
# 生成行列を構成
self._build_generator_matrix()
def _build_generator_matrix(self):
"""検査行列から組織形式の生成行列を構成"""
# Hを行簡約化してI_rの部分を右端に集める
H_sys = self.H.copy()
r = self.r
n = self.n
# ピボット列を追跡
pivot_cols = []
for row in range(r):
# ピボットを探す
for col in range(n):
if col in pivot_cols:
continue
if H_sys[row, col] == 1:
# この列をピボットに
pivot_cols.append(col)
# 他の行を消去
for other_row in range(r):
if other_row != row and H_sys[other_row, col] == 1:
H_sys[other_row] = np.mod(
H_sys[other_row] + H_sys[row], 2)
break
# 情報ビット位置とパリティ位置
self.parity_cols = sorted(pivot_cols)
self.info_cols = [c for c in range(n) if c not in self.parity_cols]
# 生成行列（非組織形式でも符号化可能）
# 簡易的に: 全情報語を列挙して符号語を生成
self.G = np.zeros((self.k, n), dtype=int)
# 情報ビット位置に単位行列
for i, col in enumerate(self.info_cols):
self.G[i, col] = 1
# パリティビットを計算: H @ c^T = 0 の条件から
# P = H_info^(-1) @ H_parity (GF(2)上)
H_info = self.H[:, self.info_cols]
H_parity = self.H[:, self.parity_cols]
# 情報ビットからパリティビットを計算する行列を求める
for i in range(self.k):
e = np.zeros(self.k, dtype=int)
e[i] = 1
# c の情報ビット位置に e を設定
c = np.zeros(n, dtype=int)
for j, col in enumerate(self.info_cols):
c[col] = e[j]
# シンドローム = H @ c^T
s = np.mod(self.H @ c, 2)
# パリティビットでシンドロームを0にする
# s + H_parity @ p = 0 => H_parity @ p = s
# ガウス消去法で解く
aug = np.hstack([H_parity.copy(), s.reshape(-1, 1)])
for row in range(self.r):
if aug[row, row] == 0:
for swap in range(row + 1, self.r):
if aug[swap, row] == 1:
aug[[row, swap]] = aug[[swap, row]]
break
for other in range(self.r):
if other != row and aug[other, row] == 1:
aug[other] = np.mod(aug[other] + aug[row], 2)
p = aug[:, -1]
for j, col in enumerate(self.parity_cols):
self.G[i, col] = p[j]
def encode(self, u):
"""情報語uを符号化"""
return np.mod(u @ self.G, 2)
def decode(self, r_vec):
"""シンドローム復号"""
s = np.mod(self.H @ r_vec, 2)
if np.all(s == 0):
return r_vec.copy(), 0 # エラーなし
# シンドロームの値がエラー位置（1-indexed → 0-indexed）
error_pos = 0
for j in range(self.r):
error_pos += s[j] * (2 ** j)
error_pos -= 1 # 0-indexed
if 0 <= error_pos < self.n:
corrected = r_vec.copy()
corrected[error_pos] ^= 1
return corrected, error_pos + 1
return r_vec.copy(), -1 # 訂正不能
def get_info_bits(self, codeword):
"""符号語から情報ビットを抽出"""
return codeword[self.info_cols]
# --- [7, 4, 3] ハミング符号のテスト ---
ham = HammingCode(3)
print(f"[{ham.n}, {ham.k}, 3] ハミング符号")
print(f"検査行列 H ({ham.r} x {ham.n}):")
print(ham.H)
print(f"\n生成行列 G ({ham.k} x {ham.n}):")
print(ham.G)
# G H^T = 0 の検証
print(f"\nG @ H^T (should be zero):")
print(np.mod(ham.G @ ham.H.T, 2))
# 全符号語の列挙と最小距離
print("\n=== 全符号語の重み分布 ===")
weight_dist = {}
for i in range(2 ** ham.k):
u = np.array([(i >> j) & 1 for j in range(ham.k)], dtype=int)
c = ham.encode(u)
w = np.sum(c)
weight_dist[w] = weight_dist.get(w, 0) + 1
print(f"重みスペクトル: {dict(sorted(weight_dist.items()))}")
d_min = min(w for w in weight_dist.keys() if w > 0)
print(f"最小距離: {d_min}")
# 1ビットエラーの完全訂正テスト
print("\n=== 1ビットエラー訂正の全パターンテスト ===")
n_correct = 0
n_total = 0
for i in range(2 ** ham.k):
u = np.array([(i >> j) & 1 for j in range(ham.k)], dtype=int)
c = ham.encode(u)
for pos in range(ham.n):
e = np.zeros(ham.n, dtype=int)
e[pos] = 1
r_vec = np.mod(c + e, 2)
decoded, _ = ham.decode(r_vec)
if np.array_equal(decoded, c):
n_correct += 1
n_total += 1
print(f"訂正成功率: {n_correct}/{n_total} = {n_correct/n_total:.6f}")
出力結果から、ハミング符号の以下の性質が確認できます。
- $\bm{G}\bm{H}^T = \bm{0}$: 生成行列と検査行列の直交性が成立しています。
- 最小距離 $d_{\min} = 3$: 重み0（ゼロ符号語）を除くと、最小の重みは3です。
- 1ビットエラーの訂正成功率 100%: 全16個の符号語に対する全7箇所のエラー位置（合計112パターン）すべてで正しく訂正されます。完全符号の性質の数値的な裏付けです。
BSCチャネルでのBER性能比較
異なるパラメータ $r$ のハミング符号のBER性能を比較します。
# BSCチャネルでのBERシミュレーション
p_range = np.linspace(0.001, 0.15, 30)
n_trials = 30000
# 複数のr値で比較
results = {}
for r_val in [3, 4, 5]:
ham_test = HammingCode(r_val)
ber_list = []
for p in p_range:
errors = 0
total = 0
for _ in range(n_trials):
u = np.random.randint(0, 2, ham_test.k)
c = ham_test.encode(u)
# BSCエラー
e = (np.random.random(ham_test.n) < p).astype(int)
r_vec = np.mod(c + e, 2)
decoded, _ = ham_test.decode(r_vec)
u_dec = ham_test.get_info_bits(decoded)
errors += np.sum(u_dec != u)
total += ham_test.k
ber_list.append(max(errors / total, 1e-7))
results[f'[{ham_test.n},{ham_test.k},3]'] = ber_list
# 未符号化BER
ber_uncoded = list(p_range)
# プロット
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# 左: BER性能
axes[0].semilogy(p_range, ber_uncoded, 'k--', linewidth=1.5, label='Uncoded')
colors = ['b', 'r', 'g']
for (name, ber), color in zip(results.items(), colors):
axes[0].semilogy(p_range, ber, f'{color}o-', markersize=3,
linewidth=1.5, label=name)
axes[0].set_xlabel('Channel error probability $p$')
axes[0].set_ylabel('BER')
axes[0].set_title('Hamming Code BER Performance on BSC')
axes[0].legend()
axes[0].grid(True, alpha=0.3)
# 右: ハミング限界と完全符号の幾何
# 球充填率の可視化
r_values = list(range(2, 11))
packing_ratios = []
for r_val in r_values:
n_val = 2**r_val - 1
k_val = n_val - r_val
sphere_size = 1 + n_val # sum_{i=0}^{1} C(n,i) = 1 + n
ratio = 2**k_val * sphere_size / 2**n_val
packing_ratios.append(ratio)
axes[1].bar(r_values, packing_ratios, color='steelblue', alpha=0.8)
axes[1].axhline(y=1.0, color='r', linestyle='--', linewidth=1.5,
label='Hamming bound (= 1.0 for perfect codes)')
axes[1].set_xlabel('Parameter $r$')
axes[1].set_ylabel('Packing ratio $2^k(1+n) / 2^n$')
axes[1].set_title('Sphere Packing Ratio (Perfect Code: ratio = 1)')
axes[1].legend()
axes[1].grid(True, alpha=0.3, axis='y')
axes[1].set_ylim(0, 1.2)
plt.tight_layout()
plt.show()
シミュレーション結果から、以下のことが読み取れます。
-
低エラー率での改善: すべてのハミング符号がチャネルエラー率 $p$ が低い領域で未符号化に比べてBERを大幅に改善しています。これは1ビットエラーの完全訂正が有効に機能している領域です。
-
符号長の効果: $r$ が大きい（符号長が長い）ほど、低エラー率での改善幅が大きくなります。これは符号化率 $R$ が高い（冗長性が相対的に少ない）ためです。しかし、高エラー率では符号長が長いほど2ビット以上のエラーが発生しやすくなり、性能が劣化します。
-
交差点の存在: ある $p$ の値で符号化ありと符号化なしのBER曲線が交差します。この交差点より高い $p$ では、符号化がかえって性能を悪化させます。これはシャノンの通信路符号化定理の限界を超えた領域に対応しています。
-
球充填率: 右のグラフでは、すべての $r$ に対して球充填率がちょうど1.0であることが確認されています。これがハミング符号が完全符号であることのグラフィカルな表現です。ハミング球が空間を隙間なく充填しています。
拡大ハミング符号（SECDED）の実装
class ExtendedHammingCode:
"""拡大ハミング符号 [2^r, 2^r - 1 - r, 4] (SECDED)"""
def __init__(self, r):
self.ham = HammingCode(r)
self.r = r
self.n = self.ham.n + 1 # 全体パリティビット追加
self.k = self.ham.k
def encode(self, u):
"""符号化（ハミング符号 + 全体パリティ）"""
c_ham = self.ham.encode(u)
overall_parity = np.sum(c_ham) % 2
return np.append(c_ham, overall_parity)
def decode(self, r_vec):
"""SECDED復号"""
r_ham = r_vec[:-1] # ハミング部分
received_parity = r_vec[-1]
# シンドローム計算（ハミング部分）
s = np.mod(self.ham.H @ r_ham, 2)
syndrome_zero = np.all(s == 0)
# 全体パリティ検査
overall_parity = np.sum(r_vec) % 2
parity_error = (overall_parity != 0)
if syndrome_zero and not parity_error:
# エラーなし
return r_vec.copy(), 'no_error'
elif not syndrome_zero and parity_error:
# 1ビットエラー → 訂正
error_pos = sum(s[j] * (2**j) for j in range(self.r)) - 1
corrected = r_vec.copy()
if 0 <= error_pos < self.ham.n:
corrected[error_pos] ^= 1
return corrected, 'corrected'
elif not syndrome_zero and not parity_error:
# 2ビットエラー → 検出のみ
return r_vec.copy(), 'detected_uncorrectable'
else:
# パリティビットのみのエラー
corrected = r_vec.copy()
corrected[-1] ^= 1
return corrected, 'parity_corrected'
# SECDED テスト
ext_ham = ExtendedHammingCode(3)
print(f"拡大ハミング符号 [{ext_ham.n}, {ext_ham.k}, 4] (SECDED)")
# テスト: 1ビットエラーの訂正と2ビットエラーの検出
u_test = np.array([1, 0, 1, 1])
c_test = ext_ham.encode(u_test)
print(f"\n情報語: {u_test}")
print(f"符号語: {c_test}")
# 1ビットエラー
for pos in range(ext_ham.n):
r_test = c_test.copy()
r_test[pos] ^= 1
decoded, status = ext_ham.decode(r_test)
assert status in ['corrected', 'parity_corrected'], \
f"1bit error at pos {pos}: {status}"
print("1ビットエラー: 全位置で正しく訂正されました")
# 2ビットエラー
n_detected = 0
n_2bit_total = 0
for i in range(ext_ham.n):
for j in range(i + 1, ext_ham.n):
r_test = c_test.copy()
r_test[i] ^= 1
r_test[j] ^= 1
decoded, status = ext_ham.decode(r_test)
n_2bit_total += 1
if status == 'detected_uncorrectable':
n_detected += 1
print(f"2ビットエラー: {n_detected}/{n_2bit_total} 検出 "
f"({n_detected/n_2bit_total:.1%})")
拡大ハミング符号のテスト結果から、SECDED（Single Error Correction, Double Error Detection）の動作が確認できます。1ビットエラーは全位置で正しく訂正され、2ビットエラーはすべて検出されます（ただし訂正は行わない）。ECCメモリではこの動作により、ソフトエラー（1ビット）の自動訂正とダブルビットエラーの検出・報告が実現されています。
まとめ
本記事では、ハミング符号の理論と実装について解説しました。
- エレガントな構成: 検査行列の列として $\mathbb{F}_2^r$ のすべてのゼロでないベクトルを並べるだけで、$[2^r – 1, 2^r – 1 – r, 3]$ 符号が得られる
- シンドロームの巧妙さ: 列を整数の2進表現として配置することで、シンドロームの値がそのままエラー位置を示す
- 完全符号: ハミング限界で等号が成り立ち、ハミング球が空間を隙間なく充填する。最小限の冗長性で最大限の訂正能力を実現する
- 拡大ハミング符号: 1ビットの全体パリティを追加するだけで $d_{\min} = 4$ を達成し、SECDEDが可能になる。ECCメモリの基盤技術
- 分類定理: 二元完全符号はハミング符号、ゴレイ符号、反復符号に限られるという深い数学的結果
ハミング符号は、符号理論の美しさと実用性の両立を体現する古典的な成果です。1950年にリチャード・ハミングがベル研究所で発表したこの符号は、世界初の実用的な誤り訂正符号であり、情報理論と符号理論の歴史における画期的な業績です。ハミングはパンチカードの読み取りエラーに悩まされた経験から、エラーを自動的に訂正する符号の開発を思い立ちました。70年以上経った今でも、ECCメモリ、QRコード、衛星通信などで広く使われています。ハミング符号の理解は、リード・ソロモン符号、BCH符号、ターボ符号、LDPC符号といった現代の高性能符号を学ぶための出発点でもあります。
次のステップとして、以下の記事も参考にしてください。
- 線形符号の理論 — 生成行列と検査行列 — ハミング符号の数学的基盤
- 畳み込み符号とビタビ復号の理論 — ブロック符号とは異なるアプローチ
- LDPC符号の理論 — スパースグラフ符号 — 現代の高性能符号。ハミング符号のスパース性のアイデアを大規模に拡張した手法
- ターボ符号の理論 — 反復復号と性能限界 — ハミング符号とは異なるアプローチでシャノン限界に迫る符号