最大3bitの誤りを訂正できるBCH(15,5)の符号化、ピーターソン法での復号の実例
原始多項式をX^4+X+1として
GF(2^4)拡大体の元を列挙すると
０・・・・００００
１・・・・０００１
α・・・・００１０
α＾２・・０１００
α＾３・・１０００
α＾４・・００１１
α＾５・・０１１０
α＾６・・１１００
α＾７・・１０１１
α＾８・・０１０１
α＾９・・１０１０
α＾１０・０１１１
α＾１１・１１１０
α＾１２・１１１１
α＾１３・１１０１
α＾１４・１００１
最大3bitの誤りを訂正できるBCH符号の生成多項式は、その生成多項式にα、α＾２、α＾３、α＾４、α＾５、α＾６をそれぞれ代入して０にならなくてはならない。
つまり(X-α)(X-α^2)(X-α^3)(X-α^4)(X-α^5)(X-α^6)を因数にもたないといけない。
しかしこれを展開すると係数にαのべき乗がでてきてしまいGF(2)では扱えない。
そこで係数が0か１になるようにしなければならない。
(X-α)(X-α^2)(X-α^4)(X-α^8)=X^4+X+1
(X-α^3)(X-α^6)(X-α^12)(X-α^9)=X^4+X^3+X^2+X+1
(X-α^5)(X-α^10)=X^2+X+1
のように左辺を展開して右辺にするとαのべきが消えて係数が0か1となる。
この3つの式を掛け算したものを生成多項式とする。
(X-α)(X-α^2)(X-α^3)(X-α^4)(X-α^5)(X-α^6)を因数としてもつ係数が0か1の多項式は
(X^4+X+1)(X^4+X^3+X^2+X+1)(X^2+X+1)
=X^10+X^8+X^5+X^4+X^2+X+1
となる。
GF(2^4)拡大体におけるBCH符号の符号長は15bit
最大3bitの誤りが訂正できる生成多項式の最大次数の項のべき数は10なのでこれで割った余りの最大次数の項の
べき数は９以下になり、この符号の検査ビットは１０bitということになる。
よって、符号長15bit-検査ビット10bit=情報長5bit
となり,BCH(15,5)符号ということが確定する。
BCH(15,5)符号は最大3bitの誤りが発生しても訂正できる。
では実際に符号化してみよう。
情報長は5bitであるから例として10000を符号化することにする。
多項式であらわすと
1*X^4+0*X^3+0*X^2+0*X+0=X^4
これに生成多項式の最大次数の項のべき数10で
X^10をかける。
X^14となる。
これを符号化するには、生成多項式で割ってやってあまりをX^14にたしてやればいい
X^14÷(X^10+X^8+X^5+X^4+X^2+X+1)=X^4+X^2+1・・・余りX^9+X^7+X^4+X^3+X+1
よって符号は
X^14+X^9+X^7+X^4+X^3+X+1
F(X)=X^14+X^9+X^7+X^4+X^3+X+1
100001010011011
となる。
これは、誤りがない送り元の符号であり、生成多項式で割り切れるので
F(X)=(X-α)(X-α^2)(X-α^3)(X-α^4)(X-α^5)(X-α^6)*G(X)
とかける。
当然シンドロームF(α)=F(α^2)=F(α^3)=F(α^4)=F(α^5)=F(α^6)=0
となる。
これが通信路でE(X)=X^8+X^7+X^6が加算されて3bit化けたとすると
これは、符号の下位から9bit目の0が1に化け8bit目の1が0に化け7bit目の0が1に化けたことを意味する
100001010011011が通信路のノイズで
100001101011011になったということである
H(X)=F(X)+E(X)=(X^14+X^9+X^7+X^4+X^3+X+1)+(X^8+X^7+X^6)
=X^14+X^9+X^8+X^6+X^4+X^3+X+1
H(X)をピータソン法で復号してみよう
まずシンドローム を計算する。$ S_{1} $ = H(α)、$ S_{2} $ = H(α^2)、$ S_{3} $ = H(α^3)、$ S_{4} $ = H(α^4)、$ S_{5} $ = H(α^5)、$ S_{6} $ = H(α^6)とする。
これらが全部0であるかを確認する。全部0だったら誤りはない。
ひとつでも０でないものがあれば、誤りがある。
計算すると$ S_{1} $ = α、$ S_{2} $ = α^2、$ S_{3} $ = α^11、$ S_{4} $ = α^4、$ S_{5} $ = 0、$ S_{6} $ = α^7
となる。
よって誤りが発生していることがわかる。
発生している誤りの総bit数はわからない。
まず誤りが3bit発生しているんではないかと疑いをかけて、それを確認する。
\begin{equation} \begin{bmatrix}
S_{3} & S_{2} & S_{1} \\
S_{4} & S_{3} & S_{2} \\
S_{5} & S_{4} & S_{3} \\
\end{bmatrix} \begin{bmatrix} \beta _{1} \\
\beta _{2} \\
\beta _{3} \\
\end{bmatrix} = \begin{bmatrix} S _{4} \\
S _{5} \\
S _{6} \\
\end{bmatrix} \end{equation}
が唯一の$ \beta _{1} $ 、 $ \beta _{2} $ 、 $ \beta _{3} $ の組をもつ
とき3bitの誤りが発生している。
つまり、3x3正方行列の行列式が0でない場合は、3bitの誤りが発生している。
0の場合は、2個以下の誤りが発生していることになる。
行列式を計算するとαとなるので、3bitの誤りが発生していることがわかる。
行列式が０でないので、逆行列が存在しそれを左側から両辺にかけてやると
$ \beta _{1} $ 、 $ \beta _{2} $ 、 $ \beta _{3} $がもとまる。
計算すると
$ \beta _{1} $ = α 、$ \beta _{2} $ = α^8 、$ \beta _{3} $ = α^6
となる。
誤り位置多項式は、$ \beta_{3} x^{3} + \beta_{2} x^{2} + \beta_{1} x + 1 $
なので、代入してやると
I(X)=α^6*X^3+α^8*X^2+α*X+1
I(X)にX=α^(-14),X=α^(-13),・・・,X=α^(-2),X=α^(-1),X=α^(0)
を順に代入してやると、0になるときが3回ある。
そのときのX=α^(-n)のnの値が誤り発生ビットである。
X=α^(-8)とX=α^(-7),X=α^(-6)を代入したとき0になるので
E(X)=X^8+X^7+X^6となって
H(X)+E(X)を計算して訂正は終了となる。
2個以下の場合は2x2行列で表される式で同様に行う。
2x2行列の行列式が0になったら、1個の誤りが発生している。
訂正された符号のシンドロームを計算して、検算を行うこともできる。
次に2個の誤りがある場合の訂正作業をやってみよう。
E(X)=X^8+X^7が加算されて誤りが2個発生している場合
H(X)=X^14+X^9+X^8+X^4+X^3+X+1
シンドロームを計算すると$ S_{1} $ = α^11、$ S_{2} $ = α^7、$ S_{3} $ = α^5、$ S_{4} $ = α^14、$ S_{5} $ = 1、$ S_{6} $ = α^10
誤りが3個あると予想して
\begin{bmatrix}
S_{3} & S_{2} & S_{1} \\
S_{4} & S_{3} & S_{2} \\
S_{5} & S_{4} & S_{3} \\
\end{bmatrix}
の行列式を計算すると0になる
よって予想ははずれて、2個以下になる。
\begin{equation} \begin{bmatrix}
S_{2} & S_{1} \\
S_{3} & S_{2} \\
\end{bmatrix} \begin{bmatrix} \beta _{1} \\
\beta _{2} \\
\end{bmatrix} = \begin{bmatrix} S _{3} \\
S _{4} \\
\end{bmatrix} \end{equation}
誤り位置多項式
$ \beta_{2} x^{2} + \beta_{1} x + 1 $
を考え、まず2x2行列の行列式の値を求める
すると、α^7になる。
0ではないので、誤りは2個に確定。
$ \beta_{1} $ 、 $ \beta_{2} $ を求めると
$ \beta _{1} $ = α^11 、$ \beta _{2} $ = 1
α^(-14),・・・,α^(-1),α^0をそれぞれ誤り位置多項式に代入すると
α^(-8)とα^(-7)を代入したときだけ０になる。
よってE(X)=X^8+X^7で訂正が完了する。
次に1個の誤りがある場合
E(X)=X^7が加算されて
H(X)=X^14+X^9+X^4+X^3+X+1
としてシンドロームを計算すると
$ S_{1} $ = α^7、$ S_{2} $ = α^14、$ S_{3} $ = α^6、$ S_{4} $ = α^13、$ S_{5} $ = α^5、$ S_{6} $ = α^12
となる。
よって誤り個数は2個以下が確定する。
次に2x2行列の行列式を計算すると0
よって誤りは1個に確定する
\begin{equation}
S_{1} \beta _{1} = S _{2}
\end{equation}
$ \beta_{1} $ を求めると
α^7
誤り位置多項式
$ \beta_{1} x + 1 $
の $ x $ に
α^(-14),・・・,α^(-1),α^0をそれぞれ代入すると
α^(-7)を代入したときだけ０になる。
よってE(X)=X^7で訂正が完了する。
