ＢＣＨ符号をつくってみよう

GF(2^4)の原始多項式はX^4+X+1

GF(2)に原始根αを導入してGF(2^4)拡大体をつくる。

G(X)=X^4+X+1とおくとG(X)=0の根は原始根αなのでG(α)=0

α＾４＋α＋１＝０

α＾４＝α＋１

これでＢＣＨ符号をつくってみよう。

α＾４＝α＋１を使って最大次の次数が３次になるように拡大体をつくる。

まずGF(2^4)のガロア拡大体を全部計算する

０
１
α
α＾２
α＾３
α＾４＝α＋１
α＾５＝α＾２＋α
α＾６＝α＾３＋α＾２
α＾７＝α＾４＋α＾３＝α＋１＋α＾３
α＾８＝α＾２＋α＋α＾４＝α＾２＋α＋α＋１＝α＾２＋１
α＾９＝α＾３＋α
α＾１０＝α＾４＋α＾２＝α＋１＋α＾２
α＾１１＝α＾２＋α＋α＾３
α＾１２＝α＾３＋α＾２＋α＾４＝α＾３＋α＾２＋α＋１
α＾１３＝α＾４＋α＾３＋α＾２＋α＝α＋１＋α＾３＋α＾２＋α＝α＾３＋α＾２＋１
α＾１４＝α＾４＋α＾３＋α＝α＋１＋α＾３＋α＝α＾３＋１
α＾１５＝α＾４＋α＝α＋１＋α＝１

ここでα＾１５＝１になって０を除く最初の項にもどる
ここで計算したものから0を除いたものはＸ＾１５＝１の１５個の根です。
０を含めるために、Ｘ＾１６＋Ｘ＝０の根とする人もいます。

そして、０，１、α・・・α＾１４の１６個の元がもとまりした。
０を除いてほかの元は１、α、α＾２、α＾３だけであらわされています。
じゃ、これを２進数（α進数）であらわしてみましょう
８の位をα＾３があるとき１、ないとき０
４の位をα＾２があるとき１、ないとき０
２の位をαがあるとき１、ないとき０
１の位をα＾０＝１があるとき１、ないとき０
とあらわします
０・・・・００００
１・・・・０００１
α・・・・００１０
α＾２・・０１００
α＾３・・１０００
α＾４・・００１１
α＾５・・０１１０
α＾６・・１１００
α＾７・・１０１１
α＾８・・０１０１
α＾９・・１０１０
α＾１０・０１１１
α＾１１・１１１０
α＾１２・１１１１
α＾１３・１１０１
α＾１４・１００１

となります。

準備がととのったところで生成多項式をつくります。

符号多項式は生成多項式で割り切れるようにつくります。だから符号多項式は、生成多

項式を因数にもっています。生成多項式にαを代入して０になれば符号多項式もαを代入

して０になります。符号多項式はべき乗数が連続した元（α、α＾２、α＾３・・・）を

それぞれ代入して０になるようにつくると符号に誤りが発生しても誤りを訂正

できます。なので生成多項式はべき乗数が連続した元をそれぞれ代入して０になるよう

につくります。

符号多項式をF(X)とすると０になるF(α）、F(α＾２）、F(α＾３）、F(α＾４）をシンド

ロームといいます。誤りが発生すると、シンドロームは普通０になりません。　　

F(α)とF(α＾２)が0になるように生成多項式を作ると最大１個の誤りを訂正できます。

F(α)とF(α＾２)とF(α＾３)とF(α＾４)が0になるように生成多項式を作ると最大２個の

誤りを訂正できます。

F(α)、・・・F(α＾６)が0になるように生成多項式を作ると最大３個の誤りを訂正

できます。

つまり訂正できる最大の誤りの個数の２倍だけシンドローム計算が必要です。

まずF(α)とF(α＾２)が0になるには、

生成多項式に(X－α）と(Xーα＾2)の積が含まれていなくてはなりません。

ＢＣＨ符号は、生成多項式の係数が１か０です。αのべき乗が係数にあってはだめで

す。

そこでGF(2^n)でなりたつf(X^2)=f(X)^2という性質を使います。

この性質より、αが根になるなら、α＾２もα＾４もα＾８・・・も根なのです。

（ｘ－α）（ｘ－α＾２）（ｘーα＾４）（Ｘ－α＾８）（Ｘ－α＾１６）

（Ｘ－α＾３２）・・・

α＾１５＝１なので

これは（ｘ－α）（ｘ－α＾２）（ｘーα＾４）（Ｘ－α＾８）（Ｘ－α＾（１５＋１））

（Ｘ－α＾（１５＊２）＋２））・・・

となり

（Ｘ－α）（Ｘ－α＾２）（ｘーα＾４）（Ｘ－α＾８）（Ｘ－α）（Ｘ－α＾２）・・・

となってα、α＾２、α＾４、α＾８がくりかえされることになります

ここで最小多項式というのがあります。

最小多項式というのは、この繰り返しがないいちばん次数が低い多項式で、しかもその

性質は展開するとかならず係数が０か１になる、つまりGF(2)での係数になることが知ら

れています。

ということでαを根とする最小多項式は次の式になることがわかりました。

（ｘ－α）（Ｘ－α＾２）（ｘーα＾４）（Ｘ－α＾８）

＝（ｘ＾２－（α＋α＾２）Ｘ＋α＾３）（Ｘ＾２－（α＾４＋α＾８）Ｘ＋α＾１２）

ガロア拡大体の足し算は、2進数表現したときのそれぞれのビットのＥＸＯＲというこ

となので上でつくったガロア拡大体の表を使って

α＋α＾２＝α＾５

００１０
０１００
０１１０

α＾４＋α＾８＝α＾５

００１１
０１０１
０１１０

（ｘ＾２＋α＾５Ｘ＋α＾３）（Ｘ＾２＋α＾５Ｘ＋α＾１２）
＝Ｘ＾４＋α＾５Ｘ＾３＋α＾１２Ｘ＾２
＋α＾５Ｘ＾３＋α＾１０Ｘ＾２＋α＾１７Ｘ
＋α＾３Ｘ＾２＋α＾８Ｘ＋α＾１５
＝Ｘ＾４
＋（α＾５＋α＾５）Ｘ＾３
＋（α＾１２＋α＾１０＋α＾３）Ｘ＾２
＋（α＾１７＋α＾８）Ｘ
＋α＾１５

α＾１２＋α＾１０＋α＾３＝０

１１１１
０１１１
１０００
００００

α＾１７＋α＾８＝α＾２＋α＾８＝１

０１００
０１０１
０００１

となって

X^4+X+1

となって、ありゃりゃ原始多項式と同じになりました。

それもそのはず、原始多項式は原始元αを根とする多項式でした。

X^4+X+1はX-αでもX-α^2でもわりきれます。

H(X)=X^4+X+1とおくと

H(α)＝H(α＾２)=0

となります。

するとWIKIの方法で１個のあやまりが訂正できます。

最大１個の誤りまで訂正できる符号は

BCH(15,11)となります。

2個の誤りを訂正するには

α、α＾２、α＾３、α＾４を根とする生成多項式なので

αとα＾２とα＾４を根とするX^4+X+1

にα＾３を根とする多項式をかければいいですね

(X-α^3)(X-α^6)(X-α^12)(X-α^24)(X-α^48)

α^15=1なので

α^24はα^9

α^48はα^3

α^96はα^6

くりかえしそうだね

最小多項式は

(X-α^3)(X-α^6)(X-α^12)(X-α^9)

を展開すればよさそうですね。

あら不思議、係数は必ず０か１になるはずです。

結果は、X^4+X^3+X^2+X+1となり

各項の係数は0か1になります。

αとα^2とα^4が根であるX^4+X+1

とα^3が根であるX^4+X^3+X^2+X+1

をかけたもの

(X^4+X+1)(X^4+X^3+X^2+X+1)

=X^8+X^7+X^6+X^4+1

が

BCH(15,7)の生成多項式になります。

最大2個の誤りを訂正する計算に必要なのは、生成多項式にαを代入して０、α＾２を代

入して０、α＾３を代入して０、α＾４を代入して０になればいいんだけど

ついでにα＾８とα＾６とα＾１２とα＾９をそれぞれ代入して０になっちゃう

おまけがついちゃうのでＢＣＨ符号はリードソロモン符号より効率が悪い符号になる。

さて、この回のタイトルはBCH符号をつくってみようでした。

BCHの生成多項式の作り方は、わかったんじゃないかと思います。

このようにＣＲＣと同じように生成多項式がもとまりました。

符号の作り方はＣＲＣと全く同じです。

送りたい情報の情報ビットを多項式化して、生成多項式の最大次数の項をかけて（おし

りに生成多項式の最大次数の数だけ０をならべて）生成多項式で割って、でたあまり

を、追加した０といれかえてできます。係数が０か１の多項式と2進数表現は同じだと

考えるとわかると思います。

X^15-1=(X-α^0)(X-α^1)(X-α^2)(X-α^3)・・・(X-α^14)

=(X-1)*(X-α)(X-α^2)(X-α^4)(X-α^8)*(X-α^3)(X-α^6)(X-α^12)(X-α^9)*(X-α^5)(X-α^10)*

(X-α^7)(X-α^14)(X-α^13)(X-α^11)

X^15-1は、拡大体の０以外の元すべてを根とする式に因数分解できる。

*で区切られたとこで展開してやると係数が１か０になる。

符号多項式をＦ(X)とすると

符号長15bitで訂正できる最大誤りビット数が１のとき

F(α)、F(α^2)が必要なシンドローム、検査ビット４ビット

訂正できる最大誤りビット数が２のとき

F(α)、F(α^2)、F(α^3)、F(α^4)が必要なシンドローム、検査ビット８ビット

訂正できる最大誤りビット数が３のとき

F(α)、F(α^2)、F(α^3)、F(α^4)、F(α^5)、F(α^6)が必要なシンドローム、検査ビット１０

ビット

訂正できる最大誤りビット数が４のとき

F(α)、F(α^2)、F(α^3)、F(α^4)、F(α^5)、F(α^6)、F(α^7)、F(α^8)が必要なシンドロー

ム、検査ビット１４ビット

となって符号が１ビットの情報ビットと検査ビット１４ビットになってしまう。１ビッ

トの情報で１４ビットの無駄なものをくっつけて、４ビット訂正できる。むむむ、ほと

んど、無駄なものがあやまったとき訂正になっちゃうね、

ということになります。

情報多項式をJ(X)としmを生成多項式の最大次のべき数とすると生成多項式でJ(X)*X^m

をわってやってあまりが０となるように検査ビットをつけます。

F(1)=0になるには、生成多項式はx-1。偶数個の１が符号にあれば、F(1)=0になる。パリ

ティ（検査ビット）は１ビット。これは、偶数パリティですね。

F(1)=0,F(α)=0になるには、(X-1)*(X-α)*多項式に、符号多項式が因数分解

できればいい。

ここでX-α、αは拡大体なのでGF(2)にするために(X-α)(X-α^2)(X-α^4)(X-α^8)

=X^4+X+1

(X-1)(X^4+X+1)を生成多項式にしてもいいが、５次の生成多項式にな

り、検査ビットが

５ビットで１ビット増えちゃう。

生成多項式がX^4+X+1だと、

F(α)=F(α^2)=F(α^4)=F(α^8)=0

F(α)=F(α^2)=0でめでたくピーターソン法で１ビットの誤りを訂正できるの

で生成多項式X^4+X+1で検査ビット４ビットと１ビットすくなくてすむ。

なので１ビット誤り訂正には生成多項式X^4+X+1が使われるのである。

シンドロームはα^l、α^(l+1)・・α^(l+2t-1)

を代入して０になるものがあればt個の誤りが訂正できるというのは、今まで書かな

かったけど

そういうことです。lは、０か１が多いです。

α、α^2、α^3、α^4　　l=1、t=2

1、α、α^2、α^3、α^4、α^5　　l=0、t=3

という具合である。

ＢＣＨは、α^nがでてこないように最少多項式化してGF(2)にする

リードソロモンは、α^nをつかえる

といったところです。α^nはGF(2^P)だとPビットをブロックとみなして、Pビット全部

誤っても訂正しちゃう。

GF(2^4)だとα^nは4ビットの2進数であらわされ０、α^0、α^1・・・α^14で

すべての４ビットの２進数を表現できて、4ビット1ブロックとしてt=1

のとき1ブロックの誤りが訂正できて

1ブロック4ビット全部まちがってても訂正できる。誤ってるかわからなくても、

検査ビットからわかる。

誤ってるならここだと位置がわかってる場合、消失訂正といいます。その場合

誤り位置多項式を求める必要はなく、さらに訂正できるビット数を増やせる場合がある

ようです。

消失訂正は興味がないので、ほかの人の説明にまかせます。