Chapter 10

BCH 符号 — 訂正能力を「設計」する

この章の位置づけ. CRC（09 章）は誤りを検出できたが、訂正はできなかった。ハミング符号（08 章）は訂正できたが、1 ビットだけだった。 BCH 符号は、訂正したいビット数\(t\)を先に決めると、その能力を持つ巡回符号を作れる方式である。Bose、Ray-Chaudhuri、Hocquenghem の 3 人が 1959〜60 年に発表した。
09 章では生成多項式\(g(x)\)を係数で与えていた。BCH 符号では\(g\)を根で指定する。\(\mathrm{GF}(2^m)\)の中で「\(g\)の根はこれらの要素」と決め、それを満たす次数最小の多項式を\(g\)にする。05 章で作った拡大体をここで使う。
この章で使う既出の用語（定義は各リンク先）. 位数（02 章 1 節）、標数（02 章 3 節）、原始元・離散対数（03 章 3 節）、有限体上の連立 1 次方程式（03 章 4 節）、因数・既約多項式（04 章 3 節）、原始多項式と\(x^4+x+1\)のべき乗表（04 章 4 節）、拡張ユークリッドの互除法（04 章 5 節）、 \(\mathrm{GF}(2^m)\)の構成と\(\alpha\)のべき表現・定理 2 の系・フロベニウス（05 章）、検出・訂正能力と\(d_{\min}\)（06 章 3 節）、線形符号・重み（07 章 1 節）、シンドローム（07 章 4 節）、巡回符号・生成多項式（09 章 1 節）

1. 設計の原理 — 根を指定する

この章で扱うのは、符号語の各桁が 0 か 1 の2 元 BCH 符号である。符号語と生成多項式\(g(x)\)は\(\mathrm{GF}(2)\)係数の多項式だが、\(g\)の根は拡大体\(\mathrm{GF}(2^m)\)の中に取る。 \(\mathrm{GF}(2)\)係数の多項式にも\(\mathrm{GF}(2^m)\)の要素を代入できる。0 と 1 は\(\mathrm{GF}(2^m)\)にも含まれるので、係数をそのまま\(\mathrm{GF}(2^m)\)の要素とみなして計算すればよい。

BCH 限界（BCH bound）

\(\alpha\)を\(\mathrm{GF}(2^m)\)の原始元とし、符号長を\(n = 2^m - 1\)とする。\(\alpha\)の位数は\(n\)なので、\(\alpha^0, \alpha^1, \dots, \alpha^{n-1}\)は互いに異なる。

定理: \(\mathrm{GF}(2)\)係数の多項式\(g(x)\)が、連続する\(2t\)個のべき

\[ \alpha, \alpha^2, \alpha^3, \dots, \alpha^{2t} \]

をすべて根に持ち、\(x^n + 1\)を割り切るとする。\(g\)を生成多項式とする長さ\(n\)の巡回符号の最小距離は

\[ d_{\min} \geq 2t + 1 \]

であり、06 章 3 節より\(t\)ビットの誤りを訂正できる。\(2t+1\)を設計距離という。

方針: 重みが\(2t\)以下の 0 でない符号語があると仮定し、その 1 の位置から連立 1 次方程式を作る。方程式の係数行列の行列式が 0 でないことから、解は 0 しかないはずなのに、0 でない解があることになって矛盾する。

導出: 符号語\(c(x)\)は\(g\)の倍数なので、\(g\)の根\(\alpha^j\)（\(j=1,\dots,2t\)）は\(c\)の根でもあり、\(c(\alpha^j) = 0\)である。重みが\(w\)（\(1 \leq w \le 2t\)）の符号語があるとし、1 が立つ位置を\(i_1 < \cdots < i_w\)として\(c(x) = x^{i_1} + x^{i_2} + \cdots + x^{i_w}\)と書く。\(c(\alpha^j) = 0\)は

\[ \sum_{l=1}^{w} (\alpha^{j})^{i_l} = 0 \qquad (j = 1,\dots,2t) \]

である。\(X_l = \alpha^{i_l}\)とおくと\((\alpha^j)^{i_l} = X_l^j\)なので、\(j = 1, \dots, w\)の\(w\)本の式は

\[ \begin{pmatrix} X_1 & X_2 & \cdots & X_w\\ X_1^2 & X_2^2 & \cdots & X_w^2\\ \vdots & & & \vdots\\ X_1^w & X_2^w & \cdots & X_w^w \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_w \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \]

が\(y_1 = \cdots = y_w = 1\)という解を持つことを表している。各列が 1 つの数のべき\(X, X^2, X^3, \dots\)になっている行列をヴァンデルモンド行列という。

正方行列には行列式という数が 1 つ決まり、行列式が 0 でなければ、上の形の連立方程式の解は\(y_1 = \cdots = y_w = 0\)だけである。03 章 4 節の掃き出し法で言えば、途中で割る数が一度も 0 にならず、すべての変数が 0 に決まることに当たる。ヴァンデルモンド行列の行列式は

\[ \det = X_1X_2\cdots X_w \prod_{p<q}(X_q - X_p) \]

である。\(w = 2\)なら\(X_1 X_2^2 - X_2 X_1^2 = X_1 X_2 (X_2 - X_1)\)と直接確かめられる。一般の\(w\)でも同じ形になることは線形代数の標準的な事実で、ここでは証明を省く。 \(i_l\)は互いに異なり\(n\)未満なので、\(X_l = \alpha^{i_l}\)は互いに異なる 0 でない要素である。したがってどの因子も 0 でなく、\(\det \neq 0\)である。すると解は\(y_1 = \cdots = y_w = 0\)だけのはずだが、\(y_l = 1\)が解になっていたので矛盾する。

よって重みが\(2t\)以下の 0 でない符号語は無く、07 章 1 節より\(d_{\min}\geq 2t+1\)である ∎

「根を\(2t\)個続けて指定する」という設計上の要求が、ヴァンデルモンド行列式が 0 でないという事実を通して、「\(t\)ビット訂正できる」という性能の保証になった。欲しい性能から符号を設計できるのが BCH 符号の特長である。

2. 生成多項式の作り方

1 節の定理を使うには、\(\alpha, \dots, \alpha^{2t}\)を根に持つ\(\mathrm{GF}(2)\)係数の多項式を作る必要がある。単に\((x - \alpha)(x - \alpha^2)\cdots\)と掛けると係数が\(\mathrm{GF}(2^m)\)の要素になってしまうので、根を追加して係数が 0 と 1 になるようにする。その方法がこの節の内容である。

最小多項式と共役類

定理: \(\mathrm{GF}(2)\)係数の多項式\(f\)が\(\beta\)を根に持てば、\(\beta^2\)も根に持つ。

導出: 標数 2 では\((a+b)^2 = a^2+b^2\)である（05 章 4 節の定理 4）。項が 3 つ以上でも\((a+b+c)^2 = ((a+b)+c)^2 = (a+b)^2 + c^2 = a^2+b^2+c^2\)と繰り返せば同じである。 \(f(x) = \sum a_i x^i\)とすると、\(a_i\)は 0 か 1 なので\(a_i^2 = a_i\)であり

\[ f(\beta)^2 = \left(\sum a_i \beta^i\right)^2 = \sum a_i^2 \beta^{2i} = \sum a_i (\beta^2)^i = f(\beta^2) \]

よって\(f(\beta)=0\)なら\(f(\beta^2) = 0^2 = 0\) ∎

\(\beta\)から 2 乗を繰り返して得られる互いに異なる要素の集合\(\{\beta, \beta^2, \beta^4, \beta^8, \dots\}\)を\(\beta\)の共役類という。 0 でない要素は\(\beta^{2^m - 1} = 1\)を満たす（05 章 4 節の定理 2 の系）ので\(\beta^{2^m} = \beta\)であり、2 乗を\(m\)回繰り返すと必ず\(\beta\)に戻る。したがって共役類の要素数は\(m\)以下である。

共役類のすべての要素\(\gamma\)について\((x - \gamma)\)を掛けた多項式

\[ M_\beta(x) = \prod_{\gamma \in \beta \text{ の共役類}}(x - \gamma) \]

を\(\beta\)の最小多項式という。\(M_\beta\)は次の 2 つの性質を持つ。

(1) 係数は 0 か 1: \(M_\beta(x) = \sum c_i x^i\)とする。上の導出と同じく\(M_\beta(x)^2 = \sum c_i^2 x^{2i}\)である。一方、各因子を 2 乗すると\((x-\gamma)^2 = x^2 - \gamma^2\)で、\(\gamma\)が共役類全体を動くと\(\gamma^2\)も共役類全体を 1 回ずつ動くので、\(M_\beta(x)^2 = \prod(x^2 - \gamma^2) = M_\beta(x^2) = \sum c_i x^{2i}\)である。 2 つを比べて\(c_i^2 = c_i\)、すなわち\(c_i(c_i - 1) = 0\)で、体には零因子が無いので\(c_i = 0\)か\(1\)である。

(2) \(\beta\)を根に持つ\(\mathrm{GF}(2)\)係数の多項式のうち次数が最小: 上の定理より、\(\beta\)を根に持つ\(\mathrm{GF}(2)\)係数の多項式は共役類のすべての要素を根に持つので、次数は共役類の要素数以上である。\(M_\beta\)の次数はちょうど共役類の要素数である。同じ理由で\(M_\beta\)は既約である。より低い次数の\(\mathrm{GF}(2)\)係数の因数が\(\beta\)を根に持つことはありえないからである。

生成多項式

\(\alpha, \alpha^2, \dots, \alpha^{2t}\)をすべて根に持つ次数最小の\(\mathrm{GF}(2)\)係数多項式は

\[ \boxed{g(x) = \mathrm{lcm}\left(M_{\alpha}(x), M_{\alpha^2}(x), \dots, M_{\alpha^{2t}}(x)\right)} \]

である。\(\mathrm{lcm}\)は最小公倍多項式で、並べた多項式すべてで割り切れる多項式のうち次数が最小のものである。 \(\alpha^j\)と\(\alpha^{2j}\)は同じ共役類に入るので\(M_{\alpha^j} = M_{\alpha^{2j}}\)で、重複が多い。各\(M\)は既約で、異なる共役類の最小多項式は共通の根を持たないので共通因数も無い。したがって\(\mathrm{lcm}\)は「異なる最小多項式を 1 回ずつ掛けた積」になる。

また、0 でない要素\(\gamma\)はすべて\(\gamma^n = 1\)、つまり\(x^n + 1\)の根なので、\(g\)の根はすべて\(x^n + 1\)の根であり、\(g\)は\(x^n+1\)を割り切る。よって 1 節の定理の条件を満たす。

上の図で\(t\)を変えると、\(\mathrm{GF}(2^4)\)で共役類と最小多項式を求めて\(g\)を組み立てる様子が表示される。

3. 実例: (15,7) 2 ビット訂正 BCH 符号

\(m=4\)とし、\(\mathrm{GF}(2^4)\)を原始多項式\(f(x)=x^4+x+1\)で作る。\(\alpha = x\)が原始元で、\(n = 2^4-1 = 15\)である。\(\alpha^i\)のビット表現は04 章 4 節の表（\(x^i \bmod f\)）のとおりである。 \(t=2\)なので、根として\(\alpha,\alpha^2,\alpha^3,\alpha^4\)を要求する。

共役類: \(\alpha^{15} = 1\)なので、指数は 15 で割った余りで見る。2 乗は指数を 2 倍することである。

\(\alpha\)の類: 指数\(1 \to 2 \to 4 \to 8 \to 16 \equiv 1\)で一周し、\(\{\alpha, \alpha^2, \alpha^4, \alpha^8\}\)。
\(\alpha^3\)の類: 指数\(3 \to 6 \to 12 \to 24 \equiv 9 \to 18 \equiv 3\)で一周し、\(\{\alpha^3, \alpha^6, \alpha^{12}, \alpha^9\}\)。

要求した\(\alpha,\alpha^2,\alpha^4\)は最初の類、\(\alpha^3\)は 2 番目の類に入るので、\(g = M_{\alpha} M_{\alpha^3}\)である。

最小多項式:

\(M_{\alpha}(x) = x^4 + x + 1\)。\(\alpha = x\)は\(f(\alpha) = 0\)を満たす（05 章 2 節）。\(f\)は\(\alpha\)を根に持つ既約多項式で、次数 4 は共役類の要素数に等しいので、\(f\)が最小多項式である。
\(M_{\alpha^3}(x) = x^4+x^3+x^2+x+1\)。\((\alpha^3)^5 = \alpha^{15} = 1\)なので\(\alpha^3\)は\(x^5 + 1 = (x + 1)(x^4+x^3+x^2+x+1)\)の根である。\(\alpha^3 \neq 1\)なので後ろの因子の根であり、この因子は既約（04 章 3 節で確認済み）で、次数 4 は共役類の要素数に等しいので最小多項式である。

生成多項式:

\[ g(x) = (x^4+x+1)(x^4+x^3+x^2+x+1) \]

を展開する。\(x^4+x^3+x^2+x+1\)に\(x^4\)、\(x\)、\(1\)をそれぞれ掛けて足す:

\[ \begin{aligned} &x^8+x^7+x^6+x^5+x^4\\ &\phantom{x^8+x^7+x^6+{}}x^5+x^4+x^3+x^2+x\\ &\phantom{x^8+x^7+x^6+x^5+{}}x^4+x^3+x^2+x+1 \end{aligned} \]

縦に足すと\(x^5\)が 2 個、\(x^4\)が 3 個、\(x^3\)・\(x^2\)・\(x\)が 2 個ずつなので、残るのは

\[ g(x) = x^8+x^7+x^6+x^4+1 \]

\(\deg g = 8\)なので\(k = 15-8 = 7\)で、\((15,7)\)符号である。1 節の定理より\(d_{\min}\geq 5\)で、2 ビット訂正できる。実際に\(2^7 - 1 = 127\)個の 0 でない符号語の重みを調べると最小は 5 で、\(d_{\min} = 5\)である。

4. 復号の流れ

BCH 符号とリード・ソロモン符号の復号は、次の 4 段階で誤りの位置と値を求め、最後に受信語から誤りを取り除いて訂正する。11 章では、この訂正を第 5 ステップとして数える。ステップ 2 と 4 の一般的な方法は、次章でリード・ソロモン符号と共通に扱う。

ステップ 1: シンドロームの計算

受信語\(r(x)\)に対し

\[ S_j = r(\alpha^j) \qquad (j = 1, 2, \dots, 2t) \]

を求める。誤りが無ければ\(r\)は\(g\)の倍数で、\(\alpha^j\)は\(g\)の根なので、すべて 0 になる。

誤りパターンを\(e(x) = \sum_{l=1}^{\nu} Y_l x^{i_l}\)とする。\(\nu\)（ニュー）は誤りの個数、\(i_l\)は誤ったビットの位置、\(Y_l\)は誤りの値で、2 元 BCH 符号ではビット反転しかないので\(Y_l=1\)である。\(r = c + e\)で\(c(\alpha^j) = 0\)なので

\[ S_j = e(\alpha^j) = \sum_{l=1}^{\nu} Y_l (\alpha^{i_l})^j = \sum_{l=1}^{\nu} Y_l X_l^j \]

となる。\(X_l = \alpha^{i_l}\)を誤り位置\(i_l\)に対応する位置元と呼ぶ。\(X_l\)が分かれば、離散対数を取って\(i_l\)が分かる。

未知数は位置元\(X_l\)と誤り値\(Y_l\)の合計\(2\nu\)個、既知の値は\(S_1,\dots,S_{2t}\)の\(2t\)個である。\(\nu \le t\)なら式の本数のほうが多い。式は\(X_l\)についてべき乗を含む（線形でない）が、次のステップで線形の問題に直して解く。

2 元 BCH 符号では\(S_{2j} = S_j^2\)が成り立つ。\(S_{2j} = r(\alpha^{2j})\)で、2 節の定理の導出と同じ計算により\(r(\beta^2) = r(\beta)^2\)だからである。したがって計算が必要なのは奇数番目の\(S_1, S_3, \dots\)だけである。

ステップ 2: 誤り位置多項式を求める

\[ \Lambda(x) = \prod_{l=1}^{\nu}(1 - X_l x) \]

を誤り位置多項式という。\(x = X_l^{-1}\)で因子\(1 - X_l x\)が 0 になるので、根は位置元の逆数\(X_l^{-1}\)である。シンドロームから\(\Lambda\)の係数を求めるのが復号の中心で、一般にはバーレカンプ・マッシー法か、多項式版の拡張ユークリッドの互除法（04 章 5 節）を使う（11 章で説明する）。\(t = 2\)なら、下の復号例のように直接の式で求められる。

ステップ 3: 根を探す（チェン探索）

\(\Lambda(x)=0\)となる\(x\)を、\(\alpha^0, \alpha^{-1}, \alpha^{-2},\dots, \alpha^{-(n-1)}\)を順に代入して探す。発案者 Chien の名前を取ってチェン探索という。 \(\Lambda(\alpha^{-i}) = 0\)なら\(\alpha^{-i}\)が\(X_l^{-1}\)のどれかなので\(X_l = \alpha^i\)、すなわち\(i\)番目のビットが誤りである。

ステップ 4: 誤り値を求める

2 元 BCH 符号では誤り値は必ず 1（ビット反転）なので、位置が分かればそのビットを反転して訂正は終わる。値が 0 と 1 以外も取るリード・ソロモン符号では、\(\Lambda\)とシンドロームから各位置の誤り値を求めるフォニー・アルゴリズムを使う（11 章）。

復号例: (15,7) 符号の 2 ビット誤り

t = 2 の誤り位置多項式の係数: 誤りが 2 個なら\(\Lambda(x) = (1 + X_1 x)(1 + X_2 x) = 1 + \sigma_1 x + \sigma_2 x^2\)で、\(\sigma_1 = X_1 + X_2\)、\(\sigma_2 = X_1X_2\)である（標数 2 なので\(-\)は\(+\)）。シンドロームは\(S_1 = X_1 + X_2 = \sigma_1\)、\(S_3 = X_1^3 + X_2^3\)である。\((X_1 + X_2)^2 = X_1^2 + X_2^2\)を使うと

\[ X_1^3 + X_2^3 = (X_1 + X_2)(X_1^2 + X_1X_2 + X_2^2) = S_1(S_1^2 + \sigma_2) \]

なので\(S_3 = S_1^3 + S_1\sigma_2\)、したがって

\[ \sigma_1 = S_1, \qquad \sigma_2 = \frac{S_3}{S_1} + S_1^2 \]

である。

受信語: 3 節の生成多項式そのもの\(c(x) = g(x) = x^8+x^7+x^6+x^4+1\)（情報語\(m(x) = 1\)の符号語）を送り、3 番目と 10 番目のビット（\(x^3\)と\(x^{10}\)の係数）が反転して

\[ r(x) = x^{10} + x^8+x^7+x^6+x^4+x^3+1 \]

を受信したとする。以下、\(\alpha^i\)のビット表現は 04 章の表を使う。

ステップ 1: \(S_1 = r(\alpha) = e(\alpha) = \alpha^3 + \alpha^{10} = 1000 \oplus 0111 = 1111 = \alpha^{12}\)。 \(S_3 = r(\alpha^3) = e(\alpha^3) = \alpha^9 + \alpha^{30} = \alpha^9 + \alpha^0 = 1010 \oplus 0001 = 1011 = \alpha^7\)。（ここでは確認のため\(e\)で計算したが、受信側は\(r\)に代入して同じ値を得る。\(c(\alpha^j) = 0\)だからである。）

ステップ 2: \(\sigma_1 = S_1 = \alpha^{12}\)。\(S_3/S_1 = \alpha^{7-12} = \alpha^{-5} = \alpha^{10}\)、\(S_1^2 = \alpha^{24} = \alpha^9\)なので

\[ \sigma_2 = \alpha^{10} + \alpha^9 = 0111 \oplus 1010 = 1101 = \alpha^{13} \]

よって\(\Lambda(x) = 1 + \alpha^{12}x + \alpha^{13}x^2\)。

ステップ 3: \(i = 0, 1, \dots, 14\)について\(\Lambda(\alpha^{-i})\)を計算すると、0 になるのは\(i = 3\)と\(i = 10\)だけである。たとえば

\[ \Lambda(\alpha^{-3}) = 1 + \alpha^{12-3} + \alpha^{13-6} = 1 + \alpha^9 + \alpha^7 = 0001 \oplus 1010 \oplus 1011 = 0000 \]

\[ \Lambda(\alpha^{-10}) = 1 + \alpha^{12-10} + \alpha^{13-20} = 1 + \alpha^2 + \alpha^{8} = 0001 \oplus 0100 \oplus 0101 = 0000 \]

（\(\alpha^{-7} = \alpha^{8}\)。）

ステップ 4: 3 番目と 10 番目のビットを反転すると\(g(x)\)に戻り、訂正が完了する。\(\sigma_2 = X_1 X_2 = \alpha^{3+10} = \alpha^{13}\)とも一致している。

5. BCH 符号の実用

用途	符号
NAND フラッシュメモリの誤り訂正	BCH 符号（\(t = 4\)〜40 程度）
POCSAG（ページャの通信規格）	BCH (31,21)
QR コードの形式情報	BCH (15,5)
SSD	BCH 符号から、近年は LDPC 符号へ移行
CD・DVD・QR コードのデータ部	リード・ソロモン符号（BCH 符号の一種、11 章）

BCH 符号とリード・ソロモン符号の関係: この章では符号語の各桁（シンボル）を 0 か 1 とし、根だけを\(\mathrm{GF}(2^m)\)に取った。各シンボルそのものを\(\mathrm{GF}(2^m)\)の要素（\(m\)ビットのかたまり）にし、生成多項式を\(g(x) = (x - \alpha)(x-\alpha^2)\cdots(x-\alpha^{2t})\)と\(\mathrm{GF}(2^m)\)係数のまま作ったものがリード・ソロモン符号である。係数を 0 と 1 にそろえる必要が無いので、2 節の共役類の議論は要らない。 1 節の定理の証明は、\(y_l\)が 1 ではなく 0 でない\(\mathrm{GF}(2^m)\)の要素になるだけでそのまま成り立つ。

\(m = 8\)にすると 1 シンボルが 1 バイトになり、コンピュータで扱いやすい。リード・ソロモン符号は 1 バイトの中で何ビット壊れても 1 シンボルの誤りとして数えるので、連続した数十ビットがまとめて壊れるバースト誤りに強い。これが次章の主題である。