誤り訂正符号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) を導出する処理を符号化と呼びます。
スポンサーサイト


コメント

コメントの投稿

管理者にだけ表示を許可する

トラックバック

http://thara.blog29.fc2.com/tb.php/16-090ba7bb

 | HOME | 

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