BCH符号 — ハミング符号とリード・ソロモン符号をつなぐ一般化

この回で学ぶこと

前回学んだハミング符号は、最小限の検査ビットで1ビットの誤りを確実に訂正できる、非常に美しい符号でした。しかしそこには明確な限界があります。ハミング符号は1ビット誤りしか訂正できません。 2ビット以上の誤りが同時に起きると、訂正はおろか、パターンによっては誤り自体を見逃してしまいます。ゴレイ符号($(23,12,7)$)のように3ビット誤り訂正を実現する符号も存在しますが、それは特定のパラメータでしか成立しない、いわば「奇跡的な」構成であり、「4ビット訂正したいなら、5ビット訂正したいなら、どう作ればよいか」という問いに体系的に答えてくれるものではありませんでした。

この回で扱う**BCH符号(Bose-Chaudhuri-Hocquenghem符号)**は、まさにこの問いに答える符号族です。ハミング符号を「訂正したい誤りビット数 $t$ を先に決め、それを保証する符号を代数的なレシピで機械的に構成する」という枠組みへと一般化したもので、$t=1$ のときにはハミング符号そのものに一致します。

そしてこの回のもう一つの山場は、前回学んだリード・ソロモン(RS)符号が、実はこのBCH符号の構成法を「2値(ビット)」から「多値(シンボル)」へ拡張しただけの、特別な場合にすぎないことを明らかにする点です。ハミング符号・BCH符号・RS符号は、バラバラの3つの符号ではなく、同じ代数的な設計図の上に並ぶ一つの系譜だったことが、この回を通じて見えてきます。

直感的な導入: 「1ビットしか直せない」を超えるには

ハミング符号がなぜ1ビットしか訂正できないかを思い出しましょう。検査行列 $H$ の列に、$0$ でない相異なるベクトルをすべて割り当てることで、シンドローム $Hr^T$ から誤り位置をただ1通りに特定できる、というのがハミング符号の仕組みでした。この構成は「1個の誤り」を識別する分だけの情報しか検査ビットに詰め込んでおらず、2個以上の誤りが重なるとシンドロームが別の誤りパターンと衝突してしまい、原理的に見分けがつかなくなります。

ゴレイ符号は、極めて特殊な組合せ論的偶然によって $(23,12)$ という特定のパラメータで3ビット訂正を実現しますが、これは「たまたまうまくいく」設計であり、$t=4,5,6,\dots$ と訂正能力を上げたいときに一般化できる方法ではありません。

BCH符号のアイデアは、この壁を代数的に突破します。鍵になるのは、RS符号の回で見た「符号語多項式に、あらかじめ指定した点を根として持たせる」という発想です。RS符号では評価点(符号語の各シンボル)自体がガロア体の元でしたが、BCH符号ではまず2値の符号として出発し、符号語のビット列を多項式の係数とみなした上で、その多項式がより大きな拡大体の中のいくつかの点を根に持つように設計します。根の個数(正確には根にする点の並び方)をコントロールすることで、訂正できる誤りビット数 $t$ を狙い通りに設計できる——これがBCH符号の骨子です。

数学的準備: 拡大体の元の「最小多項式」

RS符号では、符号語のシンボルも、根として使う評価点 $\alpha^i$ も、同じガロア体 $GF(2^m)$ の元でした。ところがBCH符号(の最も基本的な、2値の場合)では事情が違います。符号語のビット自体は $GF(2)=\{0,1\}$ の元なのに、根として使いたい点 $\alpha^i$ は、より大きな拡大体 $GF(2^m)$ の元です。生成多項式 $g(x)$ の係数を $GF(2)$ に留めたまま、根だけを拡大体に持たせるにはどうすればよいでしょうか。ここで必要になるのが**最小多項式(minimal polynomial)**という概念です。

$\beta \in GF(2^m)$ に対して、$\beta$ を根に持つ($GF(2)$ を係数とする)モニック多項式のうち、次数が最小のものを $\beta$ の最小多項式と呼び、$\phi_\beta(x)$ と書きます。

$GF(2^m)$ の標数が2であることから、$x \mapsto x^2$ という写像(フロベニウス写像)は体の自己同型になります。これを $\beta$ に繰り返し施した

$$\beta,\ \beta^2,\ \beta^4,\ \beta^8,\ \dots$$

を $\beta$ の共役元と呼びます。$\beta=\alpha^i$($\alpha$ は原始元、$n=2^m-1$)の場合、共役元の指数は $i, 2i, 4i, 8i, \dots \pmod n$ と倍々に増えていき、いずれ最初の $i$ に戻ってきます。この指数の集合を円分剰余類(cyclotomic coset) $C_i = \{i, 2i, 4i, \dots\} \bmod n$ と呼びます。最小多項式は、この共役元すべてを根とする積として得られます。

$$\phi_{\alpha^i}(x) = \prod_{j \in C_i} (x - \alpha^j)$$

この積を展開すると、係数は共役元たちの基本対称式になりますが、フロベニウス写像で共役元の集合全体が自分自身に置き換わる(不変である)ため、係数もフロベニウス写像で不変、すなわち固定体 $GF(2)$ の元になることが分かります。こうして「根は拡大体 $GF(2^m)$ の元だが、係数は $GF(2)$ に収まる」多項式が手に入ります。$\phi_{\alpha^i}(x)$ の次数は $|C_i|$ で、これは常に $m$ の約数です。

BCH符号の代数的構成

準備が整ったので、BCH符号を定義します。訂正したい誤りビット数を $t$ とし、拡大体 $GF(2^m)$ の原始元 $\alpha$($n=2^m-1$)を選びます。生成多項式を、$\alpha^1, \alpha^2, \dots, \alpha^{2t}$ それぞれの最小多項式の**最小公倍多項式(LCM)**として定義します。

$$g(x) = \mathrm{lcm}\big(\phi_{\alpha^1}(x),\, \phi_{\alpha^2}(x),\, \dots,\, \phi_{\alpha^{2t}}(x)\big)$$

$GF(2)$ 係数の多項式どうしのLCMはやはり $GF(2)$ 係数の多項式なので、$g(x)$ は正真正銘の2値符号の生成多項式として使えます。しかも構成から明らかに、$g(x)$ は $\alpha^1,\alpha^2,\dots,\alpha^{2t}$ をすべて根に持ちます。符号語は(RS符号のときと同様に)$g(x)$ の倍数となる次数 $n-1$以下の多項式全体として定義され、長さ $n=2^m-1$、次元 $k = n - \deg g(x)$ の符号 $\mathrm{BCH}(n,k)$ が得られます。

ここで重要な効率化が起きます。共役元の性質上、$C_1$ は $1,2,4,8,\dots$ という円分剰余類として $\alpha^1$ と $\alpha^2$ と $\alpha^4$ など複数の指数を一度にカバーします。つまり $2t$ 個の根 $\alpha^1,\dots,\alpha^{2t}$ を指定しても、実際に異なる最小多項式が必要になるのはその重複を除いた円分剰余類の代表元の数だけで、素朴に $2t$ 個の独立な検査条件を並べるよりずっと少ない検査ビット数(検査ビット総数は高々 $mt$ 程度)で済みます。

具体例: $\mathrm{BCH}(15,7)$、2誤り訂正符号

$m=4$、$GF(16)$、原始多項式 $p(x)=x^4+x+1$($\alpha$ はその根)として、$t=2$(2ビット誤り訂正)を狙う例を見てみましょう。$n=2^4-1=15$ です。$\bmod\ 15$ の円分剰余類を列挙すると、

$$C_1=\{1,2,4,8\}, \quad C_3=\{3,6,9,12\}, \quad C_5=\{5,10\}, \quad C_7=\{7,11,13,14\}$$

designed distance $2t+1=5$ を得るには $\alpha^1,\alpha^2,\alpha^3,\alpha^4$ をすべて根に持たせる必要があります。$1,2,4$ は $C_1$ に、$3$ は $C_3$ に含まれるので、必要なのは $\phi_{\alpha^1}(x)$ と $\phi_{\alpha^3}(x)$ の2つだけです。$\phi_{\alpha^1}(x)$ は($\alpha$ が原始元なので)原始多項式そのもの $x^4+x+1$ に一致し、$\phi_{\alpha^3}(x) = x^4+x^3+x^2+x+1$ であることが知られています(いずれも $GF(2^3)$ の場合と同じ要領で、原始多項式による剰余計算から求まります)。したがって、

$$g(x) = (x^4+x+1)(x^4+x^3+x^2+x+1) = x^8+x^7+x^6+x^4+1$$

$\deg g(x) = 8$ なので、$k = 15-8=7$。こうして得られる $\mathrm{BCH}(15,7)$ 符号は、最小距離 $d_{\min}=5$、すなわち $t=2$ ビット誤り訂正符号です。8個の検査ビットだけで、ハミング符号(1ビット訂正)を上回る2ビット訂正能力を実現していることが分かります。

$t=1$ の特別な場合: ハミング符号

この構成で $t=1$ とすると、必要な最小多項式は $\phi_{\alpha^1}(x)$ だけ、すなわち $g(x)$ は原始多項式そのもの(次数 $m$)になります。このとき $k = n - m = (2^m-1) - m$ となり、これはまさに前回学んだハミング符号 $(2^m-1,\, 2^m-1-m)$ のパラメータそのものです。ハミング符号は「BCH符号の $t=1$ の場合」だったというわけです。前回、天下り的に与えられていた検査行列の構成が、ここで「原始元の最小多項式を根に持たせる」という代数的な必然性から導けたことになります。

BCH限界: 設計距離を保証する

BCH符号がなぜ本当に $t$ 個の誤りビットを訂正できるのか、その核心にある定理が**BCH限界(BCH bound)**です。

$g(x)$ が $d-1$ 個の連続したべき $\alpha^b, \alpha^{b+1}, \dots, \alpha^{b+d-2}$ をすべて根に持つならば、この符号の最小距離は $d_{\min} \ge d$ を満たす。

狭義BCH符号($b=1$、$d=2t+1$)では $d_{\min} \ge 2t+1$ となり、有界距離復号によって $t = \lfloor (d_{\min}-1)/2 \rfloor \ge t$ 個の誤りが確実に訂正できることが保証されます。

証明の骨子を見ておきましょう。符号語 $c=(c_0,\dots,c_{n-1})$ が重み $w$ の非零符号語で、非零位置が $i_1,\dots,i_w$ だとします。$c(x)$ が $\alpha^1,\dots,\alpha^{2t}$ を根に持つことから、

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

もし $w \le 2t$ なら、この式のうち最初の $w$ 本($j=1,\dots,w$)だけを取り出して、未知数 $c_{i_1},\dots,c_{i_w}$ についての連立方程式とみなすことができます。係数行列は

$$\big[(\alpha^{i_l})^j\big]_{j=1,\dots,w;\ l=1,\dots,w}$$

という形で、各行を $\alpha^{i_l}$ で割り出すと、残りはヴァンデルモンド行列そのものです。$\alpha^{i_1},\dots,\alpha^{i_w}$ は(位置が相異なるので)すべて相異なる非零元だから、この行列の行列式は非零です。したがって連立方程式の解は $c_{i_1}=\cdots=c_{i_w}=0$ しかあり得ませんが、これは $c_{i_l}$ が非零位置であるという前提に矛盾します。ゆえに $w \le 2t$ という仮定は成り立たず、$w \ge 2t+1$ が結論されます。

RS符号のシングルトン限界の証明が「多項式の根の個数は次数を超えない」という根の側からの議論だったのに対し、BCH限界の証明は検査行列の列ベクトルの線形独立性(ヴァンデルモンド行列の非退化性)から距離を保証するという、視点の異なる議論になっている点に注目してください。ただし重要な違いとして、BCH限界はあくまで下界であり、RS符号のように必ず等号($d_{\min}=n-k+1$、MDS性)が成り立つわけではありません。実際の最小距離が設計距離 $2t+1$ より大きくなる(検査ビットを「使いすぎている」)BCH符号も珍しくありません。

復号アルゴリズムの概要: シンドロームから誤り位置多項式へ

BCH符号の復号は、RS符号の回で概観した手順と骨格を共有しますが、2値符号ならではの単純化があります。受信語を $r(x)=c(x)+e(x)$ とし、シンドロームを

$$S_j = r(\alpha^j) = e(\alpha^j), \qquad j=1,\dots,2t$$

として計算します(拡大体 $GF(2^m)$ 上の演算になる点に注意)。誤りが $v$ 個($v \le t$)の位置 $i_1,\dots,i_v$ で起きたとすると、$S_j = \sum_{l=1}^{v} (\alpha^{i_l})^j$ という「べき乗和」の形になります。

ここで大事なのは、これらのべき乗和 $S_1,S_2,\dots$ が、誤り位置多項式

$$\sigma(x) = \prod_{l=1}^{v}\big(1-\alpha^{i_l}x\big) = 1+\sigma_1 x + \cdots + \sigma_v x^v$$

の係数 $\sigma_1,\dots,\sigma_v$ を係数とする線形漸化式を満たすという事実です(ニュートンの恒等式が、べき乗和と基本対称式=誤り位置多項式の係数を結びつけます)。つまり「シンドローム列 $S_1,S_2,\dots,S_{2t}$ を生成する、次数最小の線形帰還シフトレジスタ(LFSR)を見つける」問題と、「誤り位置多項式 $\sigma(x)$ を求める」問題は、数学的に同一の問題です。RS符号の回で名前だけ紹介したBerlekamp-Massey法は、まさにこの「与えられた数列を生成する最小次数のLFSRを構成する」アルゴリズムであり、誤り数が $v \le t$ である限り、このアルゴリズムが求める最小次数のLFSRの次数が真の誤り数 $v$ に一致することが保証されます。BCH符号でもRS符号でも同じアルゴリズムが使えるのは、両者とも「シンドローム=誤り位置のべき乗和」という同じ代数構造を共有しているからです。

$\sigma(x)$ が求まれば、その根(の逆数)を体のすべての元についてしらみつぶしに探すChien探索で誤り位置が確定します。ここでRS復号との違いが1つあります。RS符号では誤り位置に加えて「どのシンボル値に化けたか」という誤り値を Forneyのアルゴリズムで別途求める必要がありました。しかし2値のBCH符号では、誤りの「値」は常に1通り(ビット反転)しかあり得ません。位置さえ分かれば、そのビットを反転させるだけで訂正が完了します。つまり2値BCH符号の復号では、シンドローム計算・Berlekamp-Massey法・Chien探索の3ステップだけで完結し、Forneyのアルゴリズムに相当するステップは不要になります。これは「シンボルが1ビットしかない」という2値符号特有の単純化であり、次節で見るRS符号(多値のBCH符号)との構造的な違いの1つでもあります。

リード・ソロモン符号との系譜: 2値から非2値への一般化

ここまでの議論は暗黙に「符号語のビットは $GF(2)$ の元、根は拡大体 $GF(2^m)$ の元」という2値BCH符号を前提にしてきました。しかしBCH符号の構成そのもの——「原始元のべき $\alpha^b,\dots,\alpha^{b+d-2}$ を根に持つ生成多項式で符号を定義する」という発想——は、符号語のシンボルを $GF(2)$ に限定する必然性はありません。

一般に、シンボルを $GF(q)$($q=p^s$)の元とし、根を「シンボル体の拡大体」$GF(q^m)$ の原始元 $\alpha$ のべきに取る構成が、一般化されたBCH符号です。生成多項式は、シンボル体 $GF(q)$ 上の最小多項式を使って同じ形で書けます。

$$g(x) = \mathrm{lcm}_{GF(q)}\big(\phi_{\alpha^b}(x),\, \phi_{\alpha^{b+1}}(x),\, \dots,\, \phi_{\alpha^{b+d-2}}(x)\big)$$

さて、ここで拡大次数 $m=1$ の場合を考えてみましょう。$m=1$ ということは、根を取る体 $GF(q^m)=GF(q)$ が、シンボル体 $GF(q)$ そのものと一致するということです。すると各 $\alpha^i$ はもとから $GF(q)$ の元であり、$GF(q)$ 上のフロベニウス写像は $GF(q)$ の元に対して恒等写像になる(共役元が自分自身しかない、円分剰余類が $\{i\}$ の1点だけになる)ため、最小多項式は単に

$$\phi_{\alpha^i}(x) = x-\alpha^i$$

という次数1の多項式に退化します。したがって生成多項式は、

$$g(x) = \prod_{i=b}^{b+d-2}(x-\alpha^i)$$

これは、RS符号の回で見た生成多項式 $g(x)=\prod_{i=1}^{n-k}(x-\alpha^i)$ の形と完全に一致します。つまり、

リード・ソロモン符号とは、「シンボル体と根を取る拡大体が一致する($m=1$)」という特別な場合のBCH符号にほかなりません。

この系譜を整理すると、次のように見通せます。

符号	シンボル体	拡大次数 $m$	訂正能力
ハミング符号	$GF(2)$	任意の $m$	$t=1$ 固定
BCH符号(狭義・2値)	$GF(2)$	任意の $m$	任意の $t$
RS符号	$GF(q)$	$m=1$(シンボル体=根の体)	任意の $t$

ハミング符号は「2値・$t=1$」、BCH符号はそれを「2値のまま・$t$ を任意に一般化」、RS符号は「$t$ を任意にしたまま・シンボルを多値化して $m=1$ に特殊化」したもの、という3者の関係が見えてきます。RS符号がシングルトン限界を等号で達成する(MDS符号になる)理由も、この視点から再解釈できます。$m=1$ のとき最小多項式がすべて次数1に退化するため、検査記号数($n-k=\deg g(x)$)がそのまま根の個数 $d-1$ に一致し、BCH限界の不等号 $d_{\min}\ge d$ が無駄なく効いてくるのです。一方、$m>1$ の2値BCH符号では、最小多項式の次数が円分剰余類のサイズ($1$ から $m$ まで様々)に依存するため、検査ビット数と保証される距離の関係が必ずしもタイトにならず、シングルトン限界に届かないのが通常です。

実務での使われ方

BCH符号という名前自体は、実はこのカリキュラムに既に何度か登場していました。CCSDS 231.0-B(TC Synchronization and Channel Coding)が規定するコマンドアップリンクのCLTU(Command Link Transmission Unit)では、TCフレームを7オクテット(56ビット)ごとに区切り、各ブロックにBCH$(63,56)$符号による7検査ビットを付加し、さらに1フィルビットを加えた64ビットのコードブロックとして送信します(space-data-link-protocolの回、COP-1の回、SLEの回を参照)。$n=63=2^6-1$ は $GF(2^6)$ 上のBCH符号であり、拡張により1ビット訂正・2ビット検出(SEC-DED的な性質)を実現します。CCSDS符号化標準の回で見た通り、アップリンクではターボ符号やLDPC符号のような反復復号方式への移行が進んでおらず、実装が枯れて検証しやすいBCH符号(や単純な畳み込み符号)が今なお標準であり続けています。

BCH符号のもう一つの重要な応用が、マスメモリの回で扱ったフラッシュメモリのエラー訂正です。あの回では、メモリワード単位の保護に拡張ハミング符号(SEC-DED、1ビット訂正・2ビット検出)を使う例を見ましたが、これはあくまで $t=1$ の場合であり、この回の言葉で言えば「$t=1$ のBCH符号」です。ところが現代のNAND型フラッシュメモリ、特に多値化が進んだMLC/TLC/QLCフラッシュでは、微細化(プロセスノードの縮小)によって生の(訂正前の)ビット誤り率が大幅に上昇しており、1024バイト(8192ビット)程度のセクタあたり数十ビットもの誤りを訂正できる能力が要求されます。SEC-DEDの $t=1$ では到底足りません。

ここで実務者が直面するのが、「なぜRS符号ではなくBCH符号を使うのか」というトレードオフです。フラッシュメモリのビット誤りは、通信路のようなバースト性を持たず、セル劣化や読み出し閾値のずれによってほぼランダムにビット単位で発生します。RS符号はシンボル(たとえば1バイト=8ビット)単位でしか誤りを数えないため、8ビットのうち1ビットだけが誤っていても、そのシンボル全体を「1シンボル誤り」として検査記号を消費してしまいます。これに対しBCH符号は、ビット粒度でそのまま誤り位置を特定・訂正できるため、ランダムな単一ビット誤りが支配的な環境では、同じ訂正能力をより少ない冗長度(検査ビット数)で実現できます。「ハミング符号より強力(任意の $t$)だが、ビット単位で誤りが散らばる場面ではRS符号よりオーバーヘッドが少ない」——これが、フラッシュメモリコントローラの多くが2値BCH符号(1024バイトあたり24〜60ビット程度の訂正能力を持つものが一般的)を採用している理由です。逆に、RS符号の回で見たような通信路のバースト誤りが支配的な場面では、この優位性は逆転し、RS符号(やBCH符号とインターリーブの組み合わせ)が選ばれる、という使い分けになります。

演習問題

1. $n=31$($m=5$、$GF(32)$)において、$\bmod\ 31$ の円分剰余類 $C_1=\{1,2,4,8,16\}$、$C_3=\{3,6,12,24,17\}$、$C_5=\{5,10,20,9,18\}$、$C_7=\{7,14,28,25,19\}$ が与えられているとします(いずれも要素数5)。3ビット誤り訂正($t=3$、設計距離 $2t+1=7$、根 $\alpha^1,\dots,\alpha^6$ が必要)を実現するBCH符号を構成するには、どの円分剰余類が必要か答え、生成多項式の次数の上限と、得られる符号の次元 $k$ を求めてください。

2. 本文中の $\mathrm{BCH}(15,7,5)$ の例について、もし2値BCH符号ではなく素朴に「2誤り訂正のためには検査ビットが最低何ビット必要か」をハミング限界(球充填限界)から見積もると、どの程度の検査ビット数になるか概算し、実際の8検査ビットという値と比較してみてください(ハミング限界: $2^r \ge \sum_{i=0}^{t}\binom{n}{i}$)。

3. なぜ2値BCH符号の復号では、RS符号の復号で必要だったForneyのアルゴリズムに相当するステップが不要になるのか、この回で学んだ「誤り値」という概念に立ち返って自分の言葉で説明してください。

4. CCSDS 231.0-BのBCH$(63,56)$符号(検査ビット7、フィルビット込みで64ビットブロック)の冗長度比 $r/n$ と、RS符号の回で扱ったCCSDS標準のRS$(255,223)$符号の冗長度比 $(n-k)/n$ を計算して比較し、両者の誤り発生モデル(ランダム誤り検出中心のアップリンク vs. バースト誤り訂正中心のダウンリンク)の違いが、この冗長度比の違いにどう反映されているか論じてください。

まとめと次回予告

この回では、ハミング符号が抱えていた「1ビットしか訂正できない」という限界を、ガロア体上の最小多項式・円分剰余類・生成多項式という代数的な道具立てによって、任意の誤り訂正能力 $t$ を持つ符号族へと一般化するBCH符号を学びました。BCH限界(ヴァンデルモンド行列の非退化性による証明)が設計距離 $d\ge 2t+1$ を保証すること、そして復号がシンドローム計算・Berlekamp-Massey法(誤り位置多項式を、シンドローム列を生成する最小次数のLFSRとして求める)・Chien探索という手順で進むこと(2値の場合はForneyのアルゴリズムが不要になること)を見ました。そして何より、ハミング符号は $t=1$・拡大次数任意のBCH符号、RS符号は拡大次数 $m=1$・シンボル多値のBCH符号という、これまで別々に学んできた3つの符号が同じ代数的設計図の上に並ぶ系譜であることを明らかにしました。

次回は、RS符号の回や実務の節で触れたインターリーバ設計理論に踏み込みます。BCH符号やRS符号がそれぞれ保証する訂正能力 $t$ を、実際の通信路で発生する長いバースト誤りに対してどこまで活かせるかは、複数の符号語をどうシャッフルして送るか(インターリーブ深さの設計)に大きく依存します。この「符号の理論的な強さ」と「実際のバースト長への耐性」を橋渡しする設計論を扱います。

参考文献

• S. Lin, D. J. Costello, Error Control Coding, 2nd ed., Prentice Hall
• R. E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley
• S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall
• CCSDS 231.0-B, TC Synchronization and Channel Coding