BCH(31,16) 3-bit ランダム誤り訂正, 6-bit 巡回バースト誤り訂正符号
このアプレットは無線通信機器用に設計した誤り訂正モジュールの動作説明用に作成したものです。
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) = x15 + x13 + x11 + x8
+ x7 + x + 1
を使用しています。
生成多項式の係数 (coefficients) 表記では、2進数 (16進数) で 1010 1001 0100 0011 ( 0xa943 ) と表されます。
生成多項式 GP(x) に、 RCR STD-41 等で採用されているものと同じ、M1 * M3 * M5 の、
GP(x) = x15
+ x11 + x10 + x9 + x8
+ x7 + x5
+ x3 + x2 + x + 1
を使った場合にはバースト長が 5 の巡回バースト誤りまでしか訂正出来なくなります。
この符号は誤り訂正前のビットエラーレートを Pi 訂正後を Po
とすると Po ≤ 4480 Pi4 が見込まれます。
BCH(31,16)符号 誤り訂正デモンストレーション

⚠️ Demo の実行には
Java 8 のインストール と
例外サイトへの追加 が必要です。
- Send code の Data 部分をクリックすると該当ビットを反転出来ます。
- Error bit の任意の部分をクリックすると該当ビットを反転出来ます。
- 最初はランダムな値の Data とランダムな1ビットの誤りになっています。
- タイトル部分をクリックすると 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 符号及びバースト誤り訂正符号



© 2000 Takayuki HOSODA.