二重誤り訂正符号 (7)

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

７．ユークリッド復号法

BCH符号のユークリッド復号法に関する解説をWeb上でも閲覧できます．ここでは文献[3]を参照しながら三重誤りを訂正するときの「例1」を簡単に紹介します．なお，文献[3]の記法は上記のものと少し異なりますが，そのまま引用します．「例1」は x⁴ + x + 1 の根αで作られた符号語長15の三重誤り訂正符号で，誤り多項式がe(z) = z + z⁴ + z⁶ の場合の処理を示しています．三重誤り訂正の場合のシンドローム多項式は

        S(z) = s₁ + s₂ z + …… + s₆ zx⁵    ( s_i = S(αⁱ), 1 ≦ i ≦ 6 )

で，誤り位置を調べる多項式は

        σ(z) = (1 - α^i₁ z)(1 - α^i₂ z)(1 - α^i₃ z)

です．ユークリッド復号法では基本方程式

        σ(z) S(z) + φ(z) z⁶ = η(z)

を構成する多項式の次数に着目して，ユークリッドの互除法で次数を削減していきます．例１に数値が詳しく示されていますが，計算内容は漸化式

       

 を用いて

         

と連分数展開し，

       

と近似したものになっています．γ は γσ(0) = 1 とするための定数です．φ(z) や η(z) が表に出てこないのでよく分かりませんでした．e(z) = z という単一誤りのときのシンドローム多項式はS(z) = α + α² z + …… + α⁶ z⁵ であり

       

となって r₁(z) で次数が 0 になります．σ(z) = α^-9(α⁹ - α⁸ z) z² としたいのですが，そうではなくてσ(z) = α^-9(α⁹ - α⁸ z) とするのかも知れません．

ユークリッド復号法は[3]で詳しく解説されていますが，上記のような連分数展開による表現の方が覚えやすく，実際，Web上でも「BCH  連分数」や「BCH  continued fraction 」の検索で多数の資料が見つかります．参考までに IEEE Xplore Digital Library に示されている論文のアブストラクトを次に示します．

I. S. Reed and T. K. Truong,  
"Simple proof of the continued fraction algorithm for decoding Reed-Solomon codes"
Proceedings of the Institution of Electrical Engineers, December 1978
Abstract:
It was shown recently that BCH and RS codes can be implemented by Berlekamp's
algorithm using continued fraction approximations. A simple transparent proof
of Berlekamp's algorithm that uses such a development is given in this paper.

この記事は式が多いので B2012-06.odt を作成してから *.txt にコピーしてブログの記事にしました．ときどき式が抜けていたのはこのためです．B2012-06.odt の方がミスが少なく，これを *.pdf に変換して
  http://pulsar.blog.ocn.ne.jp/topics/B2012-06.pdf
に upload しています．

二重誤り訂正符号 (6)

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

６．GF(2^m)上の多項式

  これまでは多項式の係数は 0，1 のいずれか（GF(2)上の元）としてきましたが，さらに議論を進めるには変数のとりうる値だけでなく係数も GF(2^m) 上で考えねばなりません．実数体上の規約多項式 x² + 4 は複素数体上では (x + 2i)(x - 2i) に因数分解できることは高校で学んだはずです．これと同様に 0, 1 を係数とするGF(2)上の規約多項式も GF(2^m) 上ではさらに因数分解できます．例えば，M₂(x) = x⁴ + x³ + x² + x + 1 の根が α³, α⁶, α⁹, α¹²であるということは

        M₂(x) = (x - α³)(x - α⁶)(x - α⁹)(x - α¹²)

を意味します．実際に M₂(x) の係数を計算すると

        

となり，M₂(x) = x⁴ + x³ + x² + x + 1 であることが確認できます．連立方程式が,  αⁱ + α^j = α⁹, α³ⁱ + α^3j = α² のように簡単であれば x = αⁱ とおいて

       x³ + (x + α⁹)³ = α⁹x² + α³x + α¹² = α²

を整理した x² + α¹¹x + α¹³ = 0 から，x の値は容易に求められます．しかし，より多くの伝送誤りを訂正できるようにしようとすると複雑な処理が必要になります．

二重誤り訂正符号 (5)

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

５．シンドロームの計算

生成多項式が G(x) = M₁(x) M₂(x)で， M₁(α) = 0，M₂(α³) = 0 とします．受信した符号語の多項式が W(x) のときのシンドロームは

        (W(α), W(α³))

で定義され，

        W(x) = Q₁(x) M₁(x) + R₁(x)，R₁(x) = W(x) mod M₁(x)

とおくと W(α) = R₁(α) と表せます．同様に W(α³) = R₂(α³) ( R₂(x) = W(x) mod M₂(x) ) です．また，一般に W(α²ⁱ) = W(αⁱ)² が成立します．
W(α³) の計算例として

        W(x) = F(x) + E(x) = (1 + x + x⁴) (1 + x + x² + x³ + x⁴) + x² + x¹¹

のときの R₂(x) = W(x) mod M₂(x) を求めると，x⁵ mod M₂(x) = 1 ですから

     

となり，R₂(α³) = α³ + α⁶ = α² が得られます．これは

        h₂ = (α⁰  α³  α⁶ α⁹  α¹²  α⁰  α³  α⁶  α⁹  α¹²  α⁰  α³  α²  α⁹  α¹²)

とおいたときのシンドローム (1  0  1  0  1  0  1  1  1  0  0  1  0  0  0) h₂^T と一致しているはずです．

二重誤り訂正符号 (4)

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

４．二重誤りの訂正

４次の原始多項式 x⁴ + x + 1 の一つの根をαとします．αとα³を根とする多項式を生成多項式とするBCH符号とはどのような符号でしょうか．この生成多項式は

        G(x) = M₁(x) M₁(x),   M₁(x) = x⁴ + x + 1,   M₂(x) = x⁴ + x³ + x² + x + 1

です（最小多項式の説明は省略します）．生成多項式をαとα⁹ = α³ + α を根とする多項式と考えてはいけないのでしょうか．とりあえず M₂(x) の根を β とおいてパリティ検査行列
         
による伝送誤り e = (0  0  1  0  0  0  0  0  0  0  0  1  0  0  0) の訂正を考えて見ましょう．伝送誤りの多項式は E(x) = x² + x¹¹ で, シンドロームは

     
です．β = α³ のときは E(β) = α⁶ + α³ = α² なので

        αⁱ + α^j = α⁹,  α³ⁱ + α^3j = α²

となる，i, j を求めることになります．β = α⁹ のときは

        E(β) = α³ + α⁹ = α,  αⁱ + α^j = α⁹,  α⁹ⁱ + α^9j = α

です． このときも，(α⁹ⁱ + α^9j)² = α¹⁸ⁱ + α^18j = α³ⁱ + α^3j = α² ですから β = α³ のときと同じ式が成立しています．なお，単一誤りは E(α)³ = E(α³) で検出でき，E(α) = αⁱ となる i は容易に求められます．

 

二重誤り訂正符号 (3)

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

３．剰余の表現

最初に示した G(x) = x³ + x + 1 で生成される符号語の多項式

    F(x) = (0  1  0  1) (x⁰ ・・・ x⁶)^T = 1 + x + x⁴ + x⁶

が G(x) で割り切れることは実際の計算

            
で確認できますが，転送誤りの位置のように G(x) で割り切れない多項式に上記のような昇べきの順の多項式で除算を行うと x の高次の式で表された剰余もどきの式が現れます．最初の例の

      (0  0  1  0  0  0  0) H^T = (0  0  1)

の場合の剰余もどきの式は x⁴ + x⁵ + x⁶ で，剰余は x⁴ + x⁵ + x⁶ mod G(x) = x² です．

      (0  0  1  0  0  0  0) (α⁰ ・・・ α⁶)^T = α²

は昇べきの順で考えた誤り多項式 E(x) = x² によるシンドロームで α² を E(α) で表わすことができます．なお，通常は使いませんが (0  0  1  0  0  0  0) を降べきの順で考えた誤り多項式E(x) = x⁴ とみなしたときのシンドローム

      (0  0  1  0  0  0  0) (α⁶ ・・・ α⁰)^T = α⁴

も E(α) で表現できます．誤りの位置 (0  0  1  0  0  0  0) は変更できないませんが，これをどう表現し，どう処理するかは自由です．