概要
この符号はバースト長が 8 までのバースト誤りを訂正することが出来ます。
ライガーの限界 (Reiger Bound) を達成している最適バースト誤り訂正符号 (Optimal burst-error-correcting code) の一つです。
その生成多項式 (generator polynomial) の一つは、式 (1) で表されます。
GP(x) =
x16 +
x13 +
x12 +
x10 +
x8 +
x5 +
x3 +
1
——(1)
生成多項式の係数 (coefficients) は、
2進数で 1 0011 0101 0010 1001（16進数 0x13529）
x:16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1
と表されます。
バースト長が 5 までの誤りは **……*** のような巡回パターンも訂正することが可能です。
全ビットが '1' の誤りを検出することができます。
(48,32) 8-bit バースト誤り訂正符号デモンストレーション
デモンストレーション (HTML5/JS 版)
元々は、ロボット間通信用に設計したハードウェアのデモンストレーション用に作成したものです。
ブラウザ上でそのまま動作します。プラグインのインストールは不要です。
- Send code の Information data 部分をクリックすると該当ビットを反転できます。
- Error bit の任意の部分をクリックすると該当ビットを反転できます。最初はランダムな値の Data とランダムな 1 ビットの誤りになっています。
- AC で全ビットをクリアします。
- Auto run を有効にすると誤りテストを自動的に繰り返します。Test1 が 1-bit 誤り、Test2 が 1〜8-bit 長のバースト誤り訂正、Test3 が 9〜16-bit 長のバースト誤り検出のテストです。
- 9〜16-bit 長のバースト誤りはその全てを検出できるわけではありません。
(48,32) バースト誤り訂正符号について
この符号は (50, 34) 8 ビットバースト誤り訂正符号を 2 ビット短縮した符号です。
これはライガーの限界 (Reiger Bound) を達成しているため、最適バースト誤り訂正符号の一つとなっています。
情報ビット長や符号長、バースト訂正能力などが全て 8 の倍数なので色々と好都合です。
符号長は 6 の倍数でもあるので ASCII 文字などへのエンコード等にも便利に使えます。
その生成多項式 (generator polynomial) の一つは 0x12959 です。
参考文献
- 符号理論, 今井秀樹, 電子情報通信学会, 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)
関連項目
