符号の代数化をさらに進めよう
このページはマス旅の一部です。
前回は、ベクトルと行列を使って、符号を代数化しました。
今回は、符号を多項式につないで、さらに代数化を進めてみよう。
１．符号と多項式を行き来しよう
＜巡回符号＞
情報ビット長３にパリティビットをつけた4ビットの偶数パリティ検査符号を作ってみよう。
2^3=8個の系列ができるが、重さとつながりの両方でわけると、巡回シフトでつながることがわかる。
巡回操作（巡回シフト）をしてもまた、符号語になっているので、巡回符号と呼ばれている。
[{0,0,0,0}],
[{1,0,1,0},{0,1,0,1}],
[{1,1,0,0},{0,1,1,0},{0,0,1,1},{1,0,0,1}],
[{1,1,1,1}]
偶数パリティーだから、1個の誤りの検出は可能だ。
＜多項式化表現＞
巡回符号を調べるとき、たとえば、a=[1,0,1,0]⇒A(x)=1+0x+1x^2+0x^3のように符号語を多項式A(x)の係数とみなすことで、多項式に置き換えることができる。
これを多項式表現という。
符号語を多項式に置き換えると、符号語どうしの演算ができる。
もちろん、係数は２を法とする剰余演算をする。
多項式は環だから、加減乗だけではなく、整除もできる。
＜周期と原始多項式＞
多項式A(x)で割り切れるｘ^n-1の最小のnがA(x)の「周期」、
m次多項式で周期が2^m-1となるものを特に「原始多項式」という。
たとえば、mが6以下では
m=1の周期が2^1-1=1 になる原始多項式は１ ＋ｘ
m=2の周期が2^2-1=3 になる原始多項式は１ ＋ｘ + x^2
m=3の周期が2^3-1=7 になる原始多項式は１ ＋ｘ + x^3
m=4の周期が2^4-1=15になる原始多項式は１ ＋ｘ + x^4
m=5の周期が2^5-1=31になる原始多項式は１ ＋ｘ^2+ x^5
m=6の周期が2^6-1=63になる原始多項式は１ ＋ｘ + x^6
＜剰余化で乗算で閉じる＞
巡回シフトを多項式で見てみよう。
最初の例の巡回符号では、
[{1,1,0,0},{0,1,1,0},{0,0,1,1},{1,0,0,1}]
は巡回シフトで同じになる符号仲間だ。
これの多項式表現に名前をつけてみよう。
A0(x)=1+1x,
A1(x)=x+x^2,
A2(x)=x^2+x^3,
A3(x)=x^3+1
さて、
x倍すると、A0→A1→A2までは順調に進む。
ところが、A2→？となる。
A2のｘ倍は4次式になるので、4要素の符号語からは外れてしまう。
ここで、x^4-1が登場する。
xA2=x(x^2+x^3)÷(x^4-1)の余りはA3になるのだ。
係数分離法で、整数÷整数をするイメージがあれば簡単だ。
x(x^2+x^3)=sift([0,0,1,1])=[0,0,0,1,1]となる。
(x^4-1)=[-1,0,0,0,1]となね。
商が１だから、
余りはただの引き算で出せる。
[0,0,0,1,1]-[-1,0,0,0,1]=[-(-1),0,0,1,1-1]⇒[1,0,0,1]=A3となるね。
ここを過ぎたらもう安心。
x A2 mod(x^4-1)= A3
x^3 A0 mod(x^4-1)= A3
.....
x^j A0(x)mod(x^4-1)=A(j(mod 4))
と巡回シフトがかけ算と剰余で実現できるね。
係数cは0，1でmod2 とすると、
さらに、
Σcjx^j A(x) mod(x^4-1)=C(x)A(x)(mod x^4-1)
が言えるので、符号語A,Cの積を(mod x^4-1)すれば、符号語になることがわかる。
だから、符号語の多項式表現は(mod x^4-1)すれば、
加減乗算で閉じていることがわかるでしょう。
＜生成多項式＞
符号多項式A(x)の最小次数のものをG(x)とおこう。
面白いことがわかる。
適当なA(x)をG(x）でわった商をQ(x)、余りをR(x)とする。
G(x)の次数をmとすると、余りの次数はm未満であること多項式の整除原理から明らかだ。
整除原理から、
A(x)=Q（x)G(x)＋R(x)だ。
R(x)＝A(x)－Q（x)G(x)だけど、係数がmod2だから、1≡-1（mod2)なので、引き算はたし算に直せる。また、Q(x)G(x)はmod(x^n-1)ではn-1次以下になるから、符号多項式になるね。
だから、
R(x)=A(x)+Q（x)G(x)(mod (x^n-1)
はn-1次以下の符号多項式になる。
しかも、さっき、次数はQ(x)の次数であるm未満だ。
最小のはずのG(x)の次数を下回るとは何事だ！矛盾だ！
ではない。
R(x)が定数式であればよい。
符号多項式が巡回符号だとしたら、定数は偶数パリティだから、オールゼロしかない。
つまり、「０という多項式」になるね。
結論。
巡回符号の多項式たちをあつめた次数最小の式Gは多項式たちの最大公約数のように
すべてを割り切る式になる。
言い換えると、「すべてGの倍数になる」から、
Gに多項式をかけると多項式ができる。
巡回符号多項式の生成元になっているということだね。
だから、Gを「生成多項式」と呼ぼう。
２．巡回符号を作ろう
＜(ｎ,ｋ)巡回符号＞
情報ビットがk、検査ビットがn-kの(n,k)巡回符号を考えよう。
符号語の場合の数は情報ビット数から2^kになるのはいいですね。
符号多項式Aには定数項もありうるので、次数はｎ-1以下となるね。
ここで、生成多項式Gの次数をmで、A＝QGだとしよう。
AはGで割り切れるから、xAもGで割り切れる。
xAを(x^n-1)で割った余りRも符号多項式になるのでGで割り切れる。
ということは、
xA-Rは(x^n-1)でもGでも割り切れる。
Gの次数mはn-1以下だから、
Gは(x^n-1)の約数多項式であるとわかるね。
さて、
A=QGから、Qの次数はn-m-1以下になる。
この次数からQを符号語にすれば、n-mビットにおさまるので、Qは2^(n-m)通りできるね。
しかし、Ａの個数は2^kあり、
A=QGからAとQは１対１対応。
結局は同数なので、指数が一致することになる。
k=n-m
言い換えると、
m=n-k
これが検査ビット数だ。
つまり、最大公約数のような存在Gの次数が、
n-kという検査ビット数で得られるということが
判明しましたね。
＜(7,4)巡回符号＞
たとえば、(7,4)巡回符号を作ってみよう。
検査ビットが7-4=3だから、Gの次数を3にしましょう。
x^7-1=(x^4+x^2+x+1)(x^3+x+1)=(x+1)(x^3+x^2+1)(x^3+x+1)(係数はmod2で演算）
だから、(x^3+x^2+1)が(x^3+x+1)がGの候補となるね。
G=1+x+x^3としてみよう。
情報ビットi=[1,0,1,0]の符号語を作る。
対応する多項式I＝1+x^2だから、
対応する符号語多項式A=IG=(1+x^2)(1+x+x^3)=1+x+x^2+x^5から
符号語候補[1,1,1,0,0,1,0]ができるがビット数7はよいが、情報ビット部分が壊れている。
方針を変える。
情報ビットを検査ビット数3だけ高位に移動して壊れるのを防ぐ。
x^3I=x^3(1+x^2)=x^3+x^5⇒[000, 1,0,1,0]
低位ビットに検査ビットを入れたい。
しかし、Gの次数が3だからG=1+x+x^3を符号にした[1,1,0,1]という4ビットを3ビットに
入れることはできない。
そこで、x^3IをGで割った商をQ,余りPとする。
x^3I=QG+P
余りPを使おう。
x^3I=x^3+x^5=x^2(1+x+x^3)+x^2から、
P＝x^2で、符号にすると、[0,0,1]だから3ビットとなり
検査ビットの場所に収まる！
A＝x^3I+P=x^2+x^3+x^5となり、
符号では
[0,0,1,1,0,1,0]のように、
検査ビットと情報ビットに分離できた。
それだけではありません。
A=x^3I+P=QG+P+P=QG+2P≡QG＝x^2(1+x+x^3)となり、AはGで割り切れます。
A=IGで失敗しましたが、
Iを3シフトしてGで割った商Qと余りPを使い、I倍をQ倍にすることで、
Gが生成多項式になるということも壊さず、情報ビットの隔離もできたのです。
これで、16通りの巡回符号を作ることができるね。
＜巡回符号のシンドローム＞
では、巡回符号の誤りを見つけるためのシンドローム（誤りの症候）はどうすれば
出せるでしょうか。
i番目に誤りがある場合は雑音多項式をE=x^iとします。
正しい符号はA=QGとすれば、
１つ誤っている符号語は
A'=A+E=QG+x^iとなりますね。
A'をG（3次式）で割った余りSは2次式です。
S=０ならば正しいですが、Sがゼロでないときは誤りがあります。
A’＝x^i(mod G)ですから、ｘ^iをGで割った余りがSになります。
S=e_0 + e_1 x + e_2 x^2
とおけます。
だから、Eの係数を分離した。[e1,e2,e3]で誤りが識別できるでしょう。
つまり、S＝x^i (mod G)
がシンドローム多項式ですね。
だから、iが別ならSも別になるとしたら、
単一誤りの位置が特定できます。
これはハミング符号と同じことなので、「巡回ハミング符号」と呼べますね。
これは、ただの古典ではありません。
（272,190)符号は8ビットのランダム誤りまで訂正できるとして、
１チップにLSI化されて、デジタル放送で使われているようです。
３．振り返り
＜振り返り＞
(7,4)巡回ハミング符号では
情報ベクトルi=[1,0,1,0]のとき、
G=1+x+x^3=>[1,1,0,1]
検査ビットがx^3I(mod G)=x^2からc=[0,0,1]となり、
送信ベクトルがa=[0,0,1,1,0,1,0]となったね。
誤りを検出するために、
iを０～6とするとき、E=x^iとaの多項式表現の和Sにして係数をmod 2にするから
i番目だけが01反転がおきる。
（テキストによっては、多項式表現のときに、
ベクトルの左から順に高位にしているものがあったり、
送信ベクトルを[c,i]ではなく、[i,c]の順にしているものもある。
その著者のルールを確認してください。
一貫性があれば、どちらでも理解するためだけなら問題ないでしょう。）
さて、高次数を高位に係数分離して整数表示すれば、
x^i÷（1+x+x^3）の筆算は100....÷1011とかける。
また、
排他的論理和の引き算は-1＝１だから、大きい方から小さいをひく。
x^3(mod G)は1000÷1011=1余り11からx+1→高次数を右もどす[1,1,0]
x^4(mod G)は10000÷1011=10余り110からx^2+x→高次数を右もどす[0,1,1]
x^5(mod G)は100000÷1011=101余り111からx^2+x+1→高次数を右もどす[1,1,1]
x^6(mod G)は1000000÷1011=1011余り101からx^2+x+1→高次数を右もどす[1,0,1]
これから、エラーごとにシンドロームsが決まるね。
i = ０：[1,0,1,1,0,1,0] s=[1,0,0]１スタートで1番目
i = １：[0,1,1,1,0,1,0] s=[0,1,0]１スタートで2番目
i = ２：[0,0,0,1,0,1,0] s=[0,0,1]１スタートで3番目
i = ３：[0,0,1,0,0,1,0] s=[1,1,0]１スタートで4番目
i = ４：[0,0,1,1,1,1,0] s=[0,1,1]１スタートで5番目
i = ５：[0,0,1,1,0,0,0] s=[1,1,1]１スタートで6番目
i = ６：[0,0,1,1,0,1,1] s=[1,0,1]１スタートで7番目
正しい：[0,0,1,1,0,1,0] s=[0,0,0]
課題：シンドロームをみてエラー位置を見つけるようすをgeogebraで視覚化しよう。
タイトルは「巡回符号のシンドロームとエラー訂正」
# 受信７ビット (1〜7番)、円環は点線でクリーム色
P = Sequence(Rotate((2, 0), (k-1) * 360°/ 7, (0, 0)), k, 1, 7)
Circle((0,0), 2)
# 送信語a
a = {0, 0, 1, 1, 0, 1, 0}
# エラー位置 (1〜7: 該当ビット反転、8: エラーなし)スライダーは見出しが「エラー位置」とし、
#ラベルは見出しのみとし、アニメーションをOnにする。
err = Slider(1, 8, 1)
# シンドローム列 (geogebraは１スタートで数える）
Ss={{1,0,0},{0,1,0},{0,0,1},{1,1,0},{0,1,1},{1,1,1},{1,0,1},{0,0,0}}
# 受信語 r (1箇所エラーの反転)とビット表示
r = Sequence(If(err == k, 1 - Element(a, k ), Element(a, k)), k, 1, 7)
Sequence(Text(Element(r, k ), Rotate((2.4, 0), (k-1) * 360° / 7, (0, 0))), k, 1, 7)
# シンドローム(errに対応）
s=Element(Ss,err)
# テキスト表示
text0= Text("" + c + "を送信しました！",(-4,5))
text1= Text("受信語は = " + r + "、シンドロームは" + s + "", (-4, 4))
text2= Text(If(s == {0,0,0}, "【シンドローム 0】エラーなし!", "【エラー検出】" + err + "番目 に誤りがあります"), (-4, 3))
#エラー点は赤で×で、大きさを6にする。
E=if(err<8,Rotate((2,0),(err-1)*((360°)/(7)),(0,0)))