７．ユークリッド復号法
BCH符号のユークリッド復号法に関する解説をWeb上でも閲覧できます．ここでは文献[3]を参照しながら三重誤りを訂正するときの「例1」を簡単に紹介します．なお，文献[3]の記法は上記のものと少し異なりますが，そのまま引用します．「例1」は x4 + x + 1 の根αで作られた符号語長15の三重誤り訂正符号で，誤り多項式がe(z) = z + z4 + z6 の場合の処理を示しています．三重誤り訂正の場合のシンドローム多項式は
S(z) = s1 + s2 z + …… + s6 zx5 ( si = S(αi), 1 ≦ i ≦ 6 )
で，誤り位置を調べる多項式は
σ(z) = (1 - αi1 z)(1 - αi2 z)(1 - αi3 z)
です．ユークリッド復号法では基本方程式
σ(z) S(z) + φ(z) z6 = η(z)
を構成する多項式の次数に着目して，ユークリッドの互除法で次数を削減していきます．例１に数値が詳しく示されていますが，計算内容は漸化式
を用いて
と連分数展開し，
と近似したものになっています．γ は γσ(0) = 1 とするための定数です．φ(z) や η(z) が表に出てこないのでよく分かりませんでした．e(z) = z という単一誤りのときのシンドローム多項式はS(z) = α + α2 z + …… + α6 z5 であり
となって r1(z) で次数が 0 になります．σ(z) = α-9(α9 - α8 z) z2 としたいのですが，そうではなくてσ(z) = α-9(α9 - α8 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 しています．
