第5章誤り訂正符号（暗号と符号） | Lemma

この章の目標

ハミング距離と最小距離から、符号が何個の誤りを検出・訂正できるかを証明できる

線形符号を生成行列・検査行列で表し、シンドロームと剰余類代表による復号が正しいことを証明できる

ハミング符号を構成し、それが完全符号であることを証明できる

シングルトン限界・ハミング限界・ギルバート–ヴァルシャモフ限界を証明し、作れる符号の範囲を見積もれる

二元対称通信路の容量 $1 - H(p)$ と、シャノンの通信路符号化定理が何を保証し何を保証しないかを説明できる

前提：02-linear-algebra 第3章（核と像・次元定理・商空間）、04-algebra 第8章（有限体 $\mathbb{F}_q$ ）。5.7 節では大数の法則（11-probability 第2章）を直観的な説明にだけ使う。暗号を扱う第1〜4章とは独立に読める。

QR コードは、一部が汚れたり欠けたりしていても読み取れる。ディスクやメモリ、無線の通信でも、途中で起きたビットの誤りが、利用者の気づかないうちに直されている。これを支えているのが誤り訂正符号 (error-correcting code) である。送りたいデータに冗長性（余分な記号）を加えておき、受け取った側で「ありえない受信語」から誤りを見つけて直す。

冗長性の分だけ、送れるデータの量は減る。少ない冗長性で多くの誤りを直すにはどう設計すればよいか、どこまでが原理的に可能か――これが符号理論の中心の問いである。本章では、距離の幾何（5.2 節）、有限体上の線形代数（5.3〜5.5 節）、数え上げ（5.6 節）でこの問いに答え、確率モデルのもとでの限界であるシャノンの定理（5.7 節）を紹介する。符号理論は、シャノンの論文（1948 年）とハミングの論文（1950 年）に始まった。効率よく復号できる実用的な符号は第6章で扱う。

本章では $q$ は素数べき、 $\mathbb{F}_q$ は $q$ 元体である（04-algebra 第8章定理 8.41）。ベクトルは行ベクトルとし、 $x^{\top}$ は転置（02-linear-algebra の ${}^tx$ と同じもの）を表す。

5.1 符号と冗長性

4 ビットのデータをそのまま送ると、1 ビットでも反転すれば別の正しいデータとして受け取られ、誤りに気づくことすらできない。冗長性を加える素朴な方法を 2 つ見よう。

例 5.1（繰り返し符号）各ビットを 3 回ずつ送る： $0 \mapsto 000$ , $1 \mapsto 111$ 。受け取った 3 ビットの多数決をとれば、1 ビットまでの反転は正しく直る。2 ビットが反転すると、誤った値に「直して」しまう。代償として、送るビット数は 3 倍になる。

例 5.2（パリティ検査符号） $k$ ビットのデータ $u_1 \cdots u_k$ の後ろに $u_1 + \cdots + u_k \bmod 2$ を付けて送る。受信語の $1$ の個数が奇数なら誤りがあったとわかる。しかし、どのビットが誤ったかはわからないので訂正はできない。

定義 5.3（符号, code） $q$ 個の元からなる集合 $A$ （アルファベット。多くの場合 $A = \mathbb{F}_q$ ）について、2 個以上の元をもつ部分集合 $C \subset A^n$ を長さ $n$ の符号といい、その元を符号語 (codeword)、 $n$ を符号長 (length)、 $R = (\log_q \lvert C \rvert)/n$ を情報率 (rate) という。 $q = 2$ のとき 2 元符号 (binary code) という。

$\lvert C \rvert = q^k$ なら、 $k$ 個の記号の情報を $n$ 個の記号で送ることになり、 $R = k/n$ である。繰り返し符号は $R = 1/3$ 、パリティ検査符号は $R = k/(k + 1)$ である。冗長性を増やすほど誤りに強くできそうだが、情報率と誤りへの強さはどこまで両立できるだろうか。

5.2 ハミング距離と最小距離

定義 5.4（ハミング距離・重み） $x, y \in A^n$ のハミング距離 (Hamming distance) を、成分が異なる位置の個数 $d(x, y) = \lvert \lbrace i \mid x_i \neq y_i \rbrace \rvert$ で定める。 $x \in \mathbb{F}_q^n$ の重み (weight) を $\operatorname{wt}(x) = d(x, 0)$ （ $0$ でない成分の個数）とする。

命題 5.5 $d$ は $A^n$ 上の距離である。すなわち $d(x, y) \geq 0$ で等号は $x = y$ のときに限り、 $d(x, y) = d(y, x)$ と三角不等式 $d(x, z) \leq d(x, y) + d(y, z)$ が成り立つ。また $x, y \in \mathbb{F}_q^n$ なら $d(x, y) = \operatorname{wt}(x - y)$ である。

証明. 三角不等式以外は定義から明らかである。 $x_i \neq z_i$ なら $x_i \neq y_i$ と $y_i \neq z_i$ の少なくとも一方が成り立つので、 $\lbrace i \mid x_i \neq z_i \rbrace \subset \lbrace i \mid x_i \neq y_i \rbrace \cup \lbrace i \mid y_i \neq z_i \rbrace$ であり、元の個数を比べればよい。最後の主張は $x_i \neq y_i \iff x_i - y_i \neq 0$ による。 $\square$

定義 5.6（最小距離）符号 $C$ の最小距離 (minimum distance) を $d(C) = \min \lbrace d(c, c') \mid c, c' \in C,\ c \neq c' \rbrace$ とする。符号長 $n$ 、符号語の個数 $M$ 、最小距離 $d$ の符号を $(n, M, d)$ 符号という。 $x \in A^n$ を中心とする半径 $r$ の球を $B(x, r) = \lbrace y \in A^n \mid d(x, y) \leq r \rbrace$ とする。

$x$ との距離がちょうど $i$ の元は、異なる位置 $i$ 個の選び方と各位置の値の選び方（ $q - 1$ 通りずつ）で決まるので、球の元の個数は中心によらず

V_q(n, r) = \sum_{i=0}^{r} \binom{n}{i}(q - 1)^i

である。

符号語 $c$ を送って $y \in A^n$ を受け取ったとき、 $d(c, y)$ を誤りの個数という。受信者は $c$ を知らない。

誤り検出：受信者は $y \notin C$ のとき「誤りあり」と判定する。 $1 \leq d(c, y) \leq s$ となるどんな $c \in C$ と $y$ についても $y \notin C$ のとき、 $C$ は $s$ 個までの誤りを検出できるという。
誤り訂正：受信者は $y$ に最も近い符号語（複数あればそのどれか）を、送られた符号語と推定する（最小距離復号, minimum distance decoding）。 $d(c, y) \leq t$ となるどんな $c$ と $y$ についても、 $y$ に最も近い符号語がただ一つで $c$ に等しいとき、 $C$ は $t$ 個までの誤りを訂正できるという。
消失訂正：どの位置の記号が読めなかったか（消失, erasure）を受信者が知っている場合もある。傷で読めない記号や、故障したディスクのデータがその例である。

定理 5.7（検出能力と訂正能力）符号 $C$ の最小距離を $d$ とし、 $t = \lfloor (d - 1)/2 \rfloor$ とする。

$C$ は $d - 1$ 個までの誤りを検出できる。 $d$ 個の誤りで検出されないものがある。

$C$ は最小距離復号で $t$ 個までの誤りを訂正できる。 $t + 1$ 個の誤りで、 $y$ に最も近い符号語が $c$ だけとは限らないものがある。

消失した位置が $d - 1$ 個以下なら、残りの位置の記号から符号語がただ一つに決まる。

証明. (1) $1 \leq d(c, y) \leq d - 1$ で $y \in C$ なら、 $y$ は $c$ との距離が $d$ 未満の別の符号語となり、最小距離の定義に反する。一方、 $d(c, c') = d$ となる符号語 $c \neq c'$ をとり、 $c$ を送って $c'$ を受け取れば、 $d$ 個の誤りは検出されない。

(2) $d \geq 2t + 1$ である。 $d(c, y) \leq t$ とし、 $c' \in C$ , $c' \neq c$ とすると、三角不等式より

d(c', y) \geq d(c, c') - d(c, y) \geq (2t + 1) - t = t + 1 > d(c, y)

となり、 $c$ がただ一つの最も近い符号語である。逆に、 $d(c, c') = d$ となる $c \neq c'$ をとり、両者が異なる $d$ 個の位置のうち $t + 1$ 個では $c'$ の値、ほかの位置では $c$ の値をとる $y$ を作ると、 $d(c, y) = t + 1$ かつ $d(c', y) = d - t - 1 \leq t + 1$ である（ $t \geq (d - 2)/2$ だから）。

(3) 消失していない位置で一致する 2 つの符号語は、高々 $d - 1$ 個の位置でしか異ならないので等しい。 $\square$

例 5.8 繰り返し符号 $\lbrace 000, 111 \rbrace$ は $d = 3$ なので、2 個までの誤りを検出でき、1 個までの誤りを訂正できる。パリティ検査符号は $d = 2$ で、1 個の誤りを検出できるが訂正はできない。ただし、検出能力と訂正能力を同時に使い切ることはできない。繰り返し符号で訂正を行うと、2 個の誤りは検出されずに誤った値に訂正される。

一般に、整数 $0 \leq a \leq b$ が $a + b \leq d - 1$ をみたせば、「距離 $a$ 以内に符号語があればそれに訂正し、なければ誤りありと判定する」という復号で、 $a$ 個までの誤りを訂正し、同時に $b$ 個までの誤りを（誤訂正せずに）検出できる。実際、 $2a + 1 \leq a + b + 1 \leq d$ なので、 $a$ 個以下の誤りは定理 5.7(2) の証明と同じ理由で正しく訂正される。 $a < d(c, y) \leq b$ なら、 $c$ 以外の符号語 $c'$ について $d(c', y) \geq d(c, c') - d(c, y) \geq d - b \geq a + 1$ なので、距離 $a$ 以内に符号語はなく、誤りが検出される。問題 5.5 の符号は $d = 4$ , $a = 1$ , $b = 2$ の例である。誤りと消失が混在する場合は問題 5.4 で扱う。

5.3 線形符号

一般の符号は符号語の一覧で与えるしかなく、 $\lvert C \rvert$ が大きいと符号化も復号も現実的でない。符号を $\mathbb{F}_q^n$ の部分空間にとると、行列で簡潔に記述でき、線形代数が使える。

定義 5.9（線形符号） $\mathbb{F}_q^n$ の $k$ 次元部分空間 $C$ （ $k \geq 1$ ）を、長さ $n$ 、次元 $k$ の線形符号 (linear code) あるいは $[n, k]$ 符号といい、最小距離が $d$ のとき $[n, k, d]$ 符号という。 $\lvert C \rvert = q^k$ で、情報率は $k/n$ である。

命題 5.10 線形符号 $C$ の最小距離は、 $0$ でない符号語の重みの最小値に等しい。

証明. $c \neq c'$ なら $d(c, c') = \operatorname{wt}(c - c')$ で $c - c' \in C \setminus \lbrace 0 \rbrace$ 。逆に $c \neq 0$ なら $\operatorname{wt}(c) = d(c, 0)$ で $0 \in C$ 。 $\square$

定義 5.11（生成行列・検査行列） $[n, k]$ 符号 $C$ について、行が $C$ の基底をなす $k \times n$ 行列 $G$ を生成行列 (generator matrix) という。このとき $C = \lbrace uG \mid u \in \mathbb{F}_q^k \rbrace$ で、 $u \mapsto uG$ を符号化に使う。階数 $n - k$ の $(n - k) \times n$ 行列 $H$ で $C = \lbrace x \in \mathbb{F}_q^n \mid Hx^{\top} = 0 \rbrace$ となるものを検査行列 (parity-check matrix) という。 $G = (I_k \mid A)$ の形の生成行列を標準形という。

標準形の生成行列で符号化すると、符号語の最初の $k$ 個の成分は情報 $u$ そのものになる。このように情報がそのまま符号語に現れる符号化を組織的 (systematic) という。

定理 5.12（生成行列と検査行列） $C$ を $[n, k]$ 符号（ $k < n$ ）とする。

$C$ の生成行列 $G$ と、階数 $n - k$ の $(n - k) \times n$ 行列 $H$ について、 $H$ が $C$ の検査行列であることと $GH^{\top} = O$ は同値である。

$G = (I_k \mid A)$ が $C$ の生成行列なら、 $H = (-A^{\top} \mid I_{n-k})$ は $C$ の検査行列である。

座標の順番を適当に入れかえると、 $C$ は標準形の生成行列をもつ。特に、 $C$ は検査行列をもつ。

証明. (1) $H$ が検査行列なら、 $G$ の各行 $g$ は $C$ に属するので $Hg^{\top} = 0$ 、すなわち $GH^{\top} = O$ 。逆に $GH^{\top} = O$ なら $C \subset C' := \lbrace x \mid Hx^{\top} = 0 \rbrace$ であり、次元定理（02-linear-algebra 第3章定理 3.9）より $\dim C' = n - \operatorname{rank} H = k = \dim C$ なので $C = C'$ 。

(2) $H$ は $I_{n-k}$ を含むので階数 $n - k$ で、 $GH^{\top} = I_k(-A) + AI_{n-k} = O$ 。(1) を使えばよい。

(3) $C$ の生成行列に行基本変形を施して簡約階段行列 $G'$ にする。行の張る空間は変わらないので、 $G'$ も $C$ の生成行列である。 $G'$ の各行の先頭の $1$ を含む $k$ 本の列を前に並べるように座標を入れかえると、生成行列は $(I_k \mid A)$ の形になる。入れかえた符号の検査行列を (2) で作り、列を元の順に戻せば $C$ の検査行列になる。 $\square$

座標の入れかえは重みを変えないので、入れかえて得られる符号（同値な符号という）は同じ $[n, k, d]$ をもつ。最小距離は検査行列の列から読み取れる。これが以下の符号の設計の基本になる。

定理 5.13（検査行列の列と最小距離） $H$ を $m \times n$ 行列とし、 $C = \lbrace x \in \mathbb{F}_q^n \mid Hx^{\top} = 0 \rbrace \neq \lbrace 0 \rbrace$ とする（ $H$ の階数は問わない）。 $C$ の最小距離は、一次従属になる $H$ の列の最小の本数に等しい。特に、 $H$ のどの $d - 1$ 本の列も一次独立なら $d(C) \geq d$ である。

証明. $H$ の列を $h_1, \dots, h_n$ とすると $Hx^{\top} = \sum_i x_ih_i$ である。重み $w$ の符号語 $x \neq 0$ の $0$ でない成分の位置の集合を $S$ とすると $\sum_{i \in S} x_ih_i = 0$ なので、 $w$ 本の列 $h_i$ （ $i \in S$ ）は一次従属である。逆に $w$ 本の列が一次従属で $\sum_j a_jh_{i_j} = 0$ （ $a_j$ のどれかは $0$ でない）なら、第 $i_j$ 成分が $a_j$ でほかが $0$ のベクトルは、重みが $1$ 以上 $w$ 以下の符号語である。命題 5.10 より主張が従う。 $\square$

例 5.14（2 元 $[7, 4, 3]$ 符号）

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}, \qquad 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}

とする。 $G = (I_4 \mid A)$ で、 $\mathbb{F}_2$ では $-A^{\top} = A^{\top}$ なので、 $H = (A^{\top} \mid I_3)$ は $G$ で生成される符号 $C$ の検査行列である（定理 5.12(2)）。 $H$ の 7 本の列 $h_1, \dots, h_7$ は $\mathbb{F}_2^3$ の $0$ でないベクトル 7 個すべてである。 $\mathbb{F}_2$ 上の 2 本のベクトルが一次従属なのは、どちらかが $0$ か両者が等しいときに限るので、どの 2 本の列も一次独立である。一方 $h_1 = h_5 + h_6$ である。定理 5.13 より $d(C) = 3$ 。16 個の符号語の重みは、 $0$ が 1 個、 $3$ が 7 個、 $4$ が 7 個、 $7$ が 1 個である（計算機で確かめた）。

5.4 シンドローム復号

最小距離復号を素朴に行うと、 $q^k$ 個の符号語すべてと距離を比べることになる。検査行列を使うと、手間を $q^{n-k}$ 行の表に移せる。以下 $C$ を $[n, k]$ 符号、 $H$ をその検査行列とする。

定義 5.15（シンドローム・剰余類代表） $y \in \mathbb{F}_q^n$ に対し $s(y) = Hy^{\top} \in \mathbb{F}_q^{n-k}$ を $y$ のシンドローム (syndrome) という。 $C$ による剰余類（02-linear-algebra 第3章定義 3.32） $y + C$ の中で重みが最小の元を、その剰余類の剰余類代表（coset leader。コセットリーダーともいう）という。

命題 5.16 $s(y) = s(y') \iff y - y' \in C \iff y + C = y' + C$ 。 $y + C \mapsto s(y)$ は剰余類全体から $\mathbb{F}_q^{n-k}$ への全単射であり、剰余類はちょうど $q^{n-k}$ 個ある。

証明. $s$ は線形写像で $\operatorname{Ker} s = C$ だから最初の同値が成り立ち、2 つめは剰余類の定義そのものである。 $\operatorname{rank} H = n - k$ より $s$ は全射なので、 $y + C \mapsto s(y)$ は well-defined な全単射である（02-linear-algebra 第3章定理 3.34 の特別な場合）。 $\square$

シンドローム復号 (syndrome decoding)：各 $\sigma \in \mathbb{F}_q^{n-k}$ について、シンドロームが $\sigma$ の剰余類の代表 $e_\sigma$ を 1 つ選んで表にしておく。 $y$ を受け取ったら $\sigma = s(y)$ を計算し、 $\hat{c} = y - e_\sigma$ を出力する。

定理 5.17（シンドローム復号の正しさ） $c \in C$ を送って $y = c + e$ を受け取ったとし、 $t = \lfloor (d(C) - 1)/2 \rfloor$ とする。

$\hat{c}$ は $C$ の元であり、 $y$ に最も近い符号語の一つである。すなわち、シンドローム復号は最小距離復号である。

$\hat{c} = c$ となるのは、誤り $e$ が表に選んだ代表 $e_{s(y)}$ に一致するときに限る。

$\operatorname{wt}(e) \leq t$ なら、 $e$ は剰余類 $e + C$ のただ一つの剰余類代表である。したがって、シンドローム復号は $t$ 個までの誤りをすべて訂正する。

証明. (1) $\sigma = s(y)$ とすると $s(e_\sigma) = \sigma$ なので、命題 5.16 より $\hat{c} = y - e_\sigma \in C$ 。任意の $c' \in C$ について $y - c' \in y + C$ なので、代表の最小性より $d(y, c') = \operatorname{wt}(y - c') \geq \operatorname{wt}(e_\sigma) = d(y, \hat{c})$ 。

(2) $e = y - c \in y + C$ より $s(e) = s(y)$ であり、 $\hat{c} = c \iff y - e_{s(y)} = y - e \iff e = e_{s(y)}$ 。

(3) $e' \in e + C$ , $e' \neq e$ とすると、 $e' - e$ は $0$ でない符号語なので $\operatorname{wt}(e' - e) \geq 2t + 1$ であり、三角不等式より $\operatorname{wt}(e') \geq \operatorname{wt}(e' - e) - \operatorname{wt}(e) \geq t + 1 > \operatorname{wt}(e)$ 。 $\square$

(2) から、誤りが確率的に起こる通信路で正しく復号される確率は、「誤りが表の代表のどれかに一致する確率」に等しい（例 5.30）。

例 5.18（ $[7, 4, 3]$ 符号のシンドローム復号）例 5.14 の符号で、情報 $u = (1, 0, 1, 1)$ を $c = uG = (1, 0, 1, 1, 0, 1, 0)$ に符号化して送り、第 6 成分が反転して $y = (1, 0, 1, 1, 0, 0, 0)$ を受け取ったとする。 $y$ の $1$ の位置は第 1, 3, 4 成分なので

s(y) = h_1 + h_3 + h_4 = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} = h_6

である。第 $j$ 成分だけが $1$ のベクトル $\varepsilon_j$ のシンドロームは $h_j$ で、 $H$ の列は $0$ でないベクトルをちょうど 1 回ずつ尽くすので、8 個の剰余類の代表は $0$ と $\varepsilon_1, \dots, \varepsilon_7$ である。したがって復号は「シンドロームに等しい列の位置を反転する」だけでよい。第 6 成分を反転して $c$ が復元され、最初の 4 成分から $u$ を得る。 $H$ の列を、第 $j$ 列が $j$ の 2 進表示になるように並べかえておけば、シンドロームを 2 進数として読むと誤りの位置がわかる（ハミングの元々の構成）。

補足

剰余類代表の表は $q^{n-k}$ 行あるので、 $n - k$ が大きい符号では作れない。実際、一般の線形符号の最小距離復号は NP 困難な問題である（Berlekamp, McEliece, van Tilborg, 1978 年）。実用の符号は、効率よく復号できる代数的な構造をもつように作る（第6章）。逆に、構造を隠した線形符号の復号の難しさは、マックエリス暗号などの「符号に基づく暗号」の安全性の根拠として使われている。

5.5 ハミング符号と完全符号

例 5.14 の符号は、検査行列の列に $0$ でないベクトルを重複なく全部並べたものだった。これを一般化する。

定義 5.19（ハミング符号, Hamming code） $r \geq 2$ とする。 $\mathbb{F}_q^r$ の 1 次元部分空間それぞれから $0$ でないベクトルを 1 つずつ選ぶ。1 次元部分空間は $n = (q^r - 1)/(q - 1)$ 個ある（ $0$ でない $q^r - 1$ 個のベクトルが $q - 1$ 個ずつに分かれる）。選んだベクトルを列とする $r \times n$ 行列 $H_r$ について、 $\operatorname{Ham}_q(r) = \lbrace x \in \mathbb{F}_q^n \mid H_rx^{\top} = 0 \rbrace$ をハミング符号という。 $q = 2$ なら $H_r$ の列は $\mathbb{F}_2^r$ の $0$ でないベクトル全部で、 $n = 2^r - 1$ である。

定義 5.20（完全符号, perfect code）最小距離 $d = 2t + 1$ の符号 $C \subset A^n$ について、半径 $t$ の球 $B(c, t)$ （ $c \in C$ ）の和集合が $A^n$ 全体になるとき、 $C$ を完全符号という。

これらの球はどの 2 つも交わらない。 $y \in B(c, t) \cap B(c', t)$ なら $d(c, c') \leq 2t < d$ だからである。したがって完全符号では、どの受信語にも距離 $t$ 以内の符号語がちょうど一つある。

定理 5.21 ハミング符号 $\operatorname{Ham}_q(r)$ は $[n, n - r, 3]$ 符号（ $n = (q^r - 1)/(q - 1)$ ）であり、完全符号である。

証明. 基本ベクトル $e_i$ の張る 1 次元部分空間を代表する列 $a_ie_i$ （ $a_i \neq 0$ ）が各 $i$ についてあるので、 $\operatorname{rank} H_r = r$ であり、次元定理より $\dim \operatorname{Ham}_q(r) = n - r$ 。 $H_r$ のどの 2 本の列も、 $0$ でなく異なる 1 次元部分空間に属するので一次独立である。一方、 $\langle e_1 \rangle$ , $\langle e_2 \rangle$ , $\langle e_1 + e_2 \rangle$ を代表する列 $ae_1$ , $be_2$ , $c(e_1 + e_2)$ は $ca^{-1}(ae_1) + cb^{-1}(be_2) - c(e_1 + e_2) = 0$ をみたす。定理 5.13 より $d = 3$ 、 $t = 1$ 。半径 1 の球は互いに交わらず、元の個数の合計は

q^{n-r} \cdot V_q(n, 1) = q^{n-r}\bigl(1 + n(q - 1)\bigr) = q^{n-r} \cdot q^r = q^n

なので、球の和集合は $\mathbb{F}_q^n$ 全体である。 $\square$

復号は例 5.18 と同じで、 $0$ でないシンドローム $\sigma$ は $H_r$ のただ一つの列 $h_j$ の定数倍 $\lambda h_j$ なので、第 $j$ 成分から $\lambda$ を引けばよい。 $\operatorname{Ham}_2(3)$ は例 5.14 の $[7, 4, 3]$ 符号（と同値な符号）、 $\operatorname{Ham}_2(4)$ は $[15, 11, 3]$ 符号である。

注意

「1 個の誤りを訂正できる」符号に 2 個の誤りが起きると、復号器は気づかずに誤った答えを出しうる。 $[7, 4, 3]$ 符号は完全符号なので、 $d(c, y) = 2$ の $y$ にも距離 1 の符号語 $c' \neq c$ がちょうど一つあり、復号結果は必ず $c'$ になる。たとえば例 5.18 の $c$ の第 2, 5 成分が反転すると、シンドロームは $h_7$ で、復号結果は $1111111$ になる。2 個の誤りの 21 通りすべてがこのように誤訂正される（計算機で確かめた）。

注意 5.22（ほかの完全符号）全体 $A^n$ や奇数長の 2 元繰り返し符号は自明な完全符号である。ハミング符号のほかに、2 元 $[23, 12, 7]$ 符号と 3 元 $[11, 6, 5]$ 符号（ゴレイ符号, Golay codes）が完全符号である：

2^{12}\left(1 + 23 + \binom{23}{2} + \binom{23}{3}\right) = 2^{12} \cdot 2^{11}, \qquad 3^6\left(1 + 2 \cdot 11 + 2^2\binom{11}{2}\right) = 3^6 \cdot 3^5

2 元ゴレイ符号は、 $x^{23} - 1$ の 11 次の既約因子 $x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1$ を生成多項式とする巡回符号（第6章）として作れる（最小距離 7 は計算機で確かめた）。 $q$ が素数べきのとき、非自明な完全符号はハミング符号かゴレイ符号と同じパラメータ $(n, M, d)$ をもつものに限る（ヴァン・リントらの先行研究を受けて、1973 年にティエタヴァイネンと、独立にジノヴィエフとレオンチェフが証明した。主張のみ。証明は MacWilliams–Sloane の第6章や van Lint の教科書の第7章を参照）。

ヒント

実務では サーバーなどの ECC メモリでは、64 ビットのデータに 8 ビットの検査ビットを加えた 72 ビット単位の符号が広く使われてきた。たとえば $\operatorname{Ham}_2(7)$ （ $[127, 120, 3]$ ）の情報ビットを 64 個に減らした（短縮した） $[71, 64, 3]$ 符号に全体のパリティを 1 ビット加えると $[72, 64, 4]$ 符号になり、1 ビットの誤りを訂正し 2 ビットの誤りを検出できる（SEC-DED。問題 5.5）。訂正できた誤りも記録しておき、同じ場所で訂正が繰り返されるなら故障を疑う、という運用が一般的である。

5.6 符号の限界

$q$ 元のアルファベット上の長さ $n$ 、最小距離 $d$ 以上の符号の符号語の個数の最大値を $A_q(n, d)$ とする。訂正能力と情報率の交換条件を定量化するのが、次の限界式である。

定理 5.23（シングルトン限界, Singleton bound） $q$ 元の $(n, M, d)$ 符号について $M \leq q^{n-d+1}$ 。特に $[n, k, d]$ 線形符号について $d \leq n - k + 1$ 。

証明. 各符号語の最後の $d - 1$ 個の成分を取り除く写像 $C \to A^{n-d+1}$ は単射である。像が等しい 2 つの符号語は高々 $d - 1$ 個の位置でしか異ならないからである。よって $M \leq q^{n-d+1}$ 。 $\square$

定義 5.24（MDS 符号） $d = n - k + 1$ をみたす $[n, k, d]$ 線形符号を MDS 符号（maximum distance separable code）という。

$\mathbb{F}_q^n$ 全体（ $[n, n, 1]$ ）、 $\lbrace x \mid \sum_i x_i = 0 \rbrace$ （ $[n, n - 1, 2]$ ）、繰り返し符号（ $[n, 1, n]$ ）は MDS 符号である。2 元ではこれら以外に MDS 符号はない（問題 5.6）。第6章のリード–ソロモン符号は、 $n \leq q$ の範囲で任意の $k$ について MDS 符号を与える。

定理 5.25（ハミング限界, Hamming bound） $q$ 元の $(n, M, d)$ 符号について、 $t = \lfloor (d - 1)/2 \rfloor$ とすると $M \cdot V_q(n, t) \leq q^n$ 。等号が成り立つのは完全符号のときに限る。

証明. 半径 $t$ の球 $B(c, t)$ （ $c \in C$ ）は互いに交わらない（定義 5.20 の後の注意）ので、元の個数の和 $M \cdot V_q(n, t)$ は $q^n$ 以下で、等号は球が全体を覆うときに限る。 $d = 2t + 2$ なら球は全体を覆わない。実際、 $d(c, c') = d$ となる $c, c'$ について、両者が異なる位置のうち $t + 1$ 個で $c'$ の値、ほかで $c$ の値をとる $y$ は、 $d(c, y) = t + 1$ で、 $c'' \neq c$ なら $d(y, c'') \geq d - (t + 1) = t + 1$ なので、どの球にも入らない。よって等号は $d$ が奇数で完全符号のときに限る。 $\square$

ハミング限界は球充填限界 (sphere-packing bound) ともいう。ここまでの 2 つは「これより良い符号はない」という上界である。逆に、良い符号の存在を保証するのが次の定理である。

定理 5.26（ギルバート–ヴァルシャモフ限界, Gilbert–Varshamov bound）

（ギルバートの限界。一般の符号） $1 \leq d \leq n$ なら $A_q(n, d) \geq q^n/V_q(n, d - 1)$ 。

（ヴァルシャモフの限界。線形符号） $2 \leq d \leq n$ , $1 \leq k < n$ とする。 $V_q(n - 1, d - 2) < q^{n-k}$ ならば、最小距離 $d$ 以上の $[n, k]$ 線形符号が存在する。

証明. (1) 最小距離 $d$ 以上の符号のうち符号語が最も多いもの $C$ をとる。ある $y \in A^n$ がすべての $c \in C$ と距離 $d$ 以上なら、 $C \cup \lbrace y \rbrace$ も最小距離 $d$ 以上で、最大性に反する。よって $A^n = \bigcup_{c \in C} B(c, d - 1)$ であり、 $q^n \leq \lvert C \rvert \cdot V_q(n, d - 1)$ 。

(2) 列 $h_1, \dots, h_n \in \mathbb{F}_q^{n-k}$ を、どの $d - 1$ 本も一次独立になるように順に選ぶ。 $h_1, \dots, h_{j-1}$ （ $1 \leq j \leq n$ ）がこの性質をもつとする。それらのうち高々 $d - 2$ 本の一次結合で書けるベクトルは、 $0$ でない係数をもつ列と係数の選び方を数えて、高々

\sum_{i=0}^{d-2}\binom{j - 1}{i}(q - 1)^i \leq V_q(n - 1, d - 2) < q^{n-k}

個しかない（ $i = 0$ の項は零ベクトル）。そこで $h_j$ をそれら以外から選ぶ。 $h_1, \dots, h_j$ の中の高々 $d - 1$ 本に非自明な一次関係があったとすると、帰納法の仮定よりそれは $h_j$ を $0$ でない係数で含むので、 $h_j$ がほかの高々 $d - 2$ 本の一次結合になり、選び方に反する。こうして作った $H = (h_1 \ \cdots \ h_n)$ について、 $C = \lbrace x \mid Hx^{\top} = 0 \rbrace$ は次元定理より $\dim C \geq k$ で、定理 5.13 より最小距離は $d$ 以上である。 $C$ の $k$ 次元部分空間をとればよい（最小距離は減らない）。 $\square$

(1) と (2) をまとめて GV 限界と呼ぶことが多い。本章では、一般の符号についての (1) と、線形符号についての (2) の両方を証明した。

例 5.27（限界の比較）2 元線形符号について、長さ $n$ と最小距離 $d$ を与えたときの次元 $k$ を比べる（数値は計算機で確かめた）。

$(n, d)$	シングルトン限界	ハミング限界	ヴァルシャモフの限界で存在が保証される $k$	知られている符号
$(7, 3)$	$k \leq 5$	$k \leq 4$	$4$	ハミング符号 $[7, 4, 3]$
$(15, 5)$	$k \leq 11$	$k \leq 8$	$6$	BCH 符号 $[15, 7, 5]$ （第6章）
$(23, 7)$	$k \leq 17$	$k \leq 12$	$7$	ゴレイ符号 $[23, 12, 7]$
$(31, 5)$	$k \leq 27$	$k \leq 22$	$18$	BCH 符号 $[31, 21, 5]$ （第6章）

たとえば $(15, 5)$ では、ハミング限界は $2^k \cdot V_2(15, 2) = 2^k \cdot 121 \leq 2^{15}$ より $k \leq 8$ を与え、ヴァルシャモフの限界は $V_2(14, 3) = 470 < 2^9$ より $n - k = 9$ で成り立つ。上界と下界の間にはすき間があり、その間のどこに最良の符号があるかは、一般には分かっていない。

符号長を大きくしたときの振る舞いは、2 元エントロピー関数

H(x) = -x\log_2 x - (1 - x)\log_2(1 - x) \quad (0 < x < 1), \qquad H(0) = H(1) = 0

で表される。ヴァルシャモフの限界から、相対距離 $d/n \geq \delta$ （ $0 < \delta \leq 1/2$ ）で情報率がほぼ $1 - H(\delta)$ 以上の 2 元線形符号が存在する（問題 5.7）。相対距離 $\delta$ を保ったまま $1 - H(\delta)$ より真に大きい情報率を達成する、いくらでも長い 2 元符号の族があるかどうかは、有名な未解決問題である（ $q \geq 49$ が平方数のときは、代数曲線を使う符号（代数幾何符号）が、相対距離のある範囲で $q$ 元の GV 限界を超えることが知られている。最初の例は 1982 年のツファスマン、ヴラドゥツ、ジンクの結果である）。

5.7 二元対称通信路とシャノンの定理

ここまでは「 $t$ 個までの誤りなら必ず直す」という最悪の場合の保証を考えてきた。実際の通信路では誤りは確率的に起こるので、確率のモデルを置くと別の限界が見えてくる。

定義 5.28（二元対称通信路, binary symmetric channel） $0 \leq p < 1/2$ とする。送った各ビットが、ほかのビットと独立に確率 $p$ で反転する通信路を、反転確率 $p$ の二元対称通信路といい、 $\mathrm{BSC}(p)$ と書く。

$c \in \mathbb{F}_2^n$ を送って $y$ を受け取る確率は $P(y \mid c) = p^{d(c, y)}(1 - p)^{n - d(c, y)}$ である。

命題 5.29（最尤復号と最小距離復号） $0 < p < 1/2$ とする。受信語 $y$ について $P(y \mid c)$ を最大にする符号語 $c$ を選ぶこと（最尤復号, maximum likelihood decoding）は、 $y$ に最も近い符号語を選ぶことと同じである。

証明. $P(y \mid c) = (1 - p)^n\bigl(p/(1 - p)\bigr)^{d(c, y)}$ で $0 < p/(1 - p) < 1$ なので、 $P(y \mid c)$ は $d(c, y)$ について狭義単調減少である。 $\square$

例 5.30（誤り率の比較） $\mathrm{BSC}(0.01)$ で 4 ビットの情報を送る。

符号化しない：4 ビットのどれかが反転する確率は $1 - 0.99^4 \approx 0.0394$ 。
$[7, 4, 3]$ 符号：剰余類代表は重み 1 以下のベクトル全部なので（例 5.18）、定理 5.17(2) より正しく復号される確率は $(1 - p)^7 + 7p(1 - p)^6$ で、誤る確率は約 $0.00203$ （20 万ブロックを送るシミュレーションでも、誤ったブロックの割合はおよそ $0.002$ になる）。情報率は $4/7$ 。
各ビットを 3 回繰り返す：1 ビットあたりの誤り確率は $3p^2(1 - p) + p^3 \approx 0.000298$ で、4 ビットのどれかを誤る確率は約 $0.00119$ 。ただし情報率は $1/3$ 。

繰り返しの回数を増やせば誤り確率はいくらでも小さくなるが、情報率は $0$ に近づく。情報率を一定に保ったまま、誤り確率を $0$ に近づけることはできるだろうか。シャノンの答えは「ある値までの情報率なら可能」である。 $\mathrm{BSC}(p)$ の通信路容量 (channel capacity) を、5.6 節の $H$ を使って $1 - H(p)$ と定める。 $1 - H(0.01) \approx 0.919$ , $1 - H(0.05) \approx 0.714$ , $1 - H(0.1) \approx 0.531$ である。

定理 5.31（シャノンの通信路符号化定理, noisy-channel coding theorem。 $\mathrm{BSC}(p)$ の場合） $0 \leq p < 1/2$ とする。

（達成可能性） $R < 1 - H(p)$ と $\varepsilon > 0$ を任意にとると、十分大きいすべての $n$ について、符号語を $2^{Rn}$ 個以上もつ長さ $n$ の 2 元符号で、最尤復号の誤り確率が、どの符号語を送った場合にも $\varepsilon$ 未満になるものが存在する。

（逆定理） $R > 1 - H(p)$ ならば、ある $\eta > 0$ があって、符号語を $2^{Rn}$ 個以上もつ長さ $n$ のどんな符号とどんな復号法についても、送る符号語を一様に選んだときの誤り確率は、十分大きい $n$ で $\eta$ 以上になる。

本章ではこの定理を証明しない（主張のみ。BSC の場合の証明は van Lint の教科書の第2章にある）。逆定理の状況では、誤り確率は実は $1$ に近づくことも知られている（強い逆定理）。証明ではないが、定理の意味を直観的に述べておく。

長さ $n$ のブロックで反転するビットの個数は、大数の法則（11-probability 第2章）より、ほとんどの場合 $np$ 前後である。そのような誤りのパターンはおよそ $2^{nH(p)}$ 通りある（問題 5.7 の評価と比べよ）。
正しく復号するには、各符号語のまわりの「ありそうな受信語」約 $2^{nH(p)}$ 個の集まりがほとんど重ならない必要がある。受信語は全部で $2^n$ 個なので、符号語は高々 $2^{n(1 - H(p))}$ 個程度しか置けない。これが逆定理の直観である。
シャノンは、符号語をランダムに選んだ符号の誤り確率の平均が、 $R < 1 - H(p)$ なら $n \to \infty$ で $0$ に近づくことを示した。平均が小さいので、誤り確率が小さい符号が存在する（ランダムな線形符号でもよい）。

注意

シャノンの定理は存在定理であり、(i) 必要な符号長、(ii) 効率のよい符号化・復号法、(iii) 誤りが独立でない通信路（バースト誤り）や敵対的な誤りについては何も述べない。また、この定理の符号は「ランダムに起こる $np$ 個前後の誤り」を高い確率で直すのであって、「 $np$ 個以下のどんな誤りも直す」わけではない。後者には最小距離が $2np$ を超える必要があり、たとえば $p \geq 1/4$ ならそのような 2 元符号の情報率は $n \to \infty$ で $0$ に近づく（プロトキン限界。証明は省略する）。

ヒント

実務では シャノンの限界に近い性能を実用的な計算量で達成する符号が現れたのは 1990 年代以降である（ターボ符号、1960 年代にギャラガーが考案し再発見された LDPC 符号、2009 年にアリカンが提案した極符号など）。5G の移動通信規格（3GPP NR）では、データに LDPC 符号、制御情報に極符号が採用されている。一方、誤りがまとまって起こる記録媒体や QR コードでは、第6章のリード–ソロモン符号が使われる。通信路のモデル（独立な誤りか、バーストか、消失か）を見誤ると、理論上の性能は出ない。

まとめ

最小距離 $d$ の符号は、 $d - 1$ 個までの誤りを検出し、 $\lfloor (d - 1)/2 \rfloor$ 個までの誤りを訂正し、 $d - 1$ 個までの消失を訂正できる。検出能力と訂正能力は同時には使い切れない（ $a \leq b$ , $a + b \leq d - 1$ なら、 $a$ 個までの訂正と $b$ 個までの検出を両立できる）。
線形符号 $[n, k, d]$ は生成行列 $G$ と検査行列 $H$ （ $GH^{\top} = O$ ）で表される。最小距離は $0$ でない符号語の最小の重みであり、一次従属になる $H$ の列の最小の本数でもある。
シンドローム $Hy^{\top}$ は剰余類 $y + C$ を決める。剰余類代表を引くシンドローム復号は最小距離復号であり、正しく復号されるのは誤りが表の代表に一致するときに限る。
ハミング符号 $[n, n - r, 3]$ （ $n = (q^r - 1)/(q - 1)$ ）は完全符号で、シンドロームが誤りの位置を直接示す。
シングルトン限界 $d \leq n - k + 1$ （等号は MDS 符号）とハミング限界 $M \cdot V_q(n, t) \leq q^n$ （等号は完全符号）は上界、ギルバート–ヴァルシャモフ限界は存在を保証する下界である。
$\mathrm{BSC}(p)$ では最尤復号は最小距離復号に一致する。容量 $1 - H(p)$ 未満の情報率なら誤り確率をいくらでも小さくでき、超えるとできない（シャノン。主張のみ）。
訂正能力を超える誤りは気づかれずに誤訂正されうる。シャノンの定理は独立な誤りのモデルでの存在定理であり、符号長・復号法・バースト誤りについては何も言わない。

演習問題

問題 5.1 ★ 例 5.14 の $[7, 4, 3]$ 符号で、受信語 $y = (0, 1, 0, 0, 1, 1, 0)$ と $y' = (1, 1, 1, 0, 0, 0, 1)$ をシンドローム復号し、送られた情報 $u$ を求めよ（誤りは高々 1 個とする）。

解答

$y$ の $1$ の位置は第 2, 5, 6 成分なので、 $s(y) = h_2 + h_5 + h_6 = (1, 0, 1)^{\top} + (1, 0, 0)^{\top} + (0, 1, 0)^{\top} = (0, 1, 1)^{\top} = h_3$ 。第 3 成分を反転して $c = (0, 1, 1, 0, 1, 1, 0)$ 、 $u = (0, 1, 1, 0)$ 。検算： $uG$ は $G$ の第 2 行と第 3 行の和で、 $c$ に一致する。

$y'$ の $1$ の位置は第 1, 2, 3, 7 成分なので、 $s(y') = (1, 1, 0)^{\top} + (1, 0, 1)^{\top} + (0, 1, 1)^{\top} + (0, 0, 1)^{\top} = (0, 0, 1)^{\top} = h_7$ 。第 7 成分を反転して $c' = (1, 1, 1, 0, 0, 0, 0)$ 、 $u = (1, 1, 1, 0)$ 。検算： $G$ の第 1〜3 行の後半 3 成分の和は $(1, 1, 0) + (1, 0, 1) + (0, 1, 1) = (0, 0, 0)$ である。

問題 5.2 ★ (1) 2 個の誤りを訂正できる 2 元 $[10, 6]$ 線形符号は存在しないことを示せ。(2) 2 元 $[10, 6, 3]$ 線形符号は存在することを示せ。

解答

(1) 2 個の誤りを訂正できるなら $d \geq 5$ である（定理 5.7(2) の後半より、 $d \leq 4$ では 2 個の誤りの訂正は保証されない）。ハミング限界（ $t = 2$ ）より $2^6 \cdot V_2(10, 2) \leq 2^{10}$ が必要だが、 $V_2(10, 2) = 1 + 10 + 45 = 56$ で $2^6 \cdot 56 = 3584 > 1024$ 。

(2) ヴァルシャモフの限界（ $n = 10$ , $k = 6$ , $d = 3$ ）で $V_2(9, 1) = 10 < 2^4$ なので、最小距離 3 以上の $[10, 6]$ 符号が存在する。具体的には、 $\mathbb{F}_2^4$ の $0$ でない相異なる 10 個のベクトル（基本ベクトル $e_1, \dots, e_4$ と $e_1 + e_2$ を含める）を列とする $4 \times 10$ 行列を検査行列とすればよい。階数は 4 で、どの 2 本の列も一次独立なので $d \geq 3$ 、列 $e_1, e_2, e_1 + e_2$ は一次従属なので $d = 3$ である（定理 5.13）。

問題 5.3 ★★ 2 元 $[5, 2]$ 符号 $C$ の生成行列を $G = (I_2 \mid A)$ とし、 $A$ の 2 つの行を $(1, 1, 0)$ と $(0, 1, 1)$ とする。 $C$ の符号語と最小距離を求め、剰余類代表の表を作れ。代表が一意でない剰余類があることを確かめ、受信語 $y = 11000$ を最小距離復号するとどうなるかを答えよ。

解答

$C = \lbrace 00000, 10110, 01011, 11101 \rbrace$ で、 $0$ でない符号語の重みは $3, 3, 4$ なので $d = 3$ 。検査行列は $H = (A^{\top} \mid I_3)$ で、その列は $h_1 = 110$ , $h_2 = 011$ , $h_3 = 100$ , $h_4 = 010$ , $h_5 = 001$ （縦ベクトルを横に書いた）である。剰余類は $2^3 = 8$ 個あり、重み 1 の $\varepsilon_j$ のシンドローム $h_j$ は相異なる。残る 2 つのシンドロームは $101 = h_3 + h_5 = h_1 + h_2$ と $111 = h_2 + h_3 = h_1 + h_5$ で、代表には重み 2 のものが 2 つずつある。

シンドローム	代表
$000$	$00000$
$h_1, \dots, h_5$	$\varepsilon_1, \dots, \varepsilon_5$ （ $10000, \dots, 00001$ ）
$101$	$00101$ または $11000$
$111$	$01100$ または $10001$

$4 \cdot V_2(5, 1) = 24 < 32$ なので $C$ は完全符号でなく、重み 1 以下の代表だけでは剰余類を尽くせないことと整合する。 $y = 11000$ のシンドロームは $h_1 + h_2 = 101$ で、代表に $00101$ を選べば $11101$ 、 $11000$ を選べば $00000$ に復号される。実際 $d(y, 00000) = d(y, 11101) = 2$ , $d(y, 10110) = d(y, 01011) = 3$ で、最も近い符号語が 2 つある。 $t = 1$ なので 2 個の誤りは訂正できない。

問題 5.4 ★★ 最小距離 $d$ の符号で、 $e$ 個の消失（位置は既知）と $t$ 個の誤りが同時に起きたとする。 $2t + e \leq d - 1$ なら、正しく復号できることを示せ。（ヒント：消失した位置を取り除いた符号を考える。）

解答

消失した位置の集合を $E$ とし、 $x \in A^n$ から $E$ の成分を取り除いたものを $x'$ とする。相異なる $c, \tilde{c} \in C$ について $d(c', \tilde{c}') \geq d(c, \tilde{c}) - e \geq d - e \geq 2t + 1$ なので、 $c \mapsto c'$ は単射で、 $C' = \lbrace c' \mid c \in C \rbrace$ は最小距離 $2t + 1$ 以上の符号である。受信語の読めた部分 $y'$ は、送った符号語の $c'$ と $E$ の外の誤りの位置でだけ異なるので $d(c', y') \leq t$ 。 $C'$ に定理 5.7(2) を使うと、 $c'$ は $y'$ に最も近いただ一つの符号語であり、単射性から $c$ が決まる。 $e = 0$ が定理 5.7(2)、 $t = 0$ が定理 5.7(3) である。

問題 5.5 ★★ $d$ が奇数の 2 元 $[n, k, d]$ 符号の各符号語の末尾に全体のパリティ（成分の和）を付け加えた符号は、 $[n + 1, k, d + 1]$ 符号であることを示せ。また、 $[7, 4, 3]$ 符号から得られる $[8, 4, 4]$ 符号で、受信語 $y$ について $\sigma = H(y_1, \dots, y_7)^{\top}$ と $\pi = y_1 + \cdots + y_8$ を計算し、「 $\pi = 1$ なら誤りは 1 個として、 $\sigma = 0$ なら第 8 成分を、 $\sigma = h_j$ なら第 $j$ 成分を反転する。 $\pi = 0$ かつ $\sigma \neq 0$ なら 2 個の誤りを検出したと報告する」という復号法が、1 個の誤りをすべて訂正し、2 個の誤りをすべて誤訂正せずに検出することを示せ。

解答

付け加えた後の重みは、元の重み以上の最小の偶数である。 $0$ でない符号語の重みは $d$ 以上で $d$ は奇数なので、付け加えた後の重みは $d + 1$ 以上であり、重み $d$ の符号語からは重み $d + 1$ の符号語ができる。付け加える写像は単射な線形写像なので、 $[n + 1, k, d + 1]$ 符号を得る。

$[8, 4, 4]$ 符号の符号語は $\sigma = 0$ , $\pi = 0$ をみたす。1 個の誤りなら $\pi = 1$ で、それが第 $j$ 成分（ $j \leq 7$ ）なら $\sigma = h_j$ 、第 8 成分なら $\sigma = 0$ なので、正しく訂正される。2 個の誤りなら $\pi = 0$ である。それが第 $i, j$ 成分（ $i, j \leq 7$ ）なら $\sigma = h_i + h_j \neq 0$ （列は相異なる）、一方が第 8 成分なら $\sigma = h_j \neq 0$ 。いずれも「2 個の誤りを検出」と報告される。

問題 5.6 ★★ $2 \leq k \leq n - 2$ のとき、2 元 $[n, k, n - k + 1]$ 線形符号（MDS 符号）は存在しないことを示せ。

解答

そのような符号 $C$ があったとする。座標の入れかえは重みを変えないので、定理 5.12(3) より生成行列は $G = (I_k \mid A)$ としてよい。 $G$ の第 $i$ 行の重みは $1 + \operatorname{wt}(a_i)$ （ $a_i$ は $A$ の第 $i$ 行で、長さ $n - k$ ）で、これが $n - k + 1$ 以上なので $\operatorname{wt}(a_i) = n - k$ 、すなわち $A$ の成分はすべて $1$ である。すると第 1 行と第 2 行の和（ $k \geq 2$ ）は $(1, 1, 0, \dots, 0)$ で、重みは $2$ である。しかし $n - k \geq 2$ より $d = n - k + 1 \geq 3$ なので矛盾する。

問題 5.7 ★★ (1) $0 < \lambda \leq 1/2$ なら $V_2(n, \lfloor \lambda n \rfloor) \leq 2^{nH(\lambda)}$ であることを示せ。（ヒント： $1 = (\lambda + (1 - \lambda))^n$ を二項展開する。） (2) $0 < \delta \leq 1/2$ かつ $n(1 - H(\delta)) > 1$ とする。最小距離が $\delta n$ 以上で $k \geq n(1 - H(\delta)) - 1$ となる 2 元 $[n, k]$ 線形符号が存在することを示せ。

解答

(1) $m = \lfloor \lambda n \rfloor$ とする。 $\lambda/(1 - \lambda) \leq 1$ なので、 $i \leq m \leq \lambda n$ なら $\bigl(\lambda/(1 - \lambda)\bigr)^i \geq \bigl(\lambda/(1 - \lambda)\bigr)^{\lambda n}$ 。よって

1 \geq \sum_{i=0}^{m}\binom{n}{i}\lambda^i(1 - \lambda)^{n-i} = (1 - \lambda)^n\sum_{i=0}^{m}\binom{n}{i}\left(\frac{\lambda}{1 - \lambda}\right)^i \geq \lambda^{\lambda n}(1 - \lambda)^{(1 - \lambda)n}V_2(n, m)

で、 $\lambda^{\lambda n}(1 - \lambda)^{(1 - \lambda)n} = 2^{-nH(\lambda)}$ である。

(2) $d = \lceil \delta n \rceil$ とする。 $d \leq 1$ なら $[n, n - 1, 2]$ 符号でよい。 $d \geq 2$ とし、 $k = \lceil n(1 - H(\delta)) \rceil - 1$ とおくと、仮定より $1 \leq k \leq n - 1$ 、また $d \leq n$ 。 $d - 2 < \delta n - 1 < \lfloor \delta n \rfloor$ なので、(1) より $V_2(n - 1, d - 2) \leq V_2(n, \lfloor \delta n \rfloor) \leq 2^{nH(\delta)}$ 。一方 $n - k = n + 1 - \lceil n(1 - H(\delta)) \rceil > nH(\delta)$ なので $2^{n-k} > 2^{nH(\delta)}$ 。定理 5.26(2) より、最小距離 $d$ 以上（したがって $\delta n$ 以上）の $[n, k]$ 線形符号が存在し、 $k \geq n(1 - H(\delta)) - 1$ である。

問題 5.8 ★★ ある担当者が「誤り率 10% の通信路なので、情報率 0.6 の符号を使い、符号長を十分大きくすれば、ブロック誤り率を $10^{-9}$ 以下にできる。シャノンの定理が保証している」と提案した。この主張を評価せよ。誤り率が 5% ならどうか。

解答

通信路を $\mathrm{BSC}(0.1)$ とみなすと、容量は $1 - H(0.1) \approx 0.531$ で、情報率 $0.6$ はこれを超える。定理 5.31(2) より、符号長をいくら大きくしても誤り確率はある正の数より小さくできない（実際には $1$ に近づく）。提案は誤りで、シャノンの定理はむしろ不可能性を示している。

誤り率 5% なら容量は約 $0.714 > 0.6$ なので、定理 5.31(1) より、十分長い符号で誤り確率を $10^{-9}$ 未満にできる符号は存在する。ただし (i) 必要な符号長、(ii) 実用的な時間で復号できるかは定理から分からないので、具体的な符号と復号法で評価する必要がある。(iii) 定理は誤りが独立に起こるという仮定に依存しており、実際の通信路で誤りがまとまって起こるなら、その対策（インターリーブなど。第6章）も要る。