Chapter 10

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

この章の狙い. CRC（09 章）は誤りを検出できたが、訂正はできなかった。ハミング符号（08 章）は訂正できたが、1 ビットだけだった。
「\(t\)ビット訂正したい」と決めたら、その通りの符号が作れる——それが BCH 符号である（Bose・Ray-Chaudhuri・Hocquenghem の 3 名、1959-60 年）。
発想の転換はこうである。09 章では生成多項式\(g(x)\)を係数で指定していた。 BCH では根で指定する。\(\mathrm{GF}(2^m)\)の中に「\(g\)の根はこれとこれ」と要求を書き、それを満たす最小の多項式を\(g\)として採用する。 第 I 部で作った拡大体が、ここでついに主役になる。

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

BCH 限界（設計定理）

\(\alpha\)を\(\mathrm{GF}(2^m)\)の原始元とする。生成多項式\(g(x)\)が

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

という連続する\(2t\)個のべきを根に持つように作れば、その巡回符号の最小距離は

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

となり、06 章の定理より\(t\)ビット訂正できる。

なぜ「連続する \(2t\) 個の根」で距離が保証されるのか

導出: 符号語\(c(x)\)は\(g\)の倍数なので、\(c(\alpha^j) = 0\)（\(j=1,\dots,2t\)）。重み\(w\)の符号語\(c(x) = x^{i_1} + x^{i_2} + \cdots + x^{i_w}\)があったとすると、各\(j\)について

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

\(X_l = \alpha^{i_l}\)とおくとこれは

\[ \begin{aligned} X_1 + X_2 + \cdots + X_w &= 0\\ X_1^2 + X_2^2 + \cdots + X_w^2 &= 0\\ &\vdots\\ X_1^{2t} + \cdots + X_w^{2t} &= 0 \end{aligned} \]

この連立式の係数行列はヴァンデルモンド行列である。\(w \leq 2t\)なら、最初の\(w\)本を取り出した\(w\times w\)のヴァンデルモンド行列式は

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

（\(X_l = \alpha^{i_l}\)は互いに異なり、かつ非零なので）。行列式が 0 でないので解は\(X_1=\cdots=X_w=0\)のみ。しかし\(X_l \neq 0\)なので矛盾。

したがって重み\(w \le 2t\)の非零符号語は存在せず、\(d_{\min}\geq 2t+1\) ∎

ここが BCH の心臓部である. 「根を\(2t\)個連続で指定する」という設計上の要求が、ヴァンデルモンド行列式が 0 でないという代数の事実を経由して、「\(t\)ビット訂正できる」という性能の保証に変換された。
欲しい性能から逆算して符号を設計できる——これが BCH が「設計できる符号」と呼ばれる理由である。

2. 生成多項式の作り方

最小多項式と共役根

\(\mathrm{GF}(2)\)係数の多項式が\(\alpha^j\)を根に持つなら、 その 2 乗\(\alpha^{2j}\)も自動的に根になる。

導出: 05 章のフロベニウス写像より、標数 2 では\((a+b)^2 = a^2+b^2\)。 \(f(x) = \sum a_i x^i\)（\(a_i \in \{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 \Rightarrow f(\beta^2)=0\) ∎

\(\{\beta, \beta^2, \beta^4, \beta^8, \dots\}\)を共役類といい、これを全部根に持つ最小の多項式を \(\beta\)の最小多項式\(M_\beta(x)\)という。

生成多項式

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

（共役類が重複するので、実際には相異なる最小多項式の積になる。）

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

\(m=4\)、\(\mathrm{GF}(2^4)\)を\(f(x)=x^4+x+1\)（原始多項式）で構成。\(n = 2^4-1 = 15\)。 \(t=2\)なので、根に\(\alpha,\alpha^2,\alpha^3,\alpha^4\)を要求する。

共役類を求める（指数を 2 倍していき\(\bmod 15\)）:

\(\{1, 2, 4, 8\}\) → \(M_1(x) = x^4+x+1\)
\(\{3, 6, 12, 9\}\) → \(M_3(x) = x^4+x^3+x^2+x+1\)

\(\alpha,\alpha^2,\alpha^4\)は最初の類、\(\alpha^3\)は 2 番目の類に属する。よって

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

展開すると（\(\mathrm{GF}(2)\)で計算）:

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

\(\deg g = 8\)なので\(k = 15-8 = 7\)。(15,7) 符号、\(d_{\min}\geq5\)、2 ビット訂正 ✓

4. 復号の流れ

BCH/RS の復号は 4 段階からなる。詳細（特にステップ 2）は次章で RS 符号と共通に扱う。

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

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

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

誤りが無ければ全部 0（\(r\)が\(g\)の倍数なら\(\alpha^j\)が根だから）。

誤りを\(e(x) = \sum_{l=1}^{\nu} Y_l x^{i_l}\)（\(\nu\)個の誤り、\(Y_l\)は誤りの値、 2 元 BCH では\(Y_l=1\)）とすると:

\[ 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}\)を誤り位置と呼ぶ。）

未知数: 誤り位置\(X_l\)と誤り値\(Y_l\)（合計\(2\nu\)個）既知: \(S_1,\dots,S_{2t}\)（\(2t\)個）

\(\nu \le t\)なら未知数\(\le 2t\)なので、原理的に解ける。

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

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

を誤り位置多項式という（根が誤り位置の逆数）。シンドロームから\(\Lambda\)を求めるのが復号の山場で、 バーレカンプ・マッシー法またはユークリッドの互除法を使う（11 章で詳述）。

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

\(\Lambda(x)=0\)となる\(x\)を、\(\alpha^0, \alpha^{-1}, \alpha^{-2},\dots\)と総当たりで探す。見つかった根の逆数が誤り位置。

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

2 元 BCH では誤り値は必ず 1（ビット反転）なので、位置さえ分かれば訂正完了。（多値の RS 符号ではフォニー・アルゴリズムで値も求める。11 章。）

5. BCH の実用

用途	符号
NAND フラッシュの ECC	BCH (t=4〜40 程度)
DVD	BCH の一種
POCSAG（ページャ）	BCH (31,21)
QR コードの形式情報	BCH (15,5)
SSD	BCH → 近年は LDPC へ移行

BCH と RS の関係. BCH 符号のうち、シンボルを \(\mathrm{GF}(2^m)\)の元にとり、符号長を\(n=2^m-1\)としたものがリード・ソロモン符号である。つまり RS は BCH の特別な場合（非 2 元 BCH）。
違いは「1 ビットずつ扱うか、1 バイトずつ扱うか」。バイト単位で扱う RS は、1 バイト内で何ビット壊れても「1 シンボル誤り」として数えるため、 バースト誤りに圧倒的に強い。次章の主題である。