Chapter 07

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

なぜ「線形」にこだわるのか. 06 章では、符号を「\(2^n\)個のビット列から\(2^k\)個を選んだもの」と定義した。 符号語を自由に選ぶと、実装が現実的でなくなる。

• 符号化: 情報語から符号語への\(2^k\)行の対応表が要る。\(k = 1000\)なら\(2^{1000} \approx 10^{301}\)行である。
• 復号: 受信語と\(2^k\)個すべての符号語との距離を比べる必要がある。

そこで符号語の集合に「XOR で閉じている」という構造を入れる。すると次のようになる。

• 符号化は行列の掛け算 1 回で済む（2 節）。
• 誤りの検出も行列の掛け算 1 回で済む（3 節）。
• 最小距離は、0 でない符号語の重みの最小値を見れば分かる（1 節）。

ハミング符号、CRC、BCH 符号、リード・ソロモン符号、LDPC 符号など、実用の誤り訂正符号はすべてこの線形符号である。

この章で使う既出の用語（定義は各リンク先）. \(\mathrm{GF}(2)\)と XOR \(\oplus\)（02 章 4 節）、符号化・\((n,k)\)符号（06 章 1 節）、 ハミング距離\(d(x,y)\)・ハミング重み\(w(x)\)・最小距離\(d_{\min}\)（06 章 2 節）、二項係数\(\binom{n}{2}\)（06 章 4 節）、 検出・訂正能力と\(d_{\min}\)の関係（06 章 3 節）

1. 定義

長さ\(n\)のビット列全体の集合を\(\mathrm{GF}(2)^n\)と書き、ビット列どうしの足し算を位置ごとの XOR \(\oplus\)で定める。すべて 0 のビット列を\(0\)と書く。 空でない部分集合\(C\)が足し算で閉じている、すなわち

を満たすとき、\(C\)を\(\mathrm{GF}(2)^n\)の部分空間といい、部分空間になっている符号を線形符号という。

一般のベクトル空間では「定数倍で閉じている」ことも条件に入る。\(\mathrm{GF}(2)\)の定数は 0 と 1 だけで、1 倍はそのまま、0 倍は\(0\)である。\(C\)の要素\(c\)について\(c \oplus c = 0\)なので\(0\)は必ず\(C\)に入り、定数倍の条件は足し算で閉じていれば自動的に満たされる。 特に、\(0\)は必ず符号語である。

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

定理: 線形符号では、最小距離は 0 でない符号語の重みの最小値に等しい。

方針: 「異なる 2 つの符号語の距離」として現れる値の集合\(A\)と、「0 でない符号語の重み」として現れる値の集合\(B\)が一致することを示す。集合が同じなら最小値も同じである。

導出:

• \(A\)の値は\(B\)に入る: 異なる符号語\(c_1, c_2\)について\(d(c_1,c_2) = w(c_1 \oplus c_2)\)である（06 章 2 節）。線形性より\(c_1\oplus c_2\)は符号語で、\(c_1 \neq c_2\)なので 0 でない。
• \(B\)の値は\(A\)に入る: 0 でない符号語\(c\)について、\(0\)も符号語なので\(w(c) = d(c, 0)\)は異なる 2 つの符号語\(c, 0\)の距離である ∎

素朴には\(2^k\)個の符号語から 2 つを選ぶ\(\binom{2^k}{2}\)組の距離を調べる必要があるが、線形符号なら 0 でない\(2^k - 1\)個の符号語の重みを見るだけでよい。

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

この節の図は\(k = 3\)、\(n = 6\)の線形符号で、生成行列\(G\)と検査行列\(H\)（3 節）、全符号語とその重み、誤りを入れたときのシンドローム（4 節）を表示する。

行列についての最小限の約束

この章から先、ビット列を横に並べたものを行ベクトル、数を長方形に並べたものを行列と呼ぶ。計算はすべて\(\mathrm{GF}(2)\)で行い、足し算は XOR、掛け算は AND である。

• \(k \times n\)行列: 行が\(k\)本、列が\(n\)本ある表。上から\(i\)番目の行を「第\(i\)行」、左から\(j\)番目の列を「第\(j\)列」と呼ぶ。
• 行ベクトル × 行列: 長さ\(k\)の行ベクトル\(m = (m_1, \dots, m_k)\)と\(k \times n\)行列\(G\)の積\(mG\)は、「\(G\)の第\(i\)行を\(m_i\)倍して全部足した」長さ\(n\)の行ベクトルである。\(m_i\)は 0 か 1 なので、\(m\)の 1 が立っている位置の行を XOR したものになる。
• 内積: 同じ長さのベクトル\(a, b\)に対し\(a \cdot b = \sum_i a_i b_i\)。\(\mathrm{GF}(2)\)では「両方 1 の位置の個数が奇数なら 1、偶数なら 0」である。内積が 0 のとき 2 つは直交するという。\(mG\)の第\(j\)成分は、\(m\)と\(G\)の第\(j\)列の内積でもある。
• 行列 × 行列: \(AB\)の第\(i\)行は「\(A\)の第\(i\)行 × \(B\)」である。成分で書けば\((AB)_{ij} = \sum_l A_{il}B_{lj}\)。
• 転置\(A^T\): 行と列を入れ替えた行列。\(A\)の第\(i\)行が\(A^T\)の第\(i\)列になる。
• 単位行列\(I_k\): \(k \times k\)で対角線だけ 1、ほかは 0 の行列。第\(i\)行は\(i\)番目だけが 1 なので、\(m\)の 1 が立つ行を XOR すると\(m\)自身に戻り、\(m I_k = m\)である。
• ブロック行列: 行列を縦や横に並べて 1 つの行列にしたもの。\([A \mid B]\)は横に並べたもの。積は\([A \mid B]\begin{bmatrix}C\\D\end{bmatrix} = AC + BD\)のように、ブロックを数のように扱って計算できる。成分ごとの定義を書き下せば確かめられる。
• 線形結合と基底: ベクトル\(v_1, \dots, v_k\)のいくつかを選んで XOR したものを線形結合という。符号\(C\)のベクトル\(k\)本で、\(C\)の要素がすべてそれらの線形結合としてちょうど 1 通りに書けるものを\(C\)の基底という。\(2^k\)個の符号語を持つ線形符号には、\(k\)本からなる基底が必ずある（証明は線形代数の標準的な事実なので省く）。

定義

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

で符号化する。\(mG\)は「\(m\)の 1 が立つ位置の行を XOR したもの」なので、\(m\)を\(2^k\)通り動かすと基底の線形結合がすべて得られ、それが\(C\)そのものである。基底の定義から、異なる\(m\)は異なる符号語になる。

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

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

\(I_k\)は\(k\times k\)単位行列、\(P\)は\(k \times (n-k)\)行列である。 \(G\)の行を入れ替えたり、ある行に別の行を XOR したりしても、行の線形結合全体（つまり符号\(C\)）は変わらない。この操作で左側を単位行列にでき、うまくいかない場合はビットの位置（列）を並べ替えればよい。 この形のとき、ブロックごとに掛けて\(mI_k = m\)を使うと

となり、符号語の前半\(k\)ビットに情報語がそのまま現れる。後半の\(n-k\)ビット\(mP\)が検査ビットである。このような符号を組織符号という。

組織符号では、誤りが無ければ受信語の前半\(k\)ビットを取り出すだけで情報が読める。多くの受信では誤りが無いので、この性質は実用上大きい。CRC（09 章）も「データ + 検査ビット」という組織符号の形をしている。

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

情報語\(m = 1011\)を符号化する。\(m\)の 1 は 1 番目・3 番目・4 番目にあるので、その行を XOR する:

前半 4 ビット\(1011\)が情報語そのもので、後半\(010\)が検査ビットである。

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

定義

\((n-k)\times n\)行列\(H\)が、長さ\(n\)の任意のビット列\(c\)について

を満たすとき、\(H\)を\(C\)の検査行列という。\(cH^T\)は長さ\(n-k\)の行ベクトルで、その第\(i\)成分は\(c\)と\(H\)の第\(i\)行の内積である。 つまり、\(H\)のどの行とも直交するビット列がちょうど符号語である。左向きの矢印（\(cH^T = 0\)なら符号語）も要求する点が大事で、これが無いと\(H = 0\)のような役に立たない行列も検査行列になってしまう。

G と H の関係

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

は\(C\)の検査行列である。

方針: 符号語なら\(cH^T = 0\)（右向き）と、\(cH^T = 0\)なら符号語（左向き）を別々に示す。

右向き: \(H\)を転置すると、横に並んだブロックが縦に積まれ、各ブロックも転置されるので\(H^T = \begin{bmatrix}P\\ I_{n-k}\end{bmatrix}\)である。ブロックごとに掛けると

\(\mathrm{GF}(2)\)では\(P + P = 0\)である。よって任意の符号語\(c = mG\)について\(cH^T = m(GH^T) = 0\)。

左向き: \(r\)を\(cH^T = 0\)を満たすビット列とし、前半\(k\)ビットを\(u\)、後半\(n-k\)ビットを\(v\)として\(r = [u \mid v]\)と書く。ブロックごとに掛けると

これが 0 なので\(v = uP\)（\(\mathrm{GF}(2)\)では\(-uP = uP\)）。したがって\(r = [u \mid uP] = uG\)であり、\(r\)は情報語\(u\)の符号語である ∎

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

2 節の\(G\)の\(P\)から

検算: \(c = 1011010\)と\(H\)の各行の内積を取る。内積は「両方 1 の位置の個数」の偶奇である。

\(cH^T = 000\)なので、\(c\)は符号語である。

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

定義と基本性質

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

をシンドロームという。医学用語の「症候群」から来た名前で、誤りの症状を表す。

送った符号語を\(c\)、誤りの位置に 1 が立ったビット列（誤りパターン）を\(e\)とすると、\(r = c \oplus e\)である。\(cH^T = 0\)なので

となる。シンドロームは送った符号語\(c\)によらず、誤りパターン\(e\)だけで決まる。何を送っても、同じ場所が壊れれば同じシンドロームが出る。

• \(s = 0\)なら、3 節の定義より\(r\)は符号語である。誤りが無いか、誤りパターン\(e\)自体が 0 でない符号語で、\(r\)が別の符号語に化けているかのどちらかである。後者は\(w(e) \geq d_{\min}\)のときにしか起きない。
• \(s \neq 0\)なら誤りがある。\(s\)から\(e\)を推定し、\(r \oplus e\)で元に戻す。

シンドローム復号の手順

1. \(s = rH^T\)を計算する。
2. \(s = 0\)なら誤り無しとして終了する。
3. \(s \neq 0\)なら、\(eH^T = s\)を満たす\(e\)のうち重みが最小のものを選ぶ。
4. \(c = r \oplus e\)と訂正する。

シンドロームは\(n - k\)ビットなので\(2^{n-k}\)通りしかない。手順 3 は、シンドロームごとに重み最小の\(e\)をあらかじめ求めた\(2^{n-k}\)行の表（シンドローム表）を引けばよい。\(2^k\)個の符号語全部と比べるより、\(n - k\)が小さいときはずっと少ない。

重み最小の\(e\)を選ぶ理由: 各ビットが独立に確率\(p\)で反転するとき、特定の誤りパターン\(e\)（重み\(w\)）が起きる確率は\(p^w (1-p)^{n-w}\)である。\(p < 1/2\)なら\(p/(1-p) < 1\)なので、この確率は\(w\)が小さいほど大きい。 つまり同じシンドロームを出す誤りパターンのうち、重みが最小のものが最も起こりやすい。最も起こりやすいものを選ぶ推定を最尤推定という。

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

定理: 線形符号の最小距離\(d_{\min}\)は、「\(H\)の列を何本か選んで XOR すると 0 になる」ような選び方のうち、最小の本数に等しい。

方針: \(cH^T\)が「\(c\)の 1 が立つ位置に対応する\(H\)の列の XOR」であることを示し、重み\(w\)の符号語と「XOR が 0 になる\(w\)本の列」を対応させる。

導出: \(cH^T\)の第\(i\)成分は\(\sum_j c_j H_{ij}\)である。これを縦に並べると\(\sum_j c_j \times (H \text{ の第 } j \text{ 列})\)、つまり\(c\)の 1 が立っている位置\(j\)に対応する\(H\)の列を XOR したものになる。 2 節の「\(mG\)は\(G\)の行を選んで XOR」と同じ計算を\(H^T\)に対して行っていて、\(H^T\)の行は\(H\)の列だからである。 したがって、\(c\)が符号語であることと、\(c\)の 1 が立つ位置の\(H\)の列の XOR が 0 であることは同じである。 重み\(w\)の 0 でない符号語があることは、\(H\)の\(w\)本の列で XOR が 0 になるものがあることと同じであり、1 節の定理より最小距離は 0 でない符号語の最小の重みなので、命題が従う ∎

系:

• \(H\)に全部 0 の列があれば\(d_{\min}=1\)（その 1 本だけで XOR が 0）。
• \(H\)に同じ列が 2 本あれば\(d_{\min}\leq 2\)（その 2 本の XOR が 0）。
• \(H\)の列がすべて 0 でなく、互いに異なるなら\(d_{\min}\geq 3\)。1 本でも 2 本でも XOR が 0 にならないからである。このとき06 章 3 節より 1 ビットの誤りを訂正できる。

最後の系が次章のハミング符号の設計原理である。\(H\)の列を互いに異なる 0 でないベクトルにすれば 1 ビット訂正できるので、\(n-k\)ビットで作れる 0 でないベクトル\(2^{n-k} - 1\)個を全部並べれば、検査ビット数に対して最も長い符号になる。

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

\(k\)ビットの情報語に、全体の 1 の個数が偶数になるように 1 ビットを付けて\(n = k+1\)とする。

\(\mathbf{1}\)は 1 が\(k\)個縦に並んだ列である。\(mG = [m \mid m \cdot \mathbf{1}]\)で、最後のビットは\(m\)の全ビットの XOR、つまりパリティになる。\(H\)は 3 節の\([P^T \mid I_1]\)で\(P = \mathbf{1}\)としたものである。

• シンドロームは 1 ビットで、受信語の全ビットの XOR である。
• 奇数個のビットが反転すると\(s = 1\)になり、誤りが検出される。
• 重み 2 の符号語（たとえば\(110\cdots0\)）があるので\(d_{\min} = 2\)である。
• したがって 1 ビットまで検出でき、訂正はできない。06 章 3 節の定理と一致する。

訂正できない理由は\(H\)を見れば分かる。\(H\)の列はすべて\(1\)で同じなので、4 節の系より\(d_{\min}\leq 2\)である。 どの位置が 1 ビット反転してもシンドロームは同じ\(1\)で、どこが壊れたかを区別できない。区別できるようにするには、\(H\)の列を互いに異なるものにすればよい。それが次章のハミング符号である。

6. 双対符号

\(C\)の検査行列\(H\)を生成行列とみなして作った\((n, n-k)\)符号を、\(C\)の双対符号といい\(C^\perp\)と書く。\(\perp\)は「直交」を表す記号である。 3 節で\(GH^T = 0\)を示した。これは\(G\)のどの行も\(H\)のどの行とも直交することを意味し、行の線形結合どうしも直交するので、\(C^\perp\)の要素は\(C\)のすべての符号語と直交する。 さらに\(C\)の生成行列\(G\)は\(C^\perp\)の検査行列になっている。つまり\(C\)と\(C^\perp\)は、生成行列と検査行列の役割を入れ替えた関係にある。

例: 5 節の単一パリティ符号\((n, n-1)\)の検査行列は\(H = [1\ 1\ \cdots\ 1]\)（1 行）である。これを生成行列とみなすと情報語は 1 ビットで、符号語は\(0 \cdot H = 00\cdots0\)と\(1 \cdot H = 11\cdots1\)の 2 つになる。これは\(n\)回繰り返し符号\((n, 1)\)である。単一パリティ符号と繰り返し符号は互いに双対である。

7. まとめ