通信や記憶装置では、ノイズや劣化により送受信データにビット誤りが生じます。誤り訂正符号（error-correcting code）は、冗長ビットを追加することで、受信側がビット誤りを検出・訂正できるようにする技術です。
リチャード・ハミングが1950年に考案したハミング符号（Hamming code）は、1ビット誤りを自動的に訂正できる最もシンプルかつ美しい線形符号であり、誤り訂正符号を学ぶ上で最良の出発点です。
本記事の内容
- 誤り検出と誤り訂正の違い
- ハミング距離の定義と性質
- 線形符号の基本（生成行列 $\bm{G}$ とパリティ検査行列 $\bm{H}$）
- ハミング符号 $(7,4)$ の構成と導出
- シンドローム復号の理論と手順
- シャノンの通信路符号化定理（第2定理）の概要
- Pythonでのスクラッチ実装
前提知識
この記事を読む前に、以下の概念を理解しておくと理解が深まります。
- 自己情報量とエントロピーの定義をわかりやすく解説
- 通信路容量の定義と計算方法を解説
- 線形代数の基礎（行列積、GF(2)上の演算）
誤り検出と誤り訂正
基本概念
通信路を通してデータを送るとき、ノイズによりビットが反転する可能性があります。
- 誤り検出（error detection）: 受信データに誤りが存在するかどうかを判定する
- 誤り訂正（error correction）: 誤りの位置を特定し、正しいデータを復元する
最も単純な誤り検出はパリティビットです。データビット列の末尾にパリティビット（ビット列の XOR）を1つ追加すると、1ビット誤りを検出できます。しかし、パリティビットだけでは誤りの位置が分からず、訂正はできません。
例: パリティビット
4ビットのデータ $\bm{d} = (1, 0, 1, 1)$ に対して、パリティビットは
$$ p = d_1 \oplus d_2 \oplus d_3 \oplus d_4 = 1 \oplus 0 \oplus 1 \oplus 1 = 1 $$
送信するのは $(1, 0, 1, 1, 1)$ です。受信側ではすべてのビットの XOR が $0$ であれば誤りなし、$1$ であれば誤りありと判定します。
ハミング距離
定義
2つの2進系列 $\bm{x}, \bm{y} \in \{0,1\}^n$ のハミング距離は、対応するビットが異なる位置の数として定義されます。
$$ d_H(\bm{x}, \bm{y}) = \sum_{i=1}^{n} (x_i \oplus y_i) = |\{i : x_i \neq y_i\}| $$
ここで $\oplus$ はGF(2)上の加法（排他的論理和、XOR）です。
具体例
$$ d_H(1011001, 1101010) = 4 $$
（第2, 3, 5, 7ビットが異なる）
ハミング距離の性質
ハミング距離は距離の公理を満たします。
- 非負性: $d_H(\bm{x}, \bm{y}) \geq 0$, 等号は $\bm{x} = \bm{y}$ のとき
- 対称性: $d_H(\bm{x}, \bm{y}) = d_H(\bm{y}, \bm{x})$
- 三角不等式: $d_H(\bm{x}, \bm{z}) \leq d_H(\bm{x}, \bm{y}) + d_H(\bm{y}, \bm{z})$
ハミング重み
ベクトル $\bm{x}$ のハミング重みは、$\bm{0}$ からのハミング距離です。
$$ w_H(\bm{x}) = d_H(\bm{x}, \bm{0}) = |\{i : x_i \neq 0\}| $$
GF(2)上では $d_H(\bm{x}, \bm{y}) = w_H(\bm{x} \oplus \bm{y})$ が成り立ちます。
符号の最小距離と誤り訂正能力
符号 $\mathcal{C}$ の最小距離は
$$ d_{\min}(\mathcal{C}) = \min_{\bm{x}, \bm{y} \in \mathcal{C}, \bm{x} \neq \bm{y}} d_H(\bm{x}, \bm{y}) $$
定理: 最小距離 $d_{\min}$ の符号は
- $d_{\min} – 1$ 個以下のビット誤りを検出できる
- $\lfloor (d_{\min} – 1)/2 \rfloor$ 個以下のビット誤りを訂正できる
証明（訂正能力）: $t = \lfloor (d_{\min} – 1)/2 \rfloor$ とします。$t$ 個以下のビット誤りが生じた場合、受信語 $\bm{r}$ は真の符号語 $\bm{c}$ から距離 $t$ 以内にあります。$d_{\min} \geq 2t + 1$ であるため、他の任意の符号語 $\bm{c}’$ に対して
$$ d_H(\bm{r}, \bm{c}’) \geq d_H(\bm{c}, \bm{c}’) – d_H(\bm{c}, \bm{r}) \geq d_{\min} – t \geq t + 1 $$
三角不等式を使いました。したがって、$\bm{r}$ に最も近い符号語は一意に $\bm{c}$ であり、正しく訂正できます。 $\square$
線形符号の基本
線形符号の定義
$(n, k)$ 線形符号 $\mathcal{C}$ は、GF(2)（$\{0, 1\}$、演算は mod 2）上の $n$ 次元ベクトル空間の $k$ 次元部分空間です。
$n$ は符号長、$k$ は情報ビット数、$r = n – k$ は冗長ビット数（パリティビット数）です。符号化率は $R = k/n$ です。
生成行列
$k$ 個の情報ビット $\bm{d} = (d_1, \dots, d_k) \in \text{GF}(2)^k$ を $n$ ビットの符号語 $\bm{c} \in \text{GF}(2)^n$ に変換する行列を生成行列 $\bm{G}$ と呼びます。
$$ \bm{c} = \bm{d} \bm{G} $$
ここで $\bm{G}$ は $k \times n$ 行列です。組織符号（systematic code）の場合、
$$ \bm{G} = [\bm{I}_k \mid \bm{P}] $$
と書けます。$\bm{I}_k$ は $k \times k$ 単位行列、$\bm{P}$ は $k \times r$ のパリティ生成行列です。組織符号では、符号語の先頭 $k$ ビットが情報ビットそのものになります。
パリティ検査行列
パリティ検査行列 $\bm{H}$ は $r \times n$ の行列で、符号語 $\bm{c} \in \mathcal{C}$ に対して
$$ \bm{H} \bm{c}^T = \bm{0} $$
を満たします。組織符号の場合、
$$ \bm{H} = [\bm{P}^T \mid \bm{I}_r] $$
です。
生成行列とパリティ検査行列の関係:
$$ \bm{G} \bm{H}^T = \bm{0} $$
証明: $\bm{G} = [\bm{I}_k \mid \bm{P}]$, $\bm{H} = [\bm{P}^T \mid \bm{I}_r]$ のとき、
$$ \begin{align} \bm{G} \bm{H}^T &= [\bm{I}_k \mid \bm{P}] \begin{bmatrix} \bm{P} \\ \bm{I}_r \end{bmatrix} \\ &= \bm{I}_k \bm{P} + \bm{P} \bm{I}_r \\ &= \bm{P} + \bm{P} = \bm{0} \quad (\text{GF}(2)\text{上で } \bm{P} + \bm{P} = \bm{0}) \end{align} $$
$\square$
最小距離と $\bm{H}$ の関係
定理: 線形符号の最小距離は、$\bm{H}$ の列ベクトルのうち線形従属となる最小の列数に等しいです。
$$ d_{\min} = \min \{w_H(\bm{c}) : \bm{c} \in \mathcal{C}, \bm{c} \neq \bm{0}\} $$
線形符号では $d_H(\bm{x}, \bm{y}) = w_H(\bm{x} \oplus \bm{y})$ であり、$\bm{x} \oplus \bm{y} \in \mathcal{C}$（部分空間の性質）なので、最小距離は最小重みの非零符号語の重みに等しくなります。
ハミング符号 $(7, 4)$ の構成
設計方針
1ビット誤りを訂正するには $d_{\min} \geq 3$ が必要です（$\lfloor (3-1)/2 \rfloor = 1$）。
$r$ ビットのパリティビットで誤りの位置を特定するには、「誤りなし」を含めて $n + 1$ 通りの状態を区別する必要があります。
$$ 2^r \geq n + 1 = (k + r) + 1 $$
$k = 4$ のとき、$2^r \geq 4 + r + 1$ を満たす最小の $r$ は $r = 3$（$2^3 = 8 \geq 8$）です。したがって $n = 7$ となり、ハミング符号 $(7, 4)$ が得られます。
パリティ検査行列の構成
$\bm{H}$ の各列は GF(2) 上の非零の $r$-ビットベクトルとします。$r = 3$ のとき非零ベクトルは $2^3 – 1 = 7$ 個あり、これは $n = 7$ に一致します。
$$ \bm{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} $$
列を並べ替えて組織符号にします。列 1,2,4 がパリティビット、列 3,5,6,7 が情報ビットに対応させると、
$$ \bm{H} = [\bm{P}^T \mid \bm{I}_3] = \begin{bmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{bmatrix} $$
ここで
$$ \bm{P}^T = \begin{bmatrix} 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix}, \quad \bm{P} = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{bmatrix} $$
生成行列
$$ \bm{G} = [\bm{I}_4 \mid \bm{P}] = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix} $$
符号化の例
情報ビット $\bm{d} = (1, 0, 1, 1)$ を符号化します。
$$ \begin{align} \bm{c} &= \bm{d} \bm{G} \\ &= (1, 0, 1, 1) \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix} \end{align} $$
各成分を GF(2) 上で計算します。
$$ \begin{align} c_1 &= 1 \cdot 1 + 0 \cdot 0 + 1 \cdot 0 + 1 \cdot 0 = 1 \\ c_2 &= 1 \cdot 0 + 0 \cdot 1 + 1 \cdot 0 + 1 \cdot 0 = 0 \\ c_3 &= 1 \cdot 0 + 0 \cdot 0 + 1 \cdot 1 + 1 \cdot 0 = 1 \\ c_4 &= 1 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 + 1 \cdot 1 = 1 \\ c_5 &= 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 0 + 1 \cdot 1 = 0 \quad (\bmod 2) \\ c_6 &= 1 \cdot 0 + 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 = 0 \quad (\bmod 2) \\ c_7 &= 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 = 0 \quad (\bmod 2) \end{align} $$
$$ \bm{c} = (1, 0, 1, 1, 0, 0, 0) $$
先頭 4 ビット $(1, 0, 1, 1)$ が情報ビット、末尾 3 ビット $(0, 0, 0)$ がパリティビットです。
検算: $\bm{H}\bm{c}^T$ を計算すると $\bm{0}$ になることを確認できます。
シンドローム復号
シンドロームの定義
受信語を $\bm{r} = \bm{c} + \bm{e}$ とします。ここで $\bm{e}$ は誤りベクトル（誤りのあるビット位置が 1、それ以外が 0）です。
シンドロームは
$$ \bm{s} = \bm{H}\bm{r}^T = \bm{H}(\bm{c} + \bm{e})^T = \bm{H}\bm{c}^T + \bm{H}\bm{e}^T = \bm{H}\bm{e}^T $$
$\bm{c}$ は符号語なので $\bm{H}\bm{c}^T = \bm{0}$ です。シンドロームは誤りベクトルのみに依存し、送信された符号語には依存しません。
シンドローム復号の手順
- 受信語 $\bm{r}$ に対してシンドローム $\bm{s} = \bm{H}\bm{r}^T$ を計算します。
- $\bm{s} = \bm{0}$ なら誤りなしと判定します。
- $\bm{s} \neq \bm{0}$ なら、$\bm{s}$ が $\bm{H}$ の第 $j$ 列と一致する $j$ を見つけます。第 $j$ ビットに誤りがあると判定し、$r_j$ を反転させます。
ハミング符号 $(7,4)$ のシンドローム復号表
ハミング符号 $(7,4)$ では、$\bm{H}$ の列が $1$ から $7$ のすべての非零 3 ビットベクトルです。シンドロームが非零のとき、そのシンドロームに等しい $\bm{H}$ の列番号が誤りの位置を直接示します。
| シンドローム $\bm{s}$ | 誤り位置 |
|---|---|
| $(0,0,0)^T$ | なし |
| $(1,0,0)^T$ | 第5ビット |
| $(0,1,0)^T$ | 第6ビット |
| $(0,0,1)^T$ | 第7ビット |
| $(1,1,0)^T$ | 第1ビット |
| $(0,1,1)^T$ | 第3ビット |
| $(1,0,1)^T$ | 第2ビット |
| $(1,1,1)^T$ | 第4ビット |
復号の具体例
先ほどの符号語 $\bm{c} = (1,0,1,1,0,0,0)$ の第3ビットに誤りが生じた場合を考えます。
$$ \bm{r} = (1,0,0,1,0,0,0) \quad (\text{第3ビットが } 1 \to 0 \text{ に反転}) $$
シンドロームを計算します。
$$ \bm{s} = \bm{H}\bm{r}^T = \begin{bmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$
$$ \begin{align} s_1 &= 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 0 + 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 0 + 0 \cdot 0 = 0 \pmod{2} \\ s_2 &= 0 \cdot 1 + 1 \cdot 0 + 1 \cdot 0 + 1 \cdot 1 + 0 \cdot 0 + 1 \cdot 0 + 0 \cdot 0 = 1 \pmod{2} \\ s_3 &= 1 \cdot 1 + 1 \cdot 0 + 1 \cdot 0 + 0 \cdot 1 + 0 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 = 1 \pmod{2} \end{align} $$
$$ \bm{s} = (0, 1, 1)^T $$
シンドローム復号表より、$(0,1,1)^T$ は第3ビットの誤りを示します。第3ビットを反転して $\bm{r}’ = (1,0,1,1,0,0,0) = \bm{c}$ となり、正しく訂正できました。
シャノンの通信路符号化定理（第2定理）の概要
定理の主張
通信路容量を $C$、情報の伝送レートを $R$ とするとき、
$$ R < C $$
であれば、誤り確率をいくらでも小さくできる符号化方式が存在します。
逆に、$R > C$ のとき、どのような符号化方式を用いても誤り確率を 0 に近づけることはできません。
2元対称通信路（BSC）の場合
反転確率 $p$ の2元対称通信路の通信路容量は
$$ C = 1 – H_2(p) = 1 + p\log_2 p + (1-p)\log_2(1-p) $$
ここで $H_2(p) = -p\log_2 p – (1-p)\log_2(1-p)$ は2元エントロピー関数です。
例えば $p = 0.1$ なら $C \approx 0.531$ bit/use です。つまり符号化率 $R < 0.531$ ならば、十分長い符号を使えば信頼性の高い通信が可能です。
ハミング符号の位置づけ
ハミング符号 $(7,4)$ の符号化率は $R = 4/7 \approx 0.571$ です。BSC の $p$ によっては $R > C$ となり、ハミング符号だけでは十分な誤り訂正能力を達成できない場合があります。
シャノンの定理は「理論的な限界」を示すもので、実際にその限界に近い性能を達成する符号（ターボ符号、LDPC符号など）が後に開発されました。
Pythonでのスクラッチ実装
ハミング符号 $(7,4)$ の実装
import numpy as np
class HammingCode74:
"""ハミング符号(7,4)の実装"""
def __init__(self):
# パリティ生成行列 P (4x3)
self.P = np.array([
[1, 0, 1],
[1, 1, 1],
[0, 1, 1],
[1, 1, 0]
], dtype=int)
# 生成行列 G = [I4 | P] (4x7)
self.G = np.hstack([np.eye(4, dtype=int), self.P])
# パリティ検査行列 H = [P^T | I3] (3x7)
self.H = np.hstack([self.P.T, np.eye(3, dtype=int)])
print("生成行列 G:")
print(self.G)
print("\nパリティ検査行列 H:")
print(self.H)
# GH^T = 0 の検証
print(f"\nG @ H^T mod 2 = \n{self.G @ self.H.T % 2}")
def encode(self, data):
"""
4ビットの情報ビットを7ビットの符号語に符号化
data: shape (4,) or (N, 4)
"""
data = np.array(data, dtype=int)
if data.ndim == 1:
return (data @ self.G) % 2
return (data @ self.G) % 2
def syndrome(self, received):
"""シンドロームを計算"""
received = np.array(received, dtype=int)
if received.ndim == 1:
return (self.H @ received) % 2
return (self.H @ received.T).T % 2
def decode(self, received):
"""
7ビットの受信語を復号（1ビット誤り訂正）
"""
received = np.array(received, dtype=int).copy()
s = self.syndrome(received)
if received.ndim == 1:
if np.any(s):
# シンドロームがH の第j列と一致する位置を探す
for j in range(7):
if np.array_equal(s, self.H[:, j]):
received[j] ^= 1 # ビット反転
break
return received[:4] # 情報ビットを返す
# バッチ処理
decoded = []
for i in range(len(received)):
r = received[i].copy()
si = s[i]
if np.any(si):
for j in range(7):
if np.array_equal(si, self.H[:, j]):
r[j] ^= 1
break
decoded.append(r[:4])
return np.array(decoded)
# テスト
hamming = HammingCode74()
# 全16通りの情報ビットで符号化テスト
print("\n=== 符号化テスト ===")
for i in range(16):
data = np.array([(i >> 3) & 1, (i >> 2) & 1, (i >> 1) & 1, i & 1])
codeword = hamming.encode(data)
s = hamming.syndrome(codeword)
print(f"d={data} -> c={codeword}, syndrome={s}")
# 誤り訂正テスト
print("\n=== 誤り訂正テスト ===")
data = np.array([1, 0, 1, 1])
codeword = hamming.encode(data)
print(f"元データ: {data}")
print(f"符号語: {codeword}")
for error_pos in range(7):
# 各ビットに1ビット誤りを注入
received = codeword.copy()
received[error_pos] ^= 1
decoded = hamming.decode(received)
s = hamming.syndrome(received)
ok = "OK" if np.array_equal(decoded, data) else "NG"
print(f" 誤り位置{error_pos}: 受信={received}, "
f"syndrome={s}, 復号={decoded} [{ok}]")
2元対称通信路でのシミュレーション
import numpy as np
import matplotlib.pyplot as plt
class HammingCode74:
"""ハミング符号(7,4)"""
def __init__(self):
self.P = np.array([[1,0,1],[1,1,1],[0,1,1],[1,1,0]], dtype=int)
self.G = np.hstack([np.eye(4, dtype=int), self.P])
self.H = np.hstack([self.P.T, np.eye(3, dtype=int)])
def encode(self, data):
return (data @ self.G) % 2
def decode(self, received):
received = received.copy()
s = (self.H @ received.T) % 2 # (3, N)
for i in range(received.shape[0]):
si = s[:, i]
if np.any(si):
for j in range(7):
if np.array_equal(si, self.H[:, j]):
received[i, j] ^= 1
break
return received[:, :4]
def simulate_bsc(p_error, n_blocks=10000):
"""2元対称通信路でハミング符号のBER性能をシミュレーション"""
hamming = HammingCode74()
# ランダムな情報ビットを生成
data = np.random.randint(0, 2, size=(n_blocks, 4))
# 符号化
codewords = hamming.encode(data)
# BSC通信路（各ビットが確率pで反転）
errors = (np.random.random(codewords.shape) < p_error).astype(int)
received = (codewords + errors) % 2
# 復号
decoded = hamming.decode(received)
# ビット誤り率（BER）
ber_coded = np.mean(decoded != data)
# 符号化なしのBER
ber_uncoded = p_error
# ブロック誤り率
block_errors = np.any(decoded != data, axis=1)
bler = np.mean(block_errors)
return ber_uncoded, ber_coded, bler
# さまざまなビット誤り率でシミュレーション
p_errors = np.logspace(-3, -0.3, 30)
ber_uncoded_list = []
ber_coded_list = []
bler_list = []
np.random.seed(42)
for p in p_errors:
ber_u, ber_c, bler = simulate_bsc(p, n_blocks=50000)
ber_uncoded_list.append(ber_u)
ber_coded_list.append(max(ber_c, 1e-7)) # log表示用
bler_list.append(max(bler, 1e-7))
# 理論値: ハミング符号(7,4)の理論BER
# 1ビット誤り訂正可能なので、2ビット以上誤りがあると失敗
from scipy.special import comb
def theoretical_bler(p, n=7):
"""ブロック誤り率の理論値（2ビット以上の誤り）"""
return 1 - (1-p)**n - n*p*(1-p)**(n-1)
theory_bler = [theoretical_bler(p) for p in p_errors]
# 可視化
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
# 左: BER
ax = axes[0]
ax.semilogy(p_errors, ber_uncoded_list, 'r--', linewidth=2, label='Uncoded BER')
ax.semilogy(p_errors, ber_coded_list, 'b-o', linewidth=1.5,
markersize=4, label='Hamming(7,4) BER')
ax.set_xlabel('Channel bit error probability p', fontsize=12)
ax.set_ylabel('Bit Error Rate (BER)', fontsize=12)
ax.set_title('BER performance of Hamming(7,4)', fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3, which='both')
ax.set_xscale('log')
# 右: BLER（理論値と比較）
ax = axes[1]
ax.semilogy(p_errors, bler_list, 'b-o', linewidth=1.5,
markersize=4, label='Simulation BLER')
ax.semilogy(p_errors, theory_bler, 'r--', linewidth=2,
label='Theoretical BLER')
ax.set_xlabel('Channel bit error probability p', fontsize=12)
ax.set_ylabel('Block Error Rate (BLER)', fontsize=12)
ax.set_title('BLER of Hamming(7,4): simulation vs theory', fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3, which='both')
ax.set_xscale('log')
plt.tight_layout()
plt.show()
通信路容量と符号化率の関係
import numpy as np
import matplotlib.pyplot as plt
def binary_entropy(p):
"""2元エントロピー関数"""
if p == 0 or p == 1:
return 0
return -p * np.log2(p) - (1-p) * np.log2(1-p)
# BSCの通信路容量
p_range = np.linspace(0.001, 0.499, 200)
capacity = [1 - binary_entropy(p) for p in p_range]
fig, ax = plt.subplots(figsize=(10, 6))
# 通信路容量の曲線
ax.plot(p_range, capacity, 'b-', linewidth=2, label='BSC capacity C = 1 - H₂(p)')
# ハミング符号(7,4)の符号化率
R_hamming = 4/7
ax.axhline(R_hamming, color='red', linewidth=2, linestyle='--',
label=f'Hamming(7,4) rate R = {R_hamming:.3f}')
# 交点を見つける
from scipy.optimize import brentq
def capacity_minus_R(p):
return 1 - binary_entropy(p) - R_hamming
p_threshold = brentq(capacity_minus_R, 0.001, 0.499)
ax.axvline(p_threshold, color='green', linewidth=1.5, linestyle=':',
label=f'Threshold p = {p_threshold:.4f}')
ax.plot(p_threshold, R_hamming, 'go', markersize=10)
# R < C の領域を塗りつぶし
ax.fill_between(p_range, R_hamming, capacity,
where=[c > R_hamming for c in capacity],
alpha=0.15, color='green', label='R < C (reliable)')
ax.fill_between(p_range, R_hamming, capacity,
where=[c < R_hamming for c in capacity],
alpha=0.15, color='red', label='R > C (unreliable)')
ax.set_xlabel('Channel error probability p', fontsize=12)
ax.set_ylabel('Rate (bits/channel use)', fontsize=12)
ax.set_title("Shannon's channel coding theorem and Hamming(7,4)", fontsize=13)
ax.legend(fontsize=10, loc='upper right')
ax.grid(True, alpha=0.3)
ax.set_xlim(0, 0.5)
ax.set_ylim(0, 1.05)
plt.tight_layout()
plt.show()
print(f"ハミング符号(7,4)の符号化率: R = {R_hamming:.4f}")
print(f"BSCで R = C となる閾値: p = {p_threshold:.4f}")
print(f"p < {p_threshold:.4f} なら理論的に信頼性のある通信が可能")
まとめ
本記事では、誤り訂正符号の基礎をハミング符号 $(7,4)$ を中心に解説しました。
- ハミング距離: 2つのビット列が異なる位置の数。最小距離 $d_{\min}$ が誤り訂正能力を決定
- 線形符号: 生成行列 $\bm{G}$ で符号化、パリティ検査行列 $\bm{H}$ で誤り検出
- ハミング符号 $(7,4)$: $d_{\min} = 3$ で1ビット誤り訂正が可能な最もコンパクトな線形符号
- シンドローム復号: $\bm{s} = \bm{H}\bm{r}^T$ で誤り位置を特定し訂正
- 通信路符号化定理: 符号化率 $R < C$（通信路容量）であれば、誤り確率を限りなく 0 に近づけられる
ハミング符号は理論的に美しく理解しやすい符号ですが、1ビットしか訂正できないという限界があります。より強力な誤り訂正が必要な場合は、BCH符号、リード=ソロモン符号、ターボ符号、LDPC符号などが使われます。
次のステップとして、以下の記事も参考にしてください。