※ G(X) の計算を間違えていました。
前回は具体的なデータ列に対してチェックデータを付けて送信符号を作ってみました。
この例を使いながら送信符号の性質、エラーが付加された場合について説明していこうと思います。何しろ手計算が大変で間違いをやらかしている可能性がありますので、その際にはご容赦願います。
送信符号はこういう計算を行った結果でした。
T(X) = I(X)･X^4 + {I(X)･X^4}mod{G(X)}
ここで G(X) は、
G(X) = (X + 1)(X + α)(X + α^2)(X + α^3)
= X^4 + α^75･X^3 + α^249･X^2 + α^78･X + α^6
= X^4 + (0Fh)･X^3 + (1Bh)･X^2 + (78h)･X + (40h)
※ 10/11 修正
でした。以後の議論では最終結果はあまり関係なく、一番最初の X の一次式の積で表されている式が重要になってきます。
さて、T(X) は I(X) を 4 桁ずらしたものを G(X) で割ってその余りを足したものなので、T(X) 自体は G(X) で割り切れます。言い換えれば送信符号が G(X) で割り切れるように加工したと云うことです。G(X) は、(X + 1)(X + α)(X + α^2)(X + α^3) なので、T(X) は (X + 1) でも (X + α) でも (X + α^2) でも (X + α^3) でも割り切れるのはお分かりかと思います。ここが重要な性質ということになります。
さて、例では送信データ列は、
3Ch, 15h, 74h, BCh, 1Fh, 2Dh, 30h, 5Fh, BFh, 03h
ということで T(X) としては、
T(X) = (3Ch)･X^9 + (15h)･X^8 + (74h)･X^7 + (BCh)･X^6 + (1Fh)･X^5 + (2Dh)･X^4 + (30h)･X^3 + (5Fh)･X^2 + (BFh)･X + (03h)
でしたが、これが誤りなく R(X) として受信されたとすると、R(X) は T(X) そのままですから、G(X) で割り切れます。もちろん、(X + 1) でも (X + α) でも (X + α^2) でも (X + α^3) でも割り切れます。
ここにエラーが発生したとします。
エラーというのはデータが化けた、という状態ですからどこかのデータ列のどこかの桁に差分が生じたということになります。
このエラーも多項式で表すことが出来ます。この例の場合では 10桁のどこか、あるいは複数の箇所に現れるわけですから、これを E(X) とすると、
E(X) = E0･X^9 + E1･X^8 + E2･X^7 + E3･X^6 + E4･X^5 + E5･X^4 + E6･X^3 + E7･X^2 + E8^X + E9
となります。これが送信データ列に付加されて誤りを含んだ受信データ列となるわけです。
式で書くと、
R(X) = T(X) + E(X)
さてここからが誤り訂正の本番です。キーポイントは生成多項式 G(X) で、T(X) がこれで割り切れた、というのが手がかりになります。最初に云っておきますと、多分 E(X) が G(X) で割り切れるような誤りが発生したらエラー訂正はおろか検出すらも不可だと思います。すごい確率だとは思いますが。理論的には Hamming 距離を越えるような誤りが発生した、ということだと思いますがここではこれ以上触れません。自分が説明出来ないからです。
（？！）
ということで、祈る思いで受信符号を G(X) で割ってその余りを見ることにします。
R(X) / G(X) = (T(X) + E(X)) / G(X)
= T(X) / G(X) + E(X) / G(X)
余りはどうなっているかというと、T(X) / G(X) は割り切れているので、
{R(X) mod{G(X)}} = {E(X) mod{G(X)}}
となって T(X) には全く無関係に発生したエラー符号だけに依存しています。もしエラーがなければ、E(X) = 0 ですから、R(X) は G(X) で割り切れる、その逆の対偶で「R(X) が G(X) で割り切れなければ E(X) = 0 ではない」ということになります。
これはどういうことかというと送信されたデータが G(X) で割り切れれば、受信データを G(X) で割って余りが出ればエラーがある、ということになります。もとデータ I(X) は G(X) で割り切れるかどうかはデータ次第ですが、これを割り切れるように送信データを加工すべくパリティデータを付けた、というわけです。以後の計算でもパリティデータを利用することはありません。パリティデータを含む送信データが G(X) で割り切れたという性質を利用して誤り検出～訂正を行っていくことになります。
さて、実際の処理では受信データを生成多項式 G(X) で直接割ることはしません。G(X) の因数である (X + 1)、(X + α)、(X + α^2)、(X + α^3) で別々に割ります。後でハード構成についても説明しますが、簡単な回路で構成できるからです。また別々に結果を得た方が使いやすいからです。もちろん、G(X) で割り切れないならば、上記の一次式のいずれでも割り切ることは出来ません。で、その結果をシンドローム S(X) と云います。S(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) が何を表しているかを解説します。
前回は具体的なデータ列に対してチェックデータを付けて送信符号を作ってみました。
この例を使いながら送信符号の性質、エラーが付加された場合について説明していこうと思います。何しろ手計算が大変で間違いをやらかしている可能性がありますので、その際にはご容赦願います。
送信符号はこういう計算を行った結果でした。
T(X) = I(X)･X^4 + {I(X)･X^4}mod{G(X)}
ここで G(X) は、
G(X) = (X + 1)(X + α)(X + α^2)(X + α^3)
= X^4 + α^75･X^3 + α^249･X^2 + α^78･X + α^6
= X^4 + (0Fh)･X^3 + (1Bh)･X^2 + (78h)･X + (40h)
※ 10/11 修正
でした。以後の議論では最終結果はあまり関係なく、一番最初の X の一次式の積で表されている式が重要になってきます。
さて、T(X) は I(X) を 4 桁ずらしたものを G(X) で割ってその余りを足したものなので、T(X) 自体は G(X) で割り切れます。言い換えれば送信符号が G(X) で割り切れるように加工したと云うことです。G(X) は、(X + 1)(X + α)(X + α^2)(X + α^3) なので、T(X) は (X + 1) でも (X + α) でも (X + α^2) でも (X + α^3) でも割り切れるのはお分かりかと思います。ここが重要な性質ということになります。
さて、例では送信データ列は、
3Ch, 15h, 74h, BCh, 1Fh, 2Dh, 30h, 5Fh, BFh, 03h
ということで T(X) としては、
T(X) = (3Ch)･X^9 + (15h)･X^8 + (74h)･X^7 + (BCh)･X^6 + (1Fh)･X^5 + (2Dh)･X^4 + (30h)･X^3 + (5Fh)･X^2 + (BFh)･X + (03h)
でしたが、これが誤りなく R(X) として受信されたとすると、R(X) は T(X) そのままですから、G(X) で割り切れます。もちろん、(X + 1) でも (X + α) でも (X + α^2) でも (X + α^3) でも割り切れます。
ここにエラーが発生したとします。
エラーというのはデータが化けた、という状態ですからどこかのデータ列のどこかの桁に差分が生じたということになります。
このエラーも多項式で表すことが出来ます。この例の場合では 10桁のどこか、あるいは複数の箇所に現れるわけですから、これを E(X) とすると、
E(X) = E0･X^9 + E1･X^8 + E2･X^7 + E3･X^6 + E4･X^5 + E5･X^4 + E6･X^3 + E7･X^2 + E8^X + E9
となります。これが送信データ列に付加されて誤りを含んだ受信データ列となるわけです。
式で書くと、
R(X) = T(X) + E(X)
さてここからが誤り訂正の本番です。キーポイントは生成多項式 G(X) で、T(X) がこれで割り切れた、というのが手がかりになります。最初に云っておきますと、多分 E(X) が G(X) で割り切れるような誤りが発生したらエラー訂正はおろか検出すらも不可だと思います。すごい確率だとは思いますが。理論的には Hamming 距離を越えるような誤りが発生した、ということだと思いますがここではこれ以上触れません。自分が説明出来ないからです。
（？！）
ということで、祈る思いで受信符号を G(X) で割ってその余りを見ることにします。
R(X) / G(X) = (T(X) + E(X)) / G(X)
= T(X) / G(X) + E(X) / G(X)
余りはどうなっているかというと、T(X) / G(X) は割り切れているので、
{R(X) mod{G(X)}} = {E(X) mod{G(X)}}
となって T(X) には全く無関係に発生したエラー符号だけに依存しています。もしエラーがなければ、E(X) = 0 ですから、R(X) は G(X) で割り切れる、その逆の対偶で「R(X) が G(X) で割り切れなければ E(X) = 0 ではない」ということになります。
これはどういうことかというと送信されたデータが G(X) で割り切れれば、受信データを G(X) で割って余りが出ればエラーがある、ということになります。もとデータ I(X) は G(X) で割り切れるかどうかはデータ次第ですが、これを割り切れるように送信データを加工すべくパリティデータを付けた、というわけです。以後の計算でもパリティデータを利用することはありません。パリティデータを含む送信データが G(X) で割り切れたという性質を利用して誤り検出～訂正を行っていくことになります。
さて、実際の処理では受信データを生成多項式 G(X) で直接割ることはしません。G(X) の因数である (X + 1)、(X + α)、(X + α^2)、(X + α^3) で別々に割ります。後でハード構成についても説明しますが、簡単な回路で構成できるからです。また別々に結果を得た方が使いやすいからです。もちろん、G(X) で割り切れないならば、上記の一次式のいずれでも割り切ることは出来ません。で、その結果をシンドローム S(X) と云います。S(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) が何を表しているかを解説します。