# 線形符号：生成行列・検査行列・符号の限界式 > Hamming 距離と誤り訂正能力の関係から始め、線形符号を生成行列・検査行列・双対符号で記述する。Singleton・Hamming・Gilbert–Varshamov・Plotkin・Griesmer の各限界、Hamming 符号、二元対称通信路の符号化定理を数え上げで証明する。 > https://rikai.mugen-giken.com/mathematics/finite-fields-coding/linear-codes ## 0. この記事の要点 0 と 1 の列を、ときどきビットが反転する通信路で送るとき、列に余分な情報を付けておけば、受け取った側で誤りに気づいたり直したりできます。この記事では、余分な情報の付け方（符号）をどう決めればよいか、またどれだけうまく付けられるかには限界があるのか、を数え上げと線形代数で調べます。読み終えると、符号の「強さ」を表す数を計算でき、7 ビットの符号で 1 ビットの誤りを実際に直せるようになります。 - 符号は $\mathbb{F}_q^n$ の部分集合で、符号語どうしの Hamming 距離の最小値 $d$ が性能を決めます。最小距離 $d$ の符号は $d - 1$ 個までの誤りを検出し、$\lfloor (d-1)/2 \rfloor$ 個までの誤りを訂正します。 - 線形符号は $\mathbb{F}_q^n$ の[部分空間](/mathematics/linear-algebra/vector-spaces#def-subspace)です。生成行列 $G$（[基底](/mathematics/linear-algebra/vector-spaces#def-independence-basis)を並べた行列）と検査行列 $H$（符号を核とする行列）の 2 通りで記述でき、$H$ は双対符号 $C^{\perp}$ の生成行列です。 - 最小距離は、検査行列の列のうち一次従属になる最小の本数に等しくなります。符号の設計は「どの $d - 1$ 本も一次独立な列を集める」問題になります。 - 符号長 $n$、次元 $k$、最小距離 $d$ は同時には大きくできません。Singleton 限界 $d \le n - k + 1$、Hamming 限界（球充填）、Plotkin 限界、Griesmer 限界が上から抑え、Gilbert–Varshamov 限界が「ここまでは必ず作れる」ことを保証します。 - Hamming 符号は Hamming 限界を等号で満たす完全符号（符号語を中心とする球で空間をすき間なく埋め尽くす符号。§5 で定義します）で、双対の単体符号はすべての符号語の重みが等しくなります。 - 誤り率 $p < 1/2$ の二元対称通信路（各ビットが独立に確率 $p$ で反転する通信路）では、情報率が $1 - H(p)$（$H$ は §7 の二元エントロピー関数）より小さければ、復号誤り確率をいくらでも小さくする線形符号が存在します（Shannon の符号化定理の順方向）。 ## 1. 動機 $0$ と $1$ の列を、ときどきビットが反転する通信路で送るとします。そのまま送れば、受け取った側は誤りがあったかどうかも分かりません。そこで送る列に冗長な部分を付け加えます。最も素朴なのは同じビットを 3 回送る方法で、$0 \mapsto 000$、$1 \mapsto 111$ とすれば、1 個のビットが反転しても多数決で直せます。ただし通信量は 3 倍になります。 もっと上手な方法があります。4 ビットの情報に 3 ビットの検査ビットを付け加えた 7 ビットを送ると、どの 1 ビットが反転しても直せます（Hamming 符号）。通信量は $7/4$ 倍で済みます。違いを生むのは、冗長な部分の作り方、つまり「送ってよい列の集合」の選び方です。 この記事の問いは 2 つです。第 1 に、よい符号とは何で、どう記述するか。答えは「符号語どうしが Hamming 距離で遠く離れた集合」で、それを部分空間に限ると線形代数の言葉（生成行列・検査行列）で書けます。第 2 に、符号の良さにはどんな限界があるか。答えは数え上げによるいくつかの不等式です。 文字の集合は [第 1 章](/mathematics/finite-fields-coding/structure-of-finite-fields) の有限体 $\mathbb{F}_q$（$q = p^e$ 個の元をもつ体。）とします。ここで定める語彙は、[第 4 章](/mathematics/finite-fields-coding/cyclic-bch-reed-solomon) の巡回符号と [第 5 章](/mathematics/finite-fields-coding/weight-enumerators-golay) の重み分布でそのまま使います。Singleton 限界を等号で満たすのが Reed–Solomon 符号、Hamming 限界を等号で満たすのが Hamming 符号と Golay 符号です。 ## 2. Hamming 距離と誤り訂正能力 $\mathbb{F}_q^n$ の元は行ベクトル $\boldsymbol{x} = (x_1, \ldots, x_n)$ で書き、誤解のないときは成分を並べて $1011$ のようにも書きます。 $\boldsymbol{x}, \boldsymbol{y} \in \mathbb{F}_q^n$ に対し、 $$ d(\boldsymbol{x}, \boldsymbol{y}) = \#\{\, i : x_i \ne y_i \,\}, \qquad \mathrm{wt}(\boldsymbol{x}) = \#\{\, i : x_i \ne 0 \,\} = d(\boldsymbol{x}, \boldsymbol{0}) $$ をそれぞれ **Hamming 距離**、**Hamming 重み**という。$\{i : x_i \ne 0\}$ を $\boldsymbol{x}$ の**台**といい $\mathrm{supp}(\boldsymbol{x})$ と書く。 すべての $\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z} \in \mathbb{F}_q^n$ について次が成り立つ。 1. $d(\boldsymbol{x}, \boldsymbol{y}) \ge 0$ で、$d(\boldsymbol{x}, \boldsymbol{y}) = 0 \iff \boldsymbol{x} = \boldsymbol{y}$。 2. $d(\boldsymbol{x}, \boldsymbol{y}) = d(\boldsymbol{y}, \boldsymbol{x})$。 3. $d(\boldsymbol{x}, \boldsymbol{z}) \le d(\boldsymbol{x}, \boldsymbol{y}) + d(\boldsymbol{y}, \boldsymbol{z})$。 4. $d(\boldsymbol{x} + \boldsymbol{z}, \boldsymbol{y} + \boldsymbol{z}) = d(\boldsymbol{x}, \boldsymbol{y}) = \mathrm{wt}(\boldsymbol{x} - \boldsymbol{y})$。また $a \in \mathbb{F}_q^{\times}$ なら $\mathrm{wt}(a\boldsymbol{x}) = \mathrm{wt}(\boldsymbol{x})$。 (1)(2) は定義から直接分かります（成分が 1 つも異ならないことは 2 つのベクトルが等しいことです）。 (3) $x_i \ne z_i$ なら、$x_i \ne y_i$ または $y_i \ne z_i$ です（どちらも等しければ $x_i = y_i = z_i$）。したがって $\{i : x_i \ne z_i\} \subseteq \{i : x_i \ne y_i\} \cup \{i : y_i \ne z_i\}$ で、元の個数を比べれば不等式が出ます。 (4) $x_i + z_i \ne y_i + z_i \iff x_i \ne y_i \iff x_i - y_i \ne 0$ です。$a \ne 0$ なら $a x_i \ne 0 \iff x_i \ne 0$ です。 $\mathbb{F}_q^n$ の空でない部分集合 $C$ を（$\mathbb{F}_q$ 上の）長さ $n$ の**符号**、その元を**符号語**という。$|C| \ge 2$ のとき $$ d(C) = \min\{\, d(\boldsymbol{c}, \boldsymbol{c}') : \boldsymbol{c}, \boldsymbol{c}' \in C,\ \boldsymbol{c} \ne \boldsymbol{c}' \,\} $$ を $C$ の**最小距離**という。長さ $n$、符号語の個数 $M$、最小距離 $d$ の符号を $(n, M, d)_q$ 符号という。$R = \dfrac{\log_q M}{n}$ を**情報率**、$\delta = d/n$ を**相対距離**という。 受信語 $\boldsymbol{y} \in \mathbb{F}_q^n$ に対し、$d(\boldsymbol{c}, \boldsymbol{y})$ が最小になる符号語 $\boldsymbol{c}$ の 1 つを出力する復号を**最小距離復号**という。 符号語 $\boldsymbol{c}$ を送って $\boldsymbol{y}$ を受け取ったとき、$\boldsymbol{e} = \boldsymbol{y} - \boldsymbol{c}$ を**誤りベクトル**といい、$\mathrm{wt}(\boldsymbol{e}) = d(\boldsymbol{c}, \boldsymbol{y})$ を誤りの個数といいます。 $C$ を最小距離 $d$ の符号とし、$t = \lfloor (d - 1)/2 \rfloor$ とする。$\boldsymbol{c} \in C$、$\boldsymbol{y} \in \mathbb{F}_q^n$ とする。 1. （検出）$1 \le d(\boldsymbol{c}, \boldsymbol{y}) \le d - 1$ ならば $\boldsymbol{y} \notin C$ である。 2. （訂正）$d(\boldsymbol{c}, \boldsymbol{y}) \le t$ ならば、$\boldsymbol{c}$ 以外のすべての符号語 $\boldsymbol{c}'$ について $d(\boldsymbol{c}', \boldsymbol{y}) > t \ge d(\boldsymbol{c}, \boldsymbol{y})$ である。したがって最小距離復号は $\boldsymbol{c}$ を出力する。 3. （限界）$d(\boldsymbol{c}, \boldsymbol{y}) = d$ かつ $\boldsymbol{y} \in C$ となる $\boldsymbol{c}, \boldsymbol{y}$ が存在する。また、$d(\boldsymbol{c}, \boldsymbol{y}) = t + 1$ かつ、ある符号語 $\boldsymbol{c}' \ne \boldsymbol{c}$ について $d(\boldsymbol{c}', \boldsymbol{y}) \le t + 1$ となる $\boldsymbol{c}, \boldsymbol{y}$ が存在する。 (1) $\boldsymbol{y} \in C$ なら、$\boldsymbol{y} \ne \boldsymbol{c}$ なので最小距離の定義から $d(\boldsymbol{c}, \boldsymbol{y}) \ge d$ となり、仮定に反します。 (2) $\boldsymbol{c}' \in C$、$\boldsymbol{c}' \ne \boldsymbol{c}$ とします。三角不等式（ の 3）より $$ d(\boldsymbol{c}', \boldsymbol{y}) \ge d(\boldsymbol{c}, \boldsymbol{c}') - d(\boldsymbol{c}, \boldsymbol{y}) \ge d - t \ge t + 1 $$ です。最後の不等号は $2t \le d - 1$ によります。 (3) 最小距離を実現する $\boldsymbol{c}, \boldsymbol{c}' \in C$（$d(\boldsymbol{c}, \boldsymbol{c}') = d$）を取ります。$\boldsymbol{y} = \boldsymbol{c}'$ とすれば前半です。後半は、$\boldsymbol{c}$ と $\boldsymbol{c}'$ が異なる $d$ 個の座標のうち $t + 1$ 個（$t + 1 \le d$）で $\boldsymbol{c}$ の成分を $\boldsymbol{c}'$ の成分に書き換えたものを $\boldsymbol{y}$ とします。$d(\boldsymbol{c}, \boldsymbol{y}) = t + 1$、$d(\boldsymbol{c}', \boldsymbol{y}) = d - (t + 1)$ で、$d \le 2t + 2$ なので $d - (t + 1) \le t + 1$ です。
c c' d = 5 t = 2
(2) は「各符号語を中心とする半径 $t$ の球が互いに交わらない」ことを言っています。$d = 3$ なら 1 個の誤りを訂正でき、$d = 4$ なら 1 個を訂正しつつ 2 個の誤りの存在を検出でき、$d = 5$ なら 2 個を訂正できます。 ## 3. 線形符号 ### 3.1. 生成行列と最小重み $\mathbb{F}_q^n$ の部分空間 $C$ を**線形符号**という。$\dim C = k$ のとき $[n, k]_q$ 符号、さらに最小距離が $d$ のとき $[n, k, d]_q$ 符号という。$C$ の基底 $\boldsymbol{g}_1, \ldots, \boldsymbol{g}_k$ を行として並べた $k \times n$ 行列 $G$ を $C$ の**生成行列**という。 $[n, k]_q$ 符号の符号語は $q^k$ 個で、情報率は $k/n$ です。生成行列を使うと、情報 $\boldsymbol{u} \in \mathbb{F}_q^k$ を符号語 $\boldsymbol{u}G = \sum_i u_i \boldsymbol{g}_i$ に写す符号化 $\mathbb{F}_q^k \to C$ が線形同型として書けます。$q^k$ 個の符号語を覚えておく代わりに、$k$ 個の基底だけを持てば済むのが線形符号の第 1 の利点です。 $C \ne \{\boldsymbol{0}\}$ を線形符号とすると、$d(C) = \min\{\, \mathrm{wt}(\boldsymbol{c}) : \boldsymbol{c} \in C,\ \boldsymbol{c} \ne \boldsymbol{0} \,\}$ である。 右辺を $w$ とします。$\boldsymbol{c} \ne \boldsymbol{c}'$ を符号語とすると、$\boldsymbol{c} - \boldsymbol{c}'$ は $C$ の $\boldsymbol{0}$ でない元で、 の 4 より $d(\boldsymbol{c}, \boldsymbol{c}') = \mathrm{wt}(\boldsymbol{c} - \boldsymbol{c}') \ge w$ です。よって $d(C) \ge w$ です。逆に重み $w$ の符号語 $\boldsymbol{c}$ について $d(\boldsymbol{c}, \boldsymbol{0}) = w$ で、$\boldsymbol{0} \in C$ なので $d(C) \le w$ です。 一般の符号では最小距離を求めるのに $\binom{M}{2}$ 組の比較が要りますが、線形符号では $M - 1$ 個の重みを見れば済みます。 $C$ を $[n, k]_q$ 符号とする。座標の順序を適当に入れ替えると、$C$ は $G = [\,I_k \mid A\,]$（$I_k$ は $k$ 次単位行列、$A$ は $k \times (n - k)$ 行列）の形の生成行列をもつ。 生成行列 $G_0$ から始めて、行基本変形（行の交換、行の $0$ でない定数倍、ある行の定数倍を別の行に加える）と列の交換を行います。行基本変形は行の張る空間 $C$ を変えず、行の一次独立性も保ちます。列の交換は座標の入れ替えです。 $j = 1, 2, \ldots, k$ の順に次を行います。この時点で第 $1$ 列から第 $j - 1$ 列までは単位行列の対応する列になっているとします。第 $j$ 行は $\boldsymbol{0}$ でなく（行は一次独立）、第 $1, \ldots, j - 1$ 成分は $0$ なので、第 $j$ 列以降に $0$ でない成分があります。列を交換してそれを $(j, j)$ 成分に移し、第 $j$ 行を定数倍して $(j, j)$ 成分を $1$ にし、ほかの行から第 $j$ 行の定数倍を引いて第 $j$ 列のほかの成分を $0$ にします。第 $j$ 行の第 $1, \ldots, j-1$ 成分は $0$ なので、この操作ですでに整えた列は変わりません。$k$ 回繰り返すと左の $k$ 列が $I_k$ になります。 標準形では $\boldsymbol{u}G = (\boldsymbol{u}, \boldsymbol{u}A)$ で、符号語の最初の $k$ 成分が情報そのもの、残りの $n - k$ 成分が検査記号になります。このような符号化を**組織符号化**といいます。 ### 3.2. 双対符号と検査行列 $\boldsymbol{x}, \boldsymbol{y} \in \mathbb{F}_q^n$ に対し $\boldsymbol{x} \cdot \boldsymbol{y} = \sum_{i=1}^{n} x_i y_i \in \mathbb{F}_q$ と書きます。これは対称な双線形形式です。 線形符号 $C \subseteq \mathbb{F}_q^n$ に対し $$ C^{\perp} = \{\, \boldsymbol{y} \in \mathbb{F}_q^n : \boldsymbol{x} \cdot \boldsymbol{y} = 0\ (\forall \boldsymbol{x} \in C) \,\} $$ を $C$ の**双対符号**という。$C \subseteq C^{\perp}$ のとき $C$ は**自己直交**、$C = C^{\perp}$ のとき**自己双対**であるという。 行が一次独立な行列 $H$ が $C = \{\boldsymbol{x} \in \mathbb{F}_q^n : H\boldsymbol{x}^{\mathsf{T}} = \boldsymbol{0}\}$ を満たすとき、$H$ を $C$ の**検査行列**という。 $C$ を $[n, k]_q$ 符号、$G$ をその生成行列とする。 1. $C^{\perp}$ は $[n, n - k]_q$ 符号である。 2. $(C^{\perp})^{\perp} = C$。 3. $C^{\perp} = \{\boldsymbol{y} : G\boldsymbol{y}^{\mathsf{T}} = \boldsymbol{0}\}$ である。また、行列 $H$ が $C$ の検査行列であることと、$H$ が $C^{\perp}$ の生成行列であることは同値である。特に検査行列は $(n - k) \times n$ 行列である。 4. $G = [\,I_k \mid A\,]$ ならば、$H = [\,-A^{\mathsf{T}} \mid I_{n-k}\,]$ は $C$ の検査行列である。 この定理の証明の中心は、$\boldsymbol{y}$ に「$\boldsymbol{x}$ との内積を取る線形形式」を対応させる写像 $\Theta$ です。$\Theta$ が同型だと分かれば、$C^{\perp}$ を双対空間の中の零化空間として捉えられ、次元が $n - k$ だと既知の次元公式から読み取れます。 (1) $V = \mathbb{F}_q^n$ とし、$\Theta : V \to V^{*}$ を $\Theta(\boldsymbol{y})(\boldsymbol{x}) = \boldsymbol{x} \cdot \boldsymbol{y}$ で定めます。$\Theta$ は線形です。$\Theta(\boldsymbol{y}) = 0$ なら、標準基底 $\boldsymbol{e}_i$ について $y_i = \boldsymbol{e}_i \cdot \boldsymbol{y} = 0$ なので $\boldsymbol{y} = \boldsymbol{0}$、つまり $\Theta$ は単射です。$\dim V^{*} = n$（ の 1）なので $\Theta$ は線形同型です（）。定義から、$\boldsymbol{y} \in C^{\perp}$ は $\Theta(\boldsymbol{y})$ が $C$ の上で $0$ になること、つまり $\Theta(\boldsymbol{y})$ が $C$ の零化空間 $C^{0}$（）に属することと同値です。よって $C^{\perp} = \Theta^{-1}(C^{0})$ は部分空間で、零化空間の次元公式（ の 1）より $\dim C^{\perp} = \dim C^{0} = n - k$ です。 (2) $\boldsymbol{x} \in C$ はすべての $\boldsymbol{y} \in C^{\perp}$ と直交するので $C \subseteq (C^{\perp})^{\perp}$ です。(1) を $C^{\perp}$ に使うと $\dim (C^{\perp})^{\perp} = n - (n - k) = k = \dim C$ なので、両者は一致します（ の 3）。 (3) $G$ の行 $\boldsymbol{g}_1, \ldots, \boldsymbol{g}_k$ は $C$ を張るので、$\boldsymbol{y}$ が $C$ のすべての元と直交することは、すべての $\boldsymbol{g}_i$ と直交することと同値です（$\boldsymbol{x} \cdot \boldsymbol{y}$ は $\boldsymbol{x}$ について線形）。$G\boldsymbol{y}^{\mathsf{T}}$ の第 $i$ 成分は $\boldsymbol{g}_i \cdot \boldsymbol{y}$ なので、前半が出ます。 $H$ が $C^{\perp}$ の生成行列なら、前半を符号 $C^{\perp}$ に使って $\{\boldsymbol{x} : H\boldsymbol{x}^{\mathsf{T}} = \boldsymbol{0}\} = (C^{\perp})^{\perp} = C$ で、$H$ の行は一次独立なので $H$ は $C$ の検査行列です。逆に $H$ を $C$ の検査行列とし、$H$ の行が張る空間を $D$ とします。$H$ は $D$ の生成行列で、前半より $D^{\perp} = \{\boldsymbol{x} : H\boldsymbol{x}^{\mathsf{T}} = \boldsymbol{0}\} = C$、(2) より $D = (D^{\perp})^{\perp} = C^{\perp}$ です。行数は $\dim C^{\perp} = n - k$ です。 (4) $H$ の右側の $n - k$ 列が単位行列なので、$H$ の行は一次独立です。$H$ の行が張る空間を $D$ とすると $\dim D = n - k$ です。ブロックごとに計算して $$ H G^{\mathsf{T}} = [\,-A^{\mathsf{T}} \mid I_{n-k}\,] \begin{bmatrix} I_k \\ A^{\mathsf{T}} \end{bmatrix} = -A^{\mathsf{T}} + A^{\mathsf{T}} = O $$ です。これは $H$ の各行が $G$ の各行と直交することを意味するので $D \subseteq C^{\perp}$ で、次元が等しいので $D = C^{\perp}$ です。(3) より $H$ は $C$ の検査行列です。 **反復符号** $\mathrm{Rep}_n = \{(a, a, \ldots, a) : a \in \mathbb{F}_q\}$ は $[n, 1, n]_q$ 符号で、生成行列は $G = [\,1\ 1\ \cdots\ 1\,]$ です。$\lfloor (n-1)/2 \rfloor$ 個の誤りを訂正しますが、情報率は $1/n$ です。 その双対は の 3 より $\{\boldsymbol{y} : y_1 + \cdots + y_n = 0\}$ で、$q = 2$ のときは重みが偶数のベクトルの全体です。これを**パリティ検査符号**といいます。$[n, n-1, 2]_q$ 符号で（重み 1 のベクトルは成分の和が $0$ でないので含まれず、$(1, -1, 0, \ldots, 0)$ は含まれます）、情報率は $(n-1)/n$ と高いですが、1 個の誤りを検出するだけで訂正はできません。 この 2 つは「情報率」と「最小距離」の両極端にあります。符号理論の主題は、その中間によい符号を見つけることです。 $H$ を $\mathbb{F}_q$ 成分で $n$ 列の行列、$\boldsymbol{h}_1, \ldots, \boldsymbol{h}_n$ をその列とし、$C = \{\boldsymbol{x} \in \mathbb{F}_q^n : H\boldsymbol{x}^{\mathsf{T}} = \boldsymbol{0}\}$ が $\{\boldsymbol{0}\}$ でないとする。このとき $C$ の最小距離は、$H$ の列から一次従属な $s$ 本を選べるような最小の $s$ に等しい。特に、$d(C) \ge \delta$ であることと、$H$ のどの $\delta - 1$ 本の列も一次独立であることは同値である。 $H\boldsymbol{x}^{\mathsf{T}} = \sum_{i=1}^{n} x_i \boldsymbol{h}_i$ なので、$\boldsymbol{x} \in C$ は $\sum_i x_i \boldsymbol{h}_i = \boldsymbol{0}$ と同値です。 $\boldsymbol{x} \in C$ を重み $w \ge 1$ の符号語とすると、$\sum_{i \in \mathrm{supp}(\boldsymbol{x})} x_i \boldsymbol{h}_i = \boldsymbol{0}$ は台に対応する $w$ 本の列の自明でない一次関係なので、一次従属な $w$ 本の列があります。逆に、$s$ 本の列 $\boldsymbol{h}_{i_1}, \ldots, \boldsymbol{h}_{i_s}$ が一次従属で、すべては $0$ でない係数で $\sum_j a_j \boldsymbol{h}_{i_j} = \boldsymbol{0}$ とすると、第 $i_j$ 成分が $a_j$ でほかが $0$ のベクトルは $C$ の $\boldsymbol{0}$ でない元で、重みは $s$ 以下です。 したがって、$C$ の $\boldsymbol{0}$ でない元の重みの最小値と、一次従属な列の本数の最小値は一致します。前者は より $d(C)$ です。後半は前半の言い換えです（一次従属な列の集合に列を足しても一次従属なので、「$\delta - 1$ 本以下のどの列も一次独立」は「どの $\delta - 1$ 本も一次独立」と同じです）。 この定理が線形符号の第 2 の利点です。最小距離という組合せ的な量が、行列の列の一次独立性という線形代数の条件に変わります。最小距離 $3$ の符号が欲しければ、「どの 2 本も一次独立」、つまり $\boldsymbol{0}$ を含まず互いに定数倍でない列を集めればよいことになります。これをぎりぎりまで集めたのが §6 の Hamming 符号です。 2 つの線形符号 $C, C' \subseteq \mathbb{F}_q^n$ が**同値**であるとは、座標の置換と、各座標に $0$ でない定数を掛ける操作の組み合わせで $C$ が $C'$ に写ることをいう。 どちらの操作も線形同型で、 の 4 と同じ理由で重みを変えないので、同値な符号は同じ $n, k, d$ をもちます。 **ISBN-10。** 10 桁の数字 $x_1 x_2 \cdots x_{10}$ を $\mathbb{F}_{11}$ の元の列とみて、条件 $$ \sum_{i=1}^{10} i\, x_i = 0 \quad (\mathbb{F}_{11} \text{ において}) $$ を課します（値 $10$ は文字 X で表し、最後の桁にだけ現れます）。これは検査行列 $H = [\,1\ 2\ \cdots\ 10\,]$ の $[10, 9]_{11}$ 符号です。$H$ の列はどれも $0$ でなく（どの 1 本も一次独立）、どの 2 本も一次従属なので、 より最小距離は $2$ で、1 個の誤りを検出します。さらに、異なる 2 つの桁 $i, j$ の入れ替えも検出します。入れ替えによる左辺の変化は $(i - j)(x_j - x_i)$ で、$x_i \ne x_j$ なら $\mathbb{F}_{11}$ が体なので $0$ になりません。$10 \equiv -1$ なので、最後の桁は $x_{10} = \sum_{i=1}^{9} i\,x_i$ で決まります。たとえば最初の 9 桁が $123456789$ なら $\sum_{i=1}^{9} i^2 = 285 = 25 \cdot 11 + 10$ で、検査数字は X です。 **ISBN-13。** 13 桁の数字に、$\mathbb{Z}/10\mathbb{Z}$ における条件 $x_1 + 3x_2 + x_3 + 3x_4 + \cdots + 3x_{12} + x_{13} = 0$ を課します。$1$ と $3$ は $10$ と互いに素なので、1 桁の誤りは左辺を変え、検出されます。しかし $\mathbb{Z}/10\mathbb{Z}$ は体ではないので、隣り合う桁の入れ替えは必ずしも検出されません。変化は $\pm 2(x_i - x_{i+1})$ で、$x_i - x_{i+1} = \pm 5$ のとき $0$ になるからです（$05 \leftrightarrow 50$、$16 \leftrightarrow 61$ など）。文字の集合を体に取ることの利点が、ここに現れています。 ## 4. シンドローム復号 $C$ を $[n, k]_q$ 符号、$H$ をその検査行列とする。$\boldsymbol{y} \in \mathbb{F}_q^n$ に対し $S(\boldsymbol{y}) = H\boldsymbol{y}^{\mathsf{T}} \in \mathbb{F}_q^{\,n-k}$ を $\boldsymbol{y}$ の**シンドローム**という。$C$ の剰余類 $\boldsymbol{y} + C$ の元のうち重みが最小のものの 1 つを、その剰余類の**代表元**（coset leader）という。 $C$ を $[n, k, d]_q$ 符号、$H$ を検査行列、$t = \lfloor (d-1)/2 \rfloor$ とする。 1. $S(\boldsymbol{y}) = S(\boldsymbol{y}') \iff \boldsymbol{y} - \boldsymbol{y}' \in C$。$S : \mathbb{F}_q^n \to \mathbb{F}_q^{\,n-k}$ は全射で、シンドロームと $C$ の剰余類は 1 対 1 に対応する。剰余類は $q^{n-k}$ 個ある。 2. 各シンドローム $\boldsymbol{s}$ に対し、対応する剰余類の代表元 $\boldsymbol{e}_{\boldsymbol{s}}$ を 1 つ選んでおく。受信語 $\boldsymbol{y}$ に対し $\hat{\boldsymbol{c}} = \boldsymbol{y} - \boldsymbol{e}_{S(\boldsymbol{y})}$ を出力する復号は最小距離復号である。すなわち $\hat{\boldsymbol{c}} \in C$ で、すべての $\boldsymbol{c}' \in C$ について $d(\hat{\boldsymbol{c}}, \boldsymbol{y}) \le d(\boldsymbol{c}', \boldsymbol{y})$。 3. 符号語 $\boldsymbol{c}$ を送り $\boldsymbol{y} = \boldsymbol{c} + \boldsymbol{e}$ を受け取ったとき、復号結果が $\boldsymbol{c}$ になることと、$\boldsymbol{e}$ が選んでおいた代表元の 1 つであることは同値である。$\mathrm{wt}(\boldsymbol{e}) \le t$ ならば $\boldsymbol{e}$ はその剰余類のただ 1 つの代表元で、復号結果は $\boldsymbol{c}$ になる。 (1) $S$ は線形で、核は $C$ です。したがって $S(\boldsymbol{y}) = S(\boldsymbol{y}') \iff S(\boldsymbol{y} - \boldsymbol{y}') = \boldsymbol{0} \iff \boldsymbol{y} - \boldsymbol{y}' \in C$ です。次元定理（）より像の次元は $n - k$ で、行き先 $\mathbb{F}_q^{\,n-k}$ の次元に等しいので $S$ は全射です。シンドロームの値は $q^{n-k}$ 個で、値ごとに剰余類が 1 つ対応します。 (2) $S(\hat{\boldsymbol{c}}) = S(\boldsymbol{y}) - S(\boldsymbol{e}_{S(\boldsymbol{y})}) = \boldsymbol{0}$ なので $\hat{\boldsymbol{c}} \in C$ です。$\boldsymbol{c}' \in C$ とすると、$\boldsymbol{y} - \boldsymbol{c}'$ は $\boldsymbol{y}$ と同じ剰余類に属するので、代表元の定義から $\mathrm{wt}(\boldsymbol{y} - \boldsymbol{c}') \ge \mathrm{wt}(\boldsymbol{e}_{S(\boldsymbol{y})})$ です。左辺は $d(\boldsymbol{c}', \boldsymbol{y})$、右辺は $d(\hat{\boldsymbol{c}}, \boldsymbol{y})$ です。 (3) $S(\boldsymbol{y}) = S(\boldsymbol{c}) + S(\boldsymbol{e}) = S(\boldsymbol{e})$ なので、$\hat{\boldsymbol{c}} = \boldsymbol{c} + \boldsymbol{e} - \boldsymbol{e}_{S(\boldsymbol{e})}$ です。これが $\boldsymbol{c}$ に等しいのは $\boldsymbol{e} = \boldsymbol{e}_{S(\boldsymbol{e})}$ のときに限ります。$\mathrm{wt}(\boldsymbol{e}) \le t$ とし、$\boldsymbol{e}'$ を同じ剰余類の元で $\mathrm{wt}(\boldsymbol{e}') \le \mathrm{wt}(\boldsymbol{e})$ なるものとします。$\boldsymbol{e} - \boldsymbol{e}' \in C$ で、三角不等式より $\mathrm{wt}(\boldsymbol{e} - \boldsymbol{e}') \le 2t < d$ なので $\boldsymbol{e} - \boldsymbol{e}' = \boldsymbol{0}$ です。つまり $\boldsymbol{e}$ はその剰余類で重みが最小のただ 1 つの元で、代表元として必ず選ばれています。 復号器は、$q^{n-k}$ 個のシンドロームと代表元の対応表を持てばよいことになります。$q^k$ 個の符号語すべてと距離を比べるより、$n - k$ が小さいときにはずっと少ない手間です。 第 $j$ 列が $j$ の 2 進表示になっている行列 $$ H = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix} $$ を検査行列とする二元符号 $C$ を考えます。$H$ の行は一次独立（第 4, 2, 1 列が単位ベクトル）なので $C$ は $[7, 4]_2$ 符号です。列はすべて $\boldsymbol{0}$ でなく相異なるので、どの 2 本も一次独立です。第 1, 2, 3 列は $001 + 010 + 011 = 000$ で一次従属です。 より $d = 3$ で、1 個の誤りを訂正できます。 第 $j$ 座標だけが $1$ の誤り $\boldsymbol{e}_j$ のシンドロームは $H$ の第 $j$ 列、つまり $j$ の 2 進表示です。したがって復号は「シンドロームを 2 進数として読み、その番号のビットを反転する（$000$ なら何もしない）」で済みます。 $\boldsymbol{c} = 1010101$ は符号語です（第 1, 3, 5, 7 列の和は $001 + 011 + 101 + 111 = 000$）。第 5 ビットが反転して $\boldsymbol{y} = 1010001$ を受け取ったとします。シンドロームは第 1, 3, 7 列の和 $001 + 011 + 111 = 101$ で、2 進数として $5$ です。第 5 ビットを反転して $1010101$ に戻ります。 最小距離復号が「もっともらしい」復号であることを確かめておきます。**$q$ 元対称通信路**とは、各座標が独立に、確率 $1 - p$ でそのまま届き、確率 $p$ でほかの $q - 1$ 個の文字のどれかに等確率で変わる通信路です。$q = 2$ のときを**二元対称通信路**といいます。受信語 $\boldsymbol{y}$ に対し、$\boldsymbol{c}$ を送ったときに $\boldsymbol{y}$ を受け取る確率 $P(\boldsymbol{y} \mid \boldsymbol{c})$ が最大になる符号語 $\boldsymbol{c}$ を出力する復号を**最尤復号**といいます。 誤り率 $p$ が $0 < p < (q - 1)/q$ を満たす $q$ 元対称通信路では、$P(\boldsymbol{y} \mid \boldsymbol{c})$ は $d(\boldsymbol{c}, \boldsymbol{y})$ の狭義単調減少関数である。したがって最尤復号と最小距離復号は一致する。 $w = d(\boldsymbol{c}, \boldsymbol{y})$ とします。$w$ 個の座標が指定された別の文字に変わり（各確率 $p/(q-1)$）、残りの $n - w$ 個がそのまま届く（各確率 $1 - p$）ので、座標ごとの独立性から $$ P(\boldsymbol{y} \mid \boldsymbol{c}) = \Bigl(\frac{p}{q-1}\Bigr)^{w} (1 - p)^{n - w} = (1 - p)^n \Bigl(\frac{p}{(q-1)(1-p)}\Bigr)^{w} $$ です。$p < (q-1)/q$ は $pq < q - 1$、すなわち $p < (q - 1)(1 - p)$ と同値なので、括弧の中は $0$ より大きく $1$ より小さく、右辺は $w$ について狭義単調減少です。 ## 5. 符号の限界式 $n$ と $d$ を決めたとき、符号語の個数 $M$（線形符号なら次元 $k$）はどこまで大きくできるでしょうか。上界を 4 つ、下界を 1 つ示します。証明はすべて数え上げです。 $\boldsymbol{x} \in \mathbb{F}_q^n$ と整数 $r \ge 0$ に対し、$B(\boldsymbol{x}, r) = \{\boldsymbol{y} \in \mathbb{F}_q^n : d(\boldsymbol{x}, \boldsymbol{y}) \le r\}$ を中心 $\boldsymbol{x}$、半径 $r$ の **Hamming 球**といい、 $$ V_q(n, r) = \sum_{i=0}^{\min(r, n)} \binom{n}{i} (q - 1)^i $$ とおく。最小距離 $d$ の符号 $C$ が、$t = \lfloor (d-1)/2 \rfloor$ について $\mathbb{F}_q^n = \bigcup_{\boldsymbol{c} \in C} B(\boldsymbol{c}, t)$ を満たすとき**完全符号**という。$d = n - k + 1$ を満たす $[n, k, d]_q$ 符号を **MDS 符号**（最大距離分離符号）という。 すべての $\boldsymbol{x} \in \mathbb{F}_q^n$ と $r \ge 0$ について $|B(\boldsymbol{x}, r)| = V_q(n, r)$ である。 $d(\boldsymbol{x}, \boldsymbol{y}) = i$ となる $\boldsymbol{y}$ を数えます。$\boldsymbol{y}$ は、$\boldsymbol{x}$ と異なる座標の集合（$i$ 元部分集合。$\binom{n}{i}$ 通り。）と、その各座標での値（$x_j$ 以外の $q - 1$ 通り）で決まるので、$\binom{n}{i}(q-1)^i$ 個です。$i = 0, 1, \ldots, \min(r, n)$ について足せば $V_q(n, r)$ です。 $(n, M, d)_q$ 符号について $M \le q^{\,n - d + 1}$ である。特に $[n, k, d]_q$ 線形符号について $d \le n - k + 1$ である。 各符号語から最後の $d - 1$ 個の座標を消す写像 $\pi : C \to \mathbb{F}_q^{\,n-d+1}$ を考えます。異なる符号語は $d$ 個以上の座標で異なるので、$d - 1$ 個の座標を消しても残りのどこかで異なります。つまり $\pi$ は単射で、$M = |C| \le q^{\,n-d+1}$ です（ の 1 の対偶）。線形符号では $M = q^k$ なので $k \le n - d + 1$ です。 $(n, M, d)_q$ 符号について、$t = \lfloor (d-1)/2 \rfloor$ とすると $$ M \cdot V_q(n, t) \le q^n $$ である。等号が成り立つことと、符号が完全符号であることは同値である。 の 2 より、異なる符号語 $\boldsymbol{c}, \boldsymbol{c}'$ について $B(\boldsymbol{c}, t) \cap B(\boldsymbol{c}', t) = \varnothing$ です（共通の元 $\boldsymbol{y}$ があれば $d(\boldsymbol{c}, \boldsymbol{y}) \le t$ かつ $d(\boldsymbol{c}', \boldsymbol{y}) \le t$ となり矛盾）。$M$ 個の球は互いに交わらず、それぞれ $V_q(n, t)$ 個の元をもつ（）ので、合併は $M \cdot V_q(n, t)$ 個の元をもち、これは $|\mathbb{F}_q^n| = q^n$ 以下です。等号は合併が $\mathbb{F}_q^n$ 全体であること、つまり完全符号であることと同値です。 上界だけでは「よい符号が存在する」ことは分かりません。次の定理は、検査行列の列を 1 本ずつ選んでいく素朴な方法で、かなりよい符号が必ず作れることを示します。 $n, k, d$ を $1 \le k \le n - 1$、$2 \le d \le n$ を満たす整数とする。 $$ V_q(n - 1,\ d - 2) < q^{\,n-k} $$ ならば、最小距離が $d$ 以上の $[n, k]_q$ 線形符号が存在する。 証明の方針は次のとおりです。 により、最小距離 $d$ 以上の符号を作ることは、「どの $d - 1$ 本も一次独立」な列を $n$ 本集めることと同じです。列を 1 本ずつ足していくとき、新しい列として使えないのは、すでに選んだ列の $d - 2$ 本以下の一次結合で書けるベクトルです。その個数を数えて $\mathbb{F}_q^{\,n-k}$ の元の総数 $q^{n-k}$ より少ないと示せば、使えるベクトルがまだ残っていることが分かり、最後の列まで選び続けられます。 $r = n - k$ とします。$\mathbb{F}_q^{\,r}$ のベクトル $\boldsymbol{h}_1, \ldots, \boldsymbol{h}_n$ を、「どの $d - 1$ 本以下も一次独立」という条件を保ちながら 1 本ずつ選びます。 $\boldsymbol{h}_1, \ldots, \boldsymbol{h}_j$（$0 \le j \le n - 1$）がこの条件を満たすように選べたとします。$\boldsymbol{h}_{j+1}$ として、$\boldsymbol{h}_1, \ldots, \boldsymbol{h}_j$ のうち $d - 2$ 本以下の一次結合で書けないベクトルを選びます。$d - 2$ 本以下の一次結合は、使う列の集合（$i$ 本、$0 \le i \le d - 2$）と $0$ でない係数（$(q - 1)^i$ 通り）で決まるので、高々 $$ \sum_{i=0}^{d-2} \binom{j}{i}(q-1)^i = V_q(j, d-2) \le V_q(n - 1, d - 2) < q^{\,r} $$ 個です（$j \le n - 1$ なら $\binom{j}{i} \le \binom{n-1}{i}$）。$\mathbb{F}_q^{\,r}$ の元は $q^r$ 個あるので、そのような $\boldsymbol{h}_{j+1}$ が選べます。 $\boldsymbol{h}_1, \ldots, \boldsymbol{h}_{j+1}$ が条件を満たすことを確かめます。$d - 1$ 本以下の列の自明でない一次関係があったとします。$\boldsymbol{h}_{j+1}$ の係数が $0$ なら、$\boldsymbol{h}_1, \ldots, \boldsymbol{h}_j$ の $d - 1$ 本以下の自明でない一次関係となり、帰納法の仮定に反します。$0$ でなければ、$\boldsymbol{h}_{j+1}$ について解いて、$\boldsymbol{h}_{j+1}$ がほかの $d - 2$ 本以下の一次結合で書け、選び方に反します。 $\boldsymbol{h}_1, \ldots, \boldsymbol{h}_n$ を列とする $r \times n$ 行列を $H$ とし、$C_0 = \{\boldsymbol{x} : H\boldsymbol{x}^{\mathsf{T}} = \boldsymbol{0}\}$ とします。次元定理（）より $\dim C_0 = n - \dim \mathrm{Im} \ge n - r = k \ge 1$ です。 より $d(C_0) \ge d$ です。$C_0$ の $k$ 次元部分空間 $C$ を取ると、$C$ の $\boldsymbol{0}$ でない元は $C_0$ の元でもあるので重みは $d$ 以上で、$C$ が求める符号です。 $\theta = 1 - 1/q$ とする。$(n, M, d)_q$ 符号が $d > \theta n$ を満たすならば $$ M \le \frac{d}{d - \theta n} $$ である。$q = 2$ のときは、$2d > n$ ならば $M \le \dfrac{2d}{2d - n}$ である。 $S = \sum d(\boldsymbol{c}, \boldsymbol{c}')$ を、符号語の順序対 $(\boldsymbol{c}, \boldsymbol{c}')$、$\boldsymbol{c} \ne \boldsymbol{c}'$ すべてにわたる和とします。順序対は $M(M-1)$ 個で各項は $d$ 以上なので $S \ge M(M-1)\,d$ です。 $S$ を座標ごとに数え直します。第 $i$ 座標が $a \in \mathbb{F}_q$ である符号語の個数を $m_a$ とすると、$\sum_a m_a = M$ で、第 $i$ 座標で異なる順序対の個数は $$ \sum_{a \in \mathbb{F}_q} m_a (M - m_a) = M^2 - \sum_{a} m_a^2 $$ です。$\sum_a (m_a - M/q)^2 \ge 0$ を展開すると $\sum_a m_a^2 - 2(M/q) M + q\,(M/q)^2 \ge 0$、つまり $\sum_a m_a^2 \ge M^2/q$ なので、上の個数は $M^2 - M^2/q = \theta M^2$ 以下です。$n$ 個の座標について足して $S \le n\theta M^2$ です。 2 つの評価を合わせると $M(M-1)\,d \le n \theta M^2$、$M$ で割って $(M - 1)\,d \le n\theta M$、すなわち $M\,(d - \theta n) \le d$ です。$d - \theta n > 0$ で割れば結論です。$q = 2$ では $\theta = 1/2$ で、$d/(d - n/2) = 2d/(2d - n)$ です。 Plotkin 限界は、相対距離 $d/n$ が $\theta$ を超えると符号語の個数が $n$ によらない定数で抑えられることを示します。大きな符号を作りたければ、相対距離は $1 - 1/q$ 以下にせざるを得ません。 線形符号に限ると、次のより細かい限界が成り立ちます。$\lceil x \rceil$ は $x$ 以上の最小の整数です。 $k \ge 2$ とし、$[n, k, d]_q$ 符号が存在するとする。このとき、ある $d' \ge \lceil d/q \rceil$ について $[n - d,\ k - 1,\ d']_q$ 符号が存在する。 この補題は、直後の Griesmer 限界の帰納法で使う道具です。最小重みの符号語 $\boldsymbol{c}$ の $0$ でない座標を消した符号を考えると、符号の次元は 1 つ下がり、長さは $d$ だけ短くなります。そのとき最小距離が $\lceil d/q \rceil$ 以上に保たれることを示します。証明の冒頭の座標の入れ替えと逆元を掛ける操作は、$\boldsymbol{c}$ を $(1, \ldots, 1, 0, \ldots, 0)$ の形にそろえて、以降の計算を見やすくするためのものです。 $C$ を $[n, k, d]_q$ 符号、$\boldsymbol{c} \in C$ を重み $d$ の符号語とします。座標を入れ替え、$\boldsymbol{c}$ の $0$ でない各座標にその成分の逆元を掛けます。この操作は $\mathbb{F}_q^n$ の線形同型で、各ベクトルの重みを変えない（$a \ne 0$ なら $a x_i \ne 0 \iff x_i \ne 0$）ので、$C$ の像も $[n, k, d]_q$ 符号です。したがって $\boldsymbol{c} = (1, \ldots, 1, 0, \ldots, 0)$（最初の $d$ 個が $1$）としてよいです。$\pi : C \to \mathbb{F}_q^{\,n-d}$ を最後の $n - d$ 個の座標への射影とし、$C' = \pi(C)$ とします。 $\boldsymbol{x} \in C$ を $\boldsymbol{c}$ の定数倍でない元とします。$x_1, \ldots, x_d$ の $d$ 個の値は $q$ 通りのどれかなので、ある $a \in \mathbb{F}_q$ が $N_a \ge \lceil d/q \rceil$ 回現れます（$\lceil d/q \rceil = 1$ のときは、$x_1$ の値を $a$ とすればよい。$\lceil d/q \rceil \ge 2$ のときは、 の 1 を $k = \lceil d/q \rceil - 1 \ge 1$ に使う。$d > q\,(\lceil d/q \rceil - 1)$ なので）。$\boldsymbol{x} - a\boldsymbol{c}$ は $C$ の $\boldsymbol{0}$ でない元で、最初の $d$ 個の座標のうち $0$ でないのは $d - N_a$ 個、最後の $n - d$ 個の座標は $\pi(\boldsymbol{x})$ と同じなので $$ d \le \mathrm{wt}(\boldsymbol{x} - a\boldsymbol{c}) = (d - N_a) + \mathrm{wt}(\pi(\boldsymbol{x})) $$ です。よって $\mathrm{wt}(\pi(\boldsymbol{x})) \ge N_a \ge \lceil d/q \rceil \ge 1$ です。 特に $\pi(\boldsymbol{x}) \ne \boldsymbol{0}$ なので、$\pi$ の核は $\boldsymbol{c}$ の定数倍の全体（1 次元）です。次元定理（）より $\dim C' = k - 1 \ge 1$ です。$C'$ の $\boldsymbol{0}$ でない元は、$\boldsymbol{c}$ の定数倍でない $\boldsymbol{x}$ による $\pi(\boldsymbol{x})$ なので、重みは $\lceil d/q \rceil$ 以上です。 $k \ge 1$ とする。$[n, k, d]_q$ 符号が存在するならば $$ n \ge \sum_{i=0}^{k-1} \Bigl\lceil \frac{d}{q^i} \Bigr\rceil $$ である。 $k$ についての帰納法で示します。$k = 1$ のとき、主張は $n \ge d$ で、重みは $n$ 以下なので成り立ちます。$k \ge 2$ とし、$k - 1$ では成り立つとします。 より $[n - d, k - 1, d']_q$ 符号（$d' \ge \lceil d/q \rceil$）があるので、帰納法の仮定から $$ n - d \ge \sum_{i=0}^{k-2} \Bigl\lceil \frac{d'}{q^i} \Bigr\rceil \ge \sum_{i=0}^{k-2} \Bigl\lceil \frac{d}{q^{i+1}} \Bigr\rceil $$ です。2 番目の不等号は $d'/q^i \ge \lceil d/q \rceil / q^i \ge d/q^{i+1}$ と、$\lceil\ \rceil$ が単調であることによります。両辺に $d = \lceil d/q^0 \rceil$ を加えれば $k$ の場合です。 長さ $10$、最小距離 $3$ 以上の二元線形符号の次元 $k$ を、各限界で評価します（上界はどれも $d$ が大きいほど厳しくなるので、$d = 3$ として計算すれば十分です）。 | 限界 | 条件 | 結論 | |---|---|---| | Singleton | $3 \le 10 - k + 1$ | $k \le 8$ | | Hamming | $2^k (1 + 10) \le 2^{10} = 1024$ | $2^k \le 93$、$k \le 6$ | | Plotkin | $2d > n$ が必要だが $2d = 6 < 10$ | 適用できない | | Griesmer | $10 \ge 3 + 2 + \underbrace{1 + \cdots + 1}_{k - 2} = k + 3$ | $k \le 7$ | | Gilbert–Varshamov | $V_2(9, 1) = 10 < 2^{10 - k}$ | $k \le 6$ なら存在する | Hamming 限界から $k \le 6$、Gilbert–Varshamov 限界から $k = 6$ の符号が存在するので、最大の次元はちょうど $6$ です。この例では上界と下界が一致しましたが、一般には両者の間に隙間があり、最良の符号のパラメータが分かっていない $(n, d)$ は数多く残っています。 限界式は必要条件でしかないことにも注意してください。$[5, 2, 4]_2$ というパラメータは、Singleton 限界（$4 \le 5 - 2 + 1$）も Hamming 限界（$2^2 (1 + 5) = 24 \le 32$）も満たしますが、Griesmer 限界は $5 \ge 4 + 2 = 6$ を要求するので、そのような符号は存在しません。 ## 6. Hamming 符号と符号の変形 $r \ge 2$ とし、$n = (q^r - 1)/(q - 1)$ とする。$\mathbb{F}_q^{\,r}$ の 1 次元部分空間のそれぞれから $\boldsymbol{0}$ でないベクトルを 1 つずつ選び、それらを列として並べた $r \times n$ 行列を $H_r$ とする。$H_r$ を検査行列とする符号 $\mathrm{Ham}(r, q) = \{\boldsymbol{x} \in \mathbb{F}_q^n : H_r\boldsymbol{x}^{\mathsf{T}} = \boldsymbol{0}\}$ を **Hamming 符号**、その双対符号を**単体符号**（シンプレックス符号）という。 $\mathbb{F}_q^{\,r}$ の $\boldsymbol{0}$ でないベクトルは $q^r - 1$ 個で、各 1 次元部分空間は $\boldsymbol{0}$ でないベクトルを $q - 1$ 個含み、異なる 1 次元部分空間は $\boldsymbol{0}$ 以外を共有しないので、1 次元部分空間は $(q^r - 1)/(q - 1)$ 個あります。代表元の選び方と列の順序を変えても、得られる符号は同値です。$q = 2$ では $n = 2^r - 1$ で、列は $\boldsymbol{0}$ でないベクトル全部です（ は $r = 3$ の場合）。 $r \ge 2$、$n = (q^r - 1)/(q-1)$ とする。 1. $\mathrm{Ham}(r, q)$ は $[n,\ n - r,\ 3]_q$ 符号である。 2. $\mathrm{Ham}(r, q)$ は完全符号である。 3. 単体符号は $[n, r]_q$ 符号で、$\boldsymbol{0}$ でない符号語の重みはすべて $q^{r-1}$ である。特に最小距離は $q^{r-1}$ である。 (1) $H_r$ の列には標準基底 $\boldsymbol{e}_1, \ldots, \boldsymbol{e}_r$ それぞれの定数倍が含まれるので、写像 $\boldsymbol{x} \mapsto H_r \boldsymbol{x}^{\mathsf{T}}$ は $\mathbb{F}_q^n$ から $\mathbb{F}_q^{\,r}$ への全射です。次元定理（）より核の次元は $n - r$ で、$H_r$ の行は一次独立（一次従属なら像の次元が $r$ より小さくなります）なので $H_r$ は検査行列です。$H_r$ の列はどれも $\boldsymbol{0}$ でなく、異なる 2 本は異なる 1 次元部分空間に属するので互いに定数倍でなく、どの 2 本も一次独立です。一方、$\boldsymbol{e}_1$、$\boldsymbol{e}_2$、$\boldsymbol{e}_1 + \boldsymbol{e}_2$ の属する 3 つの 1 次元部分空間は相異なり、それらの代表である 3 本の列は 2 次元空間に含まれるので一次従属です。 より最小距離は $3$ です。 (2) $t = 1$ で、$V_q(n, 1) = 1 + n(q - 1) = 1 + (q^r - 1) = q^r$ です。符号語は $q^{n-r}$ 個なので $q^{n-r} \cdot V_q(n, 1) = q^n$ となり、 の等号が成り立ちます。 (3) の 3 より、単体符号は $H_r$ を生成行列とする $[n, r]_q$ 符号で、符号語は $\boldsymbol{u}H_r = (\boldsymbol{u}\cdot\boldsymbol{h}_1, \ldots, \boldsymbol{u}\cdot\boldsymbol{h}_n)$（$\boldsymbol{u} \in \mathbb{F}_q^{\,r}$、$\boldsymbol{h}_j$ は $H_r$ の列）です。$\boldsymbol{u} \ne \boldsymbol{0}$ とします。$U = \{\boldsymbol{v} \in \mathbb{F}_q^{\,r} : \boldsymbol{u} \cdot \boldsymbol{v} = 0\}$ は $0$ でない線形写像 $\boldsymbol{v} \mapsto \boldsymbol{u}\cdot\boldsymbol{v}$ の核なので、次元は $r - 1$ です（次元定理）。$\boldsymbol{u}H_r$ の第 $j$ 成分が $0$ であることは $\boldsymbol{h}_j \in U$、つまり $\boldsymbol{h}_j$ の属する 1 次元部分空間が $U$ に含まれることと同値です。$U$ に含まれる 1 次元部分空間は $(q^{r-1} - 1)/(q - 1)$ 個なので、 $$ \mathrm{wt}(\boldsymbol{u}H_r) = \frac{q^r - 1}{q - 1} - \frac{q^{r-1} - 1}{q - 1} = \frac{q^r - q^{r-1}}{q - 1} = q^{r-1} $$ です。 単体符号は Griesmer 限界を等号で満たします: $\sum_{i=0}^{r-1} \lceil q^{r-1}/q^i \rceil = q^{r-1} + q^{r-2} + \cdots + 1 = n$。Plotkin 限界も等号です: $\theta n = (q^r - 1)/q$ なので $d - \theta n = 1/q$ で、$d/(d - \theta n) = q^r = M$。どの 2 つの符号語も同じ距離だけ離れている（正単体の頂点のような配置になっている）ことが名前の由来です。 既存の符号から新しい符号を作る操作を 3 つ定めます。 $C$ を $[n, k]_q$ 符号とする。 1. **パリティ拡大**: $\widehat{C} = \{(c_1, \ldots, c_n, c_{n+1}) : \boldsymbol{c} \in C,\ c_{n+1} = -(c_1 + \cdots + c_n)\}$。長さ $n + 1$、次元 $k$ の符号。 2. **穴あけ**: 第 $i$ 座標を消して得られる長さ $n - 1$ の符号。 3. **短縮**: 第 $i$ 座標が $0$ である符号語だけを集め、その第 $i$ 座標を消して得られる長さ $n - 1$ の符号。 穴あけでは各符号語の重みが高々 $1$ 減ります。短縮では、集めた符号語は「第 $i$ 座標」という線形写像の核なので $k - 1$ 次元以上あり、$0$ の座標を消しても重みは変わらないので、$[n - 1,\ \ge k - 1,\ \ge d]_q$ 符号が得られます。たとえば $\mathrm{Ham}(4, 2)$（$[15, 11, 3]_2$）を 5 回短縮すると、 で存在が保証された、最小距離 $3$ 以上の $[10, 6]_2$ 符号が具体的に得られます（次元は $6$ 以上で、Hamming 限界から $6$ 以下）。 の $[7, 4, 3]_2$ 符号 $C$ の符号語として $1110000$、$1001100$、$0101010$、$1101001$ が取れます（それぞれ $H$ の第 $\{1,2,3\}$、$\{1,4,5\}$、$\{2,4,6\}$、$\{1,2,4,7\}$ 列の和が $\boldsymbol{0}$）。第 3, 5, 6, 7 座標を見ると単位行列になっているので一次独立で、$C$ の基底です。パリティ拡大 $\widehat{C}$ の基底は $$ \boldsymbol{g}_1 = 11100001,\quad \boldsymbol{g}_2 = 10011001,\quad \boldsymbol{g}_3 = 01010101,\quad \boldsymbol{g}_4 = 11010010 $$ です。どの $\boldsymbol{g}_i$ も重み $4$ で、どの 2 つも $1$ が重なる座標がちょうど 2 個です（たとえば $\boldsymbol{g}_1$ と $\boldsymbol{g}_2$ は第 1, 8 座標）。したがって $\boldsymbol{g}_i \cdot \boldsymbol{g}_j = 0$ がすべての $i, j$ で成り立ち、$\widehat{C} \subseteq \widehat{C}^{\perp}$ です。$\dim \widehat{C}^{\perp} = 8 - 4 = 4 = \dim \widehat{C}$ なので $\widehat{C} = \widehat{C}^{\perp}$、つまり自己双対です。 最小距離を求めます。二元ベクトルについて $\mathrm{wt}(\boldsymbol{x} + \boldsymbol{y}) = \mathrm{wt}(\boldsymbol{x}) + \mathrm{wt}(\boldsymbol{y}) - 2\,|\mathrm{supp}(\boldsymbol{x}) \cap \mathrm{supp}(\boldsymbol{y})|$ で、$\boldsymbol{x} \cdot \boldsymbol{y} = 0$ は $|\mathrm{supp}(\boldsymbol{x}) \cap \mathrm{supp}(\boldsymbol{y})|$ が偶数であることを意味します。したがって、重みが $4$ の倍数で互いに直交する $\boldsymbol{x}, \boldsymbol{y}$ の和の重みも $4$ の倍数です。$\widehat{C}$ の元は $\boldsymbol{g}_i$ の和で、$\widehat{C}$ は自己直交なので、和を 1 つずつ足していけば、すべての符号語の重みが $4$ の倍数だと分かります。長さは $8$ なので $\boldsymbol{0}$ でない符号語の重みは $4$ か $8$ で、最小距離は $4$ です。$\widehat{C}$ は $[8, 4, 4]_2$ 符号で、1 個の誤りを訂正し、同時に 2 個の誤りを検出します。 $q = 3$、$r = 2$ では $n = (9 - 1)/2 = 4$ です。$\mathbb{F}_3^2$ の 4 つの 1 次元部分空間の代表として $(1,0), (0,1), (1,1), (1,2)$ を取ると $$ H_2 = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 2 \end{bmatrix} $$ で、$\mathrm{Ham}(2, 3)$ は $[4, 2, 3]_3$ 符号です。完全符号であることは $3^2 \cdot (1 + 4 \cdot 2) = 81 = 3^4$ で確かめられます。 $H_2$ の行 $\boldsymbol{r}_1 = 1011$、$\boldsymbol{r}_2 = 0112$ について、$\boldsymbol{r}_1 \cdot \boldsymbol{r}_1 = 3 = 0$、$\boldsymbol{r}_2 \cdot \boldsymbol{r}_2 = 1 + 1 + 4 = 6 = 0$、$\boldsymbol{r}_1 \cdot \boldsymbol{r}_2 = 1 + 2 = 0$ です。行の張る空間（単体符号）$D$ は自己直交で、$\dim D = 2 = 4 - 2 = \dim D^{\perp}$ なので $D = D^{\perp} = \mathrm{Ham}(2, 3)$ です。この符号は Hamming 符号であり、単体符号でもあり、自己双対です。 の 3 より、$\boldsymbol{0}$ でない 8 個の符号語の重みはすべて $3$ です。この符号は tetracode と呼ばれ、三元 Golay 符号の構成に使われます。 ## 7. エントロピー関数と漸近的な限界 符号長 $n$ を大きくしていくとき、情報率 $R = k/n$ と相対距離 $\delta = d/n$ の両方を正に保てるでしょうか。Gilbert–Varshamov 限界は「保てる」と答えます。評価には Hamming 球の体積の指数的な大きさが必要です。 $0 < \lambda < 1$ に対し $$ H(\lambda) = -\lambda \log_2 \lambda - (1 - \lambda)\log_2(1 - \lambda) $$ と定め、$H(0) = H(1) = 0$ とする。$H$ を**二元エントロピー関数**という。 $H(\lambda) = H(1 - \lambda)$ で、$H(1/2) = 1$ です。$2^{-nH(\lambda)} = \lambda^{\lambda n}(1 - \lambda)^{(1 - \lambda)n}$ という形で使います。$H$ は $(0, 1)$ 上で連続です（対数関数の連続性から）。 $0 \le \lambda \le 1$ について $H(\lambda) \le 1$ で、等号は $\lambda = 1/2$ のときに限る。 $\lambda = 0, 1$ では $H = 0 < 1$ です。$0 < \lambda < 1$ とします。まず、$x > 0$ について $\log x \le x - 1$（$\log$ は自然対数）で、等号は $x = 1$ に限ることを示します。$\phi(x) = x - 1 - \log x$ とすると $\phi'(x) = 1 - 1/x$ で、$x > 1$ では正、$0 < x < 1$ では負です。 の 3 より $\phi$ は $[1, \infty)$ で狭義単調増加、$-\phi$ は $(0, 1]$ で狭義単調増加なので、$x \ne 1$ なら $\phi(x) > \phi(1) = 0$ です。 $\log_2 y = \log y / \log 2$ と $\lambda + (1 - \lambda) = 1$ を使うと $$ H(\lambda) - 1 = \lambda \log_2 \frac{1}{2\lambda} + (1 - \lambda)\log_2 \frac{1}{2(1 - \lambda)} \le \frac{1}{\log 2}\Bigl[\lambda\Bigl(\frac{1}{2\lambda} - 1\Bigr) + (1 - \lambda)\Bigl(\frac{1}{2(1-\lambda)} - 1\Bigr)\Bigr] = \frac{1}{\log 2}\Bigl[\frac12 - \lambda + \frac12 - (1 - \lambda)\Bigr] = 0 $$ です。等号は $1/(2\lambda) = 1$ かつ $1/(2(1 - \lambda)) = 1$、つまり $\lambda = 1/2$ のときに限ります。 $0 < \lambda \le 1/2$ とし、$n \ge 1$ とする。 $$ V_2(n, \lfloor \lambda n \rfloor) = \sum_{0 \le i \le \lambda n} \binom{n}{i} \le 2^{\,n H(\lambda)}. $$ この補題は、Hamming 球の体積を $2$ のべき乗で簡単に抑えるためのものです。二項定理の和 $1$ から出発して、$i \le \lambda n$ の項だけを残して下から評価します。 二項定理（）より $$ 1 = \bigl(\lambda + (1 - \lambda)\bigr)^n = \sum_{i=0}^{n} \binom{n}{i} \lambda^i (1 - \lambda)^{n - i} \ge \sum_{0 \le i \le \lambda n} \binom{n}{i} (1 - \lambda)^n \Bigl(\frac{\lambda}{1 - \lambda}\Bigr)^{i} $$ です。$\lambda \le 1/2$ なので $0 < \lambda/(1 - \lambda) \le 1$ で、$i \le \lambda n$ なら $\bigl(\lambda/(1-\lambda)\bigr)^i \ge \bigl(\lambda/(1-\lambda)\bigr)^{\lambda n}$ です。したがって $$ 1 \ge (1 - \lambda)^n \Bigl(\frac{\lambda}{1 - \lambda}\Bigr)^{\lambda n} \sum_{0 \le i \le \lambda n} \binom{n}{i} = \lambda^{\lambda n}(1 - \lambda)^{(1 - \lambda) n} \sum_{0 \le i \le \lambda n} \binom{n}{i} = 2^{-nH(\lambda)} \sum_{0 \le i \le \lambda n} \binom{n}{i} $$ です。両辺に $2^{nH(\lambda)}$ を掛ければ結論です。 $0 < \delta < 1/2$、$\varepsilon > 0$ とする。十分大きいすべての $n$ について、最小距離が $\delta n$ 以上で、情報率が $k/n \ge 1 - H(\delta) - \varepsilon$ を満たす二元線形 $[n, k]_2$ 符号が存在する。 $d = \lceil \delta n \rceil$、$k = n - \lfloor nH(\delta) \rfloor - 1$ とします。 より $H(\delta) < 1$ なので、$n$ が十分大きければ $k \ge n(1 - H(\delta)) - 1 \ge 1$ です。また $k \le n - 1$ で、$n$ が十分大きければ $2 \le d \le n$ です。$d - 2 < \delta n$ なので、 より $$ V_2(n - 1, d - 2) \le V_2(n, \lfloor \delta n \rfloor) \le 2^{\,nH(\delta)} < 2^{\,\lfloor nH(\delta) \rfloor + 1} = 2^{\,n - k} $$ です。 より、最小距離が $d \ge \delta n$ 以上の $[n, k]_2$ 符号が存在します。$k/n \ge 1 - H(\delta) - 1/n$ なので、$n \ge 1/\varepsilon$ なら $k/n \ge 1 - H(\delta) - \varepsilon$ です。 たとえば $\delta = 0.11$ では $H(\delta) \approx 0.5$ なので、相対距離 $0.11$、情報率ほぼ $1/2$ の二元線形符号の列が存在します。$H(\delta) < 1$ なので、$\delta < 1/2$ である限り情報率を正に保てます。二元符号でこの限界を漸近的に上回る構成は、現在も知られていません。 ## 8. 二元対称通信路の符号化定理 最後に、確率的な誤りに対して符号がどこまで有効かを調べます。誤り率 $p$ の二元対称通信路で長さ $n$ の語を送ると、誤りベクトル $\boldsymbol{e} \in \mathbb{F}_2^n$ が確率 $$ P(\boldsymbol{e}) = p^{\,\mathrm{wt}(\boldsymbol{e})} (1 - p)^{\,n - \mathrm{wt}(\boldsymbol{e})} $$ で生じます。これは有限集合 $\mathbb{F}_2^n$ 上の確率です（二項定理より総和は $(p + 1 - p)^n = 1$）。誤りはおよそ $pn$ 個生じるので、最小距離による保証（）で確実に訂正するには $d > 2pn$ が必要で、Plotkin 限界から $p \ge 1/4$ では情報率を正に保てません。しかし「確実に」を「高い確率で」に緩めると、事情は一変します。 $0 < p < 1/2$、$0 < R < 1 - H(p)$ とする。各 $n \ge 1$ について、長さ $n$、次元 $k_n = \lceil Rn \rceil$ の二元線形符号 $C_n$ と復号写像 $D_n : \mathbb{F}_2^n \to C_n \cup \{\text{失敗}\}$ であって、 $$ \max_{\boldsymbol{c} \in C_n} P\bigl(D_n(\boldsymbol{c} + \boldsymbol{e}) \ne \boldsymbol{c}\bigr) \longrightarrow 0 \qquad (n \to \infty) $$ を満たすものが存在する。ここで確率は誤り率 $p$ の二元対称通信路の誤りベクトル $\boldsymbol{e}$ についてのものである。 証明の発想は、よい符号を 1 つ設計するのではなく、生成行列 $G$ を無作為に選んだときの復号誤り確率の平均を計算することです。平均が小さければ、平均以下の誤り確率をもつ $G$ が少なくとも 1 つは存在します。これで、符号を具体的に作らなくても存在が言えます。 **準備。** $H$ は連続なので、$\varepsilon > 0$ を小さく取って $\lambda = p + \varepsilon < 1/2$ かつ $R < 1 - H(\lambda)$ とできます。$n$ を固定し、$k = \lceil Rn \rceil$ とします（$R < 1$ なので $k \le n$）。 $k \times n$ 行列 $G$ に対し、復号を次のように定めます。受信語 $\boldsymbol{y}$ に対し、$\mathrm{wt}(\boldsymbol{y} - \boldsymbol{u}G) \le \lambda n$ となる $\boldsymbol{u} \in \mathbb{F}_2^k$ がただ 1 つならその $\boldsymbol{u}$（対応する符号語 $\boldsymbol{u}G$）を出力し、そうでなければ失敗とします。 **誤り事象。** 情報 $\boldsymbol{u}$ を送り $\boldsymbol{y} = \boldsymbol{u}G + \boldsymbol{e}$ を受け取ったとします。復号が $\boldsymbol{u}$ を正しく出力することは、次の 2 つがどちらも起きないことと同値です。 - (a) $\mathrm{wt}(\boldsymbol{e}) > \lambda n$。 - (b) ある $\boldsymbol{w} \in \mathbb{F}_2^k$、$\boldsymbol{w} \ne \boldsymbol{0}$ について $\mathrm{wt}(\boldsymbol{w}G + \boldsymbol{e}) \le \lambda n$。 実際、$\boldsymbol{y} - \boldsymbol{u}G = \boldsymbol{e}$ なので、$\boldsymbol{u}$ が復号の条件を満たすことは (a) が起きないことと同値です。また $\boldsymbol{u}' = \boldsymbol{u} + \boldsymbol{w}$（$\boldsymbol{w} \ne \boldsymbol{0}$）については $\boldsymbol{y} - \boldsymbol{u}'G = \boldsymbol{e} - \boldsymbol{w}G = \boldsymbol{e} + \boldsymbol{w}G$ なので、$\boldsymbol{u}$ 以外に条件を満たすものがないことは (b) が起きないことと同値です。(a)(b) は $\boldsymbol{u}$ によらないので、復号誤り確率はどの $\boldsymbol{u}$ を送っても同じ値 $P_{\mathrm{err}}(G) = P\bigl(\text{(a) または (b)}\bigr)$ で、 $$ P_{\mathrm{err}}(G) \le P\bigl(\mathrm{wt}(\boldsymbol{e}) > \lambda n\bigr) + \sum_{\boldsymbol{w} \ne \boldsymbol{0}} P\bigl(\mathrm{wt}(\boldsymbol{w}G + \boldsymbol{e}) \le \lambda n\bigr) $$ です（事象の合併の確率は確率の和以下）。 **(a) の評価。** $X_i(\boldsymbol{e}) = e_i \in \{0, 1\}$ とすると $\mathrm{wt}(\boldsymbol{e}) = \sum_i X_i$ です。$P$ の定義から、$i \ne j$ について $P(X_i = 1) = p$、$P(X_i = 1, X_j = 1) = p^2$ です（ほかの座標について和を取ると $1$ になります）。期待値（。有限集合の上では値と確率の積の有限和）は $E[X_i] = p$、分散と共分散（）は $\mathrm{Var}(X_i) = E[X_i^2] - p^2 = p(1 - p)$、$\mathrm{Cov}(X_i, X_j) = p^2 - p \cdot p = 0$ です。これは事象 $\{X_i = 1\}$ と $\{X_j = 1\}$ が独立（）であることの帰結です。したがって $E[\mathrm{wt}(\boldsymbol{e})] = np$、$\mathrm{Var}(\mathrm{wt}(\boldsymbol{e})) = np(1-p)$（ の 4）で、チェビシェフの不等式（）より $$ P\bigl(\mathrm{wt}(\boldsymbol{e}) > \lambda n\bigr) \le P\bigl(|\mathrm{wt}(\boldsymbol{e}) - np| \ge \varepsilon n\bigr) \le \frac{np(1 - p)}{\varepsilon^2 n^2} \le \frac{1}{4\varepsilon^2 n} $$ です。 **(b) の評価：符号についての平均。** $G$ を $2^{kn}$ 個の $k \times n$ 行列全体から一様に選び、$P_{\mathrm{err}}(G)$ の平均を評価します。$\boldsymbol{w} \ne \boldsymbol{0}$ と $\boldsymbol{e}$ を固定します。写像 $G \mapsto \boldsymbol{w}G$ は行列の空間 $\mathbb{F}_2^{\,k \times n}$ から $\mathbb{F}_2^n$ への線形写像で、全射です（$w_i = 1$ なる $i$ を取り、第 $i$ 行を任意のベクトル、ほかの行を $\boldsymbol{0}$ とすればよい）。次元定理より核は $2^{kn - n}$ 個の元をもち、$\mathbb{F}_2^n$ の各ベクトルはちょうど $2^{kn-n}$ 個の $G$ の像になります。$\mathrm{wt}(\boldsymbol{w}G + \boldsymbol{e}) \le \lambda n$ は $\boldsymbol{w}G \in B(\boldsymbol{e}, \lfloor \lambda n \rfloor)$ と同値なので、これを満たす $G$ の割合は $V_2(n, \lfloor\lambda n\rfloor)/2^n$ です（）。$\boldsymbol{e}$ について $P(\boldsymbol{e})$ の重みで平均しても同じ値です。したがって、 と合わせて $$ \frac{1}{2^{kn}} \sum_{G} P_{\mathrm{err}}(G) \le \frac{1}{4\varepsilon^2 n} + (2^k - 1)\,\frac{V_2(n, \lfloor \lambda n \rfloor)}{2^n} \le \frac{1}{4\varepsilon^2 n} + 2^{\,k - n + nH(\lambda)} $$ です。$k < Rn + 1$ なので、右辺を $a_n$ とおくと $a_n < \dfrac{1}{4\varepsilon^2 n} + 2 \cdot 2^{-n(1 - H(\lambda) - R)}$ で、$1 - H(\lambda) - R > 0$ より $a_n \to 0$ です。 **符号の選択。** 平均が $a_n$ 以下なので、$P_{\mathrm{err}}(G_n) \le a_n$ となる行列 $G_n$ があります。$a_n < 1$ のとき、$G_n$ の行は一次独立です。もし $\boldsymbol{w}G_n = \boldsymbol{0}$ となる $\boldsymbol{w} \ne \boldsymbol{0}$ があれば、$\mathrm{wt}(\boldsymbol{e}) \le \lambda n$ のときは $\boldsymbol{u}$ と $\boldsymbol{u} + \boldsymbol{w}$ がともに条件を満たして失敗し、$\mathrm{wt}(\boldsymbol{e}) > \lambda n$ のときは $\boldsymbol{u}$ が条件を満たさないので、復号は常に誤り、$P_{\mathrm{err}}(G_n) = 1$ となるからです。よって $G_n$ の行の張る空間 $C_n$ は $k$ 次元の線形符号で、$\boldsymbol{u} \mapsto \boldsymbol{u}G_n$ は $\mathbb{F}_2^k$ から $C_n$ への全単射、上の復号は $C_n$ への復号写像 $D_n$ を定め、どの符号語を送っても誤り確率は $a_n$ 以下です。$a_n \ge 1$ となる有限個の $n$ については任意の $k$ 次元符号を取ります。$a_n \to 0$ なので定理が示されました。 証明は符号を 1 つも具体的に作っていません。「無作為に選んだ線形符号は平均的によい」ことから存在だけを導いています。$p = 0.11$ なら $1 - H(p) \approx 0.5$ なので、情報率 $1/2$ 弱で、11% のビットが反転する通信路をほぼ誤りなく使えることになります。同じ情報率で最小距離による保証を求めると、訂正できるのは Gilbert–Varshamov 限界の符号で相対距離 $0.11$ の半分、$5.5\%$ 程度の誤りまでです。確率的な保証のほうが、およそ 2 倍の誤りに耐えます。 $1 - H(p)$ を誤り率 $p$ の二元対称通信路の**通信路容量**といいます。 の逆、すなわち「情報率が $R > 1 - H(p)$ の符号の列では、どんな復号を使っても復号誤り確率は $0$ に近づかない」も成り立ちます（符号化定理の逆）。証明には相互情報量と Fano の不等式が必要で、この記事の範囲を超えるので、主張と出典だけを記します。Shannon の原論文と、Cover–Thomas の教科書の通信路容量の章（参考文献）を参照してください。この記事の定理や証明は、この逆を使っていません。 ## 9. 演習 生成行列 $G = \begin{bmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{bmatrix}$ の二元符号 $C$ について、(a) 検査行列と最小距離を求めよ。(b) シンドロームと剰余類の代表元の表を作れ。(c) 2 個の誤りのうち、どれだけが正しく訂正されるか。 (a) $G = [\,I_2 \mid A\,]$、$A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}$ なので、 の 4 より（標数 $2$ では $-A^{\mathsf{T}} = A^{\mathsf{T}}$） $$ H = \begin{bmatrix} 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{bmatrix} $$ です。符号語は $00000, 10110, 01011, 11101$ で、最小重みは $3$ です。$C$ は $[5, 2, 3]_2$ 符号です。 (b) 剰余類は $2^{5-2} = 8$ 個です。重み $1$ の誤りのシンドロームは $H$ の列 $110, 011, 100, 010, 001$ で、相異なります。残るシンドロームは $101$ と $111$ です。$101 = 100 + 001$（第 3, 5 列）$= 110 + 011$（第 1, 2 列）なので、代表元は $00101$ か $11000$ のどちらかを選びます。$111 = 110 + 001$（第 1, 5 列）$= 011 + 100$（第 2, 3 列）なので、代表元は $10001$ か $01100$ です。 | シンドローム | 000 | 110 | 011 | 100 | 010 | 001 | 101 | 111 | |---|---|---|---|---|---|---|---|---| | 代表元 | 00000 | 10000 | 01000 | 00100 | 00010 | 00001 | 00101 | 10001 | (c) の 3 より、正しく訂正されるのは誤りベクトルが代表元であるときだけです。重み $2$ の誤り $\binom{5}{2} = 10$ 通りのうち、表に載っている $00101$ と $10001$ の 2 通りだけが訂正されます。1 個の誤りは 5 通りすべて訂正されます（$t = 1$）。 $[5, 2, 4]_2$ 符号が存在しないことを、限界式を使わずに直接示せ。また Plotkin 限界からも導け。 **直接。** $\boldsymbol{x}, \boldsymbol{y}$ を重み $4$ 以上の相異なる符号語とします。長さ $5$ なので、どちらも $0$ の座標は高々 1 個で、$\mathrm{supp}(\boldsymbol{x}) \cap \mathrm{supp}(\boldsymbol{y})$ は $3$ 個以上の座標を含みます。$\boldsymbol{x} + \boldsymbol{y}$ はその座標で $0$ なので $\mathrm{wt}(\boldsymbol{x} + \boldsymbol{y}) \le 2$ です。$2$ 次元の符号には $\boldsymbol{0}$ でない符号語が 3 個あり、$\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{x} + \boldsymbol{y}$ がすべて重み $4$ 以上であることはできません。 **Plotkin 限界。** $2d = 8 > 5 = n$ なので が使え、$M \le 8/(8 - 5) = 8/3$、つまり $M \le 2$ です。$M = 2^2 = 4$ は不可能です。 $C_1$ を $[n, k_1, d_1]_q$ 符号、$C_2$ を $[n, k_2, d_2]_q$ 符号とする。(a) $C = \{(\boldsymbol{u}, \boldsymbol{u} + \boldsymbol{v}) : \boldsymbol{u} \in C_1,\ \boldsymbol{v} \in C_2\}$ は $[2n,\ k_1 + k_2,\ \min(2d_1, d_2)]_q$ 符号であることを示せ。(b) $\mathrm{RM}(1, 1) = \mathbb{F}_2^2$ とし、$m \ge 1$ について $\mathrm{RM}(1, m + 1)$ を $C_1 = \mathrm{RM}(1, m)$、$C_2 = \mathrm{Rep}_{2^m}$ から (a) の構成で定める。$\mathrm{RM}(1, m)$ が $[2^m,\ m + 1,\ 2^{m-1}]_2$ 符号であることを示せ（1 次の Reed–Muller 符号）。 (a) $(\boldsymbol{u}, \boldsymbol{v}) \mapsto (\boldsymbol{u}, \boldsymbol{u} + \boldsymbol{v})$ は $C_1 \times C_2$ から $\mathbb{F}_q^{2n}$ への線形写像で、像が $\boldsymbol{0}$ なら $\boldsymbol{u} = \boldsymbol{0}$、$\boldsymbol{v} = \boldsymbol{0}$ なので単射です。よって $\dim C = k_1 + k_2$ です。$(\boldsymbol{u}, \boldsymbol{v}) \ne (\boldsymbol{0}, \boldsymbol{0})$ とします。$\boldsymbol{v} = \boldsymbol{0}$ なら重みは $2\,\mathrm{wt}(\boldsymbol{u}) \ge 2d_1$ です。$\boldsymbol{v} \ne \boldsymbol{0}$ なら、三角不等式（）より $\mathrm{wt}(\boldsymbol{u}) + \mathrm{wt}(\boldsymbol{u} + \boldsymbol{v}) \ge \mathrm{wt}\bigl((\boldsymbol{u} + \boldsymbol{v}) - \boldsymbol{u}\bigr) = \mathrm{wt}(\boldsymbol{v}) \ge d_2$ です。よって最小重みは $\min(2d_1, d_2)$ 以上です。$C_1$ の重み $d_1$ の元 $\boldsymbol{u}$ による $(\boldsymbol{u}, \boldsymbol{u})$ と、$C_2$ の重み $d_2$ の元 $\boldsymbol{v}$ による $(\boldsymbol{0}, \boldsymbol{v})$ が等号を与えます。 (b) $m$ についての帰納法です。$\mathrm{RM}(1, 1) = \mathbb{F}_2^2$ は $[2, 2, 1]_2$ 符号で、$m = 1$ の主張と合います。$\mathrm{RM}(1, m)$ が $[2^m, m + 1, 2^{m-1}]_2$ なら、$\mathrm{Rep}_{2^m}$ は $[2^m, 1, 2^m]_2$ なので、(a) より $\mathrm{RM}(1, m+1)$ は長さ $2^{m+1}$、次元 $m + 2$、最小距離 $\min(2 \cdot 2^{m-1}, 2^m) = 2^m$ です。$m = 3$ の $[8, 4, 4]_2$ 符号は の符号と同じパラメータをもちます。 $C$ を $[n, k, d]_2$ 符号とし、$d$ が奇数であるとする。パリティ拡大 $\widehat{C}$ は $[n + 1, k, d + 1]_2$ 符号であることを示せ。これを使って、$r \ge 2$ について $[2^r,\ 2^r - 1 - r,\ 4]_2$ 符号が存在することを示せ。 $\boldsymbol{c} \mapsto \widehat{\boldsymbol{c}} = (\boldsymbol{c}, c_1 + \cdots + c_n)$ は線形で単射なので $\dim \widehat{C} = k$ です。$\widehat{\boldsymbol{c}}$ の成分の和は $0$ なので、$\mathrm{wt}(\widehat{\boldsymbol{c}})$ は偶数です。$\mathrm{wt}(\boldsymbol{c})$ が奇数なら $\mathrm{wt}(\widehat{\boldsymbol{c}}) = \mathrm{wt}(\boldsymbol{c}) + 1$、偶数なら $\mathrm{wt}(\widehat{\boldsymbol{c}}) = \mathrm{wt}(\boldsymbol{c})$ です。$\boldsymbol{c} \ne \boldsymbol{0}$ なら $\mathrm{wt}(\boldsymbol{c}) \ge d$ で、$\mathrm{wt}(\widehat{\boldsymbol{c}})$ は $d$ 以上の偶数、$d$ が奇数なので $d + 1$ 以上です。重み $d$ の符号語は重み $d + 1$ に写るので、最小距離はちょうど $d + 1$ です。 $\mathrm{Ham}(r, 2)$ は より $[2^r - 1,\ 2^r - 1 - r,\ 3]_2$ 符号なので、そのパリティ拡大が求める符号です。$r = 3$ のときが です。 ## 参考文献 - F. J. MacWilliams, N. J. A. Sloane, *The Theory of Error-Correcting Codes*, North-Holland, 1977 — 第 1 章（線形符号）、第 17 章（符号の限界式）。 - J. H. van Lint, *Introduction to Coding Theory*, 3rd ed., Graduate Texts in Mathematics 86, Springer, 1999 — 第 2 章（Shannon の定理）、第 3 章（線形符号）、第 5 章（符号の限界式）。 - W. C. Huffman, V. Pless, *Fundamentals of Error-Correcting Codes*, Cambridge University Press, 2003 — 第 1 章・第 2 章。 - R. W. Hamming, "Error detecting and error correcting codes", *Bell System Technical Journal* 29 (1950), 147–160。 - C. E. Shannon, "A mathematical theory of communication", *Bell System Technical Journal* 27 (1948), 379–423, 623–656。 - T. M. Cover, J. A. Thomas, *Elements of Information Theory*, 2nd ed., Wiley, 2006 — 第 7 章（通信路容量。符号化定理の逆を含む）。