FC2ブログ

誤り訂正符号Blog

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

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

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


かぼちゃ具体的に計算してみる

前回、リードソロモン符号の生成多項式の作り方について述べましたが、この説明だけで本当にリードソロモン符号を使える方がどれだけいるのかというのは、はなはだ疑問であるので、もうちょっと具体的に計算をしてみます。

5進数をリードソロモン符号化する際の生成多項式は

G(x) = x2 + 4x + 3

であることを前回導きました。
これをつかって5進数で 31 という数字を符号化してみましょう。

以前の記事によると、情報多項式I(x)に情報点数(ケタ数) k = 2 の次数をかけた多項式をG(x)で割った余りR(x)を求めることが、第一ステップです。
31 を符号化するので

I(x) = 3x + 1

であり、

I(x)x2 = 3x3 + x2

ですので、これをG(x)で割って余りを求めると

R(x) = 35x + 33

となります。
第二ステップで

W(x) = I(x)x2 - R(x) = 3x3 + x2 - 35x - 33

と符号多項式を算出できます。
ここで係数を5で割って余りを取って

W(x) = 3x3 + x2 + 0x + 2

となります。
(-33 を 5 で割った余りは 2 です。数直線で考えるとすぐにご理解いただけます。)
ちなみに、この余りを取るという操作は生成多項式を作るときにもやりましたが、途中計算は通常の整数の演算で行って、 W(x) を求めた後に一度行うだけで問題ありません。
四則演算の前後で余りは変わらないので。

というわけでめでたくW(x)が求まったので、その係数を並べて 3102 という5進4桁の数を送ります。
(言うまでもないですが、上位2桁の 31 が情報部分、下位2桁の 02 がパリティ部分となっています)

そしてこれに誤りが加わって受信者が 3402 という数を受信したとして、誤りを訂正してみましょう。
受信多項式 Y(x) は

Y(x) = 3x3 + 4x2 + 0x + 2

となるので、これに生成多項式 G(x) の根である 2 と 4 を代入してみます。

Y(2) = 3×23 + 4×22 + 0×2 + 2 = 42
Y(4) = 3×43 + 4×42 + 0×4 + 2 = 258

また、誤りの数が1つであるという仮定のもと、

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

と置くと、

Y(2) = e×2i = 42     ...(2)
Y(4) = e×4i = 258

であり(W(2) = 0, W(4) = 0であることを利用)、

Y(4)/Y(2) = 2i = 258/42 = 4 (*注)

なので i = 2 と分かり、式(2)にこれを代入して e = 42/4 = 3 (*注) と分かります。

これを式(1)に代入してW(x)について解くと

W(x) = Y(x) - 3x2
      = 3x3 + 4x2 - 3x2 + 0x +2
      = 3x3 + x2 + 0x + 2

となり、もとの符号多項式を得られました。

めでたし!めでたし!

(*注)258/42 = 4, 42/4 = 3 に "?" と思われた方へ。
素晴らしい洞察力です!よく読み飛ばしませんでしたね!
ここでは ”5 で割った余りを取る世界”を考えているため、ちょっと特殊な計算が必要になります。
258/42 というのは分子分母それぞれの数字を5で割った余りを取り、3/2を計算していることと同じです。
普通に考えれば3/2 = 1.5 ですが、小数が出てくると計算が破綻してしまいます。
これは困った。
ところで割り算とは掛け算の逆演算、すなわち 3/2 を求めるということは

2x = 3

という方程式で x を求めることと同じです。
x = 4 のとき、左辺は 8 になり、5 で割った余りを取ると 3 なので、x = 4 は ”5 で割った余りを取る世界において”上記方程式の解となります。
よって、3/2 = 4 です。
(3/2 = 8/2 = 4 と考えても良いでしょう)

どうですか。
いよいよ騙されてる気がしてきましたね。
でもこれで良いのです。
この裏には興味深い代数学の世界があります。
が、それは追々と…。
スポンサーサイト


コメント

プラス?マイナス?

えにしともうします.
大変わかりやすいリードソロモン符号のご解説ありがとうございます.
他の教科書では
W(x) = I(x)x2 - R(x) = 3x3 + x2 - 35x - 33
のR(x)ところが正逆反転しており
W(x) = I(x)x2+ R(x) = 3x3 + x2 + 35x + 33
の形となっております.GF(2)ではプラスもマイナスも同じようですが,
プラスもマイナスも同じなのでしょうか?

Re: プラス?マイナス?

はじめまして。
大変興味深い質問をありがとうございます。

R(x)の定義にもよりますが、ここではI(x)x2を生成多項式G(x)で割った余りをR(x)としているのでマイナスが正しいです。

ただし、ご存知の通りGF(2のn乗)ではプラスとマイナスは同じになります。
多くの場合、GF(2のn乗)上のリードソロモン符号を使うので、それを前提にご指摘の教科書ではプラスで書いてあるのではないでしょうか(それか初めに述べたR(x)の定義が異なるか)。

ちなみに本記事の符号はGF(5)上のリードソロモン符号なのでプラスとマイナスは異なり、本来の意味通り -R(x) としなければなりません。

Re: プラス?マイナス?

さっそくのご助言ありがとうございました.

>R(x)の定義にもよりますが、ここではI(x)x2を生成多項式G(x)で割った余りをR(x)としているのでマイナスが正しいです。

よく考えてみればあたりまえなんですね.
I(x)*x^2/G(x)≡R(x) (mod G(x)) なので
I(x)*x^2/G(x)に何かをたしてG(x)で割り切れるよう送信符号にするには,
-R(x)をたすしかないですね.

でもなんで他の教科書はすべて+で書いてあるのか不思議です.

これからもよろしくお願いします.

Re: プラス?マイナス?

すみません、ほぼ同時に投稿して誤って消してしまったので、上記コメントは私が再投稿しました。

で、本題ですが、G(x)=(x-2)(x-4) と定義しようが、G(x)=(x+2)(x+4)と定義しようが、R(x)の正負には関係ありません。
生成多項式の根が入れ替わっているのに過ぎないので。
GF(5)において G(x)=(x+2)(x+4)=(x-3)(x-1)となります。

その本ではおそらくGF(2^n)上の符号に絞って書かれているのではないでしょうか。
前述したとおり、GF(2^n)ではプラスもマイナスも同じなので、それを利用してマイナスをプラスとして式を記述することはよくあります(R(x)に限らず。当然G(x)に関しても。)。
マイナスをプラスで書くことは、式の見やすさとか、実装の面で合理的であると思います。
専門家は無意識のうちにそのように書いていると思います。

もし、その本がGF(2^n)ではなく、一般的なガロア体について論じたものであれば、マイナスをプラスで書くことは明らかな誤りなので出版社に文句を言ってください!

本を見ていないので私が言えるのはこのくらいです。
ちょっと今度読んでみます。

Re: プラス?マイナス?

> すみません、ほぼ同時に投稿して誤って消してしまったので、上記コメントは私が再投稿しました。

あれれ、また前回のものが消えてしまいました。
一個上のコメントの一つ前のものは「えにし」さんからで
参照している教科書では本記事でのG(x)=(x-2)(x-4) をG(x)=(x+2)(x+4)と定義しているからR(x)の正負が反転するのではないか、というものでした。
参照している本は「やり直しのための工業数学」「スペクトル拡散技術」でよかったですか?

コメントありがとうございます.

>もし、その本がGF(2^n)ではなく、一般的なガロア体について論じたものであれば、マイナスをプラスで書くことは明らかな誤りなので出版社に文
句を言ってください!
私なりに解釈しまして,
GF(5)上で
☆thara産の解釈のように根が2,4であれば普通は(x-2)(x-4)と書きたくなりますよね.(中学校の2次方程式)そうするとR(x)=3で3を引けば
x^2I(x)%G(x)-3=R(x)-3=0 となって理屈にあいまして,
☆根が-2,-4つまり,3,1であれば(x+2)(x+4)となり,R(x)=2x+1
x^2I(x)%G(x)+2x+1=R(x)+2x+1=0 とR(x)を足せば何とかよろしいようです.
つまり根が正であればR(x)は足して,根が負であればR(x)を引けばよろしいとおもいます.
なんとも数学の専門家がみたら笑われそうですが,..
一応納得しております.
教科書はそのとおりです.教科書自体もそう考えると納得いきました.


畳み込み符号

えにしです.
やはりRS符号の根はtharaさんのように(x-2)(x-4)のようにしたほうが誰にもわかりやすいですよね.
さてさて
次は畳み込み符号に挑戦しております.
何とか符号化ビタビ復号が解けました.
tharaさんのわかりやすい御講釈お待ちしています.

うーん、なかなかうまく説明できなくてすみません。

前述したとおり、生成多項式の根の正負とR(x)の正負には関係がありません。
符号化の際にはR(x)を”引く”必要があります。

まず、ここが間違いです。

> ☆根が-2,-4つまり,3,1であれば(x+2)(x+4)となり,R(x)=2x+1
> x^2I(x)%G(x)+2x+1=R(x)+2x+1=0 とR(x)を足せば何とかよろしいようです.

GF(5)上において
R(x) + 2x + 1 = 2x + 1 + 2x + 1 = 4x + 2
で、0になりません。
(あと、本質ではありませんがR(x) = 3x + 1 のようです:計算ミス)

GF(2^p)(pは正の整数)上ではプラスとマイナスも同じですが、それ以外のガロア体では異なります。
つまりGF(5)上ではプラスとマイナスが異なるので本来の定義通りR(x)を引かねばなりません。

それでは何故上記教科書ではR(x)を「足す」と書かれているのか。
真相を知るべく(大げさ!)、その教科書「やり直しのための工業数学」を読みました。
読んでみると、「第10章 RS符号」の冒頭に「ここではGF(2^p)上の多項式で定義されるところのRS符号を扱う」という旨が書かれています。
結局同じことを繰り返し言うだけですが、GF(2^p)上ではプラスとマイナスも同じです。
したがって、GF(2^p)上では符号化の際にR(x)を「足す」ことでこと結局「引く」ことと同じことをやっていることになります。
#このR(x)を「足す」という式は8章の(13)式で「GF(2^p)上ではプラスとマイナスは同じ」という性質を用いて導出されています。

そして、もう一点。上記教科書では生成多項式G(x)を原始元αを用いて

G(x) = ( x + 1) ( x + α) …

と表現していることに関して。
これもGF(2^p)上だからOKということになります。
本来の定義は

G(x) = ( x - 1) ( x - α) …

です。
GF(2^p)上ではプラスとマイナスが同じなので

G(x) = ( x - 1) ( x - α) … = ( x + 1) ( x + α) …

とできるわけです。

結局は、上記教科書ではGF(2^p)上の符号を想定しているので「GF(2^p)上ではプラスとマイナスが同じ」という性質を使ってマイナスをプラスで表記している、ということに尽きます。
では何故わざわざマイナスをプラスで書くのか、という疑問もあるかもしれません。
これは「慣習」と言ってしまえばそれまでですが、プラスとマイナスが同じであればプラスに統一してしまった方が式としてすっきりしますし、実装面でも合理的であると思います(例えばプログラミングする際、マイナスは関数を用意せずプラスの関数で代用することができます)。

と、いったところでいかがでしょうか。

で、最後に一言だけ。
(これを言うと逆に混乱されるかもしれませんが)
符号化の際にR(x)を「足す」、生成多項式はG(x) = ( x + 1) ( x + α) … と覚えておいて実際はあまり問題ないと思います。
#ただし「プラス」でいいのはGF(2^p)の時だけ、ということは頭の隅に置いておくとよいと思います。

長々と「マイナスじゃないとダメ」と言っておいてなんなんだと思われるかもしれませんが、実用の面でGF(2^p)以外のガロア体上の符号を使うことはめったにないからです。
このブログでGF(2^p)ではないGF(5)を使ったのは、「拡大体」の知識なしにRS符号を使うためです。

本当に長くなりました。
不明点がありましたら、また言って下さい。
畳み込み符号の習得も頑張ってください。

承認待ちコメント

このコメントは管理者の承認待ちです

コメントの投稿

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

トラックバック

http://thara.blog29.fc2.com/tb.php/21-8e131f50

 | HOME | 

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