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