BCH(31,16)符号について

ここで使用している BCH(31,16) 符号は 3 ビットまでのランダム誤りとバースト長が 6 までの巡回バースト誤りを訂正することが出来ます。 また、次の誤りパターンの 7-bit バースト誤りも訂正が可能です。

burst error of length 7, pattern : 1111111
burst error of length 7, pattern : 1111101
burst error of length 7, pattern : 1111011
burst error of length 7, pattern : 1110111
burst error of length 7, pattern : 1101111
burst error of length 7, pattern : 1011111

BCH(31,16) 符号を元にした 3-bit ランダム誤り訂正 6-bit バースト誤り訂正符号の生成多項式には反転パターンを含んで次の 4 つがあります。

生成多項式の係数表記 16進数 (8進数) ↔ 反転表記 # 特記事項
0xa943 0(124503) ↔ 0xc295 (0141225) # M1 * M3 * M9
0xdd5d 0(156535) ↔ 0xbabb (0135273) # M1 * M7 * M9

ここでは生成多項式 GP(x) に、M1 * M3 * M9 の

GP(x) = x¹⁵ + x¹³ + x¹¹ + x⁸ + x⁷ + x + 1

を使用しています。
生成多項式の係数 (coefficients) 表記では、2進数 (16進数) で 1010 1001 0100 0011 ( 0xa943 ) と表されます。
生成多項式 GP(x) に、 RCR STD-41 等で採用されているものと同じ、M1 * M3 * M5 の、

GP(x) = x¹⁵ + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁵ + x³ + x² + x + 1

を使った場合にはバースト長が 5 の巡回バースト誤りまでしか訂正出来なくなります。
この符号は誤り訂正前のビットエラーレートを P_i 訂正後を P_o とすると P_o ≤ 4480 P_i⁴ が見込まれます。

BCH(31,16)符号 誤り訂正デモンストレーション

⚠️ Demo の実行には Java 8 のインストール と 例外サイトへの追加 が必要です。

• Send code の Data 部分をクリックすると該当ビットを反転出来ます。
  
• Error bit の任意の部分をクリックすると該当ビットを反転出来ます。
  
• 最初はランダムな値の Data とランダムな１ビットの誤りになっています。
  
• タイトル部分をクリックすると Information data がランダムに変更されます。
  
• Auto run 部分をクリックすると誤りテストを自動的に実行します。
  左から 1 bit 誤り、2 bit ランダム誤り、3 bit ランダム誤り, バースト誤り(length=4), バースト誤り(length=5), バースト誤り(length=6) のテストになっています。

ライブラリのサイズについて

誤り位置はチェン探索 (Chien search) により求めています。 C言語で実装した場合の BCH(31,16) 誤り訂正符号ライブラリのオブジェクトサイズは、
3-bit までのランダム誤りとバースト長が 5 までのバースト誤りに対応した場合 2Kbyte、 バースト長さが 7 の訂正可能なバースト誤りにまで拡張した場合には 4.5 Kbyte でした。

参考文献

• 符号理論, 今井秀樹, 電子情報通信学会, ISBN4-88552-090-8
  
• Chien, R. T. (October 1964), "Cyclic Decoding Procedure for the Bose-Chaudhuri-Hocquenghem Codes", IEEE Transactions on Information Theory IT-10 (4): 357-363, ISSN 0018-9448
  
• Hans J.Matt, James L. Massey (May 1980), "Determining the Burst-Correcting Limit of Cyclic Codes", IEEE Transactions on Information Theory IT-26 (3)

関連項目

2元 BCH 符号及びバースト誤り訂正符号