誤り訂正符号Blog

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

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

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


かぼちゃリードソロモン符号への道

前回まで紹介した多項式の符号化/復号法を実装しようとしたとき、

「さて、多項式の係数を何bitの変数にしようかな」

と考え始めると

「だまされた!送りたい情報に対して、符号多項式の係数の情報量が大きすぎて通信効率が悪すぎる!」

と思われるかもしれません。

いえいえ、だましたわけではありません!!

別途、符号多項式の係数をある特定区間の値にする方法があります。
とりあえずは多項式での誤り訂正の仕組みを説明するのに、整数係数の多項式を用いた方がわかりやすいのでそれを使っただけです。

それで、「符号多項式の係数をある特定区間の値にする」方法ですが、それを実現する符号の一つにリードソロモン符号があります。

リードソロモン符号では、q-2 次の符号多項式を用い、その係数を0からq-1の整数値にすることができます。
一つの係数の情報量は log2q なので、一つの符号多項式の情報量は (q-1)×log2q になります。
多項式の係数のうち、前回までと同じ議論で q-1-2t 個の係数を”送りたい情報”に割り当てることができ、受信多項式の t 個の係数の誤りを
訂正することができるのです。

この魅惑のリードソロモン符号の解説はまた次回!
スポンサーサイト


かぼちゃ多項式の符号化/復号のまとめ

いろいろと出てきて混乱されているかもしれないので、多項式の符号化/復号に関してまとめます。

送りたい情報を I(x)、生成多項式をG(x)、生成多項式G(x)の次数を k とします。

【符号化】
E1   I(x)xk を G(x)で割った余りR(x)を求める。
E2   W(x) = I(x)xk - R(x)   とする。

【通信過程】
W(x)に誤りが加わりY(x)となって受信側に到達する。

【復号】
D1   G(x)の根をa1, a2, …, akとし、Y(a1), Y(a2), …, Y(ak)を求める。
D2   Y(x) = W(x) + e1xi1 + … + ehxih とY(a1), Y(a2), …, Y(ak)から k 個の連立方程式を作り、e1, …, eh, i1, …, ih を求める。ただし h = k/2 。
D3   求まった e1, …, eh, i1, …, ih を用いて W(x) = Y(x) - (e1xi1 + … + ehxih) を計算する。

どうですか?
まとめてみると、結構すっきりしてますでしょう!?
簡単に書きましたが、実はD2の部分で連立方程式を解くのに結構技巧を要するのですが、またそれは後で。


かぼちゃ符号化の方法

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

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


かぼちゃ完!?

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

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

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

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

これは効率が悪い!

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

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

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







 | HOME | 

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