誤り訂正符号Blog

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

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

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


かぼちゃ符号化の方法

今回は送りたい情報を元に、いかにして多項式 W(x) を作るかという話をします。
誤りを訂正するには受信者が W(x) の根を知っている必要があるのですが、そもそも受信者が全部の根a1…akを知っていると、受信者はその根から

W'(x) = b (x - a1) (x - a2) … (x - ak)        ...(1)

が計算できるので、係数 b、つまり多項式の定数倍の情報しか送信者は付加することができません。
これはちょっと効率が悪いので、出し惜しみをして W(x) の一部の根のみを受信者に教えておくことにします。

W(x) = G(x) Q(x)        ...(1)

と因数分解して G(x) の根だけを受信者に教えることにすると、送信者がQ(x)を自由に作れます。
G(x) を生成多項式と呼び、Q(x) は何と呼ぶか知りません(!)。

これで受信者は送りたい情報から Q(x)を作って式(1)から W(x) を構成すれば、G(x)の根をk個としてk/2個の誤りを訂正できることになります。
で、Q(x)の作り方ですが、送りたい情報を直接 Q(x) に置いてもよいのですが、受信者が Q(x) を取り出すのに後で因数分解するのが面倒とか、W(x) の係数に直接送る情報が見えてた方が便利とか、いろいろ事情があって実際には送りたい情報の多項式を I(x) として

W(x) = I(x)xk - R(x)        ...(2)

という形式で W(x)を構成します。
k は生成多項式 G(x) の最高次数で R(x) は k 次より小さい多項式です(R(x) は俗に言うパリティの部分)。

式(1)(2)から

I(x)xk - R(x) = G(x) Q(x)        ...(3)

を満たすように Q(x), R(x) を決めることになります。
式(3)でR(x)を移項すると

I(x)xk = G(x) Q(x) +R(x)        ...(3)

となるので、R(x)はG(x)の次数より低いことに注意すると、R(x) は I(x)xk を G(x) で割った余りである、ということが分かります。
ちょっと直感的に分からなかった方は「17割る5の余りが2である」というのが

17 = 5*3 + 2        ...(4)

と表せることを思い出してください。
式(3)はこれの多項式版で I(x)xk が17、G(x) が5、Q(x) が3、R(x)が2に対応しています。

では、具体的に計算してみますか。
生成多項式 G(x) を

G(x) = (x + 1) (x + 3) = x2 + 4x + 3        ...(5)

として、送りたい情報I(x)を

I(x) = x + 5        ...(6)

とします。
G(x)の次数は 2 なので、I(x)にx2をかけて

I(x)x2 = x3 + 5x2        ...(7)

となり、これを G(x) で割って余り R(x) を求めます。

R(x)の算出


これで

R(x) = -7x -3        ...(8)

だと分かったので式(2)に代入して

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

となります。
やっと求まった!
実際にはコンピュータを使うので、計算は楽勝です。
G(x) の根 x = -1, -3 に対して W(-1)=0, W(-3)=0 とちゃんとなっています。

ところでこの W(x) を符号多項式と呼びます。
(散々今まででてきましたが、名を名乗ってませんでした。)
そして、このような I(x) から符号多項式 W(x) を導出する処理を符号化と呼びます。


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

前回は、送信者が 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符号は鬼門であるガロア体の知識が必須ですが、ある種のリードソロモン符号ならガロア体の知識がなくてもぎりぎり説明できるのではないかと。
あくまでもこのブログは実務家の皆さんに手っ取り早く誤り訂正符号を使っていただくことが目的なので、実用性の高いリードソロモン符号をさくっと説明することは、意味があることと思います。
多分、厳密な説明にはならないですが、専門書を読むための手引きになれば、と思っています。

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


«  | HOME |  »

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