# 巡回符号・BCH 符号・Reed–Solomon 符号：x^n − 1 の約数と零点で符号を設計する > 巡回符号を F_q[x]/(x^n − 1) のイデアルとして分類し、零点の集合から BCH 限界を導く。Reed–Solomon 符号が MDS 符号であること、Berlekamp–Welch の復号、鍵方程式と互除法による復号、Forney の公式、バースト誤りの訂正能力まで証明する。 > https://rikai.mugen-giken.com/mathematics/finite-fields-coding/cyclic-bch-reed-solomon ## 0. この記事の要点 データを送ったり保存したりすると、ノイズや傷で一部が壊れることがあります。そこで元のデータに余分な情報を付けておき、壊れた箇所を見つけて直せるようにする仕組みが誤り訂正符号です。この記事では、符号を「多項式の割り算」という身近な道具で設計し、CD や QR コードに使われる Reed–Solomon 符号が、なぜ多くの誤りを直せるのかを証明します。読み終えると、符号の最小距離を設計の段階で保証する方法と、受信した語から誤りを取り除く手順が分かります。 - 長さ $n$ の**巡回符号**は、剰余環 $R_n = \mathbb{F}_q[x]/(x^n-1)$ のイデアルと同じものです。各巡回符号は $x^n - 1$ のモニックな約数 $g$（**生成多項式**）でただ 1 通りに表され、次元は $n - \deg g$ です。$\gcd(n, q) = 1$ なら巡回符号は $2^{t}$ 個（$t$ は $x^n-1$ の既約因子の個数）です。 - $g$ の根の指数の集合（**定義集合**）で符号を指定すると、「連続する $\delta - 1$ 個の冪 $\alpha^b, \ldots, \alpha^{b+\delta-2}$ が零点なら最小距離は $\delta$ 以上」という **BCH 限界**が Vandermonde 行列式から出ます。 - **Reed–Solomon 符号**は、次数 $k$ 未満の多項式を $n$ 個の点で評価して作る $[n, k, n-k+1]_q$ 符号で、Singleton 限界の等号を達成します（[MDS 符号](/mathematics/finite-fields-coding/linear-codes#def-ball-volume)。最小距離が理論上の上限に届いている符号のこと）。$n = q - 1$ のときは零点 $\alpha, \alpha^2, \ldots, \alpha^{n-k}$ をもつ BCH 符号と一致します。 - 復号は 2 通り示します。**Berlekamp–Welch の方法**は連立一次方程式を 1 つ解くだけで $\lfloor (n-k)/2 \rfloor$ 個までの誤りを訂正します。**鍵方程式** $\sigma(x) S(x) \equiv \omega(x) \pmod{x^{2t}}$ は拡張 Euclid の互除法で解け（Sugiyama の方法）、誤りの値は Forney の公式で求まります。 - 巡回 $[n, k]$ 符号は長さ $n - k$ 以下のバースト誤りをすべて検出し、長さ $b$ 以下のバーストをすべて訂正できる線形符号は $n - k \ge 2b$ を満たします。 ## 1. 動機 [第 3 章](/mathematics/finite-fields-coding/linear-codes) では、線形符号を「$\mathbb{F}_q^n$ の部分空間」として扱い、最小距離の上界（Singleton 限界・Hamming 限界）と、ランダムな構成による下界（Gilbert–Varshamov 限界）を示しました。しかし、部分空間を 1 つ与えられても、その最小距離を求めるには一般にすべての符号語を調べるしかありません。次元 $k$ が 100 を超えると、これは実行できません。 そこで、符号に代数的な構造を課して、最小距離を**設計の段階で**保証することを考えます。この章で課す構造は「座標の巡回シフトで不変」という 1 つだけです。語 $(c_0, \ldots, c_{n-1})$ を多項式 $c_0 + c_1 x + \cdots + c_{n-1}x^{n-1}$ と同一視すると、巡回シフトは $x$ を掛けて $x^n = 1$ とみなす操作になり、符号は環 $\mathbb{F}_q[x]/(x^n-1)$ のイデアルになります。すると符号の分類は「$x^n - 1$ の約数の分類」になり、これは [第 2 章](/mathematics/finite-fields-coding/polynomials-trace-norm) で済んでいます。さらに、約数を根の集合で指定すれば、符号語であることが「いくつかの点で値が $0$ になる多項式であること」に言い換えられ、最小距離の評価が「次数の低い多項式は根を多くもてない」という事実に帰着します。 この見方から、BCH 符号（Bose–Ray-Chaudhuri 1960、Hocquenghem 1959）と Reed–Solomon 符号（1960）が出てきます。後者は CD・QR コード・深宇宙通信・分散ストレージで今も使われている符号です。 この章が前の章のどの定理に乗っているかを先にまとめます。 | この章の定理 | 使う前の章の定理 | |---|---| | 巡回符号の個数（） | 第 2 章の $x^n - 1$ の分解 | | 零点による記述（）、BCH 符号の次元（） | 第 2 章の最小多項式と共役元 | | 双対符号（）、MDS 符号の特徴づけ（） | 第 3 章の双対符号の次元、検査行列と最小距離 | | Reed–Solomon 符号（） | 第 3 章の Singleton 限界 | ## 2. 準備：多項式の除法と Vandermonde 行列式 ### 2.1. 記号 $q$ は素数冪、$\mathbb{F}_q$ は $q$ 元体です。語 $c = (c_0, c_1, \ldots, c_{n-1}) \in \mathbb{F}_q^n$ の座標は $0$ から数え、$c$ に多項式 $$ c(x) = c_0 + c_1 x + \cdots + c_{n-1}x^{n-1} \in \mathbb{F}_q[x] $$ を対応させます。Hamming 重み $\operatorname{wt}(c)$、最小距離 $d(C)$、双対符号 $C^{\perp}$、$[n, k, d]_q$ 符号という言葉は第 3 章のとおりです。$\mathbb{F}_q^n$ の標準的な双線形形式を $c \cdot u = \sum_{i} c_i u_i$ と書きます。 ### 2.2. 除法と根の個数 多項式の割り算と「次数 $d$ の多項式の根は $d$ 個以下」という事実は、この章の証明のほとんどで使います。体 $K$ の上で述べ直しておきます。 $K$ を体とする。 1. $a, b \in K[x]$、$b \ne 0$ に対し、$a = sb + r$、$\deg r < \deg b$（または $r = 0$）を満たす $s, r \in K[x]$ がただ 1 組ある。 2. $f \in K[x]$ と $\beta \in K$ について、$f(\beta) = 0$ であることと $x - \beta$ が $f$ を割り切ることは同値である。 3. $0$ でない $f \in K[x]$ の相異なる根は $\deg f$ 個以下である。とくに、次数が $d$ 以下の多項式が $d + 1$ 個の相異なる点で $0$ になれば、零多項式である。 (1) 存在を $\deg a$ についての帰納法で示します。$a = 0$ または $\deg a < \deg b$ なら $s = 0$、$r = a$ とします。$\deg a \ge \deg b$ のとき、$a, b$ の最高次の係数を $a_m, b_l$（$m = \deg a$、$l = \deg b$）とすると、$a' = a - (a_m/b_l)x^{m-l} b$ は $x^m$ の項が消えるので $a' = 0$ または $\deg a' < m$ です。帰納法の仮定で $a' = s'b + r$ と書け、$a = (s' + (a_m/b_l)x^{m-l})b + r$ となります。一意性: $sb + r = s'b + r'$ なら $(s - s')b = r' - r$ です。$s \ne s'$ とすると、$K[x]$ は整域で次数は積で加法的（）なので左辺の次数は $\deg b$ 以上ですが、右辺は $0$ か次数が $\deg b$ 未満で、矛盾します。よって $s = s'$、$r = r'$ です。 (2) (1) を $b = x - \beta$ に使うと $f = s\cdot(x - \beta) + r$ で、$r$ は定数です。$x = \beta$ を代入すると $r = f(\beta)$ なので、$f(\beta) = 0$ は $r = 0$、つまり $x - \beta$ が $f$ を割り切ることと同値です。 (3) $\deg f$ についての帰納法です。$\deg f = 0$ なら $f$ は $0$ でない定数で根をもちません。$\deg f = d \ge 1$ で根 $\beta$ があれば、(2) により $f = (x - \beta)f_1$、$\deg f_1 = d - 1$ です。$\beta$ と異なる根 $\beta'$ は $(\beta' - \beta)f_1(\beta') = 0$ と $K$ が整域であること（）から $f_1$ の根で、帰納法の仮定によりそれは $d - 1$ 個以下です。したがって $f$ の根は $d$ 個以下です。後半は対偶です。 ### 2.3. Vandermonde 行列式 $R$ を可換環、$x_1, \ldots, x_m \in R$ とする。$m$ 次正方行列 $V(x_1, \ldots, x_m) = (x_j^{\,i})_{0 \le i \le m-1,\ 1 \le j \le m}$（第 $i$ 行が $i$ 乗を並べた行）について $$ \det V(x_1, \ldots, x_m) = \prod_{1 \le i < j \le m} (x_j - x_i) $$ が成り立つ。とくに $R$ が体で $x_1, \ldots, x_m$ が相異なれば $V$ は正則である。 **体の場合。** $R = K$ が体のとき、$m$ についての帰納法で示します。$m = 1$ では両辺とも $1$ です（空な積は $1$）。$m \ge 2$ とします。$i = m-1, m-2, \ldots, 1$ の順に、第 $i$ 行から第 $i-1$ 行の $x_1$ 倍を引きます。この操作で行列式は変わりません（ の 3 と 5）。操作のあと、第 $0$ 行はすべて $1$ のまま、第 $i$ 行（$i \ge 1$）の第 $j$ 成分は $$ x_j^{\,i} - x_1 x_j^{\,i-1} = x_j^{\,i-1}(x_j - x_1) $$ で、第 1 列は上から $1, 0, \ldots, 0$ になります。第 1 列で余因子展開すると（）、行列式は、成分が $x_j^{\,i-1}(x_j - x_1)$（$1 \le i \le m-1$、$2 \le j \le m$）の $m - 1$ 次行列の行列式に等しくなります。この行列の第 $j$ 列から共通因子 $x_j - x_1$ をくくり出すと（同命題の 2） $$ \det V(x_1, \ldots, x_m) = \prod_{j=2}^{m}(x_j - x_1)\cdot \det V(x_2, \ldots, x_m) $$ で、帰納法の仮定から主張が従います。 **可換環の場合。** $m$ 個の不定元の整数係数多項式環 $A = \mathbb{Z}[X_1, \ldots, X_m]$ は整域で、その商体 $K$ は体です。体の場合を $K$ の元 $X_1, \ldots, X_m$ に使うと、$\det V(X_1, \ldots, X_m) = \prod_{i）なので、$X_j \mapsto x_j$ で定まる環準同型 $A \to R$ でこの等式を写すと、$R$ での等式になります。 **正則性。** $K$ が体で $x_j$ が相異なれば右辺は $0$ でない元の積で $0$ でなく、$V$ は正則です（）。 実数の場合の同じ式は [多項式補間](/mathematics/numerical-analysis/polynomial-interpolation) で補間多項式の一意性に使いました。有限体の上でも役割は同じで、「相異なる点での値が多項式を決める」ことの行列による表現です。 ## 3. 巡回符号とイデアル ### 3.1. 巡回符号は $R_n$ のイデアル 線形符号 $C \subseteq \mathbb{F}_q^n$ が**巡回符号**であるとは、$(c_0, c_1, \ldots, c_{n-1}) \in C$ ならば、その巡回シフト $(c_{n-1}, c_0, c_1, \ldots, c_{n-2})$ も $C$ に属することをいう。 $R_n = \mathbb{F}_q[x]/(x^n - 1)$ とおきます。 の 1 により、$R_n$ の各剰余類は次数 $n$ 未満の多項式をちょうど 1 つ含むので、$\pi : \mathbb{F}_q^n \to R_n$、$c \mapsto c(x) \bmod (x^n - 1)$ は $\mathbb{F}_q$ 線形な全単射です。以後、$\pi$ で $\mathbb{F}_q^n$ と $R_n$ を同一視します。 線形符号 $C \subseteq \mathbb{F}_q^n$ が巡回符号であることと、$\pi(C)$ が環 $R_n$ のイデアルであることは同値である。 $R_n$ の中で $x^n = 1$ なので $$ x \cdot c(x) = c_0 x + c_1 x^2 + \cdots + c_{n-2}x^{n-1} + c_{n-1}x^n = c_{n-1} + c_0 x + \cdots + c_{n-2}x^{n-1} $$ です。つまり、$R_n$ で $x$ を掛けることが巡回シフトです。 $\pi(C)$ がイデアルなら、$x$ 倍で閉じているので $C$ は巡回シフトで閉じています。逆に $C$ が巡回符号なら、$\pi(C)$ は $\mathbb{F}_q$ 部分空間で $x$ 倍で閉じているので、繰り返して $x^i$ 倍で閉じ、線形性から任意の多項式 $\sum_i a_i x^i$ 倍で閉じます。$R_n$ の元はすべて多項式の類なので、$\pi(C)$ は加法で閉じ、$R_n$ の元を掛けても閉じる部分集合、すなわちイデアルです（）。 ### 3.2. 生成多項式 $C \subseteq \mathbb{F}_q^n$ を巡回符号とする。 1. $x^n - 1$ のモニックな約数 $g(x)$ で、$C = \{\, a(x)g(x) \bmod (x^n-1) : a \in \mathbb{F}_q[x] \,\}$ となるものがただ 1 つある。これを $C$ の**生成多項式**という。 2. $k = n - \deg g$ とおくと、$C = \{\, a(x)g(x) : \deg a < k \,\}$（$k = 0$ のときは $C = \{0\}$）で、$g, xg, \ldots, x^{k-1}g$ が $C$ の基底である。とくに $\dim C = n - \deg g$。 3. 逆に、$x^n - 1$ のモニックな約数 $g$ はどれも、ある巡回符号の生成多項式である。したがって長さ $n$ の巡回符号は $x^n - 1$ のモニックな約数と 1 対 1 に対応する。 4. $\gcd(n, q) = 1$ で、$x^n - 1$ の $\mathbb{F}_q$ 上の相異なるモニック既約因子が $t$ 個あれば、長さ $n$ の巡回符号はちょうど $2^{t}$ 個ある。 (1) $I = \{ f \in \mathbb{F}_q[x] : f \bmod (x^n - 1) \in C \}$ とおきます。これはイデアル $\pi(C)$（）の、自然な全射準同型 $\mathbb{F}_q[x] \to R_n$ による逆像で、和と $\mathbb{F}_q[x]$ の元による積で閉じるので $\mathbb{F}_q[x]$ のイデアルです。$x^n - 1 \in I$ なので $I \ne \{0\}$ です。$\mathbb{F}_q[x]$ は単項イデアル整域なので（）$I = (g)$ と書け、最高次の係数で割って $g$ をモニックに取れます。$x^n - 1 \in (g)$ なので $g$ は $x^n - 1$ を割り切り、$C$ は $I$ の像なので $C = \{ ag \bmod (x^n - 1) \}$ です。 一意性: モニックな約数 $g'$ も同じ性質をもつとします。$g' \bmod (x^n-1) \in C$ なので $g' \in I = (g)$、つまり $g \mid g'$ です。逆に $g \bmod (x^n - 1) \in C$ なので $g \equiv a g' \pmod{x^n - 1}$ となる $a$ があり、$g' \mid x^n - 1$ と合わせて $g' \mid g$ です。互いに割り切るモニック多項式は、次数が等しく商が定数 $1$ なので一致します。 (2) $h = (x^n - 1)/g$ とおくと $\deg h = k$ です。$C$ の元を次数 $n$ 未満の多項式 $c$ で表すと、$c \in I$ なので $c = bg$（$b \in \mathbb{F}_q[x]$）と書けます。$c \ne 0$ なら $\deg b = \deg c - \deg g < n - \deg g = k$ です。逆に $\deg a < k$ なら $\deg(ag) < n$ で、$ag$ はそのまま $C$ の元を表す次数 $n$ 未満の多項式です。よって $C = \{ ag : \deg a < k\}$ で、これは $g, xg, \ldots, x^{k-1}g$ で張られます。これら $k$ 個は次数が $\deg g, \deg g + 1, \ldots, n - 1$ と相異なるので一次独立です（一次結合が $0$ なら、最高次の項を比べて係数が順に $0$ になります）。 (3) モニックな約数 $g$ に対し、$C_g = \{ ag \bmod (x^n - 1) \}$ は $R_n$ のイデアルなので巡回符号です（）。$g$ は (1) の性質をもつので、(1) の一意性から $C_g$ の生成多項式は $g$ です。対応 $C \mapsto g$ と $g \mapsto C_g$ は互いに逆です。 (4) $\gcd(n, q) = 1$ のとき、$x^n - 1 = f_1 f_2 \cdots f_t$ と相異なるモニック既約多項式の積に分解します（）。$\mathbb{F}_q[x]$ は一意分解整域なので（）、モニックな約数は $\{f_1, \ldots, f_t\}$ の部分集合の積で、異なる部分集合は異なる積を与えます。部分集合は $2^{t}$ 個です。 $g(x) = g_0 + g_1 x + \cdots + g_{n-k}x^{n-k}$ のとき、(2) の基底を行に並べた $$ G = \begin{pmatrix} g_0 & g_1 & \cdots & g_{n-k} & & & \\ & g_0 & g_1 & \cdots & g_{n-k} & & \\ & & \ddots & & & \ddots & \\ & & & g_0 & g_1 & \cdots & g_{n-k} \end{pmatrix} $$ が生成行列です（空欄は $0$）。$k \times n$ 行列を覚える代わりに、次数 $n - k$ の多項式 1 つを覚えれば済みます。これが巡回符号の実装上の利点です。 $\mathbb{F}_2$ 上で $x^7 - 1 = (x+1)(x^3+x+1)(x^3+x^2+1)$ です（右辺を展開して確かめられます）。既約因子は $t = 3$ 個なので、巡回符号は $2^3 = 8$ 個です。 | 生成多項式 $g$ | $[n, k, d]$ | 符号 | |---|---|---| | $1$ | $[7, 7, 1]$ | 全空間 | | $x + 1$ | $[7, 6, 2]$ | 偶数重みの語全体（パリティ検査符号） | | $x^3 + x + 1$ | $[7, 4, 3]$ | Hamming 符号 | | $x^3 + x^2 + 1$ | $[7, 4, 3]$ | Hamming 符号（座標を逆順にしたもの） | | $(x+1)(x^3+x+1) = x^4+x^3+x^2+1$ | $[7, 3, 4]$ | 単体符号 | | $(x+1)(x^3+x^2+1) = x^4+x^2+x+1$ | $[7, 3, 4]$ | 単体符号 | | $(x^3+x+1)(x^3+x^2+1) = x^6 + x^5 + \cdots + 1$ | $[7, 1, 7]$ | 反復符号 | | $x^7 - 1$ | $[7, 0, -]$ | $\{0\}$ | 最小距離は次のように分かります。$g = x+1$ のとき、符号語 $a(x)(x+1)$ は $x = 1$ で $0$、つまり係数の和が $0$ なので偶数重みで、次元が $6$ なので偶数重みの語全体です。$g = x^3+x+1$ が Hamming 符号を与えることは で示します。次元 $3$ の 2 つは、Hamming 符号の偶数重みの部分符号で、Hamming 符号の重みは $0, 3, 4, 7$ なので（[第 5 章](/mathematics/finite-fields-coding/weight-enumerators-golay) で重み多項式を計算します）、$0$ でない語の重みはすべて $4$ です。 ### 3.3. 検査多項式と双対符号 $h(x) = (x^n - 1)/g(x)$ を $C$ の**検査多項式**といいます。$c = ag$ なら $c h = a(x^n - 1) \equiv 0$ なので、$C$ の元は $R_n$ の中で $h$ を掛けると $0$ になります。この関係を係数で書くと、双対符号が読み取れます。次数 $m$ の多項式 $f$（$f(0) \ne 0$）の**相反多項式**を $f^{*}(x) = x^{m} f(1/x)$ と定めます。$f = \sum_{i=0}^m f_i x^i$ なら $f^{*} = \sum_{i=0}^m f_{m-i}x^i$ で、係数を逆順に並べたものです。次の定理のねらいは、双対符号（もとの符号と直交する語の全体）もまた巡回符号になり、その生成多項式が $h$ の係数を逆順にしたものから読み取れる、ということです。証明は、$h$ の係数の並びが符号語との内積で $0$ になることを見て、そのシフトが $C^{\perp}$ の基底になると次元で確かめる、という順に進みます。 $C$ を生成多項式 $g$、検査多項式 $h = (x^n - 1)/g$ の巡回 $[n, k]$ 符号とする（$k = \deg h$）。このとき $C^{\perp}$ も巡回符号で、その生成多項式は $h^{*}(x)/h(0)$ である。 $gh = x^n - 1$ の定数項を比べると $g(0)h(0) = -1$ なので、$g(0) \ne 0$、$h(0) \ne 0$ です。$h = \sum_{j=0}^{k} h_j x^j$ と書きます。 **$h^{*}$ のシフトは $C$ と直交する。** $c \in C$ を $c = ag$、$\deg a < k$ と書きます（ の 2）。多項式として $c(x)h(x) = a(x)(x^n - 1) = a(x)x^n - a(x)$ です。$\deg a < k$ なので、右辺の $x^m$ の係数は $k \le m \le n - 1$ で $0$ です。左辺の $x^m$ の係数は $\sum_{i} c_i h_{m-i}$（$0 \le m - i \le k$ の範囲の和）なので $$ \sum_{i=m-k}^{m} c_i\, h_{m-i} = 0 \qquad (k \le m \le n-1) $$ です。$m = k + s$（$0 \le s \le n-k-1$）とおくと、これは $c$ と、多項式 $x^{s}h^{*}(x) = \sum_{i=s}^{s+k} h_{k+s-i}\,x^{i}$ の係数ベクトルとの標準的な双線形形式の値が $0$ であることを述べています。よって $x^s h^{*}$（$0 \le s \le n - k - 1$）はすべて $C^{\perp}$ に属します。 **次元の比較。** $h^{*}$ の最高次の係数は $h_0 = h(0) \ne 0$ なので $\deg h^{*} = k$ で、$x^s h^{*}$（$0 \le s \le n-k-1$）は次数が $k, \ldots, n-1$ と相異なり一次独立です。$\dim C^{\perp} = n - k$ なので（）、これらが $C^{\perp}$ の基底です。 **生成多項式であること。** $g^{*}(x)h^{*}(x) = x^{n-k}g(1/x)\cdot x^{k}h(1/x) = x^n\bigl((1/x)^n - 1\bigr) = 1 - x^n$ なので、$h^{*}/h(0)$ は $x^n - 1$ のモニックな約数で、次数は $k$ です。これを生成多項式とする巡回符号は $\{ b\,h^{*} : \deg b < n - k \}$（ の 2）で、上で求めた $C^{\perp}$ の基底が張る空間と一致します。 情報 $m(x)$（$\deg m < k$）を符号語にするとき、$a = m$ として $mg$ を作る代わりに、$x^{n-k}m(x)$ を $g$ で割った余り $r(x)$ を使って $c(x) = x^{n-k}m(x) - r(x)$ とすると、$c$ は $g$ の倍数で、上位 $k$ 個の係数に情報がそのまま現れます。通信で使われる CRC（）はこの形です。 ### 3.4. 冪等生成元 $\gcd(n, q) = 1$ のとき、巡回符号には生成多項式とは別の標準的な生成元があります。次の命題は、符号 $C$ を環 $R_n$ のイデアルとして見たとき、$C$ の中だけで掛け算を考えると「$1$ に当たる元」$e$ があり、$C$ のどの元に掛けても変わらない、と述べています。この $e$ 自身が $C$ を生成します。 $\gcd(n, q) = 1$ とし、$C$ を長さ $n$ の巡回符号とする。$R_n$ の元 $e$ で、$e^2 = e$ かつ $C = \{ ae : a \in R_n \}$ を満たすものがただ 1 つある。これを $C$ の**冪等生成元**という。$e$ は環 $C$ の乗法の単位元である。 $g$ を生成多項式、$h = (x^n - 1)/g$ とします。$x^n - 1$ は相異なる既約多項式の積なので（）、$g$ と $h$ に共通の既約因子はありません。イデアル $(g) + (h)$ は単項で（）、その生成元は $g$ と $h$ の共通の約数なので定数です。よって $ug + vh = 1$ となる $u, v \in \mathbb{F}_q[x]$ があります。$e = ug \bmod (x^n - 1)$ とおきます。 $R_n$ の中で $gh = 0$ なので、$e^2 = e(1 - vh) = e - uv\,gh = e$ です。$e \in C$ で、$g = g(ug + vh) = ge + v\,gh = ge$ なので $g$ は $e$ の倍元です。よって $e$ が生成するイデアルは $g$ が生成するイデアル $C$ と一致します。 $c \in C$ を $c = ae$ と書くと $ce = ae^2 = ae = c$ なので、$e$ は $C$ の乗法の単位元です。冪等生成元 $e'$ がもう 1 つあれば、同じ計算で $e'$ も $C$ の単位元なので、$e = ee' = e'$ です。 ## 4. 零点による記述と BCH 限界 ### 4.1. 定義集合 以後この節では $\gcd(n, q) = 1$ とします。$m$ を $q^m \equiv 1 \pmod n$ となる最小の正の整数（$n$ を法とする $q$ の位数）とすると、$n$ は $q^m - 1$ を割り切ります。$\mathbb{F}_{q^m}^{\times}$ は位数 $q^m - 1$ の巡回群なので（）、位数がちょうど $n$ の元 $\alpha$（**1 の原始 $n$ 乗根**）があります。$x^n - 1$ の根は $1, \alpha, \ldots, \alpha^{n-1}$ の $n$ 個で、$\mathbb{F}_{q^m}$ で $x^n - 1 = \prod_{i=0}^{n-1}(x - \alpha^i)$ です（）。$\alpha$ を 1 つ固定します。 生成多項式 $g$ の巡回符号 $C$ に対し、$T = \{\, i \in \mathbb{Z}/n\mathbb{Z} : g(\alpha^i) = 0 \,\}$ を $C$ の（$\alpha$ に関する）**定義集合**、$\alpha^i$（$i \in T$）を $C$ の**零点**という。 $g$ は $x^n - 1$ の約数なので $g = \prod_{i \in T}(x - \alpha^i)$ で、$|T| = \deg g$ です。$g$ の係数は $\mathbb{F}_q$ に属するので、$g(\alpha^i) = 0$ なら $g(\alpha^{iq}) = g(\alpha^i)^q = 0$ です。つまり $T$ は $q$ 倍で閉じていて、$n$ を法とする **$q$-円分剰余類** $\{ i, iq, iq^2, \ldots \}$ の合併です。逆に、円分剰余類の合併 $T$ に対して $\prod_{i \in T}(x - \alpha^i)$ は $\mathbb{F}_q$ 係数です。各円分剰余類に対応する積が $\alpha^i$ の $\mathbb{F}_q$ 上の最小多項式だからです（）。こうして $$ \text{巡回符号} \;\longleftrightarrow\; x^n - 1 \text{ のモニックな約数} \;\longleftrightarrow\; q\text{-円分剰余類の合併 } T \subseteq \mathbb{Z}/n\mathbb{Z} $$ という 3 つの見方がそろいます。
α⁰α¹α²α³ α⁴α⁵α⁶
$C$ を定義集合 $T$ の巡回符号とする。次数 $n$ 未満の $c(x) \in \mathbb{F}_q[x]$ について $$ c \in C \iff c(\alpha^i) = 0 \quad (\text{すべての } i \in T) $$ が成り立つ。また $\dim C = n - |T|$ である。 $c \in C$ なら $c = ag$ で（）、$c(\alpha^i) = a(\alpha^i)g(\alpha^i) = 0$（$i \in T$）です。逆に、$c(\alpha^i) = 0$ がすべての $i \in T$ で成り立つとします。$\mathbb{F}_q[x]$ の中で $c = sg + r$、$\deg r < \deg g$（または $r = 0$）と割ると（ の 1）、$r(\alpha^i) = c(\alpha^i) - s(\alpha^i)g(\alpha^i) = 0$ が $|T| = \deg g$ 個の相異なる点 $\alpha^i$ で成り立ちます。$r$ の次数は $\deg g$ 未満なので、 の 3 を体 $\mathbb{F}_{q^m}$ の上で使って $r = 0$ です。よって $c = sg \in C$ です。次元は の 2 と $|T| = \deg g$ から出ます。 この命題は、$\mathbb{F}_{q^m}$ に成分をもつ行列 $H = (\alpha^{ij})_{i \in T,\ 0 \le j \le n-1}$ について $C = \{ c \in \mathbb{F}_q^n : Hc^{\mathsf{T}} = 0 \}$ であることを述べています。$H$ は拡大体の上の「検査行列」です。 定義集合 $T$ の巡回符号 $C$ の双対符号 $C^{\perp}$ の定義集合は $\{\, -i \bmod n : i \notin T \,\}$ である。 検査多項式 $h = (x^n - 1)/g$ の根は $\alpha^i$（$i \notin T$）です。$C^{\perp}$ の生成多項式は $h^{*}/h(0)$ で（）、$\beta \ne 0$ に対し $h^{*}(\beta) = \beta^{k}h(1/\beta)$ なので、$h^{*}$ の根は $h$ の根の逆元 $\alpha^{-i}$（$i \notin T$）です。 ### 4.2. BCH 限界 $\gcd(n, q) = 1$、$\alpha$ を 1 の原始 $n$ 乗根、$2 \le \delta \le n$ とする。巡回符号 $C \subseteq \mathbb{F}_q^n$ の定義集合が、ある整数 $b$ について連続する $\delta - 1$ 個の指数 $b, b+1, \ldots, b+\delta-2$（$n$ を法として）を含むならば、$C$ の $0$ でない符号語の重みは $\delta$ 以上である。すなわち $d(C) \ge \delta$。 重みが $\delta - 1$ 以下の $0$ でない符号語 $c$ があると仮定します。$\delta - 1 \le n - 1$ なので、$c$ の台（$c_j \ne 0$ となる $j$ の集合）を含む $\delta - 1$ 元集合 $J = \{ j_1, \ldots, j_{\delta-1} \} \subseteq \{0, \ldots, n-1\}$ が取れます。 により $c(\alpha^{b+i}) = 0$（$0 \le i \le \delta - 2$）なので $$ \sum_{l=1}^{\delta-1} c_{j_l}\,\alpha^{(b+i)j_l} = 0 \qquad (0 \le i \le \delta-2) $$ です。$x_l = \alpha^{j_l}$ とおくと、これは $\delta - 1$ 次正方行列 $M = (x_l^{\,b}\, x_l^{\,i})_{i, l}$ と列ベクトル $(c_{j_1}, \ldots, c_{j_{\delta-1}})^{\mathsf{T}}$ の積が $0$ であることを述べています。$M$ は Vandermonde 行列 $V(x_1, \ldots, x_{\delta-1})$ の第 $l$ 列を $x_l^{\,b}$ 倍したものなので $$ \det M = \prod_{l=1}^{\delta-1} x_l^{\,b} \cdot \prod_{1 \le l < l' \le \delta-1}(x_{l'} - x_l) $$ です（、 の 2）。$\alpha$ の位数は $n$ で $j_l$ は $0$ 以上 $n$ 未満の相異なる整数なので、$x_l = \alpha^{j_l}$ は相異なり、$0$ でもありません。よって $\det M \ne 0$ で、$M\boldsymbol{v} = 0$ の解は $\boldsymbol{v} = 0$ だけです（）。すると $c_{j_l} = 0$ がすべての $l$ で成り立ち、$c = 0$ となって矛盾します。 証明が使ったのは「連続する $\delta - 1$ 個の零点」だけです。そこで、これだけを要求して最大の符号を取ります。 $\gcd(n, q) = 1$、$\alpha$ を 1 の原始 $n$ 乗根、$2 \le \delta \le n$、$b$ を整数とする。$\alpha^{b}, \alpha^{b+1}, \ldots, \alpha^{b+\delta-2}$ の $\mathbb{F}_q$ 上の最小多項式の最小公倍数を生成多項式とする巡回符号を、**設計距離** $\delta$ の **BCH 符号**という。$b = 1$ のとき**狭義**、$n = q^m - 1$ のとき**原始**という。 言い換えると、BCH 符号は、$b, \ldots, b+\delta-2$ を含む最小の「円分剰余類の合併」を定義集合とする巡回符号です。 により最小距離は $\delta$ 以上です。 長さ $n$、設計距離 $\delta$ の BCH 符号の次元 $k$ は、$m$ を $n$ を法とする $q$ の位数として $$ k \ge n - m(\delta - 1) $$ を満たす。$q = 2$、$b = 1$、$\delta = 2t + 1$ のときは $k \ge n - mt$ である。 $i$ の $q$-円分剰余類は $\{ i q^j \bmod n : j \ge 0 \}$ です。$q^m \equiv 1 \pmod n$ なので $j$ は $0 \le j \le m-1$ だけ考えればよく、各剰余類の元は $m$ 個以下です。定義集合 $T$ は $b, \ldots, b+\delta-2$ の剰余類の合併なので $|T| \le m(\delta - 1)$ で、$k = n - |T|$（）から第 1 の不等式が出ます。 $q = 2$、$b = 1$、$\delta = 2t+1$ のとき、指数 $1, 2, \ldots, 2t$ のうち偶数 $2i$ は $i$ と同じ $2$-円分剰余類に属します。よって $T$ は奇数 $1, 3, \ldots, 2t-1$ の剰余類 $t$ 個の合併で、$|T| \le mt$ です。 $n = 15$、$q = 2$、$m = 4$ です。$\mathbb{F}_{16} = \mathbb{F}_2[x]/(x^4 + x + 1)$ とし、$\alpha$ を $x$ の類とします（$\alpha^4 = \alpha + 1$。$\alpha$ の位数は $15$）。$15$ を法とする $2$-円分剰余類と最小多項式は | 剰余類 | 最小多項式 | |---|---| | $\{0\}$ | $x + 1$ | | $\{1, 2, 4, 8\}$ | $m_1 = x^4 + x + 1$ | | $\{3, 6, 12, 9\}$ | $m_3 = x^4 + x^3 + x^2 + x + 1$ | | $\{5, 10\}$ | $m_5 = x^2 + x + 1$ | | $\{7, 14, 13, 11\}$ | $m_7 = x^4 + x^3 + 1$ | です。狭義の BCH 符号は次のとおりです。 | 設計距離 | 定義集合 | 生成多項式 | パラメータ | |---|---|---|---| | $\delta = 3$ | $\{1,2,4,8\}$ | $m_1$ | $[15, 11, 3]$ | | $\delta = 5$ | $\{1,2,3,4,6,8,9,12\}$ | $m_1 m_3 = x^8+x^7+x^6+x^4+1$ | $[15, 7, 5]$ | | $\delta = 7$ | 上に $\{5, 10\}$ を足す | $m_1 m_3 m_5 = x^{10}+x^8+x^5+x^4+x^2+x+1$ | $[15, 5, 7]$ | 最小距離が設計距離に等しいことは、生成多項式そのものが重み $3$、$5$、$7$ の符号語であることから分かります（$\delta = 3$ では $m_1$ の項が 3 個）。次元は の下界 $15 - 4t$（$t = 1, 2$）と一致し、$t = 3$ では剰余類 $\{5, 10\}$ が小さいぶん下界 $3$ より大きい $5$ になります。 $r \ge 2$、$n = (q^r - 1)/(q - 1)$ とし、$\gcd(r, q - 1) = 1$ とする。$\beta$ を $\mathbb{F}_{q^r}^{\times}$ の生成元、$\alpha = \beta^{q-1}$ とすると、$\alpha$ は 1 の原始 $n$ 乗根で、$\alpha$ の $\mathbb{F}_q$ 上の最小多項式を生成多項式とする長さ $n$ の巡回符号は、$[n, n - r, 3]_q$ Hamming 符号である。 $\beta$ の位数は $q^r - 1 = n(q-1)$ なので $\alpha$ の位数は $n$ です。$n = 1 + q + \cdots + q^{r-1} \equiv 1 \pmod q$ なので $\gcd(n, q) = 1$ です。 $\alpha$ の最小多項式 $g$ の根は $\alpha, \alpha^q, \alpha^{q^2}, \ldots$ で（）、 と $c(\alpha^{q^j}) = c(\alpha)^{q^j}$ から、符号は $C = \{ c \in \mathbb{F}_q^n : c(\alpha) = 0 \}$ です。$\mathbb{F}_{q^r}$ の $\mathbb{F}_q$ 上の基底を 1 つ取り、$\alpha^j$ の座標ベクトルを $\boldsymbol{h}_j \in \mathbb{F}_q^r$ とすると、$c(\alpha) = \sum_j c_j \alpha^j = 0$ は $\sum_j c_j \boldsymbol{h}_j = 0$ と同値です。つまり $H = (\boldsymbol{h}_0\ \cdots\ \boldsymbol{h}_{n-1})$ が $C$ の検査条件を与える $r \times n$ 行列です。 $H$ のどの 2 列も一次独立であることを示します。$0 \le i < j \le n-1$ で $\boldsymbol{h}_i$ と $\boldsymbol{h}_j$ が一次従属なら、$\alpha^j = \lambda\alpha^i$ となる $\lambda \in \mathbb{F}_q^{\times}$ があり、$\alpha^{j-i} = \lambda$ です。$\lambda^{q-1} = 1$ なので $\alpha^{(j-i)(q-1)} = 1$、つまり $n$ が $(j-i)(q-1)$ を割り切ります。ところが $n = \sum_{l=0}^{r-1} q^l \equiv r \pmod{q-1}$ なので $\gcd(n, q-1) = \gcd(r, q-1) = 1$ で、$n$ は $j - i$ を割り切ります。これは $0 < j - i < n$ に反します。 $\mathbb{F}_q^r$ の 1 次元部分空間は $(q^r - 1)/(q-1) = n$ 個です。$H$ の $n$ 本の列は $0$ でなく、どの 2 本も比例しないので、各 1 次元部分空間からちょうど 1 本ずつ代表元を取ったものになっています。これは Hamming 符号の検査行列の定義そのもので、$H$ の階数は $r$、$C$ は $[n, n-r, 3]_q$ 符号です（）。 $q = 2$ のときは条件 $\gcd(r, 1) = 1$ がいつも成り立つので、二元 Hamming 符号はすべて巡回符号（原始元の最小多項式が生成する、設計距離 $3$ の原始 BCH 符号）です。 の $g = x^3+x+1$ は $r = 3$ の場合です。 真の最小距離が設計距離より大きいことがあります。長さ $23$ の二元巡回符号で定義集合が $\{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\}$ のもの（二元 Golay 符号）は、連続する零点が $1, 2, 3, 4$ なので BCH 限界は $5$ ですが、真の最小距離は $7$ です。これは [第 5 章](/mathematics/finite-fields-coding/weight-enumerators-golay) で証明します。また、BCH 限界は原始 $n$ 乗根 $\alpha$ の選び方に依存します。$\alpha$ を $\alpha^s$（$\gcd(s, n) = 1$）に取り替えると定義集合が $s^{-1}T$ に変わり、連続する零点の個数が増えることがあります。 ## 5. Reed–Solomon 符号 ### 5.1. 評価による定義と MDS 性 $1 \le k \le n \le q$ とし、$a_1, \ldots, a_n$ を $\mathbb{F}_q$ の相異なる元、$v_1, \ldots, v_n$ を $\mathbb{F}_q$ の $0$ でない元とする。 $$ \mathrm{GRS}_k(a, v) = \bigl\{\, (v_1 f(a_1), \ldots, v_n f(a_n)) : f \in \mathbb{F}_q[x],\ \deg f < k \,\bigr\} $$ を**一般化 Reed–Solomon 符号**という。$v_1 = \cdots = v_n = 1$ のとき $\mathrm{RS}_k(a)$ と書き、**Reed–Solomon 符号**という（零多項式の次数は $k$ 未満とみなす）。 $\mathrm{GRS}_k(a, v)$ は $[n, k, n-k+1]_q$ 符号である。 評価写像 $\mathrm{ev} : f \mapsto (v_i f(a_i))_i$ は、次数 $k$ 未満の多項式のなす $k$ 次元空間から $\mathbb{F}_q^n$ への線形写像で、像が符号です。$f \ne 0$、$\deg f < k$ とすると、$f$ の根は $k - 1$ 個以下なので（ の 3）、$f(a_i) = 0$ となる $i$ は $k - 1$ 個以下で、$v_i \ne 0$ から $\operatorname{wt}(\mathrm{ev}(f)) \ge n - (k-1) = n - k + 1 \ge 1$ です。とくに $\mathrm{ev}$ は単射で、符号の次元は $k$、最小重みは $n - k + 1$ 以上です。Singleton 限界 $d \le n - k + 1$（）と合わせて $d = n - k + 1$ です。 証明は 2 行ですが、これで「どんな $n \le q$ と $k$ に対しても Singleton 限界を達成する符号がある」ことが分かりました。代償は、符号長がアルファベットの大きさ $q$ 以下に限られることです。 ### 5.2. 巡回符号としての Reed–Solomon 符号 $n$ が $q - 1$ の約数のとき、位数 $n$ の元 $\alpha \in \mathbb{F}_q$ があり、評価点を $a_j = \alpha^{j}$（$0 \le j \le n - 1$、座標は $0$ から数える）と取れます。このとき評価写像は有限体の上の離散 Fourier 変換です。次の補題のねらいは、多項式 $f$ を $n$ 個の点で評価して並べた語 $c$ を、さらに $\alpha^i$ で評価すると、$f$ の係数が 1 つだけ取り出される（定数倍を除く）ことを示すことです。これにより、評価で作った符号が連続する零点をもつことが次の定理で分かります。 $n$ を $q - 1$ の約数、$\alpha \in \mathbb{F}_q$ を位数 $n$ の元とする。 1. 整数 $s$ について、$\sum_{j=0}^{n-1}\alpha^{js}$ は $n \mid s$ のとき $n \cdot 1$、そうでないとき $0$ である。$n \cdot 1$ は $\mathbb{F}_q$ で $0$ でない。 2. $f = \sum_{l=0}^{n-1} f_l x^l \in \mathbb{F}_q[x]$ に対し $c_j = f(\alpha^j)$、$c(x) = \sum_{j=0}^{n-1}c_j x^j$ とおくと、すべての整数 $i$ について $c(\alpha^{i}) = n\, f_{l}$（$l$ は $0 \le l \le n-1$、$l \equiv -i \pmod n$ で定まる添字）である。 (1) $n \mid s$ なら各項が $1$ で和は $n \cdot 1$ です。$n \nmid s$ なら $\alpha^s \ne 1$ で、等比数列の和の式 $(\alpha^s - 1)\sum_{j=0}^{n-1}\alpha^{js} = \alpha^{sn} - 1 = 0$ と $\mathbb{F}_q$ が整域であることから和は $0$ です。$n$ は $q - 1$ の約数なので標数 $p$ で割り切れず、$n \cdot 1 \ne 0$ です。 (2) $c(\alpha^i) = \sum_{j} c_j \alpha^{ij} = \sum_{j}\sum_{l'} f_{l'}\alpha^{jl'}\alpha^{ij} = \sum_{l'} f_{l'}\sum_{j=0}^{n-1}\alpha^{j(l'+i)}$ です。(1) により内側の和は $n \mid l' + i$ のとき $n$、そうでないとき $0$ で、$0 \le l' \le n-1$ の範囲で $l' \equiv -i$ となる $l'$ はちょうど 1 つです。 $n$ を $q - 1$ の約数、$\alpha \in \mathbb{F}_q$ を位数 $n$ の元、$1 \le k \le n - 1$ とする。評価点を $a_j = \alpha^j$（$0 \le j \le n-1$）とした $\mathrm{RS}_k(a)$ は、生成多項式 $$ g(x) = (x - \alpha)(x - \alpha^2)\cdots(x - \alpha^{n-k}) $$ の巡回符号、すなわち $\mathbb{F}_q$ 上の長さ $n$、設計距離 $n - k + 1$ の狭義 BCH 符号と一致する。 $c \in \mathrm{RS}_k(a)$ を $c_j = f(\alpha^j)$、$f = \sum_{l=0}^{k-1}f_l x^l$ と書きます。 の 2 を $f_k = \cdots = f_{n-1} = 0$ として使うと、$1 \le i \le n - k$ に対し $l = n - i$ は $k \le l \le n-1$ の範囲にあるので $c(\alpha^i) = n f_{n-i} = 0$ です。よって $c$ は定義集合 $T = \{1, 2, \ldots, n-k\}$ の巡回符号 $C$ に属します（。$q \equiv 1 \pmod n$ なので $q$-円分剰余類はすべて 1 点で、$T$ は剰余類の合併です）。$\dim C = n - |T| = k = \dim \mathrm{RS}_k(a)$（）なので両者は一致します。$\alpha^i$ の $\mathbb{F}_q$ 上の最小多項式は $x - \alpha^i$ なので、$C$ は の意味で $b = 1$、$\delta = n - k + 1$ の BCH 符号です。 BCH 限界（）はこの符号に $d \ge n - k + 1$ を与え、 の評価と一致します。Reed–Solomon 符号では、BCH 限界と Singleton 限界が両側から最小距離を挟んで等号になっています。 ### 5.3. MDS 符号の特徴づけ 第 3 章で、Singleton 限界 $d \le n - k + 1$ の等号を達成する符号を MDS 符号と呼びました。 $1 \le k \le n - 1$ とし、$C$ を $[n, k]_q$ 符号、$G$ を生成行列、$H$ を検査行列とする。次は同値である。 1. $C$ は MDS 符号である（$d(C) = n - k + 1$）。 2. $H$ のどの $n - k$ 本の列も一次独立である。 3. $G$ のどの $k$ 本の列も一次独立である。 4. $C^{\perp}$ は MDS 符号である（$d(C^{\perp}) = k + 1$）。 (1) $\Leftrightarrow$ (2): $d(C)$ は、$H$ の列のうち一次従属なものの最小の本数です（）。よって (2) は $d(C) \ge n - k + 1$ と同値で、Singleton 限界（）により $d(C) = n - k + 1$ と同値です。 (1) $\Leftrightarrow$ (3): $k$ 個の座標の集合 $J$ に対し、$G$ の $J$ の列を並べた $k$ 次正方行列を $G_J$ とします。$G_J$ の列が一次従属であることは $\det G_J = 0$、すなわち $\det G_J^{\mathsf{T}} = 0$ と同値で（、）、これは $uG_J = 0$ となる $0$ でない行ベクトル $u \in \mathbb{F}_q^k$ があることと同値です。$G$ の行は一次独立なので $u \ne 0$ なら符号語 $uG$ は $0$ でなく、$uG_J = 0$ は「$uG$ が $J$ の座標で $0$」、つまり $\operatorname{wt}(uG) \le n - k$ を意味します。逆に重みが $n - k$ 以下の $0$ でない符号語 $uG$ は、ある $k$ 個の座標で $0$ です。よって「一次従属な $k$ 列がある」ことと $d(C) \le n - k$ は同値で、(3) は $d(C) \ge n - k + 1$ と同値です。 (3) $\Leftrightarrow$ (4): $(C^{\perp})^{\perp} = C$ なので（）、$G$ は $[n, n-k]_q$ 符号 $C^{\perp}$ の検査行列です。(1) $\Leftrightarrow$ (2) を $C^{\perp}$ に使うと、$C^{\perp}$ が MDS であることは「$G$ のどの $n - (n-k) = k$ 本の列も一次独立」と同値です。 条件 3 は、「符号語のどの $k$ 個の座標からでも情報が復元できる」ことを意味します。分散ストレージで Reed–Solomon 符号を使うのは、$n$ 台のうちどの $k$ 台が生き残ってもデータが読めるからです。 $\mathbb{F}_8 = \mathbb{F}_2[x]/(x^3 + x + 1)$、$\alpha$ を $x$ の類とします。$\alpha^3 = \alpha + 1$、$\alpha^4 = \alpha^2 + \alpha$、$\alpha^5 = \alpha^2 + \alpha + 1$、$\alpha^6 = \alpha^2 + 1$、$\alpha^7 = 1$ です。$n = 7$、$k = 3$、評価点 $a_j = \alpha^j$ とします。 情報 $(1, \alpha, \alpha^3)$ を $f(x) = 1 + \alpha x + \alpha^3x^2$ とすると、たとえば $f(1) = 1 + \alpha + \alpha^3 = 0$、$f(\alpha) = 1 + \alpha^2 + \alpha^5 = \alpha$ で、同様に計算して $$ c = (f(\alpha^0), \ldots, f(\alpha^6)) = (0,\ \alpha,\ \alpha^3,\ \alpha^3,\ 0,\ 1,\ \alpha) $$ です。重みは $5 = n - k + 1$ で、最小重みの符号語です（$f$ が評価点の中に $k - 1 = 2$ 個の根 $1, \alpha^4$ をもつ場合）。 のとおり、$c(x) = \alpha x + \alpha^3x^2 + \alpha^3x^3 + x^5 + \alpha x^6$ は $\alpha, \alpha^2, \alpha^3, \alpha^4$ を根にもち、生成多項式 $$ g(x) = (x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4) = x^4 + \alpha^3x^3 + x^2 + \alpha x + \alpha^3 $$ の倍数です。たとえば $c(\alpha) = \alpha^2 + \alpha^5 + \alpha^6 + \alpha^5 + \alpha^7 = \alpha^2 + \alpha^6 + 1 = 0$ です。 ## 6. 復号 ### 6.1. Berlekamp–Welch の方法 最小距離 $d = n - k + 1$ の符号は $\lfloor (d-1)/2 \rfloor = \lfloor (n-k)/2 \rfloor$ 個までの誤りを訂正できます（第 3 章）。しかし、最も近い符号語を総当たりで探すのでは実用になりません。Reed–Solomon 符号では、これが連立一次方程式 1 つに帰着します。 $C = \mathrm{RS}_k(a)$、$t = \lfloor (n-k)/2 \rfloor$ とする。$f \in \mathbb{F}_q[x]$、$\deg f < k$ に対する符号語 $c = (f(a_i))_i$ と、$\operatorname{wt}(e) \le t$ を満たす $e \in \mathbb{F}_q^n$ について、$y = c + e$ とおく。未知の多項式 $$ E(x) = \sum_{j=0}^{t} E_j x^j, \qquad Q(x) = \sum_{j=0}^{k+t-1} Q_j x^j $$ の係数 $(E_0, \ldots, E_t, Q_0, \ldots, Q_{k+t-1})$ についての斉次連立一次方程式 $$ Q(a_i) = y_i\, E(a_i) \qquad (1 \le i \le n) $$ を考える。 1. この方程式は $0$ でない解をもつ。 2. $0$ でない解 $(E, Q)$ はどれも $E \ne 0$ で、$E$ は $Q$ を割り切り、$Q/E = f$ である。 (1) $E_0(x) = \prod_{i :\, e_i \ne 0}(x - a_i)$、$Q_0 = fE_0$ とおきます。$\deg E_0 = \operatorname{wt}(e) \le t$、$\deg Q_0 \le k - 1 + t$ です。$e_i = 0$ の $i$ では $y_i = f(a_i)$ なので $Q_0(a_i) = f(a_i)E_0(a_i) = y_iE_0(a_i)$ です。$e_i \ne 0$ の $i$ では $E_0(a_i) = 0$ なので両辺とも $0$ です。$E_0$ はモニックで $0$ でないので、$(E_0, Q_0)$ は $0$ でない解です。 (2) $(E, Q)$ を $0$ でない解とし、$P = Q - fE$ とおきます。$\deg P \le k + t - 1$ です。$e_i = 0$ となる $i$ では $y_i = f(a_i)$ なので $P(a_i) = Q(a_i) - y_iE(a_i) = 0$ です。そのような $i$ は $n - t$ 個以上あり、$2t \le n - k$ から $n - t \ge k + t > \deg P$ です。次数が $k + t - 1$ 以下の多項式が $k + t$ 個以上の相異なる点で $0$ になるので、$P = 0$（ の 3）、すなわち $Q = fE$ です。$E = 0$ なら $Q = 0$ となり、解が $0$ でないことに反します。よって $E \ne 0$ で、$Q/E = f$ です。 未知数は $(t + 1) + (k + t) = k + 2t + 1$ 個、方程式は $n$ 本です。掃き出し法で $0$ でない解を 1 つ求め、多項式の割り算を 1 回すれば $f$ が得られます。計算量は $n$ の 3 乗の程度です。$E_0$ は誤りの位置 $a_i$ を根にもつ多項式（誤り位置多項式）ですが、アルゴリズムは誤りの位置をあらかじめ知らなくても動きます。一般化 Reed–Solomon 符号では、受信語の各座標を $v_i$ で割ってから同じ手順を使います。 の符号語 $c = (0, \alpha, \alpha^3, \alpha^3, 0, 1, \alpha)$ を送り、座標 1 に $\alpha^2$、座標 5 に $1$ の誤りが加わって $$ y = (0,\ \alpha^4,\ \alpha^3,\ \alpha^3,\ 0,\ 0,\ \alpha) $$ を受け取ったとします（$\alpha + \alpha^2 = \alpha^4$、$1 + 1 = 0$）。$t = 2$ なので、$E = E_0 + E_1x + E_2x^2$、$Q = Q_0 + \cdots + Q_4x^4$ の 8 個の係数についての 7 本の方程式 $Q(\alpha^j) = y_jE(\alpha^j)$（$0 \le j \le 6$）を解きます。係数行列の階数は $7$ で、解は定数倍を除いてただ 1 つ、 $$ E(x) = x^2 + \alpha^6x + \alpha^6, \qquad Q(x) = \alpha^3x^4 + \alpha^4x^3 + \alpha^2x^2 + \alpha^2x + \alpha^6 $$ です。たとえば $j = 0$ では $Q(1) = \alpha^3 + \alpha^4 + \alpha^2 + \alpha^2 + \alpha^6 = 0 = y_0E(1)$ です。$E(x) = (x - \alpha)(x - \alpha^5)$ と分解し（$\alpha + \alpha^5 = \alpha^6$、$\alpha\cdot\alpha^5 = \alpha^6$）、誤りの位置が $a_1 = \alpha$ と $a_5 = \alpha^5$ であることを示しています。割り算をすると $$ Q(x) = (x^2 + \alpha^6x + \alpha^6)(\alpha^3x^2 + \alpha x + 1) $$ で、$f = 1 + \alpha x + \alpha^3x^2$ が復元されます。 ### 6.2. シンドロームと鍵方程式 Berlekamp–Welch の方法は受信語 $y$ の $n$ 個の成分をそのまま使います。BCH 符号では、まず $y$ を $2t$ 個のシンドロームに縮めてから、より小さい問題を解く方法が使われます。 以下の見通しを先に述べます。受信語から計算できる $2t$ 個の値（シンドローム）を 1 つの多項式 $S(x)$ にまとめます。一方、誤りがどこにあるかを根で表した多項式 $\sigma(x)$ と、誤りの大きさを拾う多項式 $\omega(x)$ を定義します。この 3 つが鍵方程式でつながるので、$S$ から $\sigma$ と $\omega$ を求めれば誤りの位置と値が分かります。 この小節と次の小節の設定を固定します。$\gcd(n, q) = 1$、$\alpha \in \mathbb{F}_{q^m}$ を 1 の原始 $n$ 乗根、$t \ge 1$、$2t + 1 \le n$ とし、$C \subseteq \mathbb{F}_q^n$ を、$\alpha, \alpha^2, \ldots, \alpha^{2t}$ を零点にもつ巡回符号とします（設計距離 $2t+1$ の狭義 BCH 符号や、 の Reed–Solomon 符号で $n - k = 2t$ のもの）。 により $d(C) \ge 2t + 1$ です。 $c \in C$、$e \in \mathbb{F}_q^n$、$y = c + e$ とし、$I = \{ i : e_i \ne 0 \}$、$w = |I|$ とする。 - **シンドローム**: $S_j = y(\alpha^j)$（$1 \le j \le 2t$）。**シンドローム多項式**: $S(x) = \sum_{j=1}^{2t} S_j x^{j-1}$。 - **誤り位置**: $X_i = \alpha^{i}$（$i \in I$）。**誤り位置多項式**: $\sigma(x) = \prod_{i \in I}(1 - X_i x)$。 - **誤り評価多項式**: $\omega(x) = \sum_{i \in I} e_i X_i \prod_{l \in I,\ l \ne i}(1 - X_l x)$。 $c(\alpha^j) = 0$（$1 \le j \le 2t$、）なので、$S_j = e(\alpha^j) = \sum_{i \in I} e_i X_i^{\,j}$ です。シンドロームは受信語から計算でき、しかも誤り $e$ だけで決まります。$\sigma$ の根は $X_i^{-1}$ で、$\sigma$ が分かれば誤りの位置が分かります。 の記号で、 $$ \sigma(x)\,S(x) \equiv \omega(x) \pmod{x^{2t}} $$ が $\mathbb{F}_{q^m}[x]$ で成り立つ。また $\sigma(0) = 1$、$\deg \sigma = w$、$\omega = 0$ または $\deg \omega \le w - 1$ で、$w \ge 1$ のとき $\sigma$ と $\omega$ は定数でない共通因子をもたず、$\omega \ne 0$ である。 $S_j = \sum_{i \in I}e_iX_i^{\,j}$ を代入し、有限等比数列の和 $(1 - X_ix)\sum_{j=0}^{2t-1}(X_ix)^j = 1 - (X_ix)^{2t}$ を使います。 $$ \begin{aligned} \sigma(x)S(x) &= \sum_{i \in I} e_iX_i\,\sigma(x)\sum_{j=0}^{2t-1}(X_ix)^{j} = \sum_{i \in I} e_iX_i \prod_{l \ne i}(1 - X_lx)\cdot\bigl(1 - (X_ix)^{2t}\bigr) \\ &= \omega(x) - x^{2t}\sum_{i \in I} e_iX_i^{\,2t+1}\prod_{l \ne i}(1 - X_lx). \end{aligned} $$ 右辺の第 2 項は $x^{2t}$ の倍数なので、合同式が成り立ちます。$\sigma(0) = 1$ と次数の主張は定義から直ちに読み取れます（$X_i \ne 0$ なので $\sigma$ の最高次の係数 $\prod(-X_i)$ は $0$ でない）。 $w \ge 1$ とします。$\sigma$ は $\mathbb{F}_{q^m}$ で 1 次式の積に分解し、根は $X_i^{-1}$（$i \in I$）です。$\omega$ に代入すると、$l = i$ 以外の項は因子 $1 - X_iX_i^{-1} = 0$ を含むので $$ \omega(X_i^{-1}) = e_iX_i\prod_{l \ne i}(1 - X_lX_i^{-1}) $$ で、$e_i \ne 0$、$X_i \ne 0$、$X_l \ne X_i$（$l \ne i$。$\alpha$ の位数が $n$ だから）により $0$ でありません。よって $\omega \ne 0$ で、$\sigma$ の既約因子 $1 - X_ix$ はどれも $\omega$ を割り切りません（ の 2）。 ### 6.3. 互除法で鍵方程式を解く 鍵方程式は、$S$ が与えられたとき、次数の小さい $\sigma$ と $\omega$ を求める問題です。これは $x^{2t}$ と $S(x)$ に拡張 Euclid の互除法を使うと解けます。整数の互除法（）と同じ手順を、多項式について、あとで使う不変量とともに述べ直します。続く定理の証明の方針は次のとおりです。互除法の途中で余り $r_i$ の次数が初めて $t$ 未満になったところで止めると、$u_i$ と $r_i$ が、鍵方程式の解 $\sigma$ と $\omega$ の同じ定数倍になる、というものです。次数の評価を重ねて示します。 $K$ を体、$a, b \in K[x]$、$b \ne 0$、$\deg a > \deg b$ とする。$r_0 = a$、$r_1 = b$、$s_0 = 1$、$s_1 = 0$、$u_0 = 0$、$u_1 = 1$ とおき、$r_i \ne 0$ である限り、$r_{i-1}$ を $r_i$ で割った商を $q_i$ として $$ r_{i+1} = r_{i-1} - q_ir_i, \qquad s_{i+1} = s_{i-1} - q_is_i, \qquad u_{i+1} = u_{i-1} - q_iu_i $$ と定める。このとき、ある $N \ge 1$ で $r_{N+1} = 0$ となって手順は止まり、次が成り立つ。 1. $\deg r_0 > \deg r_1 > \cdots > \deg r_N$。 2. $s_ia + u_ib = r_i$（$0 \le i \le N+1$）。 3. $s_iu_{i+1} - s_{i+1}u_i = (-1)^i$（$0 \le i \le N$）。とくに $s_i$ と $u_i$ は定数でない共通因子をもたない。 4. $\deg u_i = \deg a - \deg r_{i-1}$（$1 \le i \le N+1$）。 (1) 割り算の余りなので $r_{i+1} = 0$ または $\deg r_{i+1} < \deg r_i$ です（ の 1）。次数は非負整数で真に減り続けるので、有限回で余りが $0$ になります。 (2) $i = 0, 1$ では定義から成り立ちます。$i-1$ と $i$ で成り立てば、$s_{i+1}a + u_{i+1}b = (s_{i-1}a + u_{i-1}b) - q_i(s_ia + u_ib) = r_{i-1} - q_ir_i = r_{i+1}$ です。 (3) $i = 0$ では $1\cdot 1 - 0 \cdot 0 = 1$ です。$i$ で成り立てば $$ s_{i+1}u_{i+2} - s_{i+2}u_{i+1} = s_{i+1}(u_i - q_{i+1}u_{i+1}) - (s_i - q_{i+1}s_{i+1})u_{i+1} = -(s_iu_{i+1} - s_{i+1}u_i) = (-1)^{i+1} $$ です。$s_i$ と $u_i$ の共通因子は左辺を割り切るので、定数です。 (4) $i = 1$ では $\deg u_1 = 0 = \deg a - \deg r_0$ です。$i \ge 1$ として、$i$ 以下で成り立つとします。$\deg q_i = \deg r_{i-1} - \deg r_i \ge 1$ なので $$ \deg(q_iu_i) = (\deg r_{i-1} - \deg r_i) + (\deg a - \deg r_{i-1}) = \deg a - \deg r_i $$ です。一方 $u_{i-1}$ は、$i = 1$ なら $0$、$i \ge 2$ なら次数 $\deg a - \deg r_{i-2}$ で、これは $\deg a - \deg r_i$ より小さい。よって $u_{i+1} = u_{i-1} - q_iu_i$ の次数は $\deg a - \deg r_i$ です。 6.2 節の設定で、$1 \le w = \operatorname{wt}(e) \le t$ とする。このとき $S(x) \ne 0$ である。 の手順を $K = \mathbb{F}_{q^m}$、$a = x^{2t}$、$b = S(x)$ に対して行い、$\deg r_i < t$（または $r_i = 0$）となる最小の添字 $i$ を取る。すると $u_i(0) \ne 0$ で、 $$ \sigma(x) = \frac{u_i(x)}{u_i(0)}, \qquad \omega(x) = \frac{r_i(x)}{u_i(0)} $$ が成り立つ。 により $\omega \ne 0$ で $\sigma S \equiv \omega \pmod{x^{2t}}$ なので、$S \ne 0$ です。$\deg S \le 2t - 1 < \deg a$ なので補題の仮定が満たされます。$\deg r_0 = 2t \ge t$ で、最後は $r_{N+1} = 0$ なので、条件を満たす最小の $i$ は $1 \le i \le N + 1$ の範囲にあり、$\deg r_{i-1} \ge t$ です。補題の 4 から $$ \deg u_i = 2t - \deg r_{i-1} \le t $$ で、とくに $u_i \ne 0$ です。補題の 2 から $u_iS \equiv r_i \pmod{x^{2t}}$ です。 **$\sigma r_i = \omega u_i$ であること。** 2 つの合同式から $\sigma r_i \equiv \sigma u_iS \equiv \omega u_i \pmod{x^{2t}}$ です。$\deg\sigma = w \le t$ と $\deg r_i < t$ から $\deg(\sigma r_i) < 2t$、$\deg\omega \le w - 1 < t$ と $\deg u_i \le t$ から $\deg(\omega u_i) < 2t$ です。差 $\sigma r_i - \omega u_i$ は $x^{2t}$ の倍数で次数が $2t$ 未満なので $0$ です。 **$u_i = \lambda\sigma$、$r_i = \lambda\omega$ と書けること。** $\sigma$ は $\omega u_i$ を割り切り、$\sigma$ と $\omega$ は共通の既約因子をもたないので（）、一意分解性（）から $\sigma$ は $u_i$ を割り切ります。$u_i = \lambda\sigma$（$\lambda \in K[x]$、$\lambda \ne 0$）と書くと、$\sigma r_i = \omega\lambda\sigma$ から $r_i = \lambda\omega$ です。 **$\lambda$ が定数であること。** 鍵方程式を $\sigma S = \omega + \mu x^{2t}$（$\mu \in K[x]$）と書きます。補題の 2 から $$ s_ix^{2t} = r_i - u_iS = \lambda\omega - \lambda\sigma S = -\lambda\mu x^{2t} $$ で、$K[x]$ は整域なので $s_i = -\lambda\mu$ です。$\lambda$ は $s_i$ と $u_i$ の共通因子なので、補題の 3 により定数です。 $\sigma(0) = 1$ なので $u_i(0) = \lambda \ne 0$ で、$\sigma = u_i/u_i(0)$、$\omega = r_i/u_i(0)$ が得られます。 誤りの位置は、$\sigma$ の根を $\alpha^{0}, \alpha^{-1}, \ldots, \alpha^{-(n-1)}$ の中から順に代入して探します（Chien 探索）。$\sigma(\alpha^{-i}) = 0$ となる $i$ が誤りの位置です。二元符号なら誤りの値は $1$ に決まっているので、これで復号は終わりです。$q > 2$ のときは誤りの値が必要で、次の公式で求まります。 の記号で、$\sigma'$ を $\sigma$ の形式微分とすると、各 $i \in I$ について $$ e_i = -\frac{\omega(X_i^{-1})}{\sigma'(X_i^{-1})} $$ が成り立つ。 形式微分 $\bigl(\sum_j f_jx^j\bigr)' = \sum_j jf_jx^{j-1}$ は線形で、単項式について $(x^{j}x^{l})' = (j+l)x^{j+l-1} = (x^j)'x^l + x^j(x^l)'$ なので、積の法則 $(fh)' = f'h + fh'$ が成り立ちます。これを $\sigma = \prod_{l \in I}(1 - X_lx)$ に繰り返し使うと $$ \sigma'(x) = \sum_{i \in I}(-X_i)\prod_{l \ne i}(1 - X_lx) $$ です。$x = X_i^{-1}$ を代入すると、$i$ 以外の項は因子 $1 - X_iX_i^{-1} = 0$ を含むので $\sigma'(X_i^{-1}) = -X_i\prod_{l \ne i}(1 - X_lX_i^{-1})$ です。 の証明で見たとおり $\omega(X_i^{-1}) = e_iX_i\prod_{l \ne i}(1 - X_lX_i^{-1})$ で、積の部分は $0$ でないので、比を取ると $\omega(X_i^{-1})/\sigma'(X_i^{-1}) = -e_i$ です。 の $\delta = 5$ の符号（$t = 2$）を使います。$\mathbb{F}_{16}$ の元の表は、$\alpha^4 = \alpha+1$ から順に $$ \alpha^5 = \alpha^2+\alpha,\ \ \alpha^6 = \alpha^3+\alpha^2,\ \ \alpha^7 = \alpha^3+\alpha+1,\ \ \alpha^8 = \alpha^2+1,\ \ \alpha^9 = \alpha^3+\alpha, $$ $$ \alpha^{10} = \alpha^2+\alpha+1,\ \ \alpha^{11} = \alpha^3+\alpha^2+\alpha,\ \ \alpha^{12} = \alpha^3+\alpha^2+\alpha+1,\ \ \alpha^{13} = \alpha^3+\alpha^2+1,\ \ \alpha^{14} = \alpha^3+1 $$ です。符号語 $c(x) = g(x) = 1 + x^4 + x^6 + x^7 + x^8$ を送り、座標 $2$ と $11$ が反転して $y(x) = c(x) + x^2 + x^{11}$ を受け取ったとします。 **シンドローム。** $S_j = y(\alpha^j) = \alpha^{2j} + \alpha^{11j}$ なので、$S_1 = \alpha^2 + \alpha^{11} = \alpha^9$、$S_2 = S_1^2 = \alpha^{3}$、$S_3 = \alpha^6 + \alpha^{33} = \alpha^6 + \alpha^3 = \alpha^2$、$S_4 = S_2^2 = \alpha^6$ です（受信側は $y$ から直接計算します。二元符号では $S_{2j} = S_j^2$ です）。$S(x) = \alpha^9 + \alpha^3x + \alpha^2x^2 + \alpha^6x^3$。 **互除法。** $r_0 = x^4$、$r_1 = S$ から始めます。 | $i$ | $q_i$ | $r_{i+1}$ | $u_{i+1}$ | |---|---|---|---| | $1$ | $\alpha^9x + \alpha^5$ | $\alpha^2x^2 + \alpha^{13}x + \alpha^{14}$ | $\alpha^9x + \alpha^5$ | | $2$ | $\alpha^4x$ | $\alpha^9$ | $\alpha^{13}x^2 + \alpha^9x + 1$ | $\deg r_3 = 0 < t = 2$ で止まります。$u_3(0) = 1$ なので $$ \sigma(x) = 1 + \alpha^9x + \alpha^{13}x^2, \qquad \omega(x) = \alpha^9 $$ です。 **誤りの位置。** $\sigma(\alpha^{-i}) = 0$ となる $i$ を探すと $i = 2$ と $i = 11$ です。実際 $\sigma(x) = (1 - \alpha^2x)(1 - \alpha^{11}x)$ で、$\alpha^2 + \alpha^{11} = \alpha^9$、$\alpha^2\alpha^{11} = \alpha^{13}$ です。座標 $2$ と $11$ を反転して $c$ が復元されます。 **Forney の公式の確認。** 標数 $2$ では $(x^2)' = 0$ なので $\sigma'(x) = \alpha^9$ で、$e_i = \omega/\sigma' = 1$ となり、二元符号の誤りの値と合っています。 ## 7. バースト誤りと応用 ### 7.1. バースト誤り 記録媒体の傷や通信路のフェージングでは、誤りは散らばらず、連続した区間に固まって起こります。 この節の命題のねらいは、「バースト誤りを訂正できる符号には冗長部分 $n - k$ が最低どれだけ必要か」を、シンドロームの個数を数えることで下から押さえることです。長さ $b$ 以下のバーストを区別するには、それぞれに別のシンドロームが対応していなければなりません。区別すべき語の個数が、シンドロームの取りうる個数 $q^{n-k}$ を超えないという数え上げが、Reiger の限界の証明の骨格です。 $0$ でない語 $e \in \mathbb{F}_q^n$ が**長さ $l$ 以下の（巡回）バースト**であるとは、ある $i$ と、$\deg b < l$ を満たす多項式 $b(x)$ について、$R_n$ の中で $e(x) = x^ib(x)$ と書けることをいう。すなわち、$e$ の $0$ でない成分が、巡回的に連続する $l$ 個の座標の中に収まることをいう。 1. 巡回 $[n, k]_q$ 符号 $C$ は、長さ $n - k$ 以下のバーストを符号語として含まない。したがって、長さ $n - k$ 以下のバースト誤りをすべて検出する。 2. 線形符号 $C$ について、「長さ $b$ 以下のバーストがすべて相異なるシンドロームをもち、どれもシンドロームが $0$ でない」ことと、「$C$ の $0$ でない符号語は、長さ $b$ 以下のバーストでも、そのようなバースト 2 つの差でもない」ことは同値である。 3. （Reiger の限界）2 の条件を満たす $[n, k]_q$ 符号は、$2b \le n$ のとき $n - k \ge 2b$ を満たす。 (1) $e = x^ib(x)$（$R_n$ の中で）、$b \ne 0$、$\deg b < n - k$ が符号語だとします。$x$ は $R_n$ の単元（$x \cdot x^{n-1} = 1$）で、$C$ はイデアルなので、$b = x^{n-i}e \in C$ です。$C$ の $0$ でない元を次数 $n$ 未満の多項式で表すと生成多項式 $g$ の倍数なので（ の 2）、次数は $\deg g = n - k$ 以上です。これは $\deg b < n - k$ に反します。誤り $e$ が加わった受信語 $c + e$ が符号語になるのは $e \in C$ のときだけなので、このようなバーストは必ず検出されます。 (2) 検査行列を $H$ とすると、語 $e$ のシンドロームは $He^{\mathsf{T}}$ で、$He^{\mathsf{T}} = He'^{\mathsf{T}}$ は $e - e' \in C$ と同値、$He^{\mathsf{T}} = 0$ は $e \in C$ と同値です（）。これを長さ $b$ 以下のバースト $e \ne e'$ に当てはめたものが主張です。 (3) 最初の $2b$ 個の座標の外で $0$ である語の全体 $U$ は $q^{2b}$ 元からなります。$u, u' \in U$、$u \ne u'$ とすると、$u - u'$ は $U$ の $0$ でない元で、座標 $0, \ldots, b-1$ の部分 $v$ と座標 $b, \ldots, 2b-1$ の部分 $v'$ の和 $v + v'$ に分かれます。$v, v'$ はそれぞれ $0$ か長さ $b$ 以下のバーストなので、$u - u' = v - (-v')$ は長さ $b$ 以下のバーストか、そのようなバースト 2 つの差です。2 の条件から $u - u' \notin C$ で、$u$ と $u'$ のシンドロームは異なります。シンドロームは $\mathbb{F}_q^{n-k}$ の元なので $q^{2b} \le q^{n-k}$ です。 2 の条件が成り立てば、シンドロームからバーストを一意に特定でき、長さ $b$ 以下のバースト誤りをすべて訂正できます。Reiger の限界は、ランダムな誤りに対する Singleton 限界 $n - k \ge d - 1 \ge 2t$ のバースト版です。 巡回冗長検査（CRC）では、次数 $r$ の多項式 $g(x) \in \mathbb{F}_2[x]$（$g(0) = 1$）を決め、情報 $m(x)$ に、$x^rm(x)$ を $g$ で割った余り $r(x)$ を付けて $c(x) = x^rm(x) + r(x)$ を送ります（）。受信側は受信語を $g$ で割り、余りが $0$ でなければ誤りがあったと判断します。誤り $e(x)$ が見逃されるのは $g \mid e$ のときだけです。 - **長さ $r$ 以下のバースト。** $e = x^ib(x)$、$b(0) = 1$、$\deg b < r$ とします。$g(0) = 1$ なので $g$ と $x$ は共通因子をもたず、$g \mid x^ib$ なら $g \mid b$ ですが、$\deg b < \deg g$ なので不可能です。すべて検出されます（ の 1 と同じ議論で、語の長さが $g$ の周期より短くても成り立ちます）。 - **奇数個の誤り。** $g$ が $x + 1$ で割り切れるなら、$g$ の倍数は $x = 1$ で $0$、つまり偶数重みなので、奇数重みの誤りはすべて検出されます。 - **2 個の誤り。** $e = x^i(x^{j} + 1)$ が $g$ の倍数になるのは $g \mid x^j + 1$ のときです。$g \mid x^{N} + 1$ となる最小の $N$（$g$ の周期）より語が短ければ、2 個の誤りはすべて検出されます。 $\mathbb{F}_{2^m}$ の元を $\mathbb{F}_2$ 上の基底で $m$ ビットに書くと、$\mathbb{F}_{2^m}$ 上の $[n, k, d]$ 符号は二元 $[mn, mk]$ 符号になり、最小距離は $d$ 以上です（$0$ でないシンボルは $0$ でないビットを少なくとも 1 つ含みます）。 の符号からは二元 $[21, 9]$ 符号（最小距離 $5$ 以上）が得られます。 この符号はバーストに強い符号です。もとの符号が $t$ 個のシンボル誤りを訂正できるとき、長さ $(t-1)m + 1$ ビット以下のバーストは高々 $t$ 個のシンボルにしかまたがらないので、すべて訂正できます。$[21, 9]$ 符号では $t = 2$、$m = 3$ で、長さ $4$ ビット以下のバーストを訂正します。Reiger の限界は $b \le (21 - 9)/2 = 6$ です。 ### 7.2. Reed–Solomon 符号の使われ方 - **CD（コンパクトディスク）。** 音楽 CD の誤り訂正（CIRC、cross-interleaved Reed–Solomon code）は、$\mathbb{F}_{2^8}$ 上の Reed–Solomon 符号を短縮した $[32, 28, 5]$ 符号と $[28, 24, 5]$ 符号の 2 段を、インターリーブ（シンボルの並べ替え）を挟んで組み合わせています。1 シンボルは 1 バイトです。インターリーブは、ディスクの傷による長いバーストを多くの符号語に分散させるためのものです（規格 IEC 60908）。 - **QR コード。** QR コードは $\mathbb{F}_{2^8} = \mathbb{F}_2[x]/(x^8+x^4+x^3+x^2+1)$ 上の Reed–Solomon 符号を使い、誤り訂正レベル L・M・Q・H で、コード語のおよそ 7%・15%・25%・30% を復元できます（規格 ISO/IEC 18004）。汚れや破損は連続したモジュールに起こるバースト誤りで、バイト単位の符号が向いています。 どちらも、 の「シンボルが数ビットのかたまり」という性質を利用しています。 秘密 $s \in \mathbb{F}_q$ を $n$ 人に分け、どの $k$ 人が集まれば復元でき、$k - 1$ 人では何も分からないようにします。$f_1, \ldots, f_{k-1} \in \mathbb{F}_q$ を一様ランダムに選んで $f(x) = s + f_1x + \cdots + f_{k-1}x^{k-1}$ とし、相異なる $0$ でない $a_1, \ldots, a_n$ に対して $i$ 番目の人に $f(a_i)$ を渡します。 分け前の列 $(f(a_1), \ldots, f(a_n))$ は $\mathrm{RS}_k(a)$ の符号語です。$k$ 人の分け前から $f$ が決まるのは、次数 $k$ 未満の多項式が $k$ 点の値で決まるからです（ の 3。 の条件 3 の言い換え）。$k - 1$ 人の分け前 $f(a_{i_1}), \ldots, f(a_{i_{k-1}})$ と任意の候補 $s' \in \mathbb{F}_q$ に対しては、$0, a_{i_1}, \ldots, a_{i_{k-1}}$ の $k$ 点で指定の値を取る次数 $k$ 未満の多項式がちょうど 1 つあります（$k$ 点での評価は $k$ 次元空間の間の単射な線形写像なので全単射）。したがって、どの $s'$ も同じ個数（1 個）の多項式と整合し、$k - 1$ 人は $s$ について何の情報も得ません。分け前の一部が改ざんされていても、 の復号で $\lfloor (n-k)/2 \rfloor$ 個までなら正しい $f$ が復元できます（McEliece–Sarwate、参考文献 [6]）。 ## 8. 演習 $\mathbb{F}_2$ 上の長さ $7$、生成多項式 $g = x^3 + x + 1$ の巡回符号 $C$ について、生成行列、検査多項式 $h$、双対符号 $C^{\perp}$ の生成多項式を求めよ。また $C^{\perp} \subseteq C$ を示せ。 生成行列は $g, xg, x^2g, x^3g$ の係数を並べた $$ G = \begin{pmatrix} 1&1&0&1&0&0&0\\ 0&1&1&0&1&0&0\\ 0&0&1&1&0&1&0\\ 0&0&0&1&1&0&1 \end{pmatrix} $$ です。$h = (x^7 - 1)/g = (x+1)(x^3+x^2+1) = x^4 + x^2 + x + 1$ で、係数を逆順にして $h^{*} = x^4 + x^3 + x^2 + 1$ です。$h(0) = 1$ なので、 により $C^{\perp}$ の生成多項式は $x^4 + x^3 + x^2 + 1 = (x+1)(x^3+x+1)$ です。これは $g$ の倍数なので、$C^{\perp}$ の元 $a\cdot(x+1)g$ はすべて $C$ に属し、$C^{\perp} \subseteq C$ です。$C^{\perp}$ は $[7, 3, 4]$ 単体符号です。 の $[15, 7, 5]$ BCH 符号 $C$ の双対符号 $C^{\perp}$ の定義集合と次元を求め、$d(C^{\perp}) = 4$ を示せ。 $C$ の定義集合は $T = \{1,2,3,4,6,8,9,12\}$、補集合は $\{0,5,7,10,11,13,14\}$ です。 により $C^{\perp}$ の定義集合は符号を反転した $\{0, 10, 8, 5, 4, 2, 1\} = \{0,1,2,4,5,8,10\}$ で、次元は $15 - 7 = 8$ です。連続する指数 $0, 1, 2$ を含むので、BCH 限界（$b = 0$、$\delta = 4$）から $d(C^{\perp}) \ge 4$ です。生成多項式は $(x+1)m_1m_5$ で、$m_1m_5 = (x^4+x+1)(x^2+x+1) = x^6+x^5+x^4+x^3+1$、これに $x + 1$ を掛けると $x^7 + x^3 + x + 1$ となり、重み $4$ の符号語です。よって $d(C^{\perp}) = 4$ です。 $n = q - 1$、$\alpha$ を $\mathbb{F}_q^{\times}$ の生成元、$a_j = \alpha^j$（$0 \le j \le n-1$）、$1 \le k \le n-1$ とする。$\mathrm{RS}_k(a)^{\perp} = \mathrm{GRS}_{n-k}(a, v)$、$v_j = \alpha^j$ であることを示せ。 により $\mathrm{RS}_k(a)$ の定義集合は $T = \{1, \ldots, n-k\}$ です。補集合は $\{0\} \cup \{n-k+1, \ldots, n-1\}$ で、符号を反転すると $\{0, 1, \ldots, k-1\}$ です。 により、$\mathrm{RS}_k(a)^{\perp}$ は定義集合 $\{0, 1, \ldots, k-1\}$ の巡回 $[n, n-k]$ 符号です。 一方、$\mathrm{GRS}_{n-k}(a, v)$ の元は $c_j = \alpha^jf(\alpha^j) = \tilde f(\alpha^j)$、$\tilde f = xf$ と書け、$\tilde f = \sum_l \tilde f_lx^l$ は $\tilde f_0 = 0$ かつ $\tilde f_l = 0$（$l \ge n-k+1$）を満たします。 の 2 から $c(\alpha^i) = n\tilde f_l$（$l \equiv -i$）で、$i = 0$ なら $l = 0$、$1 \le i \le k-1$ なら $l = n - i \ge n-k+1$ なので、$c(\alpha^i) = 0$（$0 \le i \le k-1$）です。よって $\mathrm{GRS}_{n-k}(a, v) \subseteq \mathrm{RS}_k(a)^{\perp}$ で、次元がともに $n - k$ なので一致します。 $\gcd(n, q) \ne 1$ の例として、$\mathbb{F}_2$ 上の長さ $4$ の巡回符号をすべて求め、 の 4 の個数の式 $2^{t}$ が成り立たないことを確かめよ。 $\mathbb{F}_2$ 上で $x^4 - 1 = (x+1)^4$ です。モニックな約数は $(x+1)^j$（$0 \le j \le 4$）の 5 個なので、巡回符号は 5 個です（ の 3）。既約因子は $x + 1$ の 1 個で $2^1 = 2$ とは一致しません。重根があると、約数は既約因子の部分集合では決まらず、重複度の選び方の数だけあります。5 個の符号は、$j = 0$ が全空間、$j = 1$ が偶数重みの $[4, 3, 2]$ 符号、$j = 2$ が $g = x^2 + 1$ の $[4, 2, 2]$ 符号 $\{0000, 1010, 0101, 1111\}$、$j = 3$ が $g = x^3+x^2+x+1$ の反復符号 $[4, 1, 4]$、$j = 4$ が $\{0\}$ です。 ## 参考文献 1. F. J. MacWilliams, N. J. A. Sloane, *The Theory of Error-Correcting Codes*, North-Holland, 1977 — 第 7 章（巡回符号）、第 9 章（BCH 符号）、第 10 章（Reed–Solomon 符号）。 2. J. H. van Lint, *Introduction to Coding Theory*, 3rd ed., Graduate Texts in Mathematics 86, Springer, 1999 — 巡回符号と BCH 符号の章。 3. R. M. Roth, *Introduction to Coding Theory*, Cambridge University Press, 2006 — 一般化 Reed–Solomon 符号とその復号（鍵方程式、互除法）の章。 4. I. S. Reed, G. Solomon, "Polynomial codes over certain finite fields", *Journal of the Society for Industrial and Applied Mathematics* 8 (1960), 300–304. 5. Y. Sugiyama, M. Kasahara, S. Hirasawa, T. Namekawa, "A method for solving key equation for decoding Goppa codes", *Information and Control* 27 (1975), 87–99. 6. R. J. McEliece, D. V. Sarwate, "On sharing secrets and Reed–Solomon codes", *Communications of the ACM* 24 (1981), 583–584. 秘密分散の原論文は A. Shamir, "How to share a secret", *Communications of the ACM* 22 (1979), 612–613。