FC2ブログ

誤り訂正符号Blog

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

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

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


かぼちゃ素数進数のリードソロモン符号

さて、手筈はそろいました!
今回は「素数進数のリードソロモン符号」を紹介します。
*通常「素数進数の~」などと呼ばないのですが、ここではイメージしやすいように、あえてそう呼びました。

では、うだうだ言わずにその符号化法をさっさとお教えしましょう。

q を素数とします。
n 乗して q で割った余りを算出したとき、n = 1, 2, ..., q - 2では 1 以外で、n = q - 1 のとき 1 となる数を α とします。
誤り訂正可能数をt、符号長を q - 1 として、生成多項式 G(x) を以下のように構成したものをリードソロモン符号と呼びます。

G(x) = ( x - α ) ( x - α2 ) … ( x - α2t )

なお、符号化・復号で使用するすべての多項式の係数値は q で割った余りを取ることにします。

これだけだとなんのこっちゃ分からないと思うので、実例を示します。

ここでは q = 5 とします。
このとき、 22 mod 5 = 4,  23 mod 5 = 3,  24 mod 5 = 1であるので、 α = 2 です。
誤り訂正数 t = 1 とすると、結局生成多項式 G(x) は

G(x) = ( x - 2 )( x - 4 )

となります。
これを展開すると

G(x) = x2 - 6x + 8

で、各係数を5で割って余りを取ると

G(x) = x2 + 4x + 3

を使うことになります。
符号化・復号の計算方法は係数値を5で割った余りを取ること以外、前回までに述べた多項式の符号化・復号方法とまったく同じです。

多項式の係数はすべて5で割って余りを取ることになるので、結局多項式の係数を並べたものは5進数となり、それを送受信することになるわけですね。

【追記】
より一般的にはリードソロモン符号の生成多項式は任意の整数 r を用いて

G(x) = ( x - αr ) ( x - αr + 1 ) … ( x - α2t + r - 1 )

と書くことができます。
上で述べたのは r = 1 としたものです。
なお世間一般では、計算の簡単さから r = 0 とすることが多いようです。
スポンサーサイト


コメント

コメントの投稿

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

トラックバック

http://thara.blog29.fc2.com/tb.php/19-56ae8a69

 | HOME | 

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