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

2026-08-05 改訂
2004-11-09
細田 隆之

概要

この (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) が下記の 2元非原始 BCH符号です。[1],[6]

より正確には、Golay (23,12) 符号は、素数長 23 の二元二次余剰 （Quadratic Residue, QR）符号として構成される。 23 は 211-1 の素因数であり、2 の乗法位数が 11 であることから、 対応する巡回符号が得られる。
同様に、47 も 223-1 の素因数であることから、 対応する (47,24) QR 符号の存在を考えた。 この生成多項式は、長さ47の非原始 BCH 符号であると同時に、 二元 QR 符号としても知られる符号である。
GP(x) = x23 + x19 + x18 + x14 + x13 + x12 + x10 + x9 + x7 + x6 + x5 + x3 + x2 + x + 1 … (1)

チェックビットのサイズも 24ビットくらいなら ハードウェアデコーダーも力技で実現できそうですし、 (24, 12) 拡大 Golay 符号のように 1 ビット拡大して (48, 24, 12) 5 ビット誤り訂正 6 ビット誤り検出符号にすると、 情報ビット長や符号長も８の倍数となって色々と好都合です。

この (48, 24) 拡大符号の符号語中の '1' の重み分布を調べてみたところ、符号号中の '1' の数は (24,12) 拡大 golay 符号と同じように 4 の倍数となっていました。

Table 1. Weight distribution of the (48,24) extended code.
Weight Number of codewords
0 1
12 17296
16 535095
203995376
247681680
283995376
32 535095
36 17296
48 1
(48,24,12) 拡大符号は、現在では Type II（doubly-even self-dual）符号として知られるクラスに属し、すべての符号語のハミング重みが4の倍数となることが知られている。[2]

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

参考文献

  1. W. W. Peterson and E. J. Weldon, Jr., Error-Correcting Codes, 2nd ed., Cambridge, MA, USA: MIT Press, 1972.
  2. E. R. Berlekamp, Algebraic Coding Theory, New York, NY, USA: McGraw-Hill, 1968.
  3. J. L. Massey, "Shift-Register Synthesis and BCH Decoding," IEEE Trans. Inf. Theory, vol. IT-15, no. 1, pp. 122-127, Jan. 1969.
  4. F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16, Amsterdam, The Netherlands: North-Holland, 1977.
  5. 宮川 洋, 岩垂 好裕, 今井 秀樹, "符号理論", 電子通信学会, 1973., ISBN4-88552-180-7
  6. H. J. Matt and J. L. Massey, "Determining the Burst-Correcting Limit of Cyclic Codes," IEEE Trans. Inf. Theory, vol. IT-26, no. 3, pp. 289-297, May 1980.
  7. V. Pless, Introduction to the Theory of Error-Correcting Codes, New York, NY, USA: John Wiley & Sons, 1982.
  8. S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, USA: Prentice-Hall, 1983.
  9. 今井 秀樹, "符号理論", 電子情報通信学会, 1990., ISBN4-88552-090-8

関連項目

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