第6章巡回符号とリード–ソロモン符号（暗号と符号）

この章の目標

巡回符号を $\mathbb{F}_q[x]/(x^n - 1)$ のイデアルとして扱い、生成多項式と次元を求められる。 $\gcd(n, q) = 1$ の仮定がどこで必要かを説明できる

円分剰余類を使って $x^n - 1$ を既約分解し、BCH 符号を構成して BCH 限界を証明できる

リード–ソロモン符号が MDS 符号であることを証明し、ピーターソン–ゴレンシュタイン–ツィーラー法で復号できる

QR コード・CD・DVD・RAID 6・分散ストレージでリード–ソロモン符号が何をしているかを説明できる

CRC のバースト誤り検出能力を正確に述べて証明し、CRC が改ざん検出に使えない理由を説明できる

前提：第5章、04-algebra 第5章（剰余環とイデアル）、04-algebra 第8章（有限体の基本定理・乗法群の巡回性）。6.3 節（BCH 限界）と 6.5 節（PGZ 法）の証明では02-linear-algebra 第4章のヴァンデルモンドの行列式を使う。有限体上の既約多項式・原始多項式・CRC は04-algebra 第11章でも扱っている。

第5章で見たように、一般の線形符号の復号は難しい。実用の符号は、復号が「有限体上の方程式を解く」問題になるように、多項式の構造をもたせて作る。その代表が巡回符号で、符号語を多項式とみると符号は多項式環のイデアルになる。中でもリード–ソロモン符号は、シングルトン限界を等号で達成し（MDS）、連立一次方程式で復号できる。QR コード、CD・DVD、RAID 6、分散ストレージは、どれもこの符号を使っている。最後に、同じ多項式の割り算を誤り検出に使う CRC を見る。

本章では $q$ は標数 $p$ の素数べきとする。

6.1 有限体の復習と $x^n - 1$ の分解

04-algebra 第8章より、 $q$ 元体 $\mathbb{F}_q$ は同型を除いてただ一つで、 $\mathbb{F}_{q^m}$ は $\mathbb{F}_q$ を部分体として含み（定理 8.41）、 $\mathbb{F}_{q^m}^\times$ は位数 $q^m - 1$ の巡回群である（04 第8章定理 8.40）。 $\varphi(a) = a^q$ は $\mathbb{F}_{q^m}$ の環準同型で（04-algebra 第5章命題 5.36 を繰り返し使う）、 $a^q = a$ となるのは $a \in \mathbb{F}_q$ のときに限る（ $x^q - x$ の根は高々 $q$ 個で、 $\mathbb{F}_q$ の元はすべて根）。したがって $f \in \mathbb{F}_q[x]$ なら $f(a)^q = f(a^q)$ である。計算には、 $\alpha = \overline{x}$ が乗法群の生成元となる $\mathbb{F}_8 = \mathbb{F}_2[x]/(x^3 + x + 1)$ （04 第8章例 8.42）と $\mathbb{F}_{16} = \mathbb{F}_2[x]/(x^4 + x + 1)$ （04-algebra 第11章例 11.1）の表を使う。

補題 6.1（ $x^n - 1$ の根） $n \geq 1$ とする。

$p \nmid n$ （すなわち $\gcd(n, q) = 1$ ）なら $x^n - 1$ は重根をもたない。 $q^m \equiv 1 \pmod n$ となる最小の $m \geq 1$ をとると、 $\mathbb{F}_{q^m}$ は位数 $n$ の元 $\beta$ （1 の原始 $n$ 乗根）を含み、 $\mathbb{F}_{q^m}[x]$ で $x^n - 1 = \prod_{i=0}^{n-1}(x - \beta^i)$ である。

$p \mid n$ なら、 $n = pn'$ として $x^n - 1 = (x^{n'} - 1)^p$ であり、 $\mathbb{F}_q$ のどの拡大体にも位数 $n$ の元はない。

証明. (1) $(x^n - 1)' = nx^{n-1}$ で $n \neq 0$ なので、その根は $0$ だけで、 $x^n - 1$ の根ではない。よって重根はない（04 第8章命題 8.36(1)）。 $q$ は $\mathbb{Z}/n\mathbb{Z}$ の単元なので $m$ は存在し、巡回群 $\mathbb{F}_{q^m}^\times$ の位数 $q^m - 1$ は $n$ で割り切れるから、生成元 $\gamma$ について $\beta = \gamma^{(q^m - 1)/n}$ の位数は $n$ である。 $\beta^0, \dots, \beta^{n-1}$ は $x^n - 1$ の相異なる $n$ 個の根なので、積の式が成り立つ。(2) 標数 $p$ の環 $\mathbb{F}_q[x]$ で $(x^{n'} - 1)^p = x^{n} - 1$ （04 第5章命題 5.36）なので、 $x^n - 1$ の相異なる根は $n'$ 個以下である。位数 $n$ の元があれば、そのべきが相異なる $n$ 個の根になってしまう。 $\square$

定義 6.2（円分剰余類, cyclotomic coset） $\gcd(n, q) = 1$ とする。 $s \in \mathbb{Z}/n\mathbb{Z}$ に対し $C_s = \lbrace s, sq, sq^2, \dots \rbrace \subset \mathbb{Z}/n\mathbb{Z}$ を、 $n$ を法とする $q$ の円分剰余類という。

$j \mapsto jq$ は $\mathbb{Z}/n\mathbb{Z}$ の全単射なので、 $\mathbb{Z}/n\mathbb{Z}$ は円分剰余類に分割される。 $sq^m = s$ より $\lvert C_s \rvert \leq m$ である。

定理 6.3（ $x^n - 1$ の既約分解） $\gcd(n, q) = 1$ とし、 $\beta$ を補題 6.1 の元とする。 $M_s(x) = \prod_{j \in C_s}(x - \beta^j)$ は $\beta^s$ の $\mathbb{F}_q$ 上の最小多項式である。したがって、円分剰余類の代表 $s$ を 1 つずつとると、 $x^n - 1 = \prod_s M_s(x)$ が $\mathbb{F}_q[x]$ における既約分解である。

証明. $\varphi$ を $M_s$ の係数に施すと $\prod_{j \in C_s}(x - \beta^{jq}) = M_s$ （ $j \mapsto jq$ は $C_s$ の置換）なので、 $M_s$ の係数は $\mathbb{F}_q$ に属する。 $\beta^s$ の最小多項式を $M$ とすると、 $M_s(\beta^s) = 0$ より $M \mid M_s$ （04 第8章命題 8.7）。逆に $j = sq^i \in C_s$ なら $M(\beta^j) = M(\beta^s)^{q^i} = 0$ なので、 $M_s$ の相異なる根はすべて $M$ の根であり、 $M_s \mid M$ 。どちらもモニックなので $M = M_s$ 。円分剰余類は $\mathbb{Z}/n\mathbb{Z}$ を分割するので、 $\prod_s M_s = \prod_{i=0}^{n-1}(x - \beta^i) = x^n - 1$ 。 $\square$

例 6.4

$q = 2$ , $n = 7$ ： $m = 3$ で、円分剰余類は $\lbrace 0 \rbrace, \lbrace 1, 2, 4 \rbrace, \lbrace 3, 6, 5 \rbrace$ 。 $\beta = \alpha$ （ $\alpha^3 = \alpha + 1$ ）とすると $M_1 = x^3 + x + 1$ 。 $M_3$ の根 $\alpha^3, \alpha^5, \alpha^6$ について、表から和は $1$ 、2 つずつの積の和は $\alpha^8 + \alpha^9 + \alpha^{11} = \alpha + \alpha^2 + \alpha^4 = 0$ 、積は $\alpha^{14} = 1$ なので $M_3 = x^3 + x^2 + 1$ 。よって $x^7 - 1 = (x + 1)(x^3 + x + 1)(x^3 + x^2 + 1)$ 。
$q = 2$ , $n = 15$ ： $m = 4$ で、円分剰余類は $\lbrace 0 \rbrace, \lbrace 1, 2, 4, 8 \rbrace, \lbrace 3, 6, 12, 9 \rbrace, \lbrace 5, 10 \rbrace, \lbrace 7, 14, 13, 11 \rbrace$ 。 $\beta = \alpha$ （ $\alpha^4 = \alpha + 1$ ）とすると $M_1 = x^4 + x + 1$ 、 $M_3 = x^4 + x^3 + x^2 + x + 1$ （ $\alpha^3$ の位数は 5）、 $M_5 = x^2 + x + 1$ （ $\alpha^5$ の位数は 3）、 $M_7 = x^4 + x^3 + 1$ である（計算機で確かめた）。

6.2 巡回符号とイデアル

ベクトル $(c_0, c_1, \dots, c_{n-1}) \in \mathbb{F}_q^n$ （成分の番号は $0$ から）を多項式 $c(x) = c_0 + c_1x + \cdots + c_{n-1}x^{n-1}$ と同一視する。 $\mathbb{F}_q[x]$ の元は $x^n - 1$ で割った余りによって次数 $n$ 未満の多項式とただ一つ対応するので（04-algebra 第5章定理 5.28）、 $\mathbb{F}_q^n$ は剰余環 $R_n = \mathbb{F}_q[x]/(x^n - 1)$ と同一視できる。 $R_n$ では $x^n = 1$ なので、 $x$ 倍は巡回シフト $c_0 + \cdots + c_{n-1}x^{n-1} \mapsto c_{n-1} + c_0x + \cdots + c_{n-2}x^{n-1}$ である。

定義 6.5（巡回符号, cyclic code）線形符号 $C \subset \mathbb{F}_q^n$ が、 $(c_0, \dots, c_{n-1}) \in C \Rightarrow (c_{n-1}, c_0, \dots, c_{n-2}) \in C$ をみたすとき、 $C$ を巡回符号という。本章では、巡回符号を数えるときなどの便宜のため、 $\lbrace 0 \rbrace$ も巡回符号に含める（第5章の定義 5.9 では $k \geq 1$ としていた）。

命題 6.6 $C \subset R_n$ が巡回符号であることと、 $C$ が $R_n$ のイデアルであることは同値である。

証明. イデアルは定数倍で閉じているので部分空間であり、 $x$ 倍で閉じている。逆に巡回符号は $x^i$ 倍で閉じており、線形性から $\sum_i a_ix^i$ 倍で閉じている。 $\square$

定理 6.7（生成多項式, generator polynomial） $C \neq \lbrace 0 \rbrace$ を長さ $n$ の巡回符号とする。

$C$ の $0$ でない元（次数 $n$ 未満の多項式）のうち、次数が最小のモニック多項式 $g$ がただ一つある。これを $C$ の生成多項式という。

$g$ は $\mathbb{F}_q[x]$ において $x^n - 1$ を割り切る。

$r = \deg g$ とすると $C = \lbrace a(x)g(x) \mid \deg a < n - r \rbrace$ であり、 $g, xg, \dots, x^{n-r-1}g$ は $C$ の基底である。特に $\dim C = n - r$ 。

逆に、 $x^n - 1$ のモニックな約数 $g$ （ $r = \deg g < n$ ）について、(3) の右辺は生成多項式が $g$ の巡回符号である。

したがって、長さ $n$ の巡回符号と $x^n - 1$ のモニックな約数は 1 対 1 に対応する（ $\lbrace 0 \rbrace$ には $x^n - 1$ を対応させる）。

証明. (1) 次数最小の $0$ でない元を最高次の係数で割ればよい。そのような $g, g'$ が 2 つあれば、 $g - g' \in C$ は次数がより低いので $0$ 。

(2) $x^n - 1 = Qg + \rho$ （ $\deg \rho < r$ ）と割る。 $R_n$ で $\rho = -Qg$ であり、 $C$ はイデアルなので $\rho \in C$ 。次数の最小性より $\rho = 0$ 。

(3) $\deg a < n - r$ なら $ag$ は次数 $n$ 未満で、 $R_n$ の元 $a \cdot g \in C$ そのものである。逆に $c \in C$ を $c = ag + \rho$ （ $\deg \rho < r$ ）と割ると、 $\deg a < n - r$ なので $ag \in C$ で、 $\rho = c - ag \in C$ から $\rho = 0$ 。 $x^ig$ （ $0 \leq i < n - r$ ）は次数が相異なるので一次独立であり、 $C$ を張る。

(4) $C_g = \lbrace ag \mid \deg a < n - r \rbrace$ は $n - r$ 次元の部分空間である。 $h = (x^n - 1)/g$ とし、 $ag \in C_g$ の $a$ の $x^{n-r-1}$ の係数を $a'$ とすると、 $R_n$ で $x \cdot ag = xag - a'(x^n - 1) = (xa - a'h)g$ であり、 $xa - a'h$ は $x^{n-r}$ の項が消えて次数 $n - r$ 未満なので、これは $C_g$ に属する。よって $C_g$ は巡回符号で、 $0$ でない元の次数は $r$ 以上だから生成多項式は $g$ 。(1)〜(4) より、 $C \mapsto g$ と $g \mapsto C_g$ は互いに逆の対応である。 $\square$

注意 6.8（ $\gcd(n, q) = 1$ の役割）定理 6.7 は $\gcd(n, q) = 1$ を仮定せずに成り立つ。この仮定が効くのは次の 3 点である。

個数： $\gcd(n, q) = 1$ なら $x^n - 1$ は相異なるモニック既約多項式 $s$ 個の積で、巡回符号はちょうど $2^s$ 個ある。一般に $x^n - 1 = \prod_i f_i^{e_i}$ なら $\prod_i(e_i + 1)$ 個である。
零点による記述（命題 6.11）：生成多項式が相異なる $x - \beta^j$ の積になり、符号が条件「 $c(\beta^j) = 0$ 」で書ける。 $p \mid n$ ではこれが崩れる。たとえば $q = 2$ , $n = 4$ では $x^4 - 1 = (x + 1)^4$ で、生成多項式 $(x + 1)^e$ （ $e = 1, 2, 3$ ）の 3 つの符号 $[4, 3, 2]$ , $\lbrace 0000, 1010, 0101, 1111 \rbrace$ , $\lbrace 0000, 1111 \rbrace$ は、どの拡大体でも零点が $1$ だけで、零点では区別できない。
BCH 限界（定理 6.13）：位数 $n$ の元 $\beta$ が必要で、それは $p \nmid n$ のときにしか存在しない（補題 6.1）。

例 6.9（長さ 7 の 2 元巡回符号） $x^7 - 1$ は 3 個の既約因子をもつので（例 6.4）、2 元巡回符号は $2^3 = 8$ 個ある。 $\lbrace 0 \rbrace$ 以外は次のとおり（最小距離は計算機で確かめた）。

生成多項式	$[n, k, d]$	名前
$1$	$[7, 7, 1]$	全体
$x + 1$	$[7, 6, 2]$	偶数重みの符号
$x^3 + x + 1$ または $x^3 + x^2 + 1$	$[7, 4, 3]$	ハミング符号
$(x + 1)(x^3 + x + 1)$ または $(x + 1)(x^3 + x^2 + 1)$	$[7, 3, 4]$
$(x^3 + x + 1)(x^3 + x^2 + 1)$	$[7, 1, 7]$	繰り返し符号

$g = x^3 + x + 1$ は $\alpha$ の最小多項式なので、 $c \in C \iff g \mid c \iff \sum_i c_i\alpha^i = 0$ 。 $\alpha^i$ を基底 $1, \alpha, \alpha^2$ の係数の縦ベクトルとみると、これは $H = (\alpha^0 \ \alpha^1 \ \cdots \ \alpha^6)$ を検査行列とする条件で、 $H$ の列は $\mathbb{F}_2^3$ の $0$ でないベクトル全部だから、 $C$ はハミング符号である（第5章定義 5.19）。 $m$ 次の原始多項式についても同様である。

例 6.10（組織的な符号化）情報 $u(x)$ （ $\deg u < n - r$ ）に対し、 $x^ru(x)$ を $g$ で割った余り $\rho(x)$ を求めて $c(x) = x^ru(x) - \rho(x)$ とすると、 $c$ は $g$ で割り切れる次数 $n$ 未満の多項式なので符号語であり、 $x^r, \dots, x^{n-1}$ の係数は $u$ のままである。 $g = x^3 + x + 1$ , $u(x) = 1 + x^2 + x^3$ なら、 $g$ を法として $x^3 \equiv x + 1$ , $x^5 \equiv x^2 + x + 1$ , $x^6 \equiv x^2 + 1$ なので $x^3u \equiv 1$ で、 $c(x) = 1 + x^3 + x^5 + x^6$ 、すなわち $c = (1, 0, 0, 1, 0, 1, 1)$ を得る。後半 4 成分が $u = (1, 0, 1, 1)$ である。

6.3 BCH 符号と BCH 限界

この節と次の 2 節では $\gcd(n, q) = 1$ とし、 $\beta \in \mathbb{F}_{q^m}$ を補題 6.1 の 1 の原始 $n$ 乗根とする。 $\beta^n = 1$ なので、 $c \in R_n$ に対し $c(\beta^j)$ は代表の選び方によらない。

命題 6.11（零点による記述）巡回符号 $C$ の生成多項式を $g$ とし、 $Z = \lbrace j \in \mathbb{Z}/n\mathbb{Z} \mid g(\beta^j) = 0 \rbrace$ （ $C$ の定義集合）とする。 $Z$ は円分剰余類の和集合で、 $g = \prod_{j \in Z}(x - \beta^j)$ かつ $C = \lbrace c \in R_n \mid c(\beta^j) = 0 \ (j \in Z) \rbrace$ である。逆に、円分剰余類の和集合 $Z$ について、 $\prod_{j \in Z}(x - \beta^j)$ を生成多項式とする $n - \lvert Z \rvert$ 次元の巡回符号がある。

証明. $g$ は根が相異なる $x^n - 1 = \prod_i(x - \beta^i)$ を割るので、 $g = \prod_{j \in Z}(x - \beta^j)$ 。 $j \in Z$ なら $g(\beta^{jq}) = g(\beta^j)^q = 0$ なので、 $Z$ は円分剰余類の和集合である。次数 $n$ 未満の $c$ について $c \in C \iff g \mid c$ （定理 6.7(3)）。 $g \mid c$ なら $c(\beta^j) = 0$ （ $j \in Z$ ）。逆にこれが成り立てば、相異なる 1 次式 $x - \beta^j$ がすべて $c$ を割るので $\mathbb{F}_{q^m}[x]$ で $g \mid c$ であり、 $\mathbb{F}_q[x]$ での割り算の商と余りは $\mathbb{F}_{q^m}[x]$ でもそのまま商と余りなので、 $\mathbb{F}_q[x]$ でも $g \mid c$ 。逆の主張は、 $\prod_{j \in Z}(x - \beta^j)$ が $M_s$ たちの積であること（定理 6.3）と定理 6.7(4) による。 $\square$

定義 6.12（BCH 符号）整数 $b$ と $2 \leq \delta \leq n$ をとる。 $b, b + 1, \dots, b + \delta - 2$ を含む最小の円分剰余類の和集合を定義集合とする巡回符号、すなわち生成多項式が $M_b, \dots, M_{b+\delta-2}$ の最小公倍元である巡回符号を、設計距離 (designed distance) $\delta$ の BCH 符号という。 $b = 1$ のとき狭義 (narrow-sense)、 $n = q^m - 1$ のとき原始的 (primitive) という。

BCH 符号の名前は、独立に見つけた Hocquenghem（1959 年）と Bose, Ray-Chaudhuri（1960 年）の頭文字による。最小距離の評価の要は次の定理である。

定理 6.13（BCH 限界, BCH bound） $C$ を長さ $n$ の巡回符号とし、ある整数 $b$ と $\delta \geq 2$ について、すべての $c \in C$ が $c(\beta^b) = c(\beta^{b+1}) = \cdots = c(\beta^{b+\delta-2}) = 0$ をみたすとする。このとき $d(C) \geq \delta$ 。

証明. 重み $w \leq \delta - 1$ の符号語 $c \neq 0$ があったとし、その $0$ でない成分の位置を $i_1 < \cdots < i_w$ （ $0 \leq i_k < n$ ）、 $X_k = \beta^{i_k}$ とおく。 $\beta$ の位数は $n$ なので $X_1, \dots, X_w$ は相異なり、 $0$ でない。 $j = 0, 1, \dots, w - 1$ （ $\leq \delta - 2$ ）について

0 = c(\beta^{b+j}) = \sum_{k=1}^{w} c_{i_k}X_k^{b+j}

であり、これは $VDv = 0$ と書ける。ここで $v = (c_{i_1}, \dots, c_{i_w})^{\top}$ 、 $D = \operatorname{diag}(X_1^b, \dots, X_w^b)$ 、 $V = (X_k^j)_{0 \leq j < w,\ 1 \leq k \leq w}$ である。 $V$ の転置はヴァンデルモンド行列なので $\det V = \prod_{k < l}(X_l - X_k) \neq 0$ （02-linear-algebra 第4章定理 4.33, 定理 4.13）。 $\det D \neq 0$ なので $v = 0$ となり、 $c_{i_k} \neq 0$ に反する。 $\square$

系 6.14 設計距離 $\delta$ の BCH 符号は、最小距離が $\delta$ 以上、次元が $n - m(\delta - 1)$ 以上である。 $q = 2$ , $b = 1$ , $\delta = 2t + 1$ なら、次元は $n - mt$ 以上である。

証明. 最小距離は命題 6.11 と定理 6.13 による。次元は $n - \lvert Z \rvert$ で、 $Z$ は高々 $\delta - 1$ 個の円分剰余類（それぞれ $m$ 個以下の元）の和集合である。 $q = 2$ なら $C_{2i} = C_i$ なので、 $1, \dots, 2t$ の円分剰余類は奇数 $1, 3, \dots, 2t - 1$ の円分剰余類で尽くされ、 $\lvert Z \rvert \leq mt$ 。 $\square$

例 6.15（長さ 15 の 2 元 BCH 符号）例 6.4(2) の $\beta = \alpha$ を使う。

$\delta = 3$ ：定義集合 $C_1$ 、 $g = M_1 = x^4 + x + 1$ 。 $[15, 11, 3]$ のハミング符号である。
$\delta = 5$ ：定義集合 $C_1 \cup C_3 = \lbrace 1, 2, 3, 4, 6, 8, 9, 12 \rbrace$ 、 $g = M_1M_3 = x^8 + x^7 + x^6 + x^4 + 1$ 。 $[15, 7]$ 符号で $d \geq 5$ であり、 $g$ 自身が重み 5 の符号語なので $d = 5$ 。
$\delta = 7$ ：定義集合 $C_1 \cup C_3 \cup C_5$ 、 $g = M_1M_3M_5 = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1$ （重み 7）。 $[15, 5, 7]$ 符号である。

$\delta = 4$ としても定義集合は $C_1 \cup C_3 \supset \lbrace 1, 2, 3, 4 \rbrace$ となり、 $\delta = 5$ と同じ符号になる。真の最小距離が設計距離より大きいこともあるわけである。 $[15, 7, 5]$ 符号は 2 個の誤りを訂正でき、第5章例 5.27 のハミング限界 $k \leq 8$ に近い。

6.4 リード–ソロモン符号

定義 6.16（リード–ソロモン符号, Reed–Solomon code） $1 \leq k \leq n \leq q$ とし、相異なる $\alpha_1, \dots, \alpha_n \in \mathbb{F}_q$ をとる。 $\operatorname{RS}_k = \lbrace (f(\alpha_1), \dots, f(\alpha_n)) \mid f \in \mathbb{F}_q[x],\ \deg f < k \rbrace$ （ $f = 0$ を含む）をリード–ソロモン符号という。

リードとソロモンが 1960 年に導入した。情報は $k$ 個の係数で、それを $n$ 点での値として送る。

定理 6.17 $\operatorname{RS}_k$ は $[n, k, n - k + 1]$ 符号、すなわち MDS 符号である。さらに、どの $k$ 個の位置の値からも符号語がただ一つに決まる。

証明. $f \mapsto (f(\alpha_1), \dots, f(\alpha_n))$ は $k$ 次元の空間 $\lbrace f \mid \deg f < k \rbrace$ 上の線形写像である。 $f \neq 0$ の根は高々 $k - 1$ 個なので（04-algebra 第5章系 5.30）、像の $0$ でない成分は $n - k + 1$ 個以上ある。よってこの写像は単射で $\dim \operatorname{RS}_k = k$ 、最小距離は $n - k + 1$ 以上であり、シングルトン限界（第5章定理 5.23）より等号が成り立つ。 $k$ 個の位置で一致する 2 つの符号語は高々 $n - k < d$ 個の位置でしか異ならないので等しい。 $\square$

最後の主張は、 $n - k$ 個までの消失を訂正できるということである（第5章定理 5.7(3)）。値を知っている $k$ 点からラグランジュ補間で $f$ を求めればよい。

定理 6.18（巡回符号としてのリード–ソロモン符号） $n = q - 1$ とし、 $\beta$ を $\mathbb{F}_q^\times$ の生成元とする。評価点を $1, \beta, \dots, \beta^{n-1}$ の順にとり、成分の番号を $0$ から $n - 1$ とする（第 $i$ 成分は $f(\beta^i)$ ）。このとき $\operatorname{RS}_k$ は、生成多項式 $g(x) = \prod_{j=1}^{n-k}(x - \beta^j)$ の巡回符号に等しい。これは $m = 1$ , $b = 1$ , 設計距離 $n - k + 1$ の BCH 符号である。

証明. $f = \sum_{l=0}^{k-1} f_lx^l$ , $c_i = f(\beta^i)$ とすると

c(\beta^j) = \sum_{i=0}^{n-1} f(\beta^i)\beta^{ij} = \sum_{l=0}^{k-1} f_l\sum_{i=0}^{n-1}(\beta^{l+j})^i

である。 $1 \leq j \leq n - k$ なら $1 \leq l + j \leq n - 1$ なので $\gamma = \beta^{l+j} \neq 1$ で、 $\gamma^n = 1$ より $\sum_{i=0}^{n-1}\gamma^i = (\gamma^n - 1)/(\gamma - 1) = 0$ 。よって $c(\beta^j) = 0$ （ $1 \leq j \leq n - k$ ）であり、命題 6.11 より $\operatorname{RS}_k$ は生成多項式 $g$ の巡回符号に含まれる。次元はどちらも $k$ なので等しい。 $m = 1$ では円分剰余類は 1 点ずつ（ $q \equiv 1 \pmod n$ ）なので、最後の主張も従う。 $\square$

例 6.19（ $\mathbb{F}_7$ 上のリード–ソロモン符号） $q = 7$ , $n = 6$ , $\beta = 3$ とする。 $3^0, \dots, 3^5$ は $1, 3, 2, 6, 4, 5$ で、 $3$ は $\mathbb{F}_7^\times$ の生成元である。 $k = 2$ とすると $[6, 2, 5]$ 符号で、2 個の誤りを訂正できる。生成多項式は $g(x) = (x - 3)(x - 2)(x - 6)(x - 4) = x^4 + 6x^3 + 3x^2 + 2x + 4$ 。情報 $f(x) = 2 + 3x$ は $c = (f(1), f(3), f(2), f(6), f(4), f(5)) = (5, 4, 1, 6, 0, 3)$ に符号化され、実際 $c(x) = 5 + 4x + x^2 + 6x^3 + 3x^5 = (3x + 3)g(x)$ である。どの 2 成分からも $f$ （2 点を通る直線）が決まるので、4 個までの消失を訂正できる。

6.5 復号：ピーターソン–ゴレンシュタイン–ツィーラー法

$t \geq 1$ とし、 $C$ を、すべての符号語が $c(\beta^j) = 0$ （ $1 \leq j \leq 2t$ ）をみたす長さ $n$ の巡回符号とする（狭義の BCH 符号で $\delta \geq 2t + 1$ のもの、または $n - k = 2t$ の定理 6.18 の符号）。BCH 限界より $d(C) \geq 2t + 1$ で、 $t$ 個までの誤りが訂正できるはずである。それを実行する手順を作る。

符号語 $c$ を送り $r = c + e$ を受け取ったとする。 $e$ の $0$ でない成分の位置を $i_1, \dots, i_\nu$ （ $\nu \leq t$ ）、値を $Y_l = e_{i_l}$ 、誤り位置 (error locator) を $X_l = \beta^{i_l}$ （相異なる）とする。シンドローム

S_j = r(\beta^j) = e(\beta^j) = \sum_{l=1}^{\nu} Y_lX_l^j \qquad (1 \leq j \leq 2t)

は $r$ から計算できる。誤り位置多項式 (error-locator polynomial) を $\Lambda(x) = \prod_{l=1}^{\nu}(1 - X_lx) = 1 + \Lambda_1x + \cdots + \Lambda_\nu x^\nu$ とする。その根 $X_l^{-1}$ がわかれば誤りの位置がわかる。

補題 6.20（鍵方程式） $1 \leq j \leq 2t - \nu$ について $S_{j+\nu} + \Lambda_1S_{j+\nu-1} + \cdots + \Lambda_\nu S_j = 0$ 。

証明. $\Lambda_0 = 1$ とすると、各 $l$ について $\sum_{i=0}^{\nu}\Lambda_iX_l^{-i} = \Lambda(X_l^{-1}) = 0$ 。これに $Y_lX_l^{j+\nu}$ を掛けて $l$ について足すと $\sum_{i=0}^{\nu}\Lambda_iS_{j+\nu-i} = 0$ （添字 $j + \nu - i$ は $1$ 以上 $2t$ 以下）。 $\square$

補題 6.21 $1 \leq \mu \leq t$ について、 $\mu \times \mu$ 行列 $M_\mu = (S_{i+j-1})_{1 \leq i, j \leq \mu}$ は、 $\mu = \nu$ なら正則、 $\mu > \nu$ なら正則でない。

証明. $\mu \times \nu$ 行列 $W = (X_l^{i-1})_{i, l}$ と $D = \operatorname{diag}(Y_1X_1, \dots, Y_\nu X_\nu)$ について、 $(WDW^{\top})_{ij} = \sum_l Y_lX_l^{i+j-1} = S_{i+j-1}$ 、すなわち $M_\mu = WDW^{\top}$ 。 $\mu > \nu$ なら $\operatorname{rank} M_\mu \leq \nu < \mu$ 。 $\mu = \nu$ なら $\det M_\nu = (\det W)^2\prod_l Y_lX_l \neq 0$ （ $W$ はヴァンデルモンド行列の転置）。 $\square$

ピーターソン–ゴレンシュタイン–ツィーラー (PGZ) 法

$S_1, \dots, S_{2t}$ を計算する。すべて $0$ なら $r$ を出力する。
$\det M_\mu \neq 0$ となる最大の $\mu \leq t$ を $\nu$ とする（なければ失敗）。
連立一次方程式 $M_\nu(\Lambda_\nu, \Lambda_{\nu-1}, \dots, \Lambda_1)^{\top} = -(S_{\nu+1}, \dots, S_{2\nu})^{\top}$ を解く。
$i = 0, \dots, n - 1$ について $\Lambda(\beta^{-i}) = 0$ かを調べる（チェン探索）。根がちょうど $\nu$ 個でなければ失敗とする。
手順 4 で見つかった位置を $i'_1, \dots, i'_\nu$ とし、 $X_l = \beta^{i'_l}$ として $\sum_l Y_lX_l^j = S_j$ （ $1 \leq j \leq \nu$ ）を解いて $Y_l$ を求める。第 $i'_l$ 成分が $Y_l$ で、ほかの成分が $0$ のベクトルを $\hat{e}$ とする（ $q = 2$ なら $Y_l = 1$ ）。
$r - \hat{e}$ のシンドローム（ $j = 1, \dots, 2t$ ）がすべて $0$ なら $r - \hat{e}$ を出力し、そうでなければ失敗とする（ $t$ 個を超える誤りに備える確認）。

定理 6.22（PGZ 法の正しさ） $\operatorname{wt}(e) \leq t$ なら、上の手順は送られた符号語 $c$ を出力する。

証明. $\nu = 0$ ならシンドロームはすべて $0$ 。 $\nu \geq 1$ なら $M_\nu$ は正則（補題 6.21）なので、シンドロームのどれかは $0$ でない。手順 2：補題 6.21 より正しい $\nu$ が得られる。手順 3：この連立方程式は補題 6.20 の $j = 1, \dots, \nu$ の場合（ $\nu \leq 2t - \nu$ なので使える）そのもので、 $M_\nu$ は正則だから解は真の係数に限る。手順 4： $\Lambda$ の根は相異なる $\nu$ 個の $X_l^{-1} = \beta^{-i_l}$ なので、見つかる位置は真の位置 $i_1, \dots, i_\nu$ である。手順 5：係数行列 $(X_l^j)_{j, l}$ はヴァンデルモンド行列の転置に $\operatorname{diag}(X_1, \dots, X_\nu)$ を掛けたもので正則なので、真の $Y_l$ が求まり、 $\hat{e} = e$ となる。手順 6： $r - \hat{e} = c$ は符号語なので確認を通り、 $c$ が出力される。 $\square$

この方法はピーターソン（1960 年、2 元 BCH 符号）とゴレンシュタイン–ツィーラー（1961 年、一般の場合）による。

例 6.23（例 6.19 の符号の復号）符号語 $c = (5, 4, 1, 6, 0, 3)$ を送り、 $r = (5, 6, 1, 3, 0, 3)$ を受け取ったとする（ $t = 2$ ）。 $S_j = \sum_i r_i\beta^{ij}$ を $\beta^{ij}$ の表から計算する。

$j$	$\beta^{ij}$ （ $i = 0, \dots, 5$ ）	$S_j$
1	$1, 3, 2, 6, 4, 5$	$5 + 18 + 2 + 18 + 0 + 15 = 58 \equiv 2$
2	$1, 2, 4, 1, 2, 4$	$5 + 12 + 4 + 3 + 0 + 12 = 36 \equiv 1$
3	$1, 6, 1, 6, 1, 6$	$5 + 36 + 1 + 18 + 0 + 18 = 78 \equiv 1$
4	$1, 4, 2, 1, 4, 2$	$5 + 24 + 2 + 3 + 0 + 6 = 40 \equiv 5$

$\det M_2 = S_1S_3 - S_2^2 = 1 \neq 0$ なので $\nu = 2$ 。連立方程式

\begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} \Lambda_2 \\ \Lambda_1 \end{pmatrix} = \begin{pmatrix} -1 \\ -5 \end{pmatrix} = \begin{pmatrix} 6 \\ 2 \end{pmatrix}

を解くと $\Lambda_2 = 4$ , $\Lambda_1 = 5$ で、 $\Lambda(x) = 1 + 5x + 4x^2 = (1 + x)(1 + 4x)$ 。根 $x = -1 = \beta^3$ と $x = -4^{-1} = 5 = \beta^5$ から $X = \beta^{-3} = \beta^3$ , $\beta^{-5} = \beta^1$ で、誤りは第 1 成分と第 3 成分にある。値は $S_1 = 3Y_1 + 6Y_3 = 2$ , $S_2 = 2Y_1 + Y_3 = 1$ を解いて $Y_1 = 2$ , $Y_3 = 4$ 。 $r$ から引くと $c$ が復元され、 $f(1) = 5$ , $f(3) = 4$ から $f(x) = 2 + 3x$ を得る。

注意

誤りが $t$ 個を超えると、復号器は失敗を報告することもあれば、別の符号語を出力して気づかないこともある。例 6.23 の $c$ に 3 個の誤りを加える $20 \cdot 6^3 = 4320$ 通りを調べると、PGZ 法は 3960 通りで失敗を報告し、360 通りで別の符号語を出力した（計算機で確かめた。手順 6 の確認を省くと、3960 通りのうち 360 通りでは、失敗を報告せずに符号語でない語を出力してしまう）。たとえば第 0, 2, 5 成分に $1$ を加えると、 $\Lambda(x) = 1 + x + 4x^2$ は $\mathbb{F}_7$ に根をもたず、失敗が検出される。上位の層で誤り検出（CRC など）を併用するのはこのためである。

注意 6.24（実用の復号法。概略） $S(x) = \sum_{j=1}^{2t} S_jx^{j-1}$ , $\Omega(x) = \sum_l Y_lX_l\prod_{k \neq l}(1 - X_kx)$ とおくと、 $S(x) \equiv \sum_l Y_lX_l/(1 - X_lx) \pmod{x^{2t}}$ から $\Lambda(x)S(x) \equiv \Omega(x) \pmod{x^{2t}}$ が従い、その係数を比べたものが補題 6.20 である。実用の復号器は、この合同式をみたす $\Lambda$ をバーレカンプ–マッシー法（1968・1969 年）や拡張ユークリッド互除法（杉山ら, 1975 年）で $O(t^2)$ 回程度の演算で求め、誤りの値をフォーニーの公式 $Y_l = -\Omega(X_l^{-1})/\Lambda'(X_l^{-1})$ で求める（例 6.23 では $\Omega(x) = 2 + 4x$ で、同じ値になる）。これらの正しさの証明は省略する（Roth の教科書を参照）。

6.6 応用

実用のリード–ソロモン符号の多くは $\mathbb{F}_{2^8}$ 上のもので、1 バイトを 1 記号として扱う。記号単位で訂正するので、連続する 8 ビット以内のバースト誤りは高々 2 個の記号の誤りにすぎない。さらに複数の符号語の記号を交互に並べるインターリーブ (interleaving) を使うと、 $D$ 個の符号語を交互に送る場合、長さ $L$ 記号のバーストは各符号語に高々 $\lceil L/D \rceil$ 個の誤りしか与えない。

QR コード（規格 ISO/IEC 18004）は、 $\mathbb{F}_{2^8} = \mathbb{F}_2[x]/(x^8 + x^4 + x^3 + x^2 + 1)$ 上のリード–ソロモン符号を使う（この多項式が原始多項式であることは計算機で確かめた）。誤り訂正レベルは L, M, Q, H の 4 段階で、それぞれ符号語のおよそ 7%, 15%, 25%, 30% を復元できるとされる。レベルを上げるほど検査記号が増え、入るデータは減る。
CD（規格 IEC 60908）の CIRC（cross-interleaved Reed–Solomon code）は、 $\mathbb{F}_{2^8}$ 上の 2 つの短縮 RS 符号 $[32, 28, 5]$ と $[28, 24, 5]$ （どちらも $[255, 251, 5]$ の RS 符号を短縮したもの）を、インターリーブをはさんで組み合わせる。ここで、線形符号の、特定の位置が $0$ の符号語だけを集めてその位置を除くことを短縮という。 $[n, k, n - k + 1]$ の MDS 符号（ $k \geq 2$ ）を短縮すると、重みは変わらないので最小距離は減らず、次元はちょうど $k - 1$ になる（減らないとすると、その位置はどの符号語でも $0$ で、それを除いた $[n - 1, k, n - k + 1]$ 符号がシングルトン限界に反する）。よって、シングルトン限界から $[n - 1, k - 1, n - k + 1]$ の MDS 符号になる。よく使われる復号法では、内側の符号で訂正しきれなかった記号を消失として外側の符号に渡す。
DVD（DVD-ROM の規格 ECMA-267）では、 $\mathbb{F}_{2^8}$ 上の短縮 RS 符号 $[182, 172, 11]$ と $[208, 192, 17]$ を、データを並べた表の行と列にそれぞれ使う積符号 (product code) で誤りを訂正する。
RAID 6 は、 $n$ 台のデータディスクに 2 台の検査用ディスクを加え、どの 2 台が同時に故障しても復元できるようにする。Linux カーネルの実装では、各バイトを QR コードと同じ $\mathbb{F}_{2^8}$ の元とみて、 $g = \overline{x}$ , $n \leq 255$ として $P = \sum_i D_i$ , $Q = \sum_i g^iD_i$ を記録する。これは $[n + 2, n, 3]$ の MDS 符号である（問題 6.5）。
分散ストレージでは、データを $k$ 個の断片に分け、MDS 符号で $n$ 個の断片に符号化して別々のサーバーに置く。どの $k$ 個からも復元できるので（定理 6.17）、 $n - k$ 台までの故障に耐える。 $(n, k) = (9, 6)$ なら容量 1.5 倍で 3 台の故障に耐える（3 重の複製は容量 3 倍で 2 台まで）。ただし素朴な方法では、失った 1 個の断片を作り直すのにも $k$ 個の断片を読む必要がある（複製なら 1 個で済む）。

ヒント

実務では 符号のパラメータは、想定する誤りのモデル（ランダムな誤りか、バーストか、位置のわかる消失か）から決める。消失は誤りの半分の冗長性で直せる（第5章問題 5.4）ので、故障したディスクのように位置がわかるなら、その情報を復号器に渡すべきである。また RAID 6 が保証するのは「同時に 2 台までの故障」からの復元であり、誤操作による削除や、ソフトウェアの不具合で書かれた誤ったデータは検査用ディスクにもそのまま反映される。冗長化はバックアップの代わりにならない。

6.7 CRC：誤り検出

04-algebra 第11章 11.10 節の CRC（巡回冗長検査）を、巡回符号の言葉で見直す。ビット列を $\mathbb{F}_2[x]$ の多項式とみて（左端を最高次）、 $r$ 次の生成多項式 $G$ （ $G(0) = 1$ ）を決める。メッセージ $M$ に対し、 $x^rM$ を $G$ で割った余り $R$ を付けた $T = x^rM + R$ を送り、受信側は受け取った多項式が $G$ で割り切れるかを調べる。これは例 6.10 の組織的な符号化と同じ計算で、 $G = x^3 + x + 1$ , $M = 1101$ なら $R = 001$ 、送信列 $1101001$ は例 6.10 の符号語 $1 + x^3 + x^5 + x^6$ を高次から並べたものである。 $G \mid x^e - 1$ となる最小の $e$ をとると（ $G(0) = 1$ より存在する）、長さ $e$ 以下の送信列の全体は、長さ $e$ の巡回符号 $(G)$ を短縮したものになる。

誤りのパターンを $E$ （反転したビットを多項式とみたもの）とすると、誤りを見逃すのは $G \mid E$ のときに限る。04 第11章命題 11.22 では、長さ $r$ 以下のバースト誤り、 $(x + 1) \mid G$ のときの奇数個の誤り、間隔が $e$ 未満の 2 ビットの誤りが検出されることを示した。バースト誤りについては、もう一歩正確に言える。

定理 6.25（CRC のバースト誤り検出） $G \in \mathbb{F}_2[x]$ を $r$ 次（ $r \geq 1$ ）で $G(0) = 1$ とする。送信列に収まる $E = x^iB$ （ $\deg B = b - 1$ , $B(0) = 1$ ）の形の誤り、すなわち反転した最初と最後のビットを含む区間の長さが $b$ の誤りを、長さ $b$ のバースト誤り (burst error) という。

$b \leq r$ なら、長さ $b$ のバースト誤りはすべて検出される。

開始位置 $i$ を固定すると、長さ $r + 1$ のバースト誤り $2^{r-1}$ 通りのうち、検出されないのは $E = x^iG$ の 1 通りだけである。

$b \geq r + 2$ なら、開始位置 $i$ を固定した長さ $b$ のバースト誤り $2^{b-2}$ 通りのうち、検出されないのはちょうど $2^{b-r-2}$ 通りである。

証明. $G(0) = 1$ より $\gcd(G, x^i) = 1$ なので、 $G \mid x^iB \iff G \mid B$ 。長さ $b \geq 2$ の $B$ は、定数項と $x^{b-1}$ の係数が $1$ で、間の $b - 2$ 個が自由なので $2^{b-2}$ 通りある。(1) $B \neq 0$ , $\deg B < r$ なら $G \nmid B$ 。(2) $\deg B = r$ で $G \mid B$ なら $B = G$ で、 $G$ は $G(0) = 1$ をみたす。(3) $G \mid B$ なら $B = GQ$ , $\deg Q = b - 1 - r \geq 1$ , $Q(0) = B(0) = 1$ 。逆にこの形の $Q$ から作った $B = GQ$ は条件をみたす。そのような $Q$ は、最高次と定数項の係数が $1$ で間の $b - r - 2$ 個が自由なので $2^{b-r-2}$ 通り。 $\square$

バーストの中身が一様にランダムだと仮定すれば、見逃す確率は $b = r + 1$ で $2^{-(r-1)}$ 、 $b \geq r + 2$ で $2^{-r}$ になる。この確率は「中身が一様」という仮定のもとでの値である。 $G = x^4 + x + 1$ と $(x + 1)(x^3 + x + 1)$ について、開始位置 $0$ 、 $b \leq 9$ のバーストをすべて調べても定理の通りの個数になる（計算機で確かめた）。

イーサネット（IEEE 802.3）、ZIP、PNG などで使われる CRC-32 の生成多項式 $G = x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$ は原始多項式である（ $x$ の位数が $2^{32} - 1$ であることを計算機で確かめた）。したがって長さ 32 以下のバーストと、長さ $2^{32} - 1$ 以下の送信列での 2 ビットの誤りをすべて検出する。 $G(1) = 1$ なので、奇数個の誤りの検出は 04 第11章命題 11.22(2) からは保証されない。

実際の CRC-32 には、(i) 各バイトの下位ビットを高次の係数とみる（ $G$ のビットを逆順にした定数 0xEDB88320 を使う）、(ii) 初期値を全ビット $1$ にする、(iii) 最後に全ビットを反転する、という約束がある。(ii) は、先頭に $0$ のビットが加わっても値が変わらないという素朴な CRC の欠点を補う。長さを固定すると CRC は線形写像に定数を加えた写像になり、 $\operatorname{crc}(m \oplus \Delta) = \operatorname{crc}(m) \oplus \operatorname{crc}(\Delta) \oplus \operatorname{crc}(0)$ （ $\oplus$ はビットごとの排他的論理和、 $0$ は同じ長さの零ビット列）が成り立つので、誤りを見逃す条件は $m$ によらず、素朴な割り算の場合と同じである。次のコードで、ビットごとの計算が zlib.crc32 と一致することと、この等式を確かめる。

import zlib

def crc32(data: bytes) -> int:
    crc = 0xFFFFFFFF                      # 初期値（全ビット 1）
    for byte in data:
        crc ^= byte
        for _ in range(8):                # 1 ビットずつ G で割る（ビットの並びは逆順）
            crc = (crc >> 1) ^ (0xEDB88320 if crc & 1 else 0)
    return crc ^ 0xFFFFFFFF               # 最後に全ビットを反転

m = b"123456789"
print(hex(crc32(m)), hex(zlib.crc32(m)))
d = bytes([0, 0, 0, 0, 0x10, 0, 0, 0, 0])            # 5 バイト目の 1 ビットを反転する差分
x = bytes(a ^ b for a, b in zip(m, d))
print(hex(crc32(x) ^ crc32(m)), hex(crc32(d) ^ crc32(bytes(9))))

0xcbf43926 0xcbf43926
0x60e09782 0x60e09782

1 行目の 0xcbf43926 は CRC-32 の検査値としてよく知られた値である。2 行目は、 $m$ を知らなくても差分 $\Delta$ だけから CRC の変化が計算できることを示している。

注意

CRC は偶然の誤りを検出するためのもので、改ざんの検出には使えない。上の等式から、攻撃者はメッセージの中身を知らなくても、好きなビットを反転させたうえで CRC を正しく直せる。無線 LAN の旧方式 WEP は、暗号化したデータの完全性を CRC-32 で守ろうとして、この種の攻撃を受けた（2001 年に指摘された）。改ざんの検出には、鍵を使うメッセージ認証符号（第7章の HMAC など）やデジタル署名を使う。

まとめ

$\gcd(n, q) = 1$ なら $x^n - 1$ は重根をもたず、円分剰余類ごとの最小多項式 $M_s$ の積に分解する。
巡回符号は $\mathbb{F}_q[x]/(x^n - 1)$ のイデアルで、 $x^n - 1$ のモニックな約数（生成多項式 $g$ ）と 1 対 1 に対応し、次元は $n - \deg g$ 。この対応に $\gcd(n, q) = 1$ は要らないが、個数の数え方・零点による記述・BCH 限界には要る。
BCH 限界：連続する $\beta^b, \dots, \beta^{b+\delta-2}$ を零点にもつ巡回符号の最小距離は $\delta$ 以上（ヴァンデルモンドの行列式）。
リード–ソロモン符号は $[n, k, n - k + 1]$ の MDS 符号で、 $n = q - 1$ なら零点 $\beta, \dots, \beta^{n-k}$ の巡回符号になる。
PGZ 法は $t$ 個以下の誤りを必ず正しく直す。 $t$ 個を超えると失敗や誤訂正が起こる。
1 バイトを 1 記号とする RS 符号とインターリーブはバーストや消失に強く、QR コード、CD・DVD、RAID 6、分散ストレージで使われている。
CRC は短縮した巡回符号で、 $r$ 次の $G$ （ $G(0) = 1$ ）は長さ $r$ 以下のバーストをすべて検出し、長さ $r + 1$ では $2^{-(r-1)}$ 、それより長いと $2^{-r}$ の割合のバーストを見逃す。CRC はアフィンなので改ざん検出には使えない。

演習問題

問題 6.1 ★ $\mathbb{F}_2$ 上で $x^9 - 1$ を円分剰余類を使って既約分解し、長さ 9 の 2 元巡回符号の個数と、とりうる次元をすべて求めよ。

解答

$2^1, \dots, 2^6 \bmod 9$ は $2, 4, 8, 7, 5, 1$ なので $m = 6$ 。円分剰余類は $\lbrace 0 \rbrace$ , $\lbrace 1, 2, 4, 8, 7, 5 \rbrace$ , $\lbrace 3, 6 \rbrace$ で、既約因子の次数は $1, 6, 2$ である。 $x^9 - 1 = (x^3 - 1)(x^6 + x^3 + 1)$ , $x^3 - 1 = (x + 1)(x^2 + x + 1)$ なので、定理 6.3 より 6 次の既約因子は $x^6 + x^3 + 1$ で、 $x^9 - 1 = (x + 1)(x^2 + x + 1)(x^6 + x^3 + 1)$ 。巡回符号は $2^3 = 8$ 個（ $\lbrace 0 \rbrace$ と全体を含む）。生成多項式の次数は $\lbrace 1, 2, 6 \rbrace$ の部分集合の和 $0, 1, 2, 3, 6, 7, 8, 9$ なので、次元は $9, 8, 7, 6, 3, 2, 1, 0$ 。

問題 6.2 ★ 例 6.4(1) の $\beta = \alpha$ を使う。BCH 限界を使って、長さ 7 の 2 元巡回符号のうち、生成多項式が $x^3 + x + 1$ , $(x + 1)(x^3 + x + 1)$ , $(x^3 + x + 1)(x^3 + x^2 + 1)$ のものの最小距離が、それぞれ 3, 4, 7 以上であることを示せ。

解答

定義集合はそれぞれ $C_1 = \lbrace 1, 2, 4 \rbrace$ , $C_0 \cup C_1 = \lbrace 0, 1, 2, 4 \rbrace$ , $C_1 \cup C_3 = \lbrace 1, \dots, 6 \rbrace$ である（命題 6.11）。連続する零点の指数は $\lbrace 1, 2 \rbrace$ , $\lbrace 0, 1, 2 \rbrace$ （ $b = 0$ ）, $\lbrace 1, \dots, 6 \rbrace$ を含むので、定理 6.13 より最小距離はそれぞれ $3, 4, 7$ 以上である。例 6.9 の表のとおり、どれも等号が成り立つ。

問題 6.3 ★★ 1 個の誤りだけを訂正する場合（ $t = 1$ ）、PGZ 法は「 $X = S_2/S_1$ , $Y = S_1^2/S_2$ 」となることを示せ。これを使って、 $\mathbb{F}_8$ （例 6.4(1) の $\alpha$ ）上の $[7, 5, 3]$ リード–ソロモン符号（零点 $\alpha, \alpha^2$ ）で、受信語 $r = (\alpha^3, \alpha^6, \alpha^5, 1, 0, \alpha^2, 0)$ を復号せよ。

解答

誤りが 1 個なら $S_1 = YX$ , $S_2 = YX^2$ で、 $X, Y \neq 0$ なので $X = S_2/S_1$ , $Y = S_1^2/S_2$ （手順 3 は $S_1\Lambda_1 = -S_2$ で、 $\Lambda(x) = 1 - (S_2/S_1)x$ の根の逆数が $X$ ）。

04 第8章例 8.42 の表（ $\alpha^3 = \alpha + 1$ , $\alpha^4 = \alpha^2 + \alpha$ , $\alpha^5 = \alpha^2 + \alpha + 1$ , $\alpha^6 = \alpha^2 + 1$ , $\alpha^7 = 1$ ）を使うと

\begin{aligned} S_1 &= r(\alpha) = \alpha^3 + \alpha^7 + \alpha^7 + \alpha^3 + \alpha^7 = 1, \\ S_2 &= r(\alpha^2) = \alpha^3 + \alpha^8 + \alpha^9 + \alpha^6 + \alpha^{12} = (\alpha + 1) + \alpha + \alpha^2 + (\alpha^2 + 1) + (\alpha^2 + \alpha + 1) = \alpha^5 \end{aligned}

よって $X = \alpha^5$ （第 5 成分）、 $Y = \alpha^{-5} = \alpha^2$ 。第 5 成分から $\alpha^2$ を引いて $c = (\alpha^3, \alpha^6, \alpha^5, 1, 0, 0, 0)$ 。検算：これは $(1 + x)(x + \alpha)(x + \alpha^2) = (1 + x)(x^2 + \alpha^4x + \alpha^3)$ の係数に等しい。

問題 6.4 ★★★ 例 6.15 の 2 元 BCH 符号 $[15, 7, 5]$ で 2 個の誤りを訂正する。

2 元の場合 $S_2 = S_1^2$ であることを示し、誤りがちょうど 2 個なら $\Lambda(x) = 1 + S_1x + \dfrac{S_3 + S_1^3}{S_1}x^2$ となることを示せ。
受信語 $r(x) = 1 + x^2 + x^4 + x^6 + x^7 + x^8 + x^{10}$ を復号せよ（ $\mathbb{F}_{16}$ の表は 04 第11章例 11.1(2)）。

解答

$r$ の係数は $\mathbb{F}_2$ に属するので $r(a)^2 = r(a^2)$ 、よって $S_2 = S_1^2$ 。誤りが 2 個なら $Y_l = 1$ で、 $S_1 = X_1 + X_2$ , $S_3 = X_1^3 + X_2^3$ 。標数 2 では $(X_1 + X_2)^3 = X_1^3 + X_2^3 + X_1X_2(X_1 + X_2)$ なので $S_1^3 = S_3 + X_1X_2S_1$ 。 $X_1 \neq X_2$ より $S_1 \neq 0$ で、 $X_1X_2 = (S_3 + S_1^3)/S_1$ 。 $\Lambda(x) = 1 + (X_1 + X_2)x + X_1X_2x^2$ から主張が従う。
$\alpha^k$ を 4 桁の 2 進数（ $\alpha^3, \alpha^2, \alpha, 1$ の係数）で表す。 $S_1 = \alpha^0 + \alpha^2 + \alpha^4 + \alpha^6 + \alpha^7 + \alpha^8 + \alpha^{10}$ は $0001 \oplus 0100 \oplus 0011 \oplus 1100 \oplus 1011 \oplus 0101 \oplus 0111 = 0011 = \alpha^4$ 。 $S_3 = r(\alpha^3)$ の指数 $0, 6, 12, 18, 21, 24, 30$ を 15 で割った余りは $0, 6, 12, 3, 6, 9, 0$ で、同じ指数の 2 項は打ち消し合うので $S_3 = \alpha^{12} + \alpha^3 + \alpha^9 = 1111 \oplus 1000 \oplus 1010 = 1101 = \alpha^{13}$ 。 $S_1^3 = \alpha^{12}$ より $S_3 + S_1^3 = 1101 \oplus 1111 = 0010 = \alpha$ 、 $\Lambda_2 = \alpha/\alpha^4 = \alpha^{12}$ 。 $\alpha^2 + \alpha^{10} = 0100 \oplus 0111 = \alpha^4$ , $\alpha^2\alpha^{10} = \alpha^{12}$ なので $\Lambda(x) = (1 + \alpha^2x)(1 + \alpha^{10}x)$ で、誤りは第 2 成分と第 10 成分である。訂正すると $c(x) = 1 + x^4 + x^6 + x^7 + x^8 = g(x)$ で、確かに符号語である。

問題 6.5 ★★ $g \in \mathbb{F}_{2^8}$ の位数を 255 とし、 $n \leq 255$ とする。データ $D_0, \dots, D_{n-1} \in \mathbb{F}_{2^8}$ に $P = \sum_i D_i$ , $Q = \sum_i g^iD_i$ を加えた $(D_0, \dots, D_{n-1}, P, Q)$ 全体は $[n + 2, n, 3]$ の MDS 符号であることを示せ。また、データ $D_x, D_y$ （ $x \neq y$ ）が同時に失われたときの復元の式を求めよ。

解答

標数 2 なので、条件は $\sum_i D_i + P = 0$ , $\sum_i g^iD_i + Q = 0$ で、検査行列の列は $(1, g^i)^{\top}$ （ $0 \leq i < n$ ）、 $(1, 0)^{\top}$ 、 $(0, 1)^{\top}$ である。データの列どうしは $\det = g^j - g^i \neq 0$ （ $0 \leq i < j < 255$ で $g$ の位数は 255）、データと $P$ の列は $\det = -g^i \neq 0$ 、残りの組は $\det = \pm 1$ なので、どの 2 本の列も一次独立である。第5章定理 5.13 より $d \geq 3 = (n + 2) - n + 1$ で MDS 符号であり、2 個の消失を訂正できる。

残ったデータから $P' = P + \sum_{i \neq x, y} D_i = D_x + D_y$ , $Q' = Q + \sum_{i \neq x, y} g^iD_i = g^xD_x + g^yD_y$ を計算すると、 $g^yP' + Q' = (g^x + g^y)D_x$ なので

D_x = \frac{g^yP' + Q'}{g^x + g^y}, \qquad D_y = P' + D_x

（ $g^x + g^y \neq 0$ ）。データと $P$ が失われたら $Q$ から、データと $Q$ なら $P$ から復元し、 $P$ と $Q$ なら再計算すればよい。

問題 6.6 ★★ ファームウェアの更新ファイルに CRC-32 を付け、機器は CRC が一致したものだけを書き込む、という設計で「改ざんも防げる」と説明された。この説明の誤りを、6.7 節の等式を使って指摘せよ。CRC を含むデータ全体を、鍵ストリームとの排他的論理和で暗号化した（ストリーム暗号）場合はどうか。

解答

CRC の計算方法は公開されていて鍵を使わないので、攻撃者は改ざんしたファイルの CRC を計算し直して付ければよい。中身を知らなくても、差分 $\Delta$ を加えた $m \oplus \Delta$ の CRC は $\operatorname{crc}(m) \oplus \operatorname{crc}(\Delta) \oplus \operatorname{crc}(0)$ で、 $\Delta$ だけから計算できる。CRC は偶然の誤りの検出にしか役立たない。

ストリーム暗号で暗号化しても防げない。暗号文のビットを反転すると、復号後の平文の同じビットが反転するので、攻撃者は平文に差分 $\Delta$ を加え、暗号化された CRC の部分を $\operatorname{crc}(\Delta) \oplus \operatorname{crc}(0)$ だけ反転させればよい。復号後の CRC は改ざん後のデータと一致する（WEP が受けた攻撃と同じ原理）。改ざん検出には、メッセージ認証符号やデジタル署名（ファームウェアなら署名の検証）が必要である。