二重誤り訂正符号 (2)

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

２．４次の規約多項式

4次の原始多項式 G(x) = x⁴ + x + 1 について考えます．G(x) の根 α の他に αⁱ も根にもつ多項式とはどのような多項式でしょうか．α⁴ = α + 1 として αⁱ を計算すると

           

となります．G(x) は４次なので G(x) = 0 は４個の根を持ちます．それはどれでしょう．とりあえず αⁱ の周期を調べると

          
となります．β⁴ + β + 1 = 0 ならば (β⁴ + β + 1)² = β⁸ + β² + 1 = 0 なので，α²，α⁴，α⁸ も G(x) = 0 の根で，α^-1 = α¹⁴, α^-2 = α¹³, α^-4 = α¹¹, α^-8 = α⁷ は x⁴(x^-4 + x^-1 + 1) = 0 の根です．他のGF(16)の元をみると，

    (α³)⁵ = (α⁶)⁵ = (α⁹)⁵ = (α¹²)⁵ = 1
    (α⁵)³ = (α¹⁰)³ = 1

であることが分かります．α^ie = 1 になる e（繰返しの周期．難しくいうと規約多項式の根の位数）を αⁱ を根とする多項式の指標といいます．指標が e である多項式は x^e - 1 の因数であることが知られています．したがって α³ⁱ を根とする多項式は指標が５だから x⁵ - 1 = (x + 1)(x⁴ + x³ + x² + x + 1) の因数 x⁴ + x³ + x² + x + 1 です．同様に α⁵ⁱ を根とする多項式は x⁵ - 1 = (x + 1)(x² + x + 1) の因数 x² + x + 1 です（GF(2)上の多項式なので  x^e - 1 = x^e + 1 ですがGF(p)でも同様の議論が成立する場合は x^e - 1 のように表現することが多いようです）．

参考：上記の数値を計算するExcelの式を以下に示します．
(1) α⁴ = α + 1 による αⁱ の計算
    A1=1, B1=0, C1=0, D1=0
    A2=D1, B2=A1+D1-2*A1*D1, C2=B1, D2=C1
    A(i+1):D(i+1) はAi:Di をコピー
(2) (αⁱ)^j のj の計算
    A1=0, A2=i, A3=A2+A$2-15*Int((A2+A$2)/15), A(j+1)はAj をコピー