BCH符号入門：理論から実装、応用まで詳解（誤り訂正の基礎と最前線）
エバープレイ編集部概要：BCH符号とは何か
BCH符号（Bose–Chaudhuri–Hocquenghem codes）は、有限体上で定義される一群の巡回誤り訂正符号で、有限体の代数的性質を利用して設計された代数誤り訂正符号（algebraic error-correcting codes）です。設計最小距離（designed distance）を指定して符号を構成できるため、任意の誤り訂正能力を持つ符号系列を構築できる点が大きな特徴です。BCH符号は1960年代に独立に提案され、その汎用性と効率性から通信・記憶装置など幅広い分野で用いられています。
歴史的背景
BCH符号は1960年代初頭に、R. C. Bose、D. K. Ray-Chaudhuri、およびA. Hocquenghemによって独立に発見されました。彼らの業績により、有限体と多項式理論を用いることで設計距離を保証する構成が可能になり、従来のハミング符号やリード・ソロモン（RS）符号と並ぶ重要な誤り訂正技術として確立しました。以降、デコーダアルゴリズムや実装手法が改良され、特に二値（binary）BCHはNANDフラッシュや通信機器など組込み実装で広く使われています。
基本的な定義とパラメータ
BCH符号は主に以下のパラメータで特徴付けられます。
- 符号長 n：通常、原始（primitive）BCHでは n = 2^m - 1（mは正整数）。非原始な場合はその約数などもあり得ます。
- 情報長 k：符号語中の情報ビット数。一般に生成多項式の次数 r により k = n - r。
- 設計距離 δ（または最小距離dの下限）：符号が保証する最小ハミング距離の下限。t = floor((δ-1)/2) により訂正可能誤り数が決まります。
- 基底体 q：多くの実装で q=2（二値）や q=p^m の有限体が用いられます。リード・ソロモン符号は q-ary BCH の特殊例とも見なせます。
狭義（narrow-sense）BCH符号は、生成多項式をα^1, α^2, …, α^{δ-1} の根を持つように選択します（αはGF(2^m)の原始元）。一般には b をオフセットとして α^b から α^{b+δ-2} までの最小多項式の最小公倍数を生成多項式 g(x) とします。
数学的構成（有限体と生成多項式）
BCH符号の理論は有限体 GF(q^m) と多項式の最小多項式に依存します。主要なポイントは次のとおりです。
- 原始元 α を持つ GF(2^m) を構成し、循環（巡回）符号の視点から根を扱う。
- 各 α^{i} に対して、その代数的最小多項式 m_i(x) を求める。m_i(x) は GF(2) 上の既約多項式であり、α^{i} を根に持ちます。
- 設計距離 δ を指定すると、g(x) = lcm(m_b(x), m_{b+1}(x), …, m_{b+δ-2}(x)) として生成多項式が得られます。これにより g(α^{b+j}) = 0 （0 ≤ j ≤ δ-2）を満たすため、シンドローム（syndrome）計算でこれらの評価値が0となる性質を利用できます。
設計自由度と次元の下限
生成多項式の次数 r は、最小多項式の重複や次数に依存しますが、一般的な下限評価として次が成り立ちます：
r ≤ m(δ-1)
したがって、符号次元は通常以下の下限を満たします：
k ≥ n - m(δ-1)
ただしこれは厳密値ではなく、実際の次数は最小多項式間の重複により小さくなり得ます。実運用ではテーブル化や具体的な多項式計算で厳密な (n,k,t) を決定します。
エンコーディング（符号化）の方法
BCH符号は巡回符号なので、エンコーダは生成多項式 g(x) を用いて以下の方法で符号語を生成できます。
- システムティック符号化：情報多項式 u(x) を x^{n-k} u(x) でシフトし、それを g(x) で割った余り r(x) を引くことで符号語 c(x) = x^{n-k} u(x) - r(x) を得る。これにより上位ビットに情報がそのまま現れます。
- LFSR（線形帰還シフトレジスタ）：ハードウェア実装では生成多項式に対応するLFSRを用い、情報ビットを逐次入力して残余を得て符号語を構成します。初期化とクロック制御だけで高速に処理可能です。
デコーディング（復号）の基本手順
代数的デコーダは一般に次の手順で進みます（受信多項式 r(x) = c(x) + e(x) と仮定）。
- シンドローム計算：S_j = r(α^{b+j-1})（j=1,…,2t）を計算。正しい符号語なら全て0。
- 誤り位置多項式（エラー・ロケータ）Λ(x) の求解：Berlekamp–Masseyアルゴリズムや拡張ユークリッドアルゴリズムを使ってΛ(x)を求める。Λ(x) の次数が誤り数νに等しい。
- エラー位置の探索：Chienサーチを用いてΛ(α^{-i})=0 となる i を列挙し、誤りの位置を特定する。Chienサーチはハードウェアで並列化しやすい。
- 誤り大きさの算出（非二値符号の場合）：Forneyの公式などで誤り評価多項式Ω(x) を用いて各位置の誤り値を算出する。二値符号では誤り値は1なので単にビット反転する。
上記のうち、Berlekamp–Massey（BM）はシンドローム列から最短線形帰還シフトレジスタを構成するアルゴリズムで、計算量は O(t^2)（有限体上の乗算等での計算量）です。拡張ユークリッドを用いる方法も同等の複雑度で実装され、実装上の都合で使い分けられます。
主要アルゴリズムの詳細と実装上の注意
- Berlekamp–Massey：入力はシンドローム列 S_1..S_{2t}。出力はエラー・ロケータ多項式 Λ(x)。反復更新により多項式を構成し、使用する有限体演算（加算はXOR、乗算は対数表やルックアップで高速化）に注意が必要です。
- Chienサーチ：Λ(α^{-i}) を i=0..n-1 について評価することで誤り位置を検出。逐次的に乗算を行うだけでよく、ハードウェア並列化に適しています。
- Forneyの公式：エラー評価多項式 Ω(x) を使い、誤り位置 i における誤り値 e_i を e_i = -Ω(α^{-i}) / (α^{-i} Λ'(α^{-i})) で計算する（Λ' は Λ の導関数）。非二値符号の符号化や高信頼度の符号化で必須です。
- 有限体実装：GF(2^m) の乗算は通常対数/逆対数テーブルによる高速化、またはKaratsubaなどのアルゴリズムによるソフトウェア高速化を行います。メモリ対速度のトレードオフがあります。
バリエーション：狭義BCH、拡張BCH、短縮BCH、非二値BCH
- 狭義（narrow-sense）BCH：b=1 を取る構成で扱いやすく、理論・実装資料でも頻出します。
- 短縮（shortened）BCH：実際の符号長を n より短くしたい場合に、情報ビットを0でパディングして符号化し、出力でパディング部を切る手法。実装上よく使われます（フラッシュメモリでの用途など）。
- 拡張（extended）BCH：パリティビットを追加して偶数パリティを強制するなどし、最小距離を1増加させる場合があります。
- 非二値BCH（q-ary BCH）：GF(q^m) 上で定義され、リード–ソロモン符号と密接に関連します。RS符号は一種の多項式評価符号で、BCHの非二値特殊ケースとして見なせる場面があります。
代表的な例
実際によく参照される例として二値BCHの小さなパラメータ群があります：
- (7,4) BCH：m=3, n=7 の場合で、1ビット誤り訂正（ハミング符号に一致）。
- (15,11) BCH：m=4, n=15 の1ビット訂正コード。
- (15,7) BCH：n=15 で2ビット訂正が可能な例。
- (15,5) BCH：n=15 で3ビット訂正が可能な例。
これらは理論的に教科書や実装例として頻繁に登場し、アルゴリズムの検証や教育用に使われます。
複雑度と性能
BCH符号のエンコードは一般に O(n k) の多項式除算やLFSRで効率的に実行できます。デコードでは主にシンドロームの計算 O(t n) とBMアルゴリズムの O(t^2)、Chienサーチの O(n t) がボトルネックです。実装ではtが大きくなるとBMの費用が増大するため、tの選択は実用的なトレードオフになります。
利点と欠点
- 利点：設計距離を指定可能、ハードウェアでの並列化やLFSRにより高速な実装が可能、二値符号はビット単位の修正が容易でフラッシュメモリなどに適する。
- 欠点：大きな誤り訂正能力tが必要な場合、デコーダの計算量が増大する。シンボル誤りに強いリード–ソロモンに比べると、誤りパターン（バースト誤りなど）に対する最適性が劣る場面もある。
実世界での応用例
BCH符号は幅広い分野で利用されています。代表的な応用先は以下の通りです。
- フラッシュメモリ（NAND）：多くのNANDフラッシュコントローラで二値BCHが採用され、ビット誤りの補正に用いられます。近年は高密度化に伴いtの大きなBCHやLDPCへ移行するケースもあります。
- 衛星通信・深宇宙通信：初期の衛星通信や特定の組込み機器でBCHが使われてきました。
- 組込みシステム：簡単で高速なハードウェア実装が可能なため、ASIC/FPGA上での誤り訂正に適しています。
- 情報理論・研究用途：代数的誤り訂正の教育・研究で代表的な例題として広く用いられます。
BCHと他の符号との比較
リード–ソロモン（RS）符号はシンボル単位（バイトなど）の誤りに強く、光ディスクやネットワーク伝送に多用されます。一方、BCHはビット単位の誤り訂正に向いており、シンプルなハードウェア実装が可能です。近年はLDPC（低密度パリティ検査）符号が大容量・高信頼通信で注目されていますが、BCHは計算資源が限られる場面で依然有用です。
実装のヒントとベストプラクティス
- 有限体演算はテーブルルックアップ（対数・逆対数）で高速化可能。メモリに余裕があれば推奨。
- Chienサーチはハードウェア的に並列化しやすく、ループの短縮に有効。
- ソフトウェア実装ではビット演算の最適化、SIMD命令による加速を検討する。
- 符号パラメータは用途（誤り分布、許容遅延、実装コスト）に応じて選択。試験的に短縮BCHを用いることで実際のフレーム長に合わせられる。
今後の展望
高密度ストレージや無線通信の発展により、より高性能な誤り訂正コード（LDPCやPolarなど）が注目を集めています。しかしBCHはその理論的単純さ、実装しやすさ、任意の設計距離を指定できる柔軟性から、特に組込み用途や限られた計算リソース下で重要な選択肢として残り続けるでしょう。また、BCHのアルゴリズムや有限体演算の最適化手法は他のコードの実装にも有用です。
まとめ
BCH符号は、有限体の代数構造を用いて設計距離を保証できる強力な巡回符号です。エンコードはLFSRや多項式除算で容易に実装でき、デコードはBerlekamp–Massey、Chienサーチ、Forneyの公式などの確立されたアルゴリズム群により実行されます。二値BCHはフラッシュメモリや組込み機器で広く利用され、現代の誤り訂正ライブラリでも重要な位置を占めています。用途に応じてパラメータ（n,k,t）を調整することで、性能と実装コストをバランスさせることが可能です。
参考文献
MathWorks: BCH encoding and decoding
MIT OpenCourseWare: Lecture notes on BCH codes
S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications
Original papers: R. C. Bose, D. K. Ray-Chaudhuri, A. Hocquenghem (historical論文は検索参照)
投稿者プロフィール
