デジタルデータを通信チャネルで伝送すると、ノイズや干渉によってビットが反転するエラーが不可避的に発生します。しかし、CDに多少の傷がついても音楽は正しく再生され、QRコードの一部が汚れていても読み取りは成功します。これらの「魔法」を支えているのが誤り訂正符号（error-correcting code）です。そして、誤り訂正符号の中で最も基本的かつ重要なクラスが線形符号（linear code）です。
線形符号が「基本的」である理由は、その名のとおり線形代数の道具を全面的に活用できる点にあります。符号語の集合が $\mathbb{F}_2^n$（2元体上の $n$ 次元ベクトル空間）の部分空間であるため、基底（生成行列）や零空間（検査行列）という馴染み深い概念で符号の構造を完全に記述できます。符号化は行列の積、エラー検出はシンドロームの計算——すべてが線形代数の範疇に収まるのです。
線形符号を理解すると、以下のような分野に直結する知識が得られます。
- 通信工学: 5G、Wi-Fi、衛星通信のすべてで誤り訂正符号が使われており、その大半が線形符号の枠組みに基づいています
- ストレージ: HDD、SSD、DVDのデータ保護にリード・ソロモン符号（線形符号の一種）が不可欠です
- 宇宙通信: 深宇宙探査機との通信では、極めて低い信号対雑音比のもとで信頼性の高い通信を実現するために強力な符号が必要です
- 量子情報: 量子誤り訂正符号（CSS符号やスタビライザー符号）は、古典的な線形符号を拡張したものです
- 暗号理論: マクエリス暗号系のように、線形符号の復号困難性を安全性の根拠とする暗号方式があります
本記事の内容
- 誤り訂正の基本的なアイデアと線形符号の定義
- 生成行列と検査行列の双対的な関係
- ハミング距離と最小距離 — 符号の誤り訂正能力の尺度
- シンドローム復号のアルゴリズム
- 符号の限界定理 — ハミング限界、シングルトン限界、ギルバート・ヴァーシャモフ限界
- 双対符号と線形符号の代数的構造
- Pythonによる線形符号の実装と性能評価
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 線形代数の基礎 — ベクトル空間、基底、行列の基本
- 交差エントロピーとKLダイバージェンスの関係 — 情報理論の基礎概念
誤り訂正の基本的なアイデア
なぜ冗長性が必要か
$k$ ビットの情報をそのまま通信チャネルに送ると、ビットが反転してもそれを検出すらできません。「0101」を送って「0111」を受け取ったとき、受信者にはエラーが起きたのかどうかを判定する手段がないのです。
この問題を解決する最も素朴な方法は反復符号（repetition code）です。各ビットを3回繰り返して送信します。「0」の代わりに「000」、「1」の代わりに「111」を送れば、1ビットのエラーが起きても多数決で正しいビットを復元できます。「010」を受け取ったら、多数決で「0」と判定すればよいのです。
しかし、反復符号は非常に非効率的です。1ビットの情報を送るのに3ビットが必要で、符号化率は $R = 1/3$ しかありません。もっと効率的に冗長性を追加する方法はないでしょうか。
その答えが線形符号です。線形符号は、$k$ ビットの情報に $n – k$ ビットの冗長ビットを「賢く」追加することで、最小限の冗長性で最大限のエラー訂正能力を実現します。その「賢さ」の核心が、線形代数に基づく体系的な構成です。
幾何学的な直感
$n$ ビットの空間 $\mathbb{F}_2^n = \{0, 1\}^n$ には $2^n$ 個のベクトルが存在します。その中から $2^k$ 個の点を符号語（codeword）として選びます。選んだ符号語たちが互いに「十分離れて」いれば、少数のビット反転が起きても最も近い正しい符号語を一意に特定でき、エラーを訂正できます。
「十分離れている」の度合いはハミング距離（Hamming distance）で測ります。2つのベクトルの間で異なるビットの個数がハミング距離です。たとえば、$d(0101, 0111) = 1$（1箇所異なる）、$d(0000, 1111) = 4$（4箇所異なる）です。
ハミング距離の直感を掴んだところで、線形符号の正式な定義に進みましょう。
線形符号の定義
$\mathbb{F}_2$ 上のベクトル空間
線形符号の舞台は2元体 $\mathbb{F}_2 = \{0, 1\}$ です。$\mathbb{F}_2$ では加算が $\text{mod}\, 2$（XOR）、乗算が通常の乗算で定義されます。
$$ 0 + 0 = 0, \quad 0 + 1 = 1, \quad 1 + 1 = 0 $$
$\mathbb{F}_2$ 上の $n$ 次元ベクトル空間 $\mathbb{F}_2^n$ は、$n$ ビットの全ベクトル $2^n$ 個からなります。通常の線形代数と同じ概念（基底、部分空間、線形独立、ランクなど）が $\mathbb{F}_2$ 上でも成り立ちますが、$1 + 1 = 0$（つまり $-1 = 1$）であることに注意が必要です。
定義
$[n, k]$ 線形符号 $C$ は、$\mathbb{F}_2^n$ の $k$ 次元部分空間です。
$$ C \subseteq \mathbb{F}_2^n, \quad \dim(C) = k, \quad |C| = 2^k $$
部分空間であるとは、以下の2つの条件を満たすことを意味します。
- ゼロベクトル $\bm{0}$ は $C$ に含まれる
- 任意の2つの符号語 $\bm{c}_1, \bm{c}_2 \in C$ に対して、$\bm{c}_1 + \bm{c}_2 \in C$（$\mathbb{F}_2$ 上の加算）
条件2は「任意の2つの符号語のXOR（ビットごとの排他的論理和）も符号語である」ことを意味します。この閉包性が線形符号の最も重要な性質であり、生成行列や検査行列といった線形代数的な構造を可能にします。
符号化率（code rate）は $R = k/n$ で定義されます。$R$ は「1ビットの符号ビットが運ぶ情報量」を表します。$R$ が1に近いほど効率的ですが、誤り訂正能力は低くなります。逆に $R$ が小さいほど冗長性が多く、誤り訂正能力が高くなります。
最小距離 $d$ も指定して $[n, k, d]$ 符号と表記することがあります。この3つのパラメータが線形符号の基本特性を完全に要約します。
生成行列による符号化
生成行列の定義
$k$ 次元部分空間 $C$ は $k$ 個の基底ベクトルで生成できます。これらの基底ベクトルを行として並べた $k \times n$ 行列 $\bm{G}$ を生成行列（generator matrix）と呼びます。
$$ \bm{G} = \begin{pmatrix} \bm{g}_1 \\ \bm{g}_2 \\ \vdots \\ \bm{g}_k \end{pmatrix} \in \mathbb{F}_2^{k \times n} $$
$\bm{g}_1, \bm{g}_2, \dots, \bm{g}_k$ は $C$ の基底（線形独立な $k$ 個の符号語）です。
符号化の操作
$k$ ビットの情報語 $\bm{u} = (u_1, u_2, \dots, u_k) \in \mathbb{F}_2^k$ を符号語 $\bm{c} \in C$ に変換する操作は、$\mathbb{F}_2$ 上の行列積で表されます。
$$ \bm{c} = \bm{u} \bm{G} \quad (\text{mod}\, 2) $$
$\bm{u}$ の各成分 $u_i$ が基底 $\bm{g}_i$ の係数であり、符号語は基底の線形結合です。
$$ \bm{c} = u_1 \bm{g}_1 + u_2 \bm{g}_2 + \cdots + u_k \bm{g}_k \quad (\text{mod}\, 2) $$
$\bm{u}$ は $2^k$ 通りの値を取りうるため、$C$ はちょうど $2^k$ 個の符号語を含みます。
組織形式の生成行列
生成行列には自由度（基底の選び方、行の入れ替え）があります。実用上重要なのが組織形式（systematic form）です。
$$ \bm{G} = [\bm{I}_k \mid \bm{P}] $$
ここで $\bm{I}_k$ は $k \times k$ の単位行列、$\bm{P}$ は $k \times (n-k)$ の行列です。この形式での符号化は、
$$ \bm{c} = \bm{u}[\bm{I}_k \mid \bm{P}] = (\bm{u} \mid \bm{u}\bm{P}) = (u_1, \dots, u_k, p_1, \dots, p_{n-k}) $$
符号語の最初の $k$ ビットが情報ビットそのもの（だから「組織的」= systematic）で、残りの $n – k$ ビットがパリティビット $\bm{p} = \bm{u}\bm{P}$ です。
組織形式の利点は、符号語から情報語を取り出すのが簡単（最初の $k$ ビットを読むだけ）であることです。任意の生成行列は行基本変形（ガウス消去法）で組織形式に変換できます。
具体例: $[7, 4]$ 符号
$[7, 4]$ 線形符号の生成行列の一例を見ましょう。
$$ \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} = (1, 0, 1, 1)$ を符号化すると、
$$ \bm{c} = (1, 0, 1, 1) \bm{G} = (1, 0, 1, 1, 0, 0, 0) \quad (\text{mod}\, 2) $$
検算: $c_5 = u_1 \oplus u_4 = 1 \oplus 1 = 0$、$c_6 = u_1 \oplus u_3 = 1 \oplus 1 = 0$、$c_7 = u_2 \oplus u_3 \oplus u_4 = 0 \oplus 1 \oplus 1 = 0$。符号語は $(1, 0, 1, 1, 0, 0, 0)$ です。
符号化のメカニズムを理解したところで、次にエラー検出の仕組みを提供する検査行列を見ていきましょう。
検査行列とシンドローム
検査行列の定義と生成行列との関係
符号 $C$ を特徴づけるもう一つの行列が検査行列（parity-check matrix）$\bm{H}$ です。$\bm{H}$ は $(n – k) \times n$ の行列であり、次の関係を満たします。
$$ \bm{c} \bm{H}^T = \bm{0} \quad (\text{mod}\, 2) \quad \Longleftrightarrow \quad \bm{c} \in C $$
すなわち、ベクトル $\bm{v} \in \mathbb{F}_2^n$ が符号語であるかどうかは、$\bm{v} \bm{H}^T$ がゼロベクトルかどうかで判定できます。$\bm{H}$ の行は $C$ の直交補空間 $C^\perp$ の基底であり、符号語はすべて $\bm{H}$ の行と直交（$\mathbb{F}_2$ 上で内積が0）する必要があります。
生成行列が組織形式 $\bm{G} = [\bm{I}_k \mid \bm{P}]$ のとき、検査行列は次のように構成できます。
$$ \bm{H} = [\bm{P}^T \mid \bm{I}_{n-k}] $$
$\mathbb{F}_2$ では $-1 = 1$ なので符号を気にする必要はありません。検証してみましょう。
$$ \bm{G}\bm{H}^T = [\bm{I}_k \mid \bm{P}] \begin{pmatrix} \bm{P} \\ \bm{I}_{n-k} \end{pmatrix} = \bm{P} + \bm{P} = \bm{0} \quad (\text{mod}\, 2) $$
確かに $\bm{G}\bm{H}^T = \bm{0}$ が成り立ちます。
シンドロームの定義と性質
通信チャネルを通過した受信語を $\bm{r}$ とします。送信された符号語を $\bm{c}$、発生したエラーパターンを $\bm{e}$ とすると、$\bm{r} = \bm{c} + \bm{e}$（$\mathbb{F}_2$ 上の加算 = XOR）です。
受信語のシンドローム（syndrome）を次のように計算します。
$$ \bm{s} = \bm{r} \bm{H}^T = (\bm{c} + \bm{e}) \bm{H}^T = \underbrace{\bm{c} \bm{H}^T}_{= \bm{0}} + \bm{e} \bm{H}^T = \bm{e} \bm{H}^T $$
この結果は極めて重要です。シンドロームはエラーパターン $\bm{e}$ のみに依存し、送信された符号語 $\bm{c}$ には依存しません。 これにより、どの符号語が送信されたかを知らなくても、エラーパターンを推定できるのです。
シンドロームの値から読み取れる情報は以下のとおりです。
- $\bm{s} = \bm{0}$: エラーなし（$\bm{e} = \bm{0}$）、または検出不能なエラーが発生（$\bm{e}$ 自体が符号語である場合）
- $\bm{s} \neq \bm{0}$: エラーが検出された。$\bm{s}$ の値からエラーパターンを推定する
コセット（剰余類）とシンドロームの代数的意味
シンドロームの意味をより深く理解するために、コセット（coset）の概念を導入します。
$\mathbb{F}_2^n$ を符号 $C$ で割ったコセット（剰余類）は、$C$ を平行移動して得られる集合です。
$$ \bm{e} + C = \{\bm{e} + \bm{c} : \bm{c} \in C\} $$
同じコセットに属するベクトルは同じシンドロームを持ちます。逆に、同じシンドロームを持つベクトルは同じコセットに属します。シンドロームはコセットの「ラベル」として機能するのです。
$\mathbb{F}_2^n$ は $2^{n-k}$ 個のコセットに分割されます（$C$ 自身を含む）。$C$ のコセットは $|C| = 2^k$ 個の要素を持ち、全体で $2^{n-k} \times 2^k = 2^n$ 個のベクトルを覆います。
各コセットの中で最もハミング重み（1の個数）が小さいベクトルをコセットリーダー（coset leader）と呼びます。シンドローム復号では、このコセットリーダーをエラーパターンの推定値として採用します。これは最尤復号（BSCの場合）と等価です。
ハミング距離と最小距離
ハミング距離の定義
2つのベクトル $\bm{x}, \bm{y} \in \mathbb{F}_2^n$ のハミング距離 $d(\bm{x}, \bm{y})$ は、両者が異なる位置の個数です。
$$ d(\bm{x}, \bm{y}) = |\{i : x_i \neq y_i, \, 1 \leq i \leq n\}| = w_H(\bm{x} + \bm{y}) $$
ここで $w_H(\bm{v}) = |\{i : v_i = 1\}|$ はハミング重みです。ハミング距離は距離の公理（非負性、対称性、三角不等式）を満たす真の距離関数です。
最小距離と誤り訂正・検出能力
符号 $C$ の最小距離 $d_{\min}$ は、異なる任意の2つの符号語間のハミング距離の最小値です。
$$ d_{\min} = \min_{\bm{c}_1 \neq \bm{c}_2 \in C} d(\bm{c}_1, \bm{c}_2) $$
線形符号では、$\bm{c}_1 – \bm{c}_2 = \bm{c}_1 + \bm{c}_2$（$\mathbb{F}_2$ では引き算と足し算が同じ）も符号語であるため、最小距離は非ゼロ符号語の最小ハミング重みに等しくなります。
$$ d_{\min} = \min_{\bm{c} \in C, \, \bm{c} \neq \bm{0}} w_H(\bm{c}) $$
最小距離 $d_{\min}$ を持つ $[n, k, d_{\min}]$ 符号の能力は以下のとおりです。
$t$ ビットのエラー訂正: $d_{\min} \geq 2t + 1$ のとき可能。直感的には、符号語同士が $d_{\min}$ 以上離れていれば、$t$ ビット以下のエラーでは「最も近い符号語」が一意に決まります。
$s$ ビットのエラー検出: $d_{\min} \geq s + 1$ のとき可能。$s$ ビット以下のエラーでは、受信語が別の符号語にたどり着くことはありません。
同時利用: $d_{\min} \geq s + t + 1$（$s \geq t$）のとき、$t$ ビットのエラーを訂正しつつ $s$ ビットのエラーを検出できます。
検査行列による最小距離の判定
最小距離と検査行列の間には美しい関係があります。
定理: $[n, k]$ 線形符号の最小距離 $d_{\min}$ は、検査行列 $\bm{H}$ の中で線形従属となる列の最小個数に等しい。等価的に、$\bm{H}$ の任意の $d_{\min} – 1$ 列は線形独立であるが、線形従属な $d_{\min}$ 列が存在する。
証明: 符号語 $\bm{c}$ は $\bm{H}\bm{c}^T = \bm{0}$ を満たします。これを列で書くと、$\bm{c}$ の1が立っている位置に対応する $\bm{H}$ の列の和（$\mathbb{F}_2$ 上）がゼロベクトルになるということです。すなわち、重み $w$ の符号語が存在することと、$\bm{H}$ の $w$ 個の列が線形従属であることは同値です。最小距離は非ゼロ符号語の最小重みなので、定理が成り立ちます。
この定理は、$d_{\min} \leq n – k + 1$（シングルトン限界）の簡単な証明にもなります。$(n-k) \times n$ 行列 $\bm{H}$ では $n – k + 1$ 列以上あれば必ず線形従属になるからです。
シンドローム復号アルゴリズム
標準配列（Standard Array）
シンドローム復号を体系的に理解するために、標準配列を構成します。
- 第1行に $C$ のすべての符号語を並べる（$\bm{0}$ を先頭にする）
- $\mathbb{F}_2^n$ の中で第1行に含まれないベクトルの中から、最小重みのものを $\bm{e}_1$ として選ぶ
- 第2行に $\bm{e}_1 + C = \{\bm{e}_1 + \bm{c} : \bm{c} \in C\}$ を並べる
- まだ出現していないベクトルの中から最小重みのものを選び、以下繰り返す
標準配列は $2^{n-k}$ 行 $2^k$ 列の表になり、$\mathbb{F}_2^n$ のすべての $2^n$ 個のベクトルが一度ずつ出現します。各行の先頭がコセットリーダーです。
復号手順
シンドローム復号は次の手順で行います。
- 受信語 $\bm{r}$ のシンドローム $\bm{s} = \bm{r}\bm{H}^T$ を計算する
- シンドローム $\bm{s}$ に対応するコセットリーダー $\hat{\bm{e}}$ を表（シンドロームテーブル）から引く
- 推定符号語を $\hat{\bm{c}} = \bm{r} – \hat{\bm{e}} = \bm{r} + \hat{\bm{e}}$（$\mathbb{F}_2$）として出力する
シンドロームテーブルは $2^{n-k}$ 個のエントリを持ち、あらかじめ構築しておくことで、復号は1回のシンドローム計算（$O(n(n-k))$）とテーブル参照で完了します。
具体例による復号
$[7, 4, 3]$ 符号で復号の例を見ましょう。検査行列は
$$ \bm{H} = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix} $$
情報語 $\bm{u} = (1, 0, 1, 1)$ を符号化すると $\bm{c} = (1, 0, 1, 1, 0, 0, 0)$ です。第3ビットにエラーが発生し、$\bm{r} = (1, 0, 0, 1, 0, 0, 0)$ を受信したとします。
シンドロームを計算すると、$\bm{s} = \bm{r}\bm{H}^T = (0, 1, 1)^T$ です。これは $\bm{H}$ の第3列に一致します。したがってエラーは第3ビットにあると推定され、$\hat{\bm{c}} = (1, 0, 1, 1, 0, 0, 0)$ が正しく復元されます。
符号の限界定理
シングルトン限界
定理（シングルトン限界）: $[n, k, d]$ 線形符号に対して、
$$ d \leq n – k + 1 $$
証明: 符号語の最初の $k – 1$ 個の座標を消去することを考えます。残りの $n – k + 1$ 座標に $2^k$ 個の符号語が写像されます。$2^k > 2^{n-k+1-1} = 2^{n-k}$ であるため、$n – k + 1$ 座標だけでは符号語を区別できるとは限りませんが、符号語間の距離は $n – k + 1$ 以下の座標でしか異なりえないため、$d \leq n – k + 1$ です。
等号 $d = n – k + 1$ を達成する符号をMDS符号（Maximum Distance Separable code）と呼びます。リード・ソロモン符号はMDS符号の代表例です。
ハミング限界（球充填限界）
定理（ハミング限界）: $t$ 個のエラーを訂正する $[n, k, 2t+1]$ 符号に対して、
$$ 2^k \sum_{i=0}^{t} \binom{n}{i} \leq 2^n $$
証明: 各符号語を中心とする半径 $t$ のハミング球（距離 $t$ 以内のすべてのベクトルの集合）は、$\sum_{i=0}^{t} \binom{n}{i}$ 個のベクトルを含みます。$t$ 個のエラーを訂正できるためには、異なる符号語のハミング球が互いに重ならない必要があります。ハミング球の総ベクトル数は $2^k \sum_{i=0}^{t} \binom{n}{i}$ であり、これが全空間 $2^n$ を超えることはできません。
等号を達成する符号を完全符号（perfect code）と呼びます。ハミング符号（$t = 1$）と、(23, 12, 7) ゴレイ符号（$t = 3$）が非自明な完全符号です。
ギルバート・ヴァーシャモフ限界
定理（GV限界）: 次の条件を満たす $[n, k, d]$ 線形符号が存在する。
$$ 2^{n-k} > \sum_{i=0}^{d-2} \binom{n-1}{i} $$
この限界は存在定理であり、特定のパラメータを持つ線形符号が確かに存在することを保証します。ハミング限界が「これ以上は不可能」という上限を与えるのに対し、GV限界は「少なくともこれだけは達成できる」という下限を与えます。
双対符号と線形符号の構造
双対符号の定義
$[n, k]$ 線形符号 $C$ の双対符号（dual code）$C^\perp$ は、$C$ のすべての符号語と直交（$\mathbb{F}_2$ 上の内積が0）するベクトルの集合です。
$$ C^\perp = \{\bm{v} \in \mathbb{F}_2^n : \bm{v} \cdot \bm{c} = 0 \text{ for all } \bm{c} \in C\} $$
$C^\perp$ は $[n, n-k]$ 線形符号であり、$C$ の検査行列 $\bm{H}$ が $C^\perp$ の生成行列になります。逆に、$C$ の生成行列 $\bm{G}$ が $C^\perp$ の検査行列になります。
自己双対符号
$C = C^\perp$ のとき、$C$ を自己双対符号（self-dual code）と呼びます。自己双対符号が存在するためには $k = n – k$、すなわち $n = 2k$ が必要です。
自己双対符号は代数的に美しい構造を持ち、格子理論やモジュラー形式との深い関係が知られています。(24, 12, 8) 拡大ゴレイ符号は有名な自己双対符号です。
双対符号の概念を理解したところで、ここまでの理論をPythonで実装して確認しましょう。
Pythonによる実装と性能評価
線形符号の基本操作
import numpy as np
import matplotlib.pyplot as plt
np.random.seed(42)
def gf2_matmul(A, B):
"""GF(2)上の行列積"""
return np.mod(A @ B, 2)
def gf2_rank(M):
"""GF(2)上の行列のランク（行簡約化で計算）"""
A = M.copy()
m, n = A.shape
rank = 0
for col in range(n):
# ピボット行を探す
pivot = None
for row in range(rank, m):
if A[row, col] == 1:
pivot = row
break
if pivot is None:
continue
# 行の交換
A[[rank, pivot]] = A[[pivot, rank]]
# 消去
for row in range(m):
if row != rank and A[row, col] == 1:
A[row] = np.mod(A[row] + A[rank], 2)
rank += 1
return rank
# --- [7, 4, 3] 線形符号 ---
# 組織形式の生成行列
G = np.array([
[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]
], dtype=int)
# 検査行列
H = np.array([
[1, 1, 0, 1, 1, 0, 0],
[1, 0, 1, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 0, 1]
], dtype=int)
n, k = 7, 4
# 検証: G H^T = 0 (mod 2)
print("G * H^T (should be zero matrix):")
print(gf2_matmul(G, H.T))
# 全符号語の列挙と最小距離の計算
print("\n=== 全符号語と重み分布 ===")
codewords = []
weights = []
for i in range(2**k):
u = np.array([(i >> j) & 1 for j in range(k)], dtype=int)
c = np.mod(u @ G, 2)
w = np.sum(c)
codewords.append(c)
weights.append(w)
if w <= 3:
print(f" u={u} -> c={c}, w(c)={w}")
codewords = np.array(codewords)
nonzero_weights = [w for w in weights if w > 0]
d_min = min(nonzero_weights)
print(f"\n符号語数: {len(codewords)}")
print(f"最小距離 d_min = {d_min}")
print(f"重み分布: {sorted(set(weights))}")
# 重みスペクトル
weight_spectrum = {}
for w in weights:
weight_spectrum[w] = weight_spectrum.get(w, 0) + 1
print(f"重みスペクトル A_w: {dict(sorted(weight_spectrum.items()))}")
上のコードでは、$[7, 4]$ 線形符号の基本的な性質を確認しています。$\bm{G}\bm{H}^T = \bm{0}$ の検証、全符号語の列挙、最小距離の計算、重みスペクトルの算出を行っています。最小距離 $d_{\min} = 3$ であるため、この符号は1ビットのエラーを訂正できることが確認できます。
シンドローム復号の実装と性能評価
def build_syndrome_table(H, n):
"""シンドロームテーブルの構築
各シンドロームに対して最小重みのエラーパターン（コセットリーダー）を格納
"""
n_syndromes = 2 ** (H.shape[0])
table = {}
# まず0エラー（シンドローム = 0）
zero_syndrome = tuple(np.zeros(H.shape[0], dtype=int))
table[zero_syndrome] = np.zeros(n, dtype=int)
# 1ビットエラーのすべてのパターン
for i in range(n):
e = np.zeros(n, dtype=int)
e[i] = 1
s = tuple(np.mod(e @ H.T, 2))
if s not in table:
table[s] = e.copy()
# 2ビットエラー（最小距離が3なので訂正不能だが、テーブルに登録）
for i in range(n):
for j in range(i + 1, n):
e = np.zeros(n, dtype=int)
e[i] = 1
e[j] = 1
s = tuple(np.mod(e @ H.T, 2))
if s not in table:
table[s] = e.copy()
return table
def syndrome_decode(r, H, table):
"""シンドローム復号"""
s = tuple(np.mod(r @ H.T, 2))
if s in table:
e_hat = table[s]
return np.mod(r + e_hat, 2)
return r # 訂正不能な場合はそのまま返す
# シンドロームテーブルの構築
syndrome_table = build_syndrome_table(H, n)
print(f"シンドロームテーブルのエントリ数: {len(syndrome_table)}")
# 1ビットエラーの訂正テスト（全パターン）
print("\n=== 1ビットエラー訂正の全パターンテスト ===")
n_correct = 0
n_total = 0
for c in codewords:
for pos in range(n):
e = np.zeros(n, dtype=int)
e[pos] = 1
r = np.mod(c + e, 2)
decoded = syndrome_decode(r, H, syndrome_table)
if np.array_equal(decoded, c):
n_correct += 1
n_total += 1
print(f"1ビットエラー訂正成功率: {n_correct}/{n_total} = {n_correct/n_total:.4f}")
# BSCチャネルでのBERシミュレーション
p_range = np.linspace(0.001, 0.2, 40)
n_trials = 20000
ber_uncoded = []
ber_coded = []
for p in p_range:
err_unc = 0
err_cod = 0
total_bits = 0
for _ in range(n_trials):
# ランダムな情報語
u = np.random.randint(0, 2, k)
c = np.mod(u @ G, 2)
# BSCエラー
error_unc = (np.random.random(k) < p).astype(int)
error_cod = (np.random.random(n) < p).astype(int)
# 受信
r_unc = np.mod(u + error_unc, 2)
r_cod = np.mod(c + error_cod, 2)
# 復号
decoded = syndrome_decode(r_cod, H, syndrome_table)
u_decoded = decoded[:k] # 組織符号
# エラー計数
err_unc += np.sum(r_unc != u)
err_cod += np.sum(u_decoded != u)
total_bits += k
ber_uncoded.append(err_unc / total_bits)
ber_coded.append(max(err_cod / total_bits, 1e-7))
# プロット
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# 左: BER性能
axes[0].semilogy(p_range, ber_uncoded, 'ro-', markersize=3, linewidth=1.5,
label='Uncoded')
axes[0].semilogy(p_range, ber_coded, 'bs-', markersize=3, linewidth=1.5,
label='[7,4,3] Hamming code')
axes[0].set_xlabel('Channel error probability $p$')
axes[0].set_ylabel('Bit Error Rate')
axes[0].set_title('[7,4,3] Code: BER vs Channel Error Rate')
axes[0].legend()
axes[0].grid(True, alpha=0.3)
# 右: 重みスペクトル
w_values = sorted(weight_spectrum.keys())
a_values = [weight_spectrum[w] for w in w_values]
axes[1].bar(w_values, a_values, color='steelblue', alpha=0.8)
axes[1].set_xlabel('Weight $w$')
axes[1].set_ylabel('Number of codewords $A_w$')
axes[1].set_title('[7,4,3] Code: Weight Spectrum')
axes[1].grid(True, alpha=0.3, axis='y')
plt.tight_layout()
plt.show()
シミュレーション結果から、以下のことが読み取れます。
-
低エラー率での大幅な改善: チャネルエラー率 $p$ が低い（$p < 0.05$）領域では、$[7, 4, 3]$ ハミング符号のBERが未符号化に比べて劇的に低下しています。1ビットエラーの訂正が有効に機能している領域です。
-
高エラー率での性能劣化: $p$ が大きくなる（$p > 0.1$）と、符号化の利点が失われ、場合によっては未符号化よりも悪化することがあります。これは符号化率 $R = 4/7$ により実効的なSNRが低下すること、および2ビット以上のエラーが頻発して訂正が裏目に出ることが原因です。
-
符号化率と訂正能力のトレードオフ: $[7, 4, 3]$ 符号は $R = 4/7 \approx 0.57$ の符号化率で1ビットの訂正が可能です。より強力な訂正（2ビット以上）には、より大きな冗長性（低い符号化率）を持つ符号が必要です。
-
重みスペクトル: 右のグラフに示された重みスペクトルから、重み3の符号語が7個あることがわかります。この符号語数が高SNR領域でのBERを支配する「多重度」に対応しています。
まとめ
本記事では、線形符号の基本理論を体系的に解説しました。
- 線形符号の定義: $\mathbb{F}_2^n$ の $k$ 次元部分空間であり、線形代数の道具で構造を完全に記述できる
- 生成行列と検査行列: 符号化は $\bm{c} = \bm{u}\bm{G}$ で行い、エラー検出は $\bm{s} = \bm{r}\bm{H}^T$ で行う。両者は直交補空間の関係で結ばれている
- 最小距離: 非ゼロ符号語の最小ハミング重みであり、$d_{\min} \geq 2t + 1$ のとき $t$ ビットのエラーを訂正できる
- シンドローム復号: シンドロームがエラーパターンのみに依存するという性質を利用した効率的な復号法
- 限界定理: シングルトン限界、ハミング限界、GV限界が、線形符号のパラメータの可能な範囲を特徴づける
線形符号の理論は、より高度な符号（ハミング符号、BCH符号、リード・ソロモン符号、LDPC符号）すべての基盤です。
次のステップとして、以下の記事も参考にしてください。
- ハミング符号の理論と誤り訂正能力 — 最も効率的な1ビット訂正符号
- 畳み込み符号とビタビ復号の理論 — ブロック符号とは異なるアプローチ
- LDPC符号の理論 — スパースグラフ符号 — シャノン限界に近い性能を持つ線形符号