昨日までの記事で結構計算の誤りが発見されました。もし実際に計算などをしようと思っている方は一応チェックして下さい。
誤り訂正では誤りがあるかどうかのチェックに受信したデータからシンドロームというものを計算して、その結果から判断できる、としました。
早い話が生成多項式で割ってみて余りがオールゼロでなければ（多分一部だけゼロというのはないと思います）誤りがあるということでした。
それは生成多項式の因数でそれぞれ割るということは、E(X) というエラー多項式があると次のような計算をしているということから分かります。
S0(X) = E(X) / (X + 1)
S1(X) = E(X) / (X + α)
S2(X) = E(X) / (X + α^2)
S3(X) = E(X) / (X + α^3)
一般的には、
Sn(X) = E(X) / (X + α^n)
繰り返しますが、シンドローム S(X) は誤り多項式のみみ依存し送信されたデータには無関係と云うことです。
そこで今一つだけエラーがあると仮定して、受信データ列の i 桁目(この場合は、i = 0 ～ 9、0 が一番右)がエラーでエラー量は e だとします。E(X) = e･X^i です。
S(X) と計算してみます。
S0(X) = E(X) / (X + 1)
ですから、i > 0 の時（i = 0 はそれがそのまま S0）
e･X^(i-1) + e･X^(i-2) + e･X^(i-3)
----------------------------------------
X + 1 | e･X^i
e･X^i + e･X^(i-1)
-------------------------
e･X^(i-1)
e･X^(i-1) + e･X^(i-2)
----------------------
e･X^(i-2) + e･X^(i-3)
・・・・・・・・・・
---------------------
e
となります。すなわち S0 はエラー量 e そのものを表します。
その他のシンドロームはどうでしょうか。以下の式では書式の都合上αを a とします。i = 0 の時は計算するまでもなく S1 = e･a です。
e･X^(i-1) + e･a･X^(i-2) + e･a^3･X^(i-3)
----------------------------------------
X + a | e･X^i
e･X^i + e･a･X^(i-1)
-------------------------
e･a･X^(i-1)
e･a･X^(i-1) + e･a^2･X^(i-2)
--------------------------
e･a^2･X^(i-2) + e･a^3･X^(i-3)
・・・・・・・・・・・・・・
-----------------------------
e･a^i
ということで、S1 = e･a^i すなわちエラー量とαのエラー桁乗ということになります。
以下、同様な計算をしていくと、
Sn = e･α^(ni) ：n = 0 ～ m（シンドロームの個数、パリティデータ数）
というのが確認できます。
今一つだけエラーがあるとしたわけですから、以上の計算から二つの式を取り出して「エラー量」と「エラー桁」を求めれば訂正が出来るというわけです。
要するに、
e = S0
i = logα(S1 / S0)
いきなり log ってなんだよ、と思うかも知れませんが、ご安心下さい。
S1 / S0 の結果は 8 ビットの数値ですが、それをα^i となりますから表示上は底がαの log で i を表しただけです。実際には前の表を使ってα^n の n を求めるだけです。
では複数あった場合との区別が付くのか、ということは確認しておかなくてはいけません。そこで S2 を引っ張り出してきます。
S2 = e･a^(2i)
エラーがもし複数個有ったとすると、先の e と i を求める計算では何も考えずに計算しただけなのでそれで良いのかどうか分かりません。しかしさらに S2 の情報を確認することで e と i が妥当であるならば一個のエラーだけがあって、それを訂正できたと言えます。つまり e･a^(2i) を計算してみて S2 と一致すれば一個エラーの訂正は正しい、といえます。
実際にはあらかじめ S2 * S0 - (S1 ^2）を計算することでこれがゼロになったときエラーが一つしかないから、先の計算で e と i を求めれば良い、ということと判断します。
エラーの場所とエラー量がわかったので受信データの中からその場所にエラー量を足して（本当は引いてだが、XOR なので同じ）エラー訂正完了となります。
ということでまずはエラーが一個だけの場合のエラー検出とエラー訂正をしてみました。
次回は実際の計算例をやってみます。
誤り訂正では誤りがあるかどうかのチェックに受信したデータからシンドロームというものを計算して、その結果から判断できる、としました。
早い話が生成多項式で割ってみて余りがオールゼロでなければ（多分一部だけゼロというのはないと思います）誤りがあるということでした。
それは生成多項式の因数でそれぞれ割るということは、E(X) というエラー多項式があると次のような計算をしているということから分かります。
S0(X) = E(X) / (X + 1)
S1(X) = E(X) / (X + α)
S2(X) = E(X) / (X + α^2)
S3(X) = E(X) / (X + α^3)
一般的には、
Sn(X) = E(X) / (X + α^n)
繰り返しますが、シンドローム S(X) は誤り多項式のみみ依存し送信されたデータには無関係と云うことです。
そこで今一つだけエラーがあると仮定して、受信データ列の i 桁目(この場合は、i = 0 ～ 9、0 が一番右)がエラーでエラー量は e だとします。E(X) = e･X^i です。
S(X) と計算してみます。
S0(X) = E(X) / (X + 1)
ですから、i > 0 の時（i = 0 はそれがそのまま S0）
e･X^(i-1) + e･X^(i-2) + e･X^(i-3)
----------------------------------------
X + 1 | e･X^i
e･X^i + e･X^(i-1)
-------------------------
e･X^(i-1)
e･X^(i-1) + e･X^(i-2)
----------------------
e･X^(i-2) + e･X^(i-3)
・・・・・・・・・・
---------------------
e
となります。すなわち S0 はエラー量 e そのものを表します。
その他のシンドロームはどうでしょうか。以下の式では書式の都合上αを a とします。i = 0 の時は計算するまでもなく S1 = e･a です。
e･X^(i-1) + e･a･X^(i-2) + e･a^3･X^(i-3)
----------------------------------------
X + a | e･X^i
e･X^i + e･a･X^(i-1)
-------------------------
e･a･X^(i-1)
e･a･X^(i-1) + e･a^2･X^(i-2)
--------------------------
e･a^2･X^(i-2) + e･a^3･X^(i-3)
・・・・・・・・・・・・・・
-----------------------------
e･a^i
ということで、S1 = e･a^i すなわちエラー量とαのエラー桁乗ということになります。
以下、同様な計算をしていくと、
Sn = e･α^(ni) ：n = 0 ～ m（シンドロームの個数、パリティデータ数）
というのが確認できます。
今一つだけエラーがあるとしたわけですから、以上の計算から二つの式を取り出して「エラー量」と「エラー桁」を求めれば訂正が出来るというわけです。
要するに、
e = S0
i = logα(S1 / S0)
いきなり log ってなんだよ、と思うかも知れませんが、ご安心下さい。
S1 / S0 の結果は 8 ビットの数値ですが、それをα^i となりますから表示上は底がαの log で i を表しただけです。実際には前の表を使ってα^n の n を求めるだけです。
では複数あった場合との区別が付くのか、ということは確認しておかなくてはいけません。そこで S2 を引っ張り出してきます。
S2 = e･a^(2i)
エラーがもし複数個有ったとすると、先の e と i を求める計算では何も考えずに計算しただけなのでそれで良いのかどうか分かりません。しかしさらに S2 の情報を確認することで e と i が妥当であるならば一個のエラーだけがあって、それを訂正できたと言えます。つまり e･a^(2i) を計算してみて S2 と一致すれば一個エラーの訂正は正しい、といえます。
実際にはあらかじめ S2 * S0 - (S1 ^2）を計算することでこれがゼロになったときエラーが一つしかないから、先の計算で e と i を求めれば良い、ということと判断します。
エラーの場所とエラー量がわかったので受信データの中からその場所にエラー量を足して（本当は引いてだが、XOR なので同じ）エラー訂正完了となります。
ということでまずはエラーが一個だけの場合のエラー検出とエラー訂正をしてみました。
次回は実際の計算例をやってみます。