衛星から送られてくる画像、QRコードの読み取り、SSDへの書き込み——これらに共通するのは、「ノイズで一部のビットが化けても、元のデータを正しく復元したい」という要求です。たとえば深宇宙探査機が10億キロ彼方から送る信号は地表に届くころには極めて微弱になり、受信ビットの数パーセントが反転していてもおかしくありません。それでも私たちは鮮明な惑星の写真を手にできます。なぜそんなことが可能なのでしょうか。
その鍵が誤り訂正符号（error-correcting code）であり、その最も基礎的で美しい枠組みが線形ブロック符号（linear block code）です。線形ブロック符号は、送りたい $k$ ビットの情報に巧妙な冗長ビットを付け加えて $n$ ビットの符号語にします。受信側は、たとえ何ビットか反転していても、「ありうる符号語」の中から最も近いものを選ぶことで元の情報を取り戻します。この「近さ」と「ありうる符号語の集合」を線形代数（ベクトル空間）の言葉で記述できる点が、線形ブロック符号の強力さの源です。
線形ブロック符号を理解すると、以下のような分野への扉が開きます。
- 衛星・深宇宙通信: CCSDS規格のテレメトリ符号化や、ハミング符号・リードソロモン符号・LDPC符号といった実用符号はすべて線形ブロック符号の枠組みの上に構築されています
- ストレージとメモリ: ECCメモリ（誤り訂正メモリ）は(72,64)ハミング系符号でDRAMの単一ビット誤りを訂正しています。SSDのコントローラもBCH符号やLDPC符号を内蔵しています
- 現代符号の基礎理論: LDPC符号やリードソロモン符号といった最先端の符号も、生成行列・検査行列・シンドロームという線形ブロック符号の概念をそのまま使います
本記事の内容
- 線形ブロック符号がガロア体 $\mathrm{GF}(2)^n$ の部分空間であること（直感と定義）
- 組織符号と生成行列 $\bm{G} = [\bm{I} \mid \bm{P}]$ による符号化
- 検査行列 $\bm{H} = [\bm{P}^T \mid \bm{I}]$ と関係式 $\bm{G}\bm{H}^T = \bm{0}$ の導出
- シンドローム $\bm{s} = \bm{H}\bm{r}^T$ が誤りパターンのみに依存することの証明
- 最小ハミング距離 $d_{\min}$ と訂正能力 $t = \lfloor (d-1)/2 \rfloor$
- 標準配列とシンドローム復号
- (7,4)ハミング符号の具体例
- PythonによるG/Hの構築、符号化、シンドローム復号、BER対符号化利得の評価
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- ビット誤り率（BER）とは — ディジタル通信の品質指標 — 符号化利得を評価する際の基準となる指標
- CRCによる誤り検出の仕組み — 誤り「検出」符号の代表例。本記事の誤り「訂正」と対比すると理解が深まります
- リードソロモン符号の理論と実装 — 線形ブロック符号の発展形。本記事の概念がそのまま使われます
行列とベクトルの積、ベクトル空間（部分空間・基底・次元）の基本的な扱いを知っていると、本記事の数式がスムーズに読めます。ただし、ここで扱うのは普通の実数ではなく「0と1だけの世界」での演算なので、その点はこれから丁寧に説明していきます。
なぜ「冗長」を加えると誤りが直せるのか — 直感
まず、誤り訂正がなぜ可能なのかを直感的につかみましょう。アナロジーとして、地図上の都市を考えます。送りたいメッセージが「都市の位置」だとして、もし都市同士が密集していたら、ちょっと座標がずれただけでどの都市を指していたのか分からなくなります。しかし、都市同士が十分に離れて配置されていれば、座標が多少ノイズでずれても「一番近い都市」を答えれば正しい都市を当てられます。
誤り訂正符号がやっているのは、まさにこれです。$k$ ビットの情報は $2^k$ 通りありますが、これをそのまま送らず、$n > k$ ビットの空間（全体では $2^n$ 通りの点がある）の中に、$2^k$ 個の「符号語」としてまばらに配置します。符号語同士を十分離して置けば、ノイズで何ビットか反転しても、受信したビット列は本来の符号語の「近く」にとどまり、最も近い符号語を選ぶことで元の情報を復元できます。
ここで「近さ」を測る物差しがハミング距離です。2つのビット列の異なるビットの個数がハミング距離で、たとえば 1011 と 1110 のハミング距離は2です（2番目と4番目が違う）。1ビットの反転はハミング距離1の移動に対応します。符号語同士のハミング距離を大きく保つことが、誤り訂正能力の鍵になります。
もうひとつ重要なのが線形性です。$2^k$ 個の符号語をデタラメに配置してもよいのですが、それでは符号化や復号の計算が膨大になります。そこで「符号語の集合が足し算について閉じている」、つまり任意の2つの符号語を足すとまた符号語になるという性質を課します。これが線形ブロック符号の「線形」の意味です。線形性のおかげで、符号は行列ひとつ（生成行列）でコンパクトに表現でき、復号も劇的に簡単になります。
この「足し算」がどんな足し算なのかを、次のセクションで正確に定義しましょう。
ガロア体 GF(2) と符号語空間
0と1だけの算術
ビットは0か1の2値です。この2値の世界で四則演算を定義したものがガロア体 $\mathrm{GF}(2)$（位数2の有限体、$\mathbb{F}_2$ とも書く）です。加算と乗算は次のように定義されます。
$$ \begin{array}{c|cc} + & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \qquad \begin{array}{c|cc} \times & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \end{array} $$
加算の表をよく見ると、これは排他的論理和（XOR、$\oplus$）と完全に一致しています。$1 + 1 = 0$ という点が普通の算術と違う最大のポイントです。これは「同じものを2回足すと打ち消し合う」ことを意味し、後で何度も使う重要な性質です。乗算は論理積（AND）と一致します。
$\mathrm{GF}(2)$ では、加算と減算が同じになります。なぜなら $a + a = 0$ より $-a = a$ だからです。したがって $a – b = a + b$ であり、引き算を意識する必要がありません。この性質が線形符号の理論を非常にすっきりさせます。
符号語はベクトル空間の部分空間
$n$ ビットのビット列は、$\mathrm{GF}(2)$ の要素を $n$ 個並べたベクトル、すなわち $\mathrm{GF}(2)^n$ の元とみなせます。$\mathrm{GF}(2)^n$ は $2^n$ 個の点を持つベクトル空間です。ベクトル同士の加算は要素ごとのXOR、スカラー倍は0倍（零ベクトル）か1倍（そのまま）の2通りだけです。
ここで $(n, k)$ 線形ブロック符号を次のように定義します。
$(n, k)$ 線形ブロック符号 $\mathcal{C}$ とは、$\mathrm{GF}(2)^n$ の $k$ 次元部分空間である。
「部分空間」であるとは、次の2条件を満たすことです。
- 零ベクトル $\bm{0}$ を含む
- 任意の符号語 $\bm{c}_1, \bm{c}_2 \in \mathcal{C}$ について $\bm{c}_1 + \bm{c}_2 \in \mathcal{C}$（加法について閉じている）
スカラー倍については $\mathrm{GF}(2)$ では0倍と1倍しかなく、いずれも条件1・2から従うので、加法閉性が線形性の本質です。これがまさに前セクションで述べた「2つの符号語を足すとまた符号語になる」という性質の数学的な言い換えです。
$k$ 次元部分空間なので、$\mathcal{C}$ にはちょうど $2^k$ 個の符号語が含まれます（$k$ 個の基底ベクトルの線形結合の個数）。これは送りたい情報 $k$ ビットの総数 $2^k$ とぴったり一致します。つまり、$k$ ビットの各情報パターンに1つずつ符号語が割り当てられるわけです。
部分空間であることから得られる便利な性質を1つ挙げておきます。符号 $\mathcal{C}$ の最小重み（零でない符号語の中で1の個数が最小のもの）が、後で定義する最小ハミング距離に等しくなります。これは線形符号特有の性質で、$2^k$ 個の符号語の全ペアの距離を調べる代わりに、各符号語の重みだけ調べればよいことを意味します。証明は後のセクションで行います。
符号がベクトル空間の部分空間だと分かったので、次はその部分空間を「行列」で表現する方法を見ていきましょう。これが生成行列です。
生成行列 G による符号化
基底を並べた行列
$k$ 次元部分空間 $\mathcal{C}$ には $k$ 個の基底ベクトル $\bm{g}_1, \bm{g}_2, \dots, \bm{g}_k$ があり、任意の符号語はこれらの線形結合で書けます。この基底ベクトルを行に並べた $k \times n$ 行列を生成行列（generator matrix）$\bm{G}$ と呼びます。
$$ \bm{G} = \begin{pmatrix} \bm{g}_1 \\ \bm{g}_2 \\ \vdots \\ \bm{g}_k \end{pmatrix} $$
送りたい情報ビットを行ベクトル $\bm{m} = (m_1, m_2, \dots, m_k) \in \mathrm{GF}(2)^k$ とすると、符号化は単なる行列とベクトルの積で表されます。
$$ \bm{c} = \bm{m}\bm{G} = \sum_{i=1}^{k} m_i \bm{g}_i $$
これは「情報ビット $m_i$ が1の基底ベクトル $\bm{g}_i$ だけをXORで足し合わせる」操作です。$\bm{m}$ が $k$ ビットの全パターン $2^k$ 通りを動けば、$\bm{c}$ は $\mathcal{C}$ の全符号語 $2^k$ 個をちょうど一巡します。これで「情報 $\to$ 符号語」の対応が行列 $\bm{G}$ ひとつで完全に決まりました。
組織符号と標準形 G = [I | P]
生成行列は基底の取り方によって何通りもありますが、特に扱いやすいのが組織符号（systematic code）の形です。組織符号とは、符号語の中に情報ビットがそのままの形で現れる符号のことです。生成行列を次の標準形にすると組織符号になります。
$$ \bm{G} = [\,\bm{I}_k \mid \bm{P}\,] $$
ここで $\bm{I}_k$ は $k \times k$ の単位行列、$\bm{P}$ は $k \times (n-k)$ の行列です。このとき符号語は
$$ \bm{c} = \bm{m}\bm{G} = \bm{m}[\,\bm{I}_k \mid \bm{P}\,] = (\,\bm{m} \mid \bm{m}\bm{P}\,) $$
となります。前半の $k$ ビットは情報そのもの（$\bm{m}$）、後半の $n-k$ ビットは $\bm{m}\bm{P}$ というパリティビット（検査ビット）です。受信側は復号後、前半の $k$ ビットを読むだけで情報を取り出せるので、実装上とても便利です。
組織符号でない生成行列も、行基本変形（行の入れ替えとXOR）と必要なら列の入れ替えによって標準形 $[\bm{I}_k \mid \bm{P}]$ に変形できます。行基本変形は基底の取り替えにすぎず、生成される部分空間（符号語の集合）は変わりません。したがって、符号の性能を論じるうえでは組織形を仮定しても一般性を失いません。
具体例として、後で詳しく扱う(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{I}_4 \mid \bm{P}\,] $$
左側の $4\times4$ が単位行列で、右側の $4\times3$ が $\bm{P}$ です。たとえば情報 $\bm{m}=(1,0,1,1)$ を符号化すると、$\bm{g}_1, \bm{g}_3, \bm{g}_4$ をXORして $\bm{c}=(1,0,1,1,0,1,0)$ となります（前半4ビットがそのまま情報です）。
生成行列で符号語を作れるようになりました。では、受信したビット列が「正しい符号語かどうか」をどうやって判定すればよいでしょうか。そのための道具が検査行列です。
検査行列 H とシンドローム
パリティ検査の行列表現
符号語の集合 $\mathcal{C}$ は $\mathrm{GF}(2)^n$ の $k$ 次元部分空間でした。線形代数では、部分空間は「ある線形方程式系の解空間」として特徴づけられます。すなわち、ある $(n-k) \times n$ 行列 $\bm{H}$ が存在して、
$$ \bm{c} \in \mathcal{C} \iff \bm{H}\bm{c}^T = \bm{0} $$
が成り立ちます。この $\bm{H}$ を検査行列（parity-check matrix）と呼びます。$\bm{H}\bm{c}^T = \bm{0}$ は $n-k$ 本のパリティ検査式（各行が1本のXOR方程式）をまとめたもので、符号語はすべての検査式を満たさなければなりません。検査行列の各行が「このビットたちのXORは0でなければならない」という制約を表しているわけです。
G から H を作る — GH^T = 0 の導出
生成行列 $\bm{G} = [\bm{I}_k \mid \bm{P}]$ が与えられたとき、検査行列 $\bm{H}$ を具体的に構成しましょう。結論から言うと、
$$ \bm{H} = [\,\bm{P}^T \mid \bm{I}_{n-k}\,] $$
とすればよいです。これを導きます。検査行列が満たすべき条件は、すべての符号語 $\bm{c} = \bm{m}\bm{G}$ に対して $\bm{H}\bm{c}^T = \bm{0}$ となることです。$\bm{c}^T = (\bm{m}\bm{G})^T = \bm{G}^T\bm{m}^T$ なので、
$$ \bm{H}\bm{c}^T = \bm{H}\bm{G}^T\bm{m}^T = \bm{0} $$
がすべての $\bm{m}$ について成り立つ必要があります。任意の $\bm{m}$ で成り立つには $\bm{H}\bm{G}^T = \bm{0}$、すなわち転置して $\bm{G}\bm{H}^T = \bm{0}$ であればよいことが分かります。これが基本関係式です。
では $\bm{H} = [\bm{P}^T \mid \bm{I}_{n-k}]$ が本当に $\bm{G}\bm{H}^T = \bm{0}$ を満たすか確かめましょう。$\bm{H}^T$ はブロックで書くと
$$ \bm{H}^T = \begin{pmatrix} \bm{P} \\ \bm{I}_{n-k} \end{pmatrix} $$
です（$\bm{P}^T$ の転置は $\bm{P}$）。これに $\bm{G} = [\bm{I}_k \mid \bm{P}]$ を掛けると、ブロック行列の積として
$$ \bm{G}\bm{H}^T = [\,\bm{I}_k \mid \bm{P}\,]\begin{pmatrix} \bm{P} \\ \bm{I}_{n-k} \end{pmatrix} = \bm{I}_k \bm{P} + \bm{P}\,\bm{I}_{n-k} = \bm{P} + \bm{P} $$
となります。ここで $\mathrm{GF}(2)$ では $\bm{P} + \bm{P} = \bm{0}$（同じものを2回足すと打ち消し合う）なので、
$$ \bm{G}\bm{H}^T = \bm{P} + \bm{P} = \bm{0} $$
が確かに成り立ちます。$\mathrm{GF}(2)$ の「1+1=0」がここで効いているわけです。普通の実数だと $\bm{P}+\bm{P} = 2\bm{P} \neq \bm{0}$ なので、符号と引き算の工夫が必要になりますが、$\mathrm{GF}(2)$ ではそのまま消えてくれます。
また $\bm{H}$ は明らかに右側に $\bm{I}_{n-k}$ を含むのでランクは $n-k$ あり、その零空間（解空間）の次元は $n-(n-k)=k$ です。これは符号 $\mathcal{C}$ の次元 $k$ と一致するので、$\bm{H}$ の零空間はちょうど $\mathcal{C}$ そのものになります。すなわち $\bm{H}\bm{c}^T=\bm{0}$ を満たす $\bm{c}$ の全体が $\mathcal{C}$ です。
シンドロームは誤りパターンだけで決まる
いよいよ復号の核心です。符号語 $\bm{c}$ を送り、通信路で誤りが起きて受信ベクトルが
$$ \bm{r} = \bm{c} + \bm{e} $$
になったとします。ここで $\bm{e} \in \mathrm{GF}(2)^n$ は誤りパターンで、誤りが起きたビット位置で1、それ以外で0です。たとえば3番目のビットだけが反転したなら $\bm{e}=(0,0,1,0,\dots,0)$ です。受信側は $\bm{r}$ しか観測できず、$\bm{c}$ も $\bm{e}$ も直接は分かりません。
そこで受信ベクトルに検査行列を掛けた量、シンドローム（syndrome）を計算します。
$$ \bm{s} = \bm{H}\bm{r}^T $$
これを展開すると、
$$ \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{c}$ は符号語なので $\bm{H}\bm{c}^T = \bm{0}$ です。これを代入すると、
$$ \bm{s} = \bm{0} + \bm{H}\bm{e}^T = \bm{H}\bm{e}^T $$
が得られます。これは驚くほど重要な結果です。シンドローム $\bm{s}$ は送った符号語 $\bm{c}$ に一切依存せず、誤りパターン $\bm{e}$ だけで決まるのです。どの情報を送ったかに関わらず、シンドロームを見れば「どんな誤りが起きたか」の手がかりが直接得られます。
さらに2つの重要な事実が読み取れます。第一に、$\bm{s} = \bm{0}$ なら誤りパターンが符号語（$\bm{H}\bm{e}^T=\bm{0}$）であるか、あるいは誤りなし（$\bm{e}=\bm{0}$）です。つまりシンドロームが零ベクトルなら「誤りは検出されなかった」と判断します。第二に、$\bm{s} = \bm{H}\bm{e}^T$ は $\bm{H}$ の列ベクトルを $\bm{e}$ の1の位置で足し合わせたものに等しいので、1ビット誤り（$\bm{e}$ が単位ベクトル）の場合、シンドロームは $\bm{H}$ のその列ベクトルそのものになります。この性質がハミング符号の鮮やかな復号につながります。
シンドロームが誤りの情報を持っていると分かりました。では、シンドロームからどうやって誤りパターンを推定し、訂正するのか。その前に、「どこまで訂正できるのか」という限界を決めるハミング距離を見ておきましょう。
ハミング距離と訂正能力
ハミング距離・ハミング重み
冒頭で触れたように、2つのビット列 $\bm{x}, \bm{y}$ のハミング距離 $d_H(\bm{x}, \bm{y})$ は、対応する位置で異なるビットの個数です。$\mathrm{GF}(2)$ では $\bm{x}$ と $\bm{y}$ の差 $\bm{x}+\bm{y}$ の1の個数に等しくなります。また、ベクトル $\bm{x}$ の1の個数をハミング重み $w(\bm{x})$ と呼びます。したがって
$$ d_H(\bm{x}, \bm{y}) = w(\bm{x} + \bm{y}) $$
という関係が成り立ちます。距離が重みで書けるのは、$\mathrm{GF}(2)$ で加算と減算が同じだからです。
符号 $\mathcal{C}$ の最小ハミング距離 $d_{\min}$ は、相異なる符号語ペアの距離の最小値として定義されます。
$$ d_{\min} = \min_{\substack{\bm{c}_1, \bm{c}_2 \in \mathcal{C} \\ \bm{c}_1 \neq \bm{c}_2}} d_H(\bm{c}_1, \bm{c}_2) $$
最小距離は最小重みに等しい（線形符号の性質）
ここで線形符号の便利な性質を証明します。$d_{\min}$ は、零でない符号語の最小重みに等しい、すなわち
$$ d_{\min} = \min_{\substack{\bm{c} \in \mathcal{C} \\ \bm{c} \neq \bm{0}}} w(\bm{c}) $$
です。証明は簡単です。距離は $d_H(\bm{c}_1, \bm{c}_2) = w(\bm{c}_1 + \bm{c}_2)$ と書けますが、線形符号では $\bm{c}_1 + \bm{c}_2$ もまた符号語です（部分空間の加法閉性）。$\bm{c}_1 \neq \bm{c}_2$ ならこの和は零でない符号語なので、「相異なる符号語ペアの距離の最小値」を求めることは「零でない符号語の重みの最小値」を求めることと同じになります。
この性質のおかげで、$2^k$ 個の符号語の全ペア（$\binom{2^k}{2}$ 通り）の距離を調べる必要はなく、$2^k – 1$ 個の零でない符号語の重みを調べるだけで $d_{\min}$ が分かります。計算量が劇的に減ります。
検査行列から最小距離を読む
最小距離は検査行列 $\bm{H}$ からも判定できます。重要な定理は次のものです。
符号の最小距離が $d$ であることは、$\bm{H}$ の任意の $d-1$ 列が線形独立であり、かつ線形従属な $d$ 列が存在することと同値である。
なぜなら、零でない符号語 $\bm{c}$ で $\bm{H}\bm{c}^T = \bm{0}$ を満たすものは、$\bm{H}$ の列のうち $\bm{c}$ の1に対応する列が（XORで）足して零になる、すなわち線形従属になることを意味するからです。重み $w$ の符号語が存在する $\iff$ $\bm{H}$ の $w$ 列が線形従属、という対応です。したがって、最小重みは「線形従属になる最小の列数」に等しくなります。
この定理は符号設計の指針を与えます。たとえばハミング符号は、検査行列の列をすべて「相異なる零でないベクトル」にすることで、どの2列も線形独立（GF(2)では零でない相異なる2ベクトルが従属になるには一致する必要があるが、相異なるので独立）にし、$d_{\min} \geq 3$ を保証します。
訂正能力 t と検出能力
最小距離が分かると、何ビットまで訂正・検出できるかが決まります。冒頭の「都市」のアナロジーを思い出してください。符号語同士が距離 $d_{\min}$ 以上離れているとき、各符号語を中心とする半径 $t$ の球（ハミング距離 $t$ 以内のベクトルの集合）が互いに重ならないためには、球の直径 $2t$ が $d_{\min}$ 未満であればよく、
$$ 2t < d_{\min} \quad\Longrightarrow\quad t = \left\lfloor \frac{d_{\min} - 1}{2} \right\rfloor $$
ビットまでの誤りを訂正できます。受信ベクトルがどれかの符号語の球の中に入っていれば、その中心の符号語に訂正すればよいからです。$t$ ビット以下の誤りなら、受信ベクトルは必ず正しい符号語の球の中にとどまります。
一方、誤りを検出だけする（訂正はしない）なら、受信ベクトルが別の符号語に化けない限り検出できます。$d_{\min} – 1$ ビットまでの誤りなら、どんな誤りパターンでも別の符号語にぴったり一致することはない（距離が $d_{\min}$ 未満だから）ので、
$$ \text{検出可能ビット数} = d_{\min} – 1 $$
です。たとえば $d_{\min} = 3$ なら、1ビット訂正（$t=1$）または2ビット検出ができます。$d_{\min}=4$ なら1ビット訂正かつ2ビット検出（SECDED: Single Error Correction, Double Error Detection）が可能で、これがECCメモリで使われる方式です。
訂正能力の理論的な限界が分かりました。次に、シンドロームを使って実際に誤りを訂正する具体的な手続き——シンドローム復号——を見ていきましょう。
標準配列とシンドローム復号
剰余類による空間の分割
シンドローム復号の理論的背景が標準配列（standard array）です。$\bm{r} = \bm{c} + \bm{e}$ という関係から、受信ベクトル $\bm{r}$ は「ある符号語に誤りパターンを足したもの」です。同じシンドロームを持つベクトルの集合を考えると、$\mathrm{GF}(2)^n$ がきれいに分割されます。
具体的には、$\mathrm{GF}(2)^n$ を部分空間 $\mathcal{C}$ による剰余類（coset）に分けます。各剰余類は
$$ \bm{e} + \mathcal{C} = \{\bm{e} + \bm{c} : \bm{c} \in \mathcal{C}\} $$
の形で、$\bm{e}$ をずらすことで $2^{n-k}$ 個の剰余類ができ、それぞれが $2^k$ 個のベクトルを含みます（合計 $2^{n-k}\cdot 2^k = 2^n$ で全空間を覆う）。同じ剰余類に属するベクトルは、すべて同じシンドロームを持ちます。なぜなら、$\bm{r} = \bm{e}+\bm{c}$ なら $\bm{H}\bm{r}^T = \bm{H}\bm{e}^T + \bm{H}\bm{c}^T = \bm{H}\bm{e}^T$ で、剰余類内では $\bm{e}$ が共通だからです。つまりシンドロームと剰余類は1対1に対応します。
標準配列は、各剰余類を1行に並べた表です。各行の先頭（最も重みの小さいベクトル）をコセットリーダー（coset leader）と呼び、これがその剰余類で「最もありそうな誤りパターン」になります。誤りが少ないほど起こりやすいという最尤推定の考え方に基づき、各シンドロームに対して最小重みの誤りパターンを割り当てるのです。
シンドローム復号のアルゴリズム
以上を踏まえると、シンドローム復号は次の手順になります。
- 受信ベクトル $\bm{r}$ からシンドローム $\bm{s} = \bm{H}\bm{r}^T$ を計算する
- シンドローム $\bm{s}$ に対応するコセットリーダー（最小重みの誤りパターン）$\hat{\bm{e}}$ をあらかじめ作った表（シンドローム表）から引く
- 訂正後の符号語を $\hat{\bm{c}} = \bm{r} + \hat{\bm{e}}$ とする
- 組織符号なら $\hat{\bm{c}}$ の前半 $k$ ビットが復元された情報
ステップ2のシンドローム表は、$2^{n-k}$ 個のシンドロームそれぞれに対し、それを生むベクトルの中で最小重みのものを事前計算して持っておきます。$n-k$ が小さければこの表はコンパクトで、復号は表引き1回で済むので非常に高速です。これがシンドローム復号の利点です。全 $2^n$ 個のベクトルとの距離を総当たりで比較する最尤復号に比べ、$2^{n-k}$ の表で済むので計算量が大幅に減ります。
ステップ2でコセットリーダーが一意に決まる（最小重みのベクトルがただ1つ）のは、その剰余類の誤りが訂正能力 $t$ 以内の範囲です。複数の最小重みベクトルがある剰余類では、どれを選んでも訂正は確実には保証されません（これが訂正能力を超えた誤りに対応します）。
ハミング符号のように $d_{\min}=3$ の符号では、$t=1$ なので「重み0または1の誤りパターン」が一意のコセットリーダーになります。重み1の誤りパターンのシンドロームは $\bm{H}$ の対応する列そのものなので、シンドロームを $\bm{H}$ の列と照合するだけで誤り位置が分かります。次のセクションでこの鮮やかな仕組みを具体的に見ましょう。
(7,4)ハミング符号の具体例
検査行列の設計
(7,4)ハミング符号は、$n=7$、$k=4$、$d_{\min}=3$ の符号で、1ビット誤り訂正ができます。検査行列 $\bm{H}$ は $3 \times 7$ で、その7本の列を「3ビットの零でないベクトルすべて」にします。3ビットの零でないベクトルは $2^3 – 1 = 7$ 通りあり、ちょうど7列に対応します。
組織形 $\bm{H} = [\bm{P}^T \mid \bm{I}_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} $$
右側の $3\times3$ が単位行列 $\bm{I}_3$、左側の $3\times4$ が $\bm{P}^T$ です。先に挙げた生成行列 $\bm{G}=[\bm{I}_4 \mid \bm{P}]$ の $\bm{P}$ と、この $\bm{P}^T$ が転置の関係にあることを確認できます（$\bm{P}$ の第1行 $(1,1,0)$ が $\bm{P}^T$ の第1列）。どの列も零でなく、互いに相異なるので、任意の2列は線形独立、すなわち $d_{\min} \geq 3$ が保証されます。実際 $d_{\min}=3$ です。
1ビット誤りの訂正
(7,4)ハミング符号の復号がなぜ美しいかを示しましょう。第 $j$ ビットだけが反転した誤り $\bm{e}_j$ のシンドロームは、$\bm{s} = \bm{H}\bm{e}_j^T = \bm{H}$ の第 $j$ 列です。$\bm{H}$ の7列はすべて相異なるので、シンドロームを見ればそれが第何列かが一意に分かり、誤りビットの位置が即座に特定できます。
たとえば符号語 $\bm{c}=(1,0,1,1,0,1,0)$（先ほど $\bm{m}=(1,0,1,1)$ から作ったもの）を送り、3番目のビットが反転して $\bm{r}=(1,0,0,1,0,1,0)$ を受信したとします。シンドロームは
$$ \bm{s} = \bm{H}\bm{r}^T = \bm{H}\text{の第3列} = (0,1,1)^T $$
になります。$\bm{H}$ の列を見ると $(0,1,1)^T$ は第3列なので、「3番目のビットが誤っている」と判定し、$\bm{r}$ の3番目を反転して $\hat{\bm{c}}=(1,0,1,1,0,1,0)$ を復元、前半4ビット $(1,0,1,1)$ が元の情報です。シンドローム表を引かずとも、列との照合だけで訂正できるのがハミング符号の特長です。
ハミング限界（完全符号）
(7,4)ハミング符号は完全符号（perfect code）でもあります。$n=7$ の空間には $2^7=128$ 個のベクトルがあり、$2^4=16$ 個の符号語それぞれを中心とする半径1の球は、中心1個＋距離1のベクトル7個＝8個を含みます。$16 \times 8 = 128$ でちょうど全空間を覆い尽くします。隙間も重なりもないので「完全」と呼ばれ、ハミング限界
$$ 2^k \sum_{i=0}^{t}\binom{n}{i} \leq 2^n $$
を等号で満たします。これは符号効率の理論的限界に達していることを意味し、ハミング符号の効率の良さを表しています。
単一パリティ符号との関係
ハミング符号の対極にあるのが単一パリティ符号（single parity check code）です。これは $k$ 情報ビットに1個のパリティビットを加える $(k+1, k)$ 符号で、全ビットのXORが0になるようにします。検査行列は $\bm{H}=(1,1,\dots,1)$（すべて1の1行）で、$d_{\min}=2$ です。$t=\lfloor (2-1)/2\rfloor = 0$ なので訂正はできませんが、$d_{\min}-1=1$ ビットの検出はできます。これがパリティチェックの正体で、最も単純な線形ブロック符号です。
逆に、もう1つの極端な例が繰り返し符号（repetition code）です。1ビットを $n$ 回繰り返す $(n,1)$ 符号で、生成行列は $\bm{G}=(1,1,\dots,1)$、$d_{\min}=n$ です。$n=3$ なら多数決で1ビット訂正できますが、効率（符号化率 $R=k/n=1/3$）は極めて悪いです。
これらと比べると、(7,4)ハミング符号は符号化率 $R=4/7\approx0.57$ で1ビット訂正を実現しており、効率と訂正能力のバランスが取れた符号だと分かります。理論を一通り押さえたので、これらをPythonで実装して動かしてみましょう。
Pythonでの実装
G と H の構築
まず(7,4)ハミング符号の生成行列 $\bm{G}=[\bm{I}_4\mid\bm{P}]$ と検査行列 $\bm{H}=[\bm{P}^T\mid\bm{I}_3]$ を構築し、基本関係式 $\bm{G}\bm{H}^T=\bm{0}$ を確認します。
import numpy as np
# (7,4)ハミング符号のパリティ部分行列 P (4x3)
# 各行は3ビットの零でないベクトル（重み2以上のものを選ぶ）
P = np.array([
[1, 1, 0],
[1, 0, 1],
[0, 1, 1],
[1, 1, 1],
], dtype=int)
k, nk = P.shape # k=4, n-k=3
n = k + nk # n=7
# 生成行列 G = [I_k | P]
G = np.hstack([np.eye(k, dtype=int), P])
# 検査行列 H = [P^T | I_{n-k}]
H = np.hstack([P.T, np.eye(nk, dtype=int)])
print("G =\n", G)
print("H =\n", H)
# 基本関係式 G H^T = 0 (mod 2) の確認
print("G H^T mod 2 =\n", (G @ H.T) % 2)
出力を見ると、G H^T mod 2 がすべて0の $4\times3$ 行列になっていることが確認できます。これは導出した $\bm{G}\bm{H}^T=\bm{P}+\bm{P}=\bm{0}$ が $\mathrm{GF}(2)$ で正しく成り立っていることを意味します。$\bm{G}$ の左4列、$\bm{H}$ の右3列がそれぞれ単位行列になっており、組織符号の標準形になっていることも目視できます。
符号化と全符号語の重み
次に、全 $2^4=16$ 通りの情報ベクトルを符号化し、最小ハミング距離を「零でない符号語の最小重み」として計算します。
import itertools
def encode(m, G):
"""情報ベクトル m を符号化（mod 2 の行列積）"""
return (m @ G) % 2
# 全16通りの符号語を生成
codewords = []
for bits in itertools.product([0, 1], repeat=k):
m = np.array(bits, dtype=int)
codewords.append(encode(m, G))
codewords = np.array(codewords)
# 零でない符号語の最小重み = 最小ハミング距離
weights = codewords.sum(axis=1)
nonzero_weights = weights[weights > 0]
d_min = nonzero_weights.min()
print("符号語の数:", len(codewords))
print("各符号語の重み:", sorted(weights.tolist()))
print("最小ハミング距離 d_min =", d_min)
print("訂正能力 t =", (d_min - 1) // 2)
出力から、符号語が16個あり、零でない符号語の最小重みが3、すなわち $d_{\min}=3$ であることが確認できます。したがって訂正能力は $t=\lfloor(3-1)/2\rfloor=1$ ビットです。重みの分布を見ると、重み3の符号語が複数あり、これらが「最も近い符号語ペア」を作っていることが分かります。線形符号の性質により、ペアの距離を総当たりせずとも最小重みだけで $d_{\min}$ が得られている点に注目してください。
シンドローム表の構築と1ビット誤り訂正
シンドローム復号器を実装します。1ビット誤り（と誤りなし）に対するシンドローム表を作り、それを使って誤りを訂正します。
def syndrome(r, H):
"""受信ベクトル r のシンドローム s = H r^T (mod 2)"""
return (H @ r) % 2
# シンドローム表: シンドローム(タプル) -> コセットリーダー(誤りパターン)
syndrome_table = {}
# 誤りなし（重み0）
syndrome_table[tuple(np.zeros(nk, dtype=int))] = np.zeros(n, dtype=int)
# 重み1の誤りパターン（各ビットの単一誤り）
for j in range(n):
e = np.zeros(n, dtype=int)
e[j] = 1
s = tuple(syndrome(e, H))
syndrome_table[s] = e
# シンドロームと H の列の対応を表示
print("各誤り位置に対するシンドローム（= H の列）:")
for j in range(n):
e = np.zeros(n, dtype=int); e[j] = 1
print(f" 位置 {j}: s = {syndrome(e, H)}")
出力を見ると、第 $j$ ビットの単一誤りに対するシンドロームが、検査行列 $\bm{H}$ の第 $j$ 列とぴったり一致していることが分かります。7つの列がすべて相異なるため、シンドロームから誤り位置が一意に逆引きできます。これがハミング符号の1ビット訂正の仕組みそのものです。
def decode(r, H, syndrome_table, k):
"""シンドローム復号: 受信 r を訂正し、情報ビットを返す"""
s = tuple(syndrome(r, H))
e_hat = syndrome_table.get(s, np.zeros(len(r), dtype=int))
c_hat = (r + e_hat) % 2 # 訂正後の符号語
return c_hat, c_hat[:k] # 組織符号なので前半kビットが情報
# 動作確認: m=(1,0,1,1) を送り、3番目のビットを反転させる
m = np.array([1, 0, 1, 1])
c = encode(m, G)
r = c.copy()
r[2] ^= 1 # 3番目（index 2）を反転
c_hat, m_hat = decode(r, H, syndrome_table, k)
print("送信情報 m :", m)
print("送信符号語 c :", c)
print("受信 r :", r, "（3番目を反転）")
print("復元符号語 :", c_hat)
print("復元情報 m_hat:", m_hat, "-> 一致:", np.array_equal(m, m_hat))
出力から、3番目のビットが反転した受信ベクトルから元の情報 $(1,0,1,1)$ が正しく復元されたことが確認できます。シンドローム $\bm{s}=(0,1,1)$ が $\bm{H}$ の第3列に対応し、誤りパターン $\hat{\bm{e}}$ の3番目だけが1になり、$\bm{r}+\hat{\bm{e}}$ で誤りが打ち消されました。先ほどの手計算の例と完全に一致しています。
BER対符号化利得の評価
最後に、AWGN通信路（BPSK変調＋硬判定）で(7,4)ハミング符号のビット誤り率（BER）を測定し、符号化なしと比較して符号化利得を可視化します。符号化率 $R=4/7$ を考慮して雑音分散を設定します。
import numpy as np
import matplotlib.pyplot as plt
from scipy.special import erfc
np.random.seed(0)
R = k / n # 符号化率 4/7
def simulate_ber(ebn0_db, num_frames=20000):
"""指定 Eb/N0 (dB) でハミング符号と未符号化のBERを測定"""
ebn0 = 10 ** (ebn0_db / 10)
# 符号化時は1符号語あたりEb*Rのエネルギー -> 雑音分散を調整
sigma = np.sqrt(1.0 / (2 * R * ebn0))
coded_err = 0
for _ in range(num_frames):
m = np.random.randint(0, 2, k)
c = encode(m, G)
x = 1 - 2 * c # BPSK: 0->+1, 1->-1
y = x + sigma * np.random.randn(n) # AWGN
r = (y < 0).astype(int) # 硬判定
_, m_hat = decode(r, H, syndrome_table, k)
coded_err += np.sum(m_hat != m)
ber_coded = coded_err / (num_frames * k)
# 未符号化BER（理論値）: 同じEb/N0
ber_uncoded = 0.5 * erfc(np.sqrt(ebn0))
return ber_coded, ber_uncoded
ebn0_range = np.arange(0, 10.5, 1.0)
ber_coded_list, ber_uncoded_list = [], []
for e in ebn0_range:
bc, bu = simulate_ber(e)
ber_coded_list.append(bc)
ber_uncoded_list.append(bu)
ここまでで各 $E_b/N_0$ における符号化BERと未符号化BERを計算しました。未符号化BERは $Q$ 関数（erfc で表現）による理論値、符号化BERはモンテカルロ・シミュレーションで求めています。続いて結果をプロットします。
plt.figure(figsize=(8, 5))
plt.semilogy(ebn0_range, [max(b, 1e-6) for b in ber_uncoded_list],
'b--o', label='Uncoded BPSK (theory)')
plt.semilogy(ebn0_range, [max(b, 1e-6) for b in ber_coded_list],
'r-s', label='(7,4) Hamming code')
plt.xlabel('$E_b/N_0$ (dB)')
plt.ylabel('BER')
plt.title('(7,4) Hamming Code: Coding Gain over Uncoded BPSK')
plt.legend()
plt.grid(True, which='both', alpha=0.3)
plt.ylim(1e-6, 1)
plt.tight_layout()
plt.show()
このグラフから、3つの重要な点が読み取れます。第一に、ある $E_b/N_0$ より高い領域では、ハミング符号のBER曲線（赤）が未符号化（青）より下に来ており、同じ誤り率をより低い送信電力で達成できることが分かります。たとえばBER$=10^{-4}$付近では、ハミング符号は未符号化より約0.5 dB低い $E_b/N_0$ で済みます（BER$=10^{-5}$ では約0.6 dB）。この差が符号化利得です。硬判定・1ビット訂正のみの単純な符号なので利得は控えめですが、それでも確実に存在することが上のシミュレーションから読み取れます。第二に、低 $E_b/N_0$ 領域では符号化BERが未符号化より悪くなる「交差点」が存在します。これは雑音が大きすぎて1符号語あたり2ビット以上の誤りが頻発し、$t=1$ の訂正能力を超えてしまうためで、冗長ビット分だけ実効的に不利になります。第三に、訂正できるのは1ビットまでなので、利得はLDPC符号のような強力な符号には及びませんが、極めて単純な表引き復号でこれだけの利得が得られる点が重要です。
シミュレーションが理論と整合していることを確認できました。最後に全体を振り返りましょう。
まとめ
本記事では、誤り訂正符号の基礎である線形ブロック符号について、ベクトル空間の視点から解説しました。
- 部分空間としての符号: $(n,k)$ 線形ブロック符号は $\mathrm{GF}(2)^n$ の $k$ 次元部分空間で、$2^k$ 個の符号語を含みます。$\mathrm{GF}(2)$ では加算がXOR、$1+1=0$ という性質が理論を簡潔にします
- 生成行列 G: 組織形 $\bm{G}=[\bm{I}_k\mid\bm{P}]$ により、符号化は $\bm{c}=\bm{m}\bm{G}$ で行え、符号語の前半に情報がそのまま現れます
- 検査行列 H とシンドローム: $\bm{H}=[\bm{P}^T\mid\bm{I}_{n-k}]$ は $\bm{G}\bm{H}^T=\bm{0}$ を満たします。シンドローム $\bm{s}=\bm{H}\bm{r}^T=\bm{H}\bm{e}^T$ は送った符号語に依存せず誤りパターンだけで決まる——これが復号の心臓部です
- ハミング距離と訂正能力: 最小距離 $d_{\min}$ は線形符号では零でない符号語の最小重みに等しく、$t=\lfloor(d_{\min}-1)/2\rfloor$ ビットの訂正、$d_{\min}-1$ ビットの検出ができます
- シンドローム復号: 標準配列とコセットリーダーの理論に基づき、シンドローム表を引くだけで高速に誤りを訂正できます
- (7,4)ハミング符号: $d_{\min}=3$ の完全符号で、シンドロームが $\bm{H}$ の列と一致することから1ビット誤りを鮮やかに訂正できます。単一パリティ符号や繰り返し符号との対比で、効率と訂正能力のバランスが理解できます
線形ブロック符号の枠組み——生成行列・検査行列・シンドローム・ハミング距離——は、より強力な現代符号を理解するための共通言語です。ここで学んだ概念は、有限体を $\mathrm{GF}(2^m)$ に拡張したリードソロモン符号や、検査行列をスパースにしたLDPC符号にそのまま受け継がれます。
次のステップとして、以下の記事も参考にしてください。
- LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — 検査行列をスパースにし、シャノン限界に迫る現代符号
- リードソロモン符号の理論と実装 — 有限体を拡張したバースト誤りに強い符号
- CRCによる誤り検出の仕組み — 訂正ではなく検出に特化した実用符号
- ビット誤り率（BER）とは — ディジタル通信の品質指標 — 符号化利得を定量化する基準