FC2ブログ

誤り訂正符号Blog

誤り訂正符号に関してなんでも

かぼちゃスポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


かぼちゃ根の数と誤り訂正可能数

前回は、送信者が W(x) という多項式を送り、受信者が誤りを含む多項式 Y(x) を受信するという状況で

Y(x) = W(x) + exi        ...(1)

と置き、W(x)の2つの根をY(x)に代入して二つの方程式を作り、e, i を求めて誤りを訂正する、という手続きを説明しました。

式(1)は、誤りが一個という仮定でこのように置きました。誤りが0個の時は e=0 となるのでこれでOKですが、誤りが二個以上あるときは訂正不可能です。

そこで、誤りが二個ある場合は式(1)の代わりに

Y(x) = W(x) + e1xi1 + e2xi2        ...(2)

と置きます。
i1, i2 が誤りの位置、e1, e2が i1, i2 それぞれの位置でどれだけ値が変わっているかを示す変数となっています。
このように式(2)は4変数です。
4変数を同定するには、4つの方程式が必要です。
W(x)の根の数だけ方程式を作れるので、つまり二個の誤りを訂正するには、W(x)に4つの根が必要である、ということが分かります。

これをもとに発展させて考えると、t 個の誤りを訂正するには 2t 個の変数(t 個の誤り位置と t 個の係数の変化分)を同定する必要があるので、W(x)の根が 2t 個必要である、という結論に達します。
逆に言えば、W(x) が異なる 2t 個の根を持てば、t 個以下の誤りを正しく訂正することができる、ということですね。


かぼちゃ多項式の根が復号へのキー

今回は、簡単な例を通じて多項式の誤り訂正の仕組み見ていきます。
今回も前回と同じ多項式

W(x) = x3 + 5x2 + 7x + 3

を送信することにします。
ところで、この多項式を因数分解すると

W(x) = (x + 1)2 (x + 3)

となるので、 x=-1, -3 が W(x)=0 の解となっていることが分かります。
誤り訂正業界では「解」よりも「根」と呼ぶことがオシャレだとされているので(?)、以降 W(x)=0 を満たす x を W(x) のと呼ぶことにします。

さて、多項式 W(x) を送信してみましょう。
係数を取り出して

1, 5, 7, 3

という数列を送ります。
途中でノイズが入り、受信者には

1, 8, 7, 3

という数列が受信されたとします。
受信者はこの数列を並べて多項式を作ります。

Y(x) = x3 + 8x2 + 7x + 3

これを受信多項式と呼びます。

この多項式から、受信者は送信者がどんな多項式を送ったのかを推理することになります。
受信者は送信者が送った多項式の根は x=-1, -3 であるという知識のみを持っているとします。
なので、とりあえずその根を受信多項式 Y(x) に代入してみて

Y(-1) = 3        ...(1)
Y(-3) = 27        ...(2)

となり、あれ、0にならない!誤りがある、と判断できます。
じゃあ、どこにどういう誤りがあるのか、という話になるのですが、1つの係数が誤った場合、

Y(x) = W(x) + exi        ...(3)

となっているはずです。
e は係数値がどれだけ変化しているかを示し、i は誤りのあった係数の位置を示します。

ここで式(3)に x=-1, -3 を代入すると W(-1)=0, W(-3)=0であることから

Y(-1) = W(-1) + e(-1)i = e(-1)i        ...(4)
Y(-3) = W(-3) + e(-3)i = e(-3)i        ...(5)

となります。
すると式(1)(4)と式(2)(5)から、次の連立方程式が得られます。

e(-1)i = 3        ...(6)
e(-3)i = 27        ...(7)

ここまで来れば、後は楽勝ですね。
式(7)を式(6)で割って

3i = 9        ...(8)

したがって、 i=2ということが分かり、これを式(6)に代入して e=3 と分かります。
これらを式(3)に代入して

Y(x) = W(x) + 3x2        ...(9)

となるので、W(x)について解くと

W(x) = Y(x) - 3x2
      = x3 + 8x2 + 7x + 3 - 3x2
      = x3 + 5x2 + 7x + 3

エクセレント!
元の多項式を復元できました。

これで、多項式の根を使って誤りを訂正する、という感覚がつかめましたでしょうか?
何かだまされている気がしたら、もう一度、式をゆっくり追ってみてください。


かぼちゃ多項式で通信

さて、リードソロモン符号の第1回です。
リードソロモン符号を扱うに当たって避けて通れないのは多項式です。
多項式というのは、

x3 + 5x2 + 7x + 3

みたいなやつですね。
リードソロモン符号では送りたい情報を元に”ある条件”を満たす多項式を作って、それを送信します。
多項式を送信するといっても、そのまま送る必要はなくて、係数の列だけ送ります。
たとえば、上の多項式だったら

1, 5, 7, 3

という数列を送ります。
受信側でまた多項式に戻せばいいわけですから。

で、一体なぜ多項式なのか?
これが肝で、ちゃんとした説明は次回以降にしますが、簡単に言うと多項式にある数を代入すると 0 になるように作っておくのです。
上の例だと x=-3 を代入すると

(-3)3 + 5(-3)2 + 7(-3) + 3 = -27 + 45 -21 + 3 = 0

となっています。
もし通信途中で誤りがあって多項式の係数が変わってしまうと、 x=-3 を代入しても当然 0 にならなくなります(偶然 0 になることもありますが、その偶然性を減らすことも重要な要素です)。
これだけでも誤りがあったことが分かりますし、 x=-3 を代入した結果から、どの係数がどのように間違ったのかを知る方法があるのです。

具体的にどうやるのかは、次回以降のお楽しみに!


かぼちゃダビンチコードよりもリードソロモンコード

安直なタイトルですみません。この間、ようやくダ・ヴィンチ・コードを読み終えたもので…。ダ・ヴィンチ・コードは数千万部の大ベストセラーだそうですが、これから紹介するリードソロモン符号(Reed-Solomon Code)は間違いなくそれ以上の空前の大大ベストセラーでしょう。普段目につくことはないですが、CD/DVD, QRコード, ADSLといった身近なものから深宇宙通信まで使われている誤り訂正符号です。

ということで、これから数回にわたってこのリードソロモン符号の原理・使用法を紹介しようかと思います。
通常は「ハミング符号→ガロア体→巡回符号→BCH符号→リードソロモン符号」のような流れになるのですが、ハミング符号なんてあまり使わないし、応用上重要な2元BCH符号は鬼門であるガロア体の知識が必須ですが、ある種のリードソロモン符号ならガロア体の知識がなくてもぎりぎり説明できるのではないかと。
あくまでもこのブログは実務家の皆さんに手っ取り早く誤り訂正符号を使っていただくことが目的なので、実用性の高いリードソロモン符号をさくっと説明することは、意味があることと思います。
多分、厳密な説明にはならないですが、専門書を読むための手引きになれば、と思っています。

とにかく実用的で数学的に美しい神秘の符号「リードソロモン符号」の世界を体験してみましょう。
理解したときはかなり感動的ですよ。


かぼちゃ完!?

前回は情報を繰り返して符号化する方法を紹介しましたが、もうこれで事が足りるのでは?と思われたかもしれません。

いやいや、全然まだまだですです。

ということで、今回は繰り返すだけでは何が問題なのかについてご説明致しましょう。
これからからはちょっと玄人っぽく情報を0と1のビット列で表すことにします(今までがあまりに素人っぽかったっだけですが)。

"0"を送信するのに三回繰り返して送るとすると、"000"というビット列を送ることになります。
送りたい情報は"0"すなわち1ビットですが、実際に送信するのは"000"の3ビットとなります。
符号のビット列長に対する送りたい情報のビット列長の割合を符号化率と言うのですが、この場合符号化率は1/3になります。

これは効率が悪い!

と、思いませんか。
と、思ってください。
じゃないと話が進みません。
満員電車で三人分の席を占領して座っているやつがいたらむかつきますよね!!

繰り返し符号の場合、n回繰り返すとして符号化率は1/nになります。
最高の符号化率でも1/2です。
しかもこのときは誤り訂正ができません。

うーむ、もっと低い符号化率で多くの誤りを訂正できる符号を作れんかね、というのが次への動機となるのです。







«  | HOME |  »

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。