二重誤り訂正符号 (1)

記事一覧, sys.pdf，sys-s.pdf

巡回ハミング符号は分かったが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

１．巡回ハミング符号

準備として単一誤りを訂正する巡回ハミング符号の復習をします．GF(2)上の3次の原始多項式 G(x) = x³ + 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) H^T = (0  0  1)

です．(0  1  0  1) を符号化した多項式は

                         

で，上記のシンドロームを生成多項式の根αを用いて表わすと

       

となります．n = 3 のときは別の原始多項式 x³ + x² + 1 も用いて

       

を考えても二重誤りは訂正できません．その理由はつぎの n = 4 の例で分かります．