(47,24) 二元非原始 5-bit ランダム誤り訂正符号

Dec. 9, 2004
細田 隆之

概要

この (47, 24) 符号は 二元非原始誤り訂正符号で 5-bit までのランダム誤りを訂正することが可能です。

(47,24) 符号 5-bit ランダム誤り訂正デモンストレーション

(47,24) 二元非原始 5-bit ランダム誤り訂正符号 Demo [Java Web Start, 8KB]

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

解説

この (47, 24) 符号も文献を探せばきっとあるのではとは思うのですが、この符号は筆者が、
 「Golay(23, 12) 符号が 211 - 1 = 23 * 89 から導かれたのなら 223 - 1 = 47 * 178481 なので設計距離を越える (47, 24) 符号が 無いかなぁ」
と計算機探索してみて見付け出した、生成多項式 GP(x) が、
GP(x) = x23 + x19 + x18 + x14 + x13 + x12 + x10 + x9 + x7 + x6 + x5 + x3 + x2 + x + 1 … (1)
の 2元非原始 BCH符号です。
チェックビットのサイズも 24ビットくらいなら ハードウェアデコーダーも力技で実現できそうですし、 (24, 12) 拡大 Golay 符号のように 1 ビット拡大して (48, 24, 12) 5 ビット誤り訂正 6 ビット誤り検出符号にすると、 情報ビット長や符号長も８の倍数となって色々と好都合です。

この (48, 24) 拡大符号の符号語中の '1' の重み分布を調べてみたところ、符号号中の '1' の数は (24,12) 拡大 golay 符号と同じように 4 の倍数となっていました。 拡大符号の符号語中の '1' の重み分布は Table1 のようになっています。
Table1 [(48,24) 拡大符号の重み分布]
 weight  quantity of code 
0 1
12 17296
16 535095
203995376
247681680
283995376
32 535095
36 17296
48 1

あとがき

後日、東京大学生産技術研究所　今井研究室の方にご紹介頂いた下記の参考文献 [1] に生成多項式の記載はないものの (47, 24, 11) BCH 符号の存在が書かれてました。 もっと後になって、参考文献[3] にこの符号の記載があるのを見つけました。

参考文献

  1. 今井秀樹, "符号理論", 電子情報通信学会 (1990), ISBN4-88552-090-8
  2. 宮川洋, 岩垂好裕, 今井秀樹, "符号理論", 電子通信情報学会 (1973), ISBN4-88552-180-7
  3. (3) 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 符号及びバースト誤り訂正符号
www.finetune.co.jp [Mail] © 2000 Takayuki HOSODA.