具体的に計算してみる

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

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

G(x) = x² + 4x + 3

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

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

I(x) = 3x + 1

であり、

I(x)x² = 3x³ + x²

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

R(x) = 35x + 33

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

W(x) = I(x)x² - R(x) = 3x³ + x² - 35x - 33

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

W(x) = 3x³ + x² + 0x + 2

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

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

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

Y(x) = 3x³ + 4x² + 0x + 2

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

Y(2) = 3×2³ + 4×2² + 0×2 + 2 = 42
Y(4) = 3×4³ + 4×4² + 0×4 + 2 = 258

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

Y(x) = W(x) + exⁱ     ...(1)

と置くと、

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

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

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

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

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

W(x) = Y(x) - 3x²
      = 3x³ + 4x² - 3x² + 0x +2
      = 3x³ + x² + 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 と考えても良いでしょう）

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

素数進数のリードソロモン符号

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

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

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

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

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

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

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

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

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

G(x) = x² - 6x + 8

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

G(x) = x² + 4x + 3

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

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

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

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

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

リードソロモン符号への道

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

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

と考え始めると

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

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

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

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

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

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

この魅惑のリードソロモン符号の解説はまた次回！

多項式の符号化/復号のまとめ

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

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

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

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

【復号】
D1   G(x)の根をa₁, a₂, …, a_kとし、Y(a₁), Y(a₂), …, Y(a_k)を求める。
D2   Y(x) = W(x) + e₁xⁱ¹ + … + e_hx^ih とY(a₁), Y(a₂), …, Y(a_k)から k 個の連立方程式を作り、e₁, …, e_h, i₁, …, i_h を求める。ただし h = k/2 。
D3   求まった e₁, …, e_h, i₁, …, i_h を用いて W(x) = Y(x) - (e₁xⁱ¹ + … + e_hx^ih) を計算する。

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

符号化の方法

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

W'(x) = b (x - a₁) (x - a₂) … (x - a_k)        ...(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)x^k - R(x)        ...(2)

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

式(1)(2)から

I(x)x^k - R(x) = G(x) Q(x)        ...(3)

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

I(x)x^k = G(x) Q(x) ＋R(x)        ...(3)

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

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

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

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

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

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

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

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

I(x)x² = x³ + 5x²        ...(7)

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




これで

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

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

W(x) = x³ + 5x² +7x + 3        ...(9)

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

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