QRコードを少し汚しても読み取れるのはなぜでしょうか。あるいは、地上から何億kmも離れた探査機が送ってくる画像が、宇宙線や微弱な信号の中でもビット欠けせずに復元できるのはどうしてでしょうか。その裏側にあるのが誤り訂正符号であり、なかでも「あらかじめ指定した数の誤りを確実に訂正できる」という強力な保証を持つのがBCH符号（Bose–Chaudhuri–Hocquenghem code）です。
ハミング符号は1ビットの誤りしか直せませんでした。「2ビット、3ビット、あるいは $t$ ビットまで確実に直したい」という要求に、設計レベルで応えられるのがBCH符号の最大の魅力です。しかもその設計は、ガロア体（有限体）という美しい代数構造の上で、ほとんど機械的に行えます。BCH符号を理解すると、次のような分野への扉が開きます。
- ストレージとメモリ: NANDフラッシュメモリやSSDのECC（誤り訂正回路）では、BCH符号やその一般化であるリード・ソロモン符号が標準的に使われ、セルの経年劣化によるビット誤りを訂正しています
- 衛星・深宇宙通信: CCSDS（宇宙データシステム諮問委員会）の規格でも、BCH符号やリード・ソロモン符号が連接符号の外符号として用いられ、限られた送信電力で高信頼な通信を支えています
- 二次元コード・放送: QRコード（リード・ソロモン）や地上デジタル放送、DVDなど、身近なメディアの随所でBCH系の符号が活躍しています
本記事の内容
- BCH符号を理解するための土台 — ガロア体 $\mathrm{GF}(2^m)$ と原始元
- 「連続する $2t$ 個の冪をゼロ点に持つ」という設計思想と生成多項式の作り方
- 設計距離とBCH限界の導出 — なぜ $t$ 個の誤りが訂正できるのか
- 受信語のシンドローム $S_i = r(\alpha^i)$ の計算
- 誤り位置多項式とBerlekamp-Massey法、Chien探索による誤り位置の特定
- Pythonによる $\mathrm{GF}(2^m)$ 演算・符号化・復号のスクラッチ実装と訂正能力の検証
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 巡回符号の理論 — 生成多項式と多項式による符号化 — BCH符号は巡回符号の特別な場合であり、生成多項式による符号化が共通します
- 線形ブロック符号の基礎 — 生成行列と検査行列 — 符号語・最小距離・誤り訂正能力の基本概念
- リード・ソロモン符号の理論と実装 — BCH符号を非二元体に一般化した符号で、シンドローム復号の流れが共通します
BCH符号とは — 「誤りの個数を指定して設計する」符号
具体的な数式に入る前に、BCH符号が何を実現したのかをイメージで掴んでおきましょう。
誤り訂正符号の世界では、「最小距離」$d$ という量が訂正能力を決めます。任意の2つの符号語が少なくとも $d$ ビット異なるように符号を設計すれば、$t = \lfloor (d-1)/2 \rfloor$ 個までの誤りを訂正できます。ところが、ハミング符号のような古典的な符号では、「最小距離をいくつにするか」を直接コントロールするのは簡単ではありませんでした。符号を作ってみて、後から最小距離を調べる、という後手の設計になりがちだったのです。
BCH符号の発想は逆転しています。「最小距離を $2t+1$ 以上にしたい」と先に決めてから、その条件を満たす符号を代数的に構成するのです。鍵となるのは次の事実です。
巡回符号の生成多項式 $g(x)$ が、ある体の元 $\alpha$ の連続する冪 $\alpha, \alpha^2, \dots, \alpha^{2t}$ をすべて根に持つように作れば、その符号の最小距離は必ず $2t+1$ 以上になる。
これをBCH限界と呼びます。「連続する $2t$ 個の根」という条件を満たすだけで、訂正能力 $t$ が代数的に保証される — これがBCH符号の核心です。この「連続する冪を根に持つ」という条件を扱うために、ガロア体という舞台が必要になります。
まずはその舞台を整えましょう。次のセクションでガロア体 $\mathrm{GF}(2^m)$ を構成します。
ガロア体 GF(2^m) の構成
なぜ有限体が必要なのか
通常の整数や実数は無限にありますが、ディジタル通信で扱うのは0と1のビットです。0と1の世界で「足し算」「掛け算」「割り算」がきちんと閉じて行える数の体系 — それが有限体（ガロア体）です。最も単純なものは2つの元 $\{0, 1\}$ からなる $\mathrm{GF}(2)$ で、加算はXOR（$1+1=0$）、乗算は通常のANDです。
しかしBCH符号では「連続する冪 $\alpha, \alpha^2, \dots$」を考える必要があり、$\mathrm{GF}(2)$ の中だけでは $\alpha$ のような豊かな元が足りません。そこで、$\mathrm{GF}(2)$ を拡大した $2^m$ 個の元を持つ体 $\mathrm{GF}(2^m)$ を使います。これは、係数が0/1の多項式を、ある「既約多項式」で割った余りとして元を定義することで作れます。
既約多項式と原始元
$\mathrm{GF}(2^m)$ を作るには、$\mathrm{GF}(2)$ 上で因数分解できない $m$ 次の既約多項式 $p(x)$ を一つ選びます。さらに、その根 $\alpha$ が体の0以外のすべての元を冪 $\alpha^0, \alpha^1, \dots, \alpha^{2^m-2}$ で生成できるとき、$p(x)$ を原始多項式、$\alpha$ を原始元と呼びます。
具体例として $m=4$、原始多項式 $p(x) = x^4 + x + 1$ を考えましょう。$\alpha$ を $p(x)$ の根とすると、$p(\alpha)=0$ すなわち
$$ \alpha^4 = \alpha + 1 $$
という関係が成り立ちます（$\mathrm{GF}(2)$ では $-1 = +1$ なので移項は単なる加算です）。この一本の関係式から、$\alpha$ の高い冪をすべて低い冪の組み合わせに書き直せます。たとえば $\alpha^5$ を計算してみましょう。$\alpha^5 = \alpha \cdot \alpha^4$ に上の関係を代入すると、
$$ \alpha^5 = \alpha \cdot \alpha^4 = \alpha(\alpha + 1) = \alpha^2 + \alpha $$
となります。同様に $\alpha^6 = \alpha \cdot \alpha^5 = \alpha^3 + \alpha^2$ です。このように $\alpha^0$ から $\alpha^{14}$ まで計算していくと、ちょうど15個の異なる非ゼロ元が得られ、$\alpha^{15} = 1$ に戻ります。$2^4 – 1 = 15$ なので、$\alpha$ は確かに非ゼロ元をすべて生成する原始元です。
元の二つの表現 — 冪表現とベクトル表現
$\mathrm{GF}(2^m)$ の各元には2つの顔があります。
- 冪表現: $\alpha^i$ という形。乗算が簡単（指数を足すだけ、$\alpha^i \cdot \alpha^j = \alpha^{(i+j) \bmod (2^m-1)}$）
- ベクトル（多項式）表現: $1, \alpha, \alpha^2, \dots, \alpha^{m-1}$ の線形結合の係数を並べたもの。加算が簡単（成分ごとのXOR）
たとえば $m=4$ では $\alpha^5 = \alpha^2 + \alpha$ なので、ベクトル表現は係数 $(\alpha^3, \alpha^2, \alpha^1, \alpha^0) = (0,1,1,0)$、すなわち 2進数で 0110 となります。乗算は冪表現で、加算はベクトル表現で行うのが効率的です。この相互変換のために、後で「指数表 (log table)」と「逆引き表 (antilog/exp table)」を作ります。
これでBCH符号を載せる舞台が整いました。次は、この体の上で生成多項式を設計します。
生成多項式の設計 — 連続する冪を根に持たせる
最小多項式
BCH符号の生成多項式 $g(x)$ は、$\mathrm{GF}(2)$ 上の多項式（係数が0/1）でなければなりません。一方で、$g(x)$ には $\alpha, \alpha^2, \dots, \alpha^{2t}$ という $\mathrm{GF}(2^m)$ の元を根に持たせたい。この「橋渡し」をするのが最小多項式です。
元 $\beta \in \mathrm{GF}(2^m)$ の最小多項式 $M_\beta(x)$ とは、$\beta$ を根に持つ $\mathrm{GF}(2)$ 係数の多項式のうち、次数が最小のモニック多項式です。重要な性質として、$\mathrm{GF}(2)$ 係数の多項式が $\beta$ を根に持つなら、自動的に $\beta^2, \beta^4, \beta^8, \dots$ も根に持ちます。これはフロベニウス写像（2乗写像）の性質によります。$\mathrm{GF}(2)$ 上では任意の多項式 $f(x) = \sum a_i x^i$（$a_i \in \{0,1\}$）について、
$$ f(x)^2 = \left(\sum_i a_i x^i\right)^2 = \sum_i a_i^2 x^{2i} = \sum_i a_i x^{2i} = f(x^2) $$
が成り立ちます。途中で $a_i^2 = a_i$（$a_i$ は0か1）を使い、また標数2では交差項 $2a_ia_j x^{i+j}$ が消えることを使いました。したがって $f(\beta)=0$ ならば $f(\beta^2) = f(\beta)^2 = 0$ となり、$\beta^2$ も根です。
このことから、ある元の最小多項式の根の集合は $\{\beta, \beta^2, \beta^4, \dots\}$ という形になります。この集合を共役類（cyclotomic coset、円分類）と呼びます。$\beta = \alpha^i$ のとき、共役類は指数の集合 $\{i, 2i, 4i, \dots \bmod (2^m-1)\}$ で表せます。
共役類の具体例
$m=4$（$2^m – 1 = 15$）で共役類を作ってみましょう。指数を2倍していき、15で割った余りを取ります。
- $C_1 = \{1, 2, 4, 8\}$（$16 \bmod 15 = 1$ で閉じる）
- $C_3 = \{3, 6, 12, 24\bmod 15=9\} = \{3, 6, 12, 9\}$
- $C_5 = \{5, 10, 20\bmod 15 = 5\} = \{5, 10\}$
- $C_7 = \{7, 14, 28\bmod 15 = 13, 26\bmod 15 = 11\} = \{7, 14, 13, 11\}$
各共役類に対応する最小多項式は、その類に属する指数の元をすべて根とする多項式です。たとえば $C_1$ に対応する最小多項式は
$$ M_1(x) = (x – \alpha)(x – \alpha^2)(x – \alpha^4)(x – \alpha^8) $$
で、展開すると $\mathrm{GF}(2)$ 係数の多項式 $x^4 + x + 1$ になります（実際これが原始多項式そのものです）。共役類が「自動的に巻き込まれる根」をまとめてくれるおかげで、$M_1(x)$ は確実に0/1係数になるのです。
生成多項式を作る
訂正能力 $t$ のBCH符号を作るには、$\alpha^1, \alpha^2, \dots, \alpha^{2t}$ の連続する $2t$ 個の冪をすべて根に持つ最小次数の生成多項式が必要です。連続する冪のそれぞれが属する共役類の最小多項式を集め、その最小公倍多項式 (lcm) を取ります。
$$ g(x) = \mathrm{lcm}\bigl(M_1(x), M_2(x), \dots, M_{2t}(x)\bigr) $$
ここで、$\alpha^2, \alpha^4, \dots$ は $\alpha$ と同じ共役類に属するため、最小多項式が重複します。lcmを取ることで重複が自然に排除され、必要十分な根だけを持つ $g(x)$ が得られます。
$m=4$、$t=2$ の例で作りましょう。連続する冪 $\alpha^1, \alpha^2, \alpha^3, \alpha^4$ を根に持たせます。これらが属する共役類は $C_1 = \{1,2,4,8\}$（$\alpha^1, \alpha^2, \alpha^4$ を含む）と $C_3 = \{3,6,12,9\}$（$\alpha^3$ を含む）です。したがって
$$ g(x) = \mathrm{lcm}(M_1, M_2, M_3, M_4) = M_1(x) \cdot M_3(x) $$
となります。$M_1(x) = x^4 + x + 1$、$M_3(x) = x^4 + x^3 + x^2 + x + 1$ なので、両者を $\mathrm{GF}(2)$ 上で掛け合わせると
$$ g(x) = (x^4 + x + 1)(x^4 + x^3 + x^2 + x + 1) = x^8 + x^7 + x^6 + x^4 + 1 $$
が得られます。$g(x)$ の次数は8で、これがパリティビット数 $n-k$ になります。符号長 $n = 2^m – 1 = 15$、情報長 $k = n – \deg g = 15 – 8 = 7$ で、$[15, 7]$ BCH符号、訂正能力 $t=2$ が完成します。
このように「連続する冪を根に持つ」という一行の方針から、$g(x)$ が機械的に決まります。しかし、なぜ連続する $2t$ 個の根があれば $t$ 個の誤りを訂正できるのでしょうか。それを保証するのが次のBCH限界です。
BCH限界 — 最小距離が 2t+1 以上である証明
主張と方針
BCH符号の心臓部はこの定理です。
$g(x)$ が連続する冪 $\alpha^b, \alpha^{b+1}, \dots, \alpha^{b+2t-1}$（$2t$ 個）を根に持つなら、この符号の最小距離 $d$ は $d \geq 2t+1$ である。
最小距離が $2t+1$ なら、訂正能力は $t = \lfloor (d-1)/2 \rfloor$ となり、$t$ 個の誤りが訂正できます。以下では設計上もっともよく使う $b=1$（狭義BCH符号）の場合で証明します。方針は背理法です。「重み（非ゼロ成分の数）が $2t$ 以下の非ゼロ符号語が存在する」と仮定し、それが矛盾を導くことを示します。
パリティ検査行列とヴァンデルモンド行列
符号語多項式 $c(x) = c_0 + c_1 x + \dots + c_{n-1}x^{n-1}$ は $g(x)$ の倍数なので、$g(x)$ の根である $\alpha^i$（$i = 1, \dots, 2t$）を代入すると0になります。
$$ c(\alpha^i) = \sum_{j=0}^{n-1} c_j (\alpha^i)^j = \sum_{j=0}^{n-1} c_j \alpha^{ij} = 0, \quad i = 1, 2, \dots, 2t $$
これを行列で書くと、パリティ検査行列 $\bm{H}$ が現れます。
$$ \bm{H} = \begin{pmatrix} \alpha^0 & \alpha^1 & \alpha^2 & \cdots & \alpha^{n-1} \\ \alpha^0 & \alpha^2 & \alpha^4 & \cdots & \alpha^{2(n-1)} \\ \vdots & \vdots & \vdots & & \vdots \\ \alpha^0 & \alpha^{2t} & \alpha^{2 \cdot 2t} & \cdots & \alpha^{2t(n-1)} \end{pmatrix} $$
任意の符号語ベクトル $\bm{c}$ は $\bm{H}\bm{c}^\top = \bm{0}$ を満たします。
背理法による証明
いま、重みが $w \leq 2t$ の非ゼロ符号語 $\bm{c}$ が存在したとします。非ゼロ成分の位置を $j_1, j_2, \dots, j_w$、その値を $c_{j_1}, \dots, c_{j_w}$（すべて非ゼロ）とします。$\bm{H}\bm{c}^\top = \bm{0}$ のうち、最初の $w$ 本の方程式（$i=1,\dots,w$）だけを取り出すと、
$$ \sum_{l=1}^{w} c_{j_l} (\alpha^{j_l})^i = 0, \quad i = 1, 2, \dots, w $$
となります。$\beta_l := \alpha^{j_l}$ と置き、$i$ で割り出した構造を見やすくするために行列形式で書くと、
$$ \begin{pmatrix} \beta_1 & \beta_2 & \cdots & \beta_w \\ \beta_1^2 & \beta_2^2 & \cdots & \beta_w^2 \\ \vdots & \vdots & & \vdots \\ \beta_1^w & \beta_2^w & \cdots & \beta_w^w \end{pmatrix} \begin{pmatrix} c_{j_1} \\ c_{j_2} \\ \vdots \\ c_{j_w} \end{pmatrix} = \bm{0} $$
各列から共通因子 $\beta_l$ をくくり出すと、係数行列は $\mathrm{diag}(\beta_1, \dots, \beta_w)$ とヴァンデルモンド行列の積に分解できます。
$$ \det = \left(\prod_{l=1}^{w}\beta_l\right) \cdot \det\begin{pmatrix} 1 & 1 & \cdots & 1 \\ \beta_1 & \beta_2 & \cdots & \beta_w \\ \vdots & \vdots & & \vdots \\ \beta_1^{w-1} & \beta_2^{w-1} & \cdots & \beta_w^{w-1} \end{pmatrix} $$
ヴァンデルモンド行列式は $\prod_{l 行列式が非ゼロということは、この連立方程式の係数行列は正則であり、解は自明解 $c_{j_1} = \dots = c_{j_w} = 0$ しかありません。これは「$c_{j_l}$ がすべて非ゼロ」という仮定に矛盾します。よって重み $2t$ 以下の非ゼロ符号語は存在せず、最小距離は $d \geq 2t+1$ が示されました。 この証明の美しさは、「連続する冪」がヴァンデルモンド構造を生み、その正則性が訂正能力を保証する、という点に集約されています。設計距離 $\delta = 2t+1$ を達成する保証が、純粋に代数的に得られたわけです。次は、実際に誤りが乗った受信語からその誤りを見つけ出す復号の話に進みます。 送信した符号語多項式を $c(x)$、通信路で加わった誤りを $e(x)$ とすると、受信語は $$
r(x) = c(x) + e(x)
$$ です。誤り多項式 $e(x) = \sum_l Y_l x^{j_l}$ は、誤りが起きた位置 $j_l$ に値 $Y_l$ を持ちます（二元符号では $Y_l = 1$ ですが、一般的に書いておきます）。復号の目標は、$r(x)$ から $e(x)$ を特定し、$c(x) = r(x) – e(x)$ を回復することです。 ここで、受信語に $g(x)$ の根 $\alpha^i$ を代入してみましょう。$c(\alpha^i) = 0$（符号語だから）なので、 $$
S_i := r(\alpha^i) = c(\alpha^i) + e(\alpha^i) = e(\alpha^i), \quad i = 1, 2, \dots, 2t
$$ となります。これがシンドローム $S_i$ です。シンドロームは受信語から直接計算できる一方で、その値は誤り $e(x)$ だけで決まります。つまり、シンドロームは「誤りの指紋」なのです。誤りがなければ $e(x)=0$ なので全シンドロームが0になり、これが誤り検出の判定にもなります。 誤り位置を $X_l := \alpha^{j_l}$（誤り位置数、error locator）、誤り値を $Y_l$ とすると、シンドロームは次のように書けます。 $$
S_i = e(\alpha^i) = \sum_{l=1}^{\nu} Y_l (\alpha^{j_l})^i = \sum_{l=1}^{\nu} Y_l X_l^i, \quad i = 1, \dots, 2t
$$ ここで $\nu$ は実際に起きた誤りの個数（$\nu \le t$ なら訂正可能）です。これは未知数 $X_l, Y_l$ に関する $2t$ 本の非線形連立方程式です。$X_l$ について非線形なので、直接解くのは困難です。そこで、まず誤り位置 $X_l$ だけを取り出すための「誤り位置多項式」という道具を導入します。 シンドロームという指紋が手に入りました。次に、この指紋から誤りの「位置」を読み解く鍵を作ります。 誤り位置数 $X_1, \dots, X_\nu$ を根に持つ多項式を考えるのは自然な発想です。ただし慣習として、根が $X_l^{-1}$（逆数）になるように定義した誤り位置多項式 $\sigma(x)$ を使います。 $$
\sigma(x) = \prod_{l=1}^{\nu}(1 – X_l x) = 1 + \sigma_1 x + \sigma_2 x^2 + \dots + \sigma_\nu x^\nu
$$ この定義では $\sigma(X_l^{-1}) = 0$、つまり誤り位置数の逆数 $X_l^{-1}$ が根になります。後でChien探索により、どの $\alpha^{-j}$ が根かを総当たりで調べ、誤り位置 $j$ を特定します。 $\sigma(x)$ の係数 $\sigma_1, \dots, \sigma_\nu$ とシンドローム $S_i$ の間には、線形の関係があります。これを導きましょう。$\sigma(X_l^{-1})=0$ より、各 $l$ について $$
1 + \sigma_1 X_l^{-1} + \sigma_2 X_l^{-2} + \dots + \sigma_\nu X_l^{-\nu} = 0
$$ が成り立ちます。両辺に $Y_l X_l^{i+\nu}$ を掛けると、 $$
Y_l X_l^{i+\nu} + \sigma_1 Y_l X_l^{i+\nu-1} + \dots + \sigma_\nu Y_l X_l^{i} = 0
$$ となります。これを $l = 1, \dots, \nu$ について総和すると、各項が $\sum_l Y_l X_l^{m} = S_m$ の形に化けます。実際、$\sum_l Y_l X_l^{i+\nu} = S_{i+\nu}$、$\sum_l Y_l X_l^{i+\nu-1} = S_{i+\nu-1}$、… となるので、 $$
S_{i+\nu} + \sigma_1 S_{i+\nu-1} + \sigma_2 S_{i+\nu-2} + \dots + \sigma_\nu S_i = 0
$$ が得られます。整理すると、未知の誤り個数 $\nu$ に対し、 $$
S_{i+\nu} = -\bigl(\sigma_1 S_{i+\nu-1} + \sigma_2 S_{i+\nu-2} + \dots + \sigma_\nu S_i\bigr), \quad i = 1, 2, \dots, \nu
$$ という漸化式になります。これは「シンドローム列が次数 $\nu$ の線形漸化式（線形フィードバックシフトレジスタ, LFSR）で生成される」ことを意味し、その漸化式の係数こそが $\sigma_1, \dots, \sigma_\nu$ です。これをキー方程式と呼びます。 $\nu$ が分かっていれば、これは $\sigma_i$ に関する線形連立方程式（行列形式ではシンドロームからなるトープリッツ行列）なので、ガウス消去で解けます。しかし $\nu$ 自体が未知であることが多く、また効率も重要です。この「最短のLFSRを見つける」問題を $O(t^2)$ で解くのが、次のBerlekamp-Massey法です。 シンドロームと誤り位置多項式の橋渡しができました。次は、それを効率的に解くアルゴリズムです。 Berlekamp-Massey法（BM法）は、与えられたシンドローム列 $S_1, S_2, \dots, S_{2t}$ を生成する最短の線形漸化式（LFSR）を求めるアルゴリズムです。直感的には、シンドロームを1つずつ順番に「予測」しながら、予測が外れたら漸化式を修正していく、という適応的な手続きです。予測の外れ具合を差分 (discrepancy) $\Delta$ と呼び、これが非ゼロのときだけ多項式を更新します。 このアプローチが正しい誤り位置多項式に収束する理由は、キー方程式が「シンドローム列を生成するLFSR」と「誤り位置多項式」が同一であることを保証しているからです。最短のLFSRを見つければ、それが最小個数の誤りに対応する $\sigma(x)$ になります。 記号を整理します。$\sigma(x)$ を現在の誤り位置多項式の候補、$L$ をその次数（現在のLFSRの長さ）、$B(x)$ を直前に更新したときの補正多項式とします。$2t$ 回のステップを回します。 ステップ4の $L \leftarrow n+1-L$ という長さの更新が、最短LFSRを保証するMasseyの定理の核心部分です。二元体 $\mathrm{GF}(2)$ では $-1 = +1$ なので減算は加算（XOR）になりますが、誤り値が体の一般の元になるリード・ソロモン符号でも同じ枠組みが使えるよう、ここでは一般の体演算で書いています。 $2t$ ステップ後に得られた $\sigma(x)$ の次数 $L$ が、推定された誤り個数 $\nu$ です。もし $L > t$ なら、訂正能力を超える誤りが起きたと判断して復号失敗を宣言します。 得られた $\sigma(x)$ は誤り位置数の逆数を根に持ちます。次は、その根を実際に探し出すChien探索です。 $\sigma(x)$ の根は $X_l^{-1} = \alpha^{-j_l}$ の形をしているので、$x$ にすべての非ゼロ元 $\alpha^0, \alpha^1, \dots, \alpha^{n-1}$ を代入し、$\sigma(\alpha^{-j}) = 0$ となる $j$ を探せば、誤り位置 $j$ が分かります。これがChien探索です。$n$ 個すべてを試す総当たりですが、$\mathrm{GF}(2^m)$ の元は有限なので必ず終わります。 具体的には、各位置 $j = 0, 1, \dots, n-1$ について $$
\sigma(\alpha^{-j}) = 1 + \sigma_1 \alpha^{-j} + \sigma_2 \alpha^{-2j} + \dots + \sigma_\nu \alpha^{-\nu j}
$$ を計算し、これが0になれば「位置 $j$ に誤りがある」と判定します。実装上は $\alpha^{-(j+1)} = \alpha^{-j}\cdot\alpha^{-1}$ という関係を使い、各項を1ステップずつ更新していくことで乗算回数を減らせます（これがハードウェアでChien探索が好まれる理由です）。 二元BCH符号では、誤りが起きた位置のビットを反転（$Y_l = 1$）するだけなので、位置さえ分かれば訂正は完了です。一方、リード・ソロモン符号のように誤り値が体の一般の元になる場合は、Forney（フォーニー）のアルゴリズムで誤り値を計算します。誤り評価多項式 $\Omega(x) = S(x)\sigma(x) \bmod x^{2t}$ を使い、 $$
Y_l = -\frac{\Omega(X_l^{-1})}{\sigma'(X_l^{-1})}
$$ で求めます（$\sigma’$ は形式微分）。本記事の主眼である二元BCH符号では $Y_l=1$ なので、Chien探索で位置を見つけ、そのビットを反転すれば復号完了です。 ここまでで、シンドローム計算 → BM法で $\sigma(x)$ → Chien探索で位置特定、という復号の全工程が揃いました。いよいよPythonで一気通貫に実装します。 まず、$\mathrm{GF}(2^m)$ の乗算・除算を高速に行うための指数表（exp）と対数表（log）を構築します。原始多項式から $\alpha$ の冪を順に計算し、ビットがあふれたら原始多項式で還元します。 このクラスでは、左シフト（$\times\alpha$）でビットが $m$ 桁目に達したら原始多項式でXOR還元する、という $\alpha^4 = \alpha+1$ の関係をそのままコード化しています。 構築したテーブルが正しいか、$m=4$、原始多項式 $x^4+x+1$（ビット表現 出力を見ると、 次に、連続する冪 $\alpha^1, \dots, \alpha^{2t}$ を根に持つ生成多項式を、$\mathrm{GF}(2)$ 上で $(x-\alpha^i)$ を順に掛けて構成します。共役類の重複は、すでに根になっている冪をスキップすることで自然に排除します。 出力では生成多項式の係数が 巡回符号の標準的な系統符号化を行います。情報多項式 $u(x)$ を $x^{n-k}$ 倍してから $g(x)$ で割った余り（パリティ）を付加します。これにより符号語 $c(x) = u(x)x^{n-k} + \bigl(u(x)x^{n-k} \bmod g(x)\bigr)$ は $g(x)$ の倍数になります。 出力では、符号化した符号語のシンドロームがすべて0になります。これは $c(\alpha^i)=0$、すなわち符号語が確かに生成多項式の倍数（=正しい符号語）であることを意味します。系統符号化なので、符号語の後半 $k$ ビットには情報ビットがそのまま現れている点も確認できます。 いよいよ復号の核心です。受信語にシンドローム計算、Berlekamp-Massey法、Chien探索を適用して誤り位置を特定し、訂正します。まずBM法を実装します。 BM法の実装は、先に述べたアルゴリズムの手順をそのまま写したものです。差分 続いてChien探索と全体の復号関数を実装し、誤りを注入してテストします。 出力では「訂正したビット数: 2」「復号成功: True」となり、注入した2か所の誤りが正しく特定・訂正されたことが分かります。BM法が次数2の誤り位置多項式を導き、Chien探索がその根から位置3と11を見つけ、ビット反転で元の符号語が完全に復元されています。理論で構築した復号の流れが、そのまま動いていることが確認できます。 最後に、「$t=2$ までは確実に訂正でき、$t+1=3$ 個の誤りでは訂正に失敗（または誤訂正）する」という設計上の限界を、ランダムな誤りパターンで統計的に検証します。 このシミュレーション結果から、BCH限界が保証する訂正能力がはっきりと読み取れます。 訂正能力をさらに上げたい場合は $t$ を大きくして生成多項式の次数を上げればよく（その分 $k$ が減って符号化率が下がる）、より長い符号が必要なら $m$ を大きくして $n=2^m-1$ を伸ばせます。この設計の自由度と明快さが、BCH符号が半世紀にわたり使われ続けている理由です。 本記事では、BCH符号の設計から復号までを、ガロア体の代数構造に基づいて一貫して解説しました。 BCH符号は、線形ブロック符号・巡回符号の理論が、有限体という代数の舞台の上で最も美しく結実した例です。ここで学んだシンドローム復号・BM法・Chien探索の枠組みは、誤り値の計算まで含めて非二元体に一般化すれば、そのままリード・ソロモン符号へと拡張されます。符号理論の「次の一歩」として、ぜひ関連記事に進んでみてください。 次のステップとして、以下の記事も参考にしてください。復号の第一歩 — シンドロームの計算
受信語と誤りの分離
シンドロームの定義
誤り位置多項式とキー方程式
誤り位置多項式の定義
キー方程式（シンドロームと係数の関係）
Berlekamp-Massey 法 — 最短のLFSRを見つける
アルゴリズムの直感
アルゴリズムの手順
Chien 探索 — 誤り位置多項式の根を見つける
総当たりで根を探す
誤り値の決定
Pythonでの実装
GF(2^m) の演算テーブルの構築
import numpy as np
class GF2m:
"""GF(2^m) の演算（exp/log テーブルによる）"""
def __init__(self, m, prim_poly):
self.m = m
self.n = (1 << m) - 1 # 非ゼロ元の個数 = 2^m - 1
self.prim = prim_poly # 原始多項式（整数のビット表現）
self.exp = [0] * (2 * self.n) # exp[i] = alpha^i
self.log = [0] * (self.n + 1) # log[a] = i (a = alpha^i)
x = 1
for i in range(self.n):
self.exp[i] = x
self.log[x] = i
x <<= 1 # x に alpha を掛ける（左シフト）
if x & (1 << m): # m次の項が立ったら還元
x ^= self.prim
# 折り返し（指数の加算で範囲外に出ても引けるよう倍にしておく）
for i in range(self.n, 2 * self.n):
self.exp[i] = self.exp[i - self.n]
def mul(self, a, b):
if a == 0 or b == 0:
return 0
return self.exp[self.log[a] + self.log[b]]
def div(self, a, b):
if a == 0:
return 0
return self.exp[(self.log[a] - self.log[b]) % self.n]
def inv(self, a):
return self.exp[(self.n - self.log[a]) % self.n]
def pow_alpha(self, i):
return self.exp[i % self.n]
exp 表を2倍の長さで持っておくことで、乗算 log[a]+log[b] が範囲を超えても余計な剰余演算なしに引けるようにしている点が実装上の工夫です。テーブルの確認
0b10011 = 19）で確認します。gf = GF2m(4, 0b10011) # x^4 + x + 1
# alpha^i の多項式（ビット）表現を表示
for i in [0, 1, 4, 5, 6, 14]:
print(f"alpha^{i:2d} = {gf.exp[i]:04b}")
print("alpha^15 ==", gf.exp[15], "(should wrap to alpha^0 = 1)")
print("alpha^5 * alpha^7 = alpha^? ->", gf.log[gf.mul(gf.exp[5], gf.exp[7])])
alpha^4 = 0011（$\alpha+1$）、alpha^5 = 0110（$\alpha^2+\alpha$）となり、手計算で求めた $\alpha^4=\alpha+1$、$\alpha^5=\alpha^2+\alpha$ と一致します。また $\alpha^5 \cdot \alpha^7 = \alpha^{12}$ となり、指数の加算（$5+7=12$）が乗算に対応していることが確認できます。$\alpha^{15}$ が $\alpha^0=1$ に巻き戻ることも、$\alpha$ が周期15の原始元である証拠です。生成多項式の構成
def gf_poly_mul(p, q, gf):
"""GF(2^m)係数の多項式の積（係数は整数のビット表現）"""
r = [0] * (len(p) + len(q) - 1)
for i, a in enumerate(p):
for j, b in enumerate(q):
r[i + j] ^= gf.mul(a, b)
return r
def bch_generator(gf, t):
"""連続冪 alpha^1..alpha^(2t) を根に持つ生成多項式 g(x) を作る"""
g = [1] # g(x) = 1 から開始
roots = set()
for i in range(1, 2 * t + 1):
ai = gf.pow_alpha(i)
if ai in roots:
continue # すでに含まれる根（共役）はスキップ
# この根の共役 alpha^(i*2^k) をすべて (x - r) として掛け込む
r = ai
while r not in roots:
roots.add(r)
# (x - r) = x + r を掛ける（GF(2)なので -=+）
g = gf_poly_mul(g, [r, 1], gf)
r = gf.mul(r, r) # 2乗してフロベニウス共役へ
return g
gf = GF2m(4, 0b10011)
t = 2
g = bch_generator(gf, t)
print("生成多項式の係数 (低次→高次):", g)
print("次数 deg g =", len(g) - 1)
n = gf.n
k = n - (len(g) - 1)
print(f"[n, k, t] = [{n}, {k}, {t}]")
[1, 0, 0, 0, 1, 0, 1, 1, 1]（低次から $1 + x^4 + x^6 + x^7 + x^8$）となり、これは手計算した $g(x) = x^8 + x^7 + x^6 + x^4 + 1$ と完全に一致します。次数は8、したがって $[n,k,t]=[15,7,2]$ の二元BCH符号が得られたことが確認できます。共役のスキップが効いて、無駄な根を増やさず最小次数の $g(x)$ になっています。符号化
def poly_mod2(dividend, divisor):
"""GF(2)係数多項式の剰余（係数は0/1のリスト、高次が末尾）"""
d = dividend[:]
dl = len(divisor)
for i in range(len(d) - 1, dl - 2, -1):
if d[i]:
for j in range(dl):
d[i - (dl - 1) + j] ^= divisor[j]
return d[:dl - 1] # 余り（次数 < deg divisor）
def bch_encode(info_bits, g, n):
"""系統的BCH符号化。info_bits は長さ k のリスト（0/1）"""
k = n - (len(g) - 1)
# u(x) * x^(n-k) を表す係数列（低次→高次）
shifted = [0] * (n - k) + list(info_bits)
# GF(2)で g(x) で割った余りを計算
g_bits = [c & 1 for c in g] # 生成多項式の係数は0/1
parity = poly_mod2(shifted, g_bits)
codeword = parity + list(info_bits)
return codeword
np.random.seed(0)
k = n - (len(g) - 1)
info = list(np.random.randint(0, 2, size=k))
codeword = bch_encode(info, g, n)
print("情報ビット :", info)
print("符号語 :", codeword, "長さ", len(codeword))
# 符号語が g(x) の倍数か（= 全シンドローム0か）を確認
def syndromes(recv, gf, t):
S = []
for i in range(1, 2 * t + 1):
acc = 0
for j, b in enumerate(recv):
if b:
acc ^= gf.pow_alpha((i * j) % gf.n)
S.append(acc)
return S
print("符号語のシンドローム:", syndromes(codeword, gf, t), "(全0なら正しい符号語)")
誤り注入と復号（BM法 + Chien探索）
def berlekamp_massey(S, gf, t):
"""シンドローム列 S から誤り位置多項式 sigma(x) を求める"""
sigma = [1] # sigma(x) = 1
B = [1]
L = 0 # 現在のLFSR長
m = 1
b = 1 # 直前の非ゼロ差分
for n_idx in range(2 * t):
# 差分 Delta の計算
delta = S[n_idx]
for i in range(1, L + 1):
delta ^= gf.mul(sigma[i], S[n_idx - i])
if delta == 0:
m += 1
elif 2 * L <= n_idx:
T = sigma[:] # 一時保存
coef = gf.div(delta, b)
# sigma -= coef * x^m * B
shifted = [0] * m + [gf.mul(coef, bb) for bb in B]
sigma = poly_add(sigma, shifted, gf)
L = n_idx + 1 - L
B = T
b = delta
m = 1
else:
coef = gf.div(delta, b)
shifted = [0] * m + [gf.mul(coef, bb) for bb in B]
sigma = poly_add(sigma, shifted, gf)
m += 1
return sigma, L
def poly_add(p, q, gf):
"""GF(2^m)係数多項式の加算（XOR）"""
r = [0] * max(len(p), len(q))
for i, a in enumerate(p):
r[i] ^= a
for i, a in enumerate(q):
r[i] ^= a
return r
delta をシンドロームと現在の sigma から計算し、delta が非ゼロのときだけ補正多項式 B を $x^m$ シフトして加える、という流れになっています。2*L <= n_idx の分岐がLFSR長を更新する場合に対応します。def chien_search(sigma, gf, n):
"""sigma(x) の根 alpha^{-j} を探し、誤り位置 j のリストを返す"""
positions = []
for j in range(n):
# sigma(alpha^{-j}) を評価
x_inv = gf.pow_alpha((gf.n - j) % gf.n) # alpha^{-j}
val = 0
xp = 1
for c in sigma:
val ^= gf.mul(c, xp)
xp = gf.mul(xp, x_inv)
if val == 0:
positions.append(j)
return positions
def bch_decode(recv, gf, t):
"""二元BCH復号: シンドローム -> BM法 -> Chien探索 -> ビット反転"""
S = syndromes(recv, gf, t)
if all(s == 0 for s in S):
return recv[:], 0 # 誤りなし
sigma, L = berlekamp_massey(S, gf, t)
if L > t:
raise ValueError("訂正能力を超える誤り（復号失敗）")
err_pos = chien_search(sigma, gf, gf.n)
if len(err_pos) != L:
raise ValueError("根の数が次数と不一致（復号失敗）")
corrected = recv[:]
for j in err_pos:
corrected[j] ^= 1 # 二元なのでビット反転
return corrected, len(err_pos)
# t=2 個までの誤りを注入して訂正を確認
np.random.seed(1)
recv = codeword[:]
error_positions = [3, 11] # 2か所に誤りを注入
for j in error_positions:
recv[j] ^= 1
print("注入した誤り位置:", error_positions)
decoded, num_corrected = bch_decode(recv, gf, t)
print("訂正したビット数:", num_corrected)
print("復号成功:", decoded == codeword)
訂正能力 t の限界の検証
import numpy as np
def trial(gf, g, n, t, num_errors, n_trials=2000, seed=2):
"""num_errors 個のランダム誤りに対する正しい復号の成功率を測る"""
rng = np.random.default_rng(seed)
k = n - (len(g) - 1)
success = 0
for _ in range(n_trials):
info = list(rng.integers(0, 2, size=k))
cw = bch_encode(info, g, n)
recv = cw[:]
pos = rng.choice(n, size=num_errors, replace=False)
for j in pos:
recv[j] ^= 1
try:
dec, _ = bch_decode(recv, gf, t)
if dec == cw:
success += 1
except ValueError:
pass # 復号失敗として数えない
return success / n_trials
gf = GF2m(4, 0b10011)
t = 2
g = bch_generator(gf, t)
n = gf.n
for ne in [0, 1, 2, 3]:
rate = trial(gf, g, n, t, ne)
print(f"誤り {ne} 個: 正しく復号できた割合 = {rate:.3f}")
まとめ