巡回ハミング符号は分かったがBCH符号はよく分からないという諸君のために,非常に簡単な例を用いてこの間の橋渡しを試みました.教科書・参考書と参照しながら読めるように,sys.pdf や sys-s.pdf のような異端的表現ではなく,慣用の記法に準じています.
[1] W. W. Peterson, Error-correcting codes, M.I.T. PRESS, 1961
Appendix C: TABLES OF IRREDUCIBLE POLYNOMIALS OVER GF(2)
DEGREE 3 1 13F
DEGREE 4 1 23F 3 37D 5 07
[2] 宮川,岩垂,今井,符号理論 第3版,昭晃堂,昭51.
[3] 平澤茂一, 符号理論 http://www.hirasa.mgmt.waseda.ac.jp/lab/ct.pdf.
[4] 今井,萩原:日本における符号理論の原点 https://www.jstage.jst.go.jp/article/essfr/2/4/2_4_4_9/_pdf
[5] 平澤,笠原:ユークリッド復号法 https://www.jstage.jst.go.jp/article/essfr/4/3/4_3_183/_pdf
1.巡回ハミング符号
準備として単一誤りを訂正する巡回ハミング符号の復習をします.GF(2)上の3次の原始多項式 G(x) = x3 + x + 1 を生成多項式とする巡回符号の H,G として次の形のものを考えます.
この G を用いて (0 1 0 1) を符号化すると
(0 1 0 1) G = (1 1 0 0 1 0 1)
となり,(1 1 1 0 1 0 1) を受信したときも (0 1 0 1) に復号されます.シンドロームは
(1 1 0 0 1 0 1) HT = (0 0 1)
です.(0 1 0 1) を符号化した多項式は
で,上記のシンドロームを生成多項式の根αを用いて表わすと
となります.n = 3 のときは別の原始多項式 x3 + x2 + 1 も用いて
を考えても二重誤りは訂正できません.その理由はつぎの n = 4 の例で分かります.