Chapter 07

線形符号 — 生成行列・検査行列・シンドローム

なぜ「線形」にこだわるのか. 06 章で「符号とは\(2^n\)個の中から\(2^k\)個を選ぶこと」と定義した。しかし本当に自由に選ぶと、実装が絶望的になる。
符号化: \(2^k\)行の巨大な変換表が要る（\(k=1000\)なら宇宙の原子数を超える）
復号: 受信語と全\(2^k\)個の符号語との距離を比較する必要がある
そこで符号語の集合に「線形空間」という構造を入れる。すると:
符号化が行列の掛け算 1 回になる
誤り検出が行列の掛け算 1 回になる
最小距離が最も軽い符号語 1 つを見るだけで分かる
実用符号（ハミング、CRC、BCH、RS、LDPC）はすべて線形符号である。

1. 定義

\(\mathrm{GF}(2)^n\)（長さ\(n\)のビット列全体）の部分空間になっている符号を線形符号という。すなわち:

\[ c_1, c_2 \in C \Longrightarrow c_1 \oplus c_2 \in C \]

（\(\mathrm{GF}(2)\)ではスカラー倍は 0 倍か 1 倍なので、加法で閉じていれば部分空間。）

当然の帰結: \(c \oplus c = 0\)なので、零ベクトル\(00\cdots0\)は必ず符号語である。

線形性がもたらす第一の恩恵: 最小距離の計算が激減

定理: 線形符号では

\[ d_{\min} = \min_{c \in C, c \neq 0} w(c) \]

（最小距離 = 零でない符号語の最小重み）

導出: \(d(c_1,c_2) = w(c_1 \oplus c_2)\)であり、線形性より\(c_1\oplus c_2\)もまた符号語。逆に任意の非零符号語\(c\)は\(d(c, 0)\)として距離に現れる。よって「全ペアの距離の集合」と「非零符号語の重みの集合」が一致する ∎

計算量が劇的に減る. 素朴には\(\binom{2^k}{2}\)ペアの距離を調べる必要があったが、線形なら\(2^k - 1\)個の重みを見るだけでよい。

2. 生成行列 G — 符号化の装置

定義

符号\(C\)の基底ベクトル\(k\)本を行に並べた\(k \times n\)行列\(G\)を生成行列という。情報語\(m\)（長さ\(k\)の行ベクトル）に対し

\[ \boxed{c = mG} \]

で符号化する。\(m\)を動かすと\(G\)の行の全ての線形結合が得られ、それが\(C\)そのものになる。

組織符号形式（系統形式）

\(G\)を次の形に変形しておくと便利:

\[ G = [I_k \mid P] \]

（\(I_k\)は\(k\times k\)単位行列、\(P\)は\(k \times (n-k)\)行列。）

このとき

\[ c = mG = m[I_k \mid P] = [m \mid mP] \]

となり、符号語の前半にそのまま情報語が現れる。後半\(mP\)が検査ビット（パリティ）。このような符号を組織符号 (systematic code) という。

なぜ組織符号が好まれるのか. 誤りが無ければ、受信語の前半\(k\)ビットを切り出すだけで情報が読める（復号処理が不要）。通信の大部分は誤りが無いので、この「素通しできる」性質は実用上とても大きい。 CRC も「データ + 検査ビット」という組織符号の形をしている。

例: (7,4) ハミング符号の生成行列

\[ G = \begin{bmatrix} 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{bmatrix} \]

情報語\(m = 1011\)を符号化する:

\[ c = mG = (\text{1 行目}) \oplus (\text{3 行目}) \oplus (\text{4 行目}) \]

\[ = 1000110 \oplus 0010011 \oplus 0001111 = 1011010 \]

（各桁を XOR。前半 4 ビット 1011 が情報語そのもの ✓、後半 010 が検査ビット。）

3. 検査行列 H — 誤り検出の装置

定義

すべての符号語\(c\)に対して

\[ \boxed{cH^T = 0} \]

を満たす\((n-k)\times n\)行列\(H\)を検査行列という。言い換えれば、\(H\)の行は符号空間\(C\)に直交するベクトルである。

G と H の関係

\(G = [I_k \mid P]\)のとき

\[ \boxed{H = [P^T \mid I_{n-k}]} \]

導出（この式が条件を満たす確認）:

\[ GH^T = [I_k \mid P]\begin{bmatrix}P\\ I_{n-k}\end{bmatrix} = I_k \cdot P + P\cdot I_{n-k} = P + P = 0 \]

（\(\mathrm{GF}(2)\)では\(P + P = 0\)。） \(GH^T = 0\)なら、任意の符号語\(c=mG\)について\(cH^T = mGH^T = 0\) ✓ ∎

例: (7,4) ハミング符号の検査行列

上の\(G\)の\(P\)は

\[ P = \begin{bmatrix}1&1&0\\1&0&1\\0&1&1\\1&1&1\end{bmatrix} \Longrightarrow H = [P^T \mid I_3] = \begin{bmatrix} 1&1&0&1 & 1&0&0\\ 1&0&1&1 & 0&1&0\\ 0&1&1&1 & 0&0&1 \end{bmatrix} \]

検算: \(c = 1011010\)に対し

1 行目との内積: \(1\cdot1 + 0\cdot1 + 1\cdot0 + 1\cdot1 + 0\cdot1+1\cdot0+0\cdot0 = 1+1 = 0\) ✓
2 行目: \(1\cdot1+0\cdot0+1\cdot1+1\cdot1+0\cdot0+1\cdot1+0\cdot0 = 1+1+1+1 = 0\) ✓
3 行目: \(1\cdot0+0\cdot1+1\cdot1+1\cdot1+0+0+0\cdot1 = 1+1 = 0\) ✓

\(cH^T = 000\) ✓ 符号語である。

4. シンドローム — 誤りの「指紋」

定義と基本性質

受信語\(r\)（誤りを含むかもしれない）に対し

\[ \boxed{s = rH^T} \]

をシンドロームという（症候群、の意）。

送信符号語\(c\)、誤りパターン\(e\)（誤った位置に 1 が立つベクトル）として\(r = c \oplus e\)と書くと:

\[ s = (c \oplus e)H^T = \underbrace{cH^T}_{=0} \oplus eH^T = eH^T \]

これが誤り訂正の核心である. シンドロームは受信語\(r\)に依らず、誤りパターン\(e\)だけで決まる。送ったのが何であれ、同じ場所が壊れれば同じシンドロームが出る。
つまりシンドロームは「どんな誤りが起きたか」だけを抽出した指紋である。
\(s = 0\) → 誤り無し（あるいは符号語に化けるほど大きな誤り）
\(s \neq 0\) → 誤りあり。\(s\)の値から\(e\)を推定して\(r \oplus e\)で復元

シンドローム復号の手順

\(s = rH^T\)を計算
\(s = 0\)なら誤り無しとして終了
\(s \neq 0\)なら、\(eH^T = s\)を満たす最も軽い（重みの小さい）\(e\)を求める
\(c = r \oplus e\)と訂正

なぜ「最も軽い\(e\)」なのか. ビット誤り率が 0.5 未満なら、誤りビット数は少ないほど起こりやすい。「1 ビット誤り」の確率は「3 ビット誤り」よりずっと高い。よって候補の中で最も軽いものを選ぶのが最尤推定（最も確からしい推定）になる。

最小距離を H から読む（重要な定理）

定理: \(d_{\min} = \)「\(H\)の列ベクトルのうち、XOR して 0 になる最小の本数」

導出: \(c\)が符号語 \(\iff\) \(cH^T = 0\) \(\iff\) \(c\)の 1 が立っている位置に対応する\(H\)の列の和が 0。重み\(w\)の符号語が存在する \(\iff\) \(w\)本の列が和 0 になる組み合わせが存在する。線形符号では\(d_{\min}\) = 最小重み（§1）なので、命題が従う ∎

系:

\(H\)に零列があれば\(d_{\min}=1\)（その 1 列だけで和が 0）
\(H\)に同じ列が 2 本あれば\(d_{\min}\leq 2\)
\(H\)の全列が「相異なる非零ベクトル」なら\(d_{\min}\geq 3\) → 1 ビット訂正可能

最後の系が次章のハミング符号の設計原理そのものである. 「\(H\)の列を全部違う非零ベクトルにすればよい」と分かれば、あとは\(n-k\)ビットで作れる非零ベクトルを全部並べるのが最も効率的、という結論が自動的に出る。

5. 双対符号

\(H\)を生成行列とみなして作った\((n, n-k)\)符号を双対符号\(C^\perp\)という。 \(C\)の検査行列が\(C^\perp\)の生成行列、\(C\)の生成行列が\(C^\perp\)の検査行列という美しい対称性がある。

例: 単純パリティ符号\((n, n-1)\)の双対は繰り返し符号\((n,1)\)。

6. 単純な例で全体を確認: 単一パリティ符号

\(k\)ビットに 1 ビットのパリティを付けて\(n = k+1\)とする（全体の 1 の個数が偶数になるように）。

\[ G = [I_k \mid \mathbf{1}], \qquad H = [1\ 1\ \cdots\ 1] \]

シンドロームは 1 ビット: 受信語の全ビットの XOR
\(s=1\)なら奇数個の誤り → 検出
\(d_{\min} = 2\)（重み 2 の符号語が存在: 例 110...0）
よって1 ビット検出、訂正は不可（06 章の定理と一致 ✓）

なぜ訂正できないのか、\(H\)から即座に分かる. \(H\)の列はすべて 1 で、全部同じ。§4 の系より\(d_{\min}\leq 2\)。シンドロームが 1 でも「どの位置が壊れたか」を区別する情報が無い（全列が同じなので）。 区別したければ、列を全部違うものにすればよい——それが次章。

7. まとめ

道具	式	役割
生成行列\(G\)	\(c = mG\)	符号化
組織形式	\(G=[I\mid P]\)	情報がそのまま見える
検査行列\(H\)	\(H=[P^T\mid I]\)、\(cH^T=0\)	符号語かどうかの判定
シンドローム	\(s = rH^T = eH^T\)	誤りだけを抽出した指紋
最小距離	\(H\)の列の最小従属本数	性能の決定