身の程知らずにも誤り訂正技術について解説（怪説？）してみることにしました。
私は「回想録」で書いたように光ディスクドライブの開発に携わっていたのですが、アナログ回路中心ながらもサーボをやったりデジタル部分もちょっとやったり I/F も少しいじったり、ディスクについて、光ピックアップについてと色々深さはともかく雑学的に手を出してきました。が、今回解説に挑戦する誤り訂正技術だけは数学的取り扱いが多いことからなかなか手が出ませんでした。
EXCEL：「頭が悪い？」
画蔵：「やかましい！」
そこで今一度本を読みながら自分なりに確かめてみて少しは理解が深まったようなので、解説してみようと思います。
数学的、理論的取り扱いはすでに良書がたくさん出ていると思うので、ここではどちらかというと使う側、設計する側の立場で見ていこうと思います。
さて誤り訂正技術はなぜ必要かということから簡単に説明します。
たとえばあるところに何かを表す信号があったとして、その信号を何らかの媒体を通じて伝えるとします。その媒体の信頼性が高くて信号を完全に正しく伝えてくれれば良いのですが、実際にはそうはいきません。媒体が電波ならばノイズが入ったり、光ディスクならばディスクのキズやゴミ、基板上で配線されているメモリや CPU 間の伝送ではノイズ、メモリ内部でのセル不良など信号を歪ませる要素はたくさんあります。
さらに今はそういった信号はデジタルデータだったりするものですから、一つのデータの伝送ミスが大変なデータ処理不能に陥ったりすることもありえます。アナログ信号の伝送ならその瞬間だけ変な信号が現れておしまいなんですけど。
M くん：「やっぱりアナログ信号処理の方が優れているのですね」
W 助手：「違う！」
ということでデジタルデータを伝送しようと思ったら、途中でデータの欠落やらデータ化けなどがあるという前提でシステム全体を考えなくてはいけません。システムも伝送経路、媒体の特徴を考慮してものでなくてはいけないのは言うまでもないことです。
この話はここまでということで乱暴に打ち切ってしまいますが、とにかくデータは伝送中に誤るものだということを理解しておいて下さい。
さて、非常に簡単な例で考えてみます。
送りたいデータが 100, 150, 210, 270 だったとします。一応正の整数とします。
これをそのまま 4 つのデータとして送ったらどうでしょうか。そしてこの中の一つにノイズか何かの影響で誤りが発生したとします。受信側ではどうやってその誤りを検出～訂正できるでしょうか。
ノイズ自身をデータとは別に観測できる機能があれば、もしかしたら誤り検出は出来るかも知れません。ですがデータを見ているだけでは検出も訂正も不可能です。
それはデータに冗長度がないので、どんな系列のデータかを推定する手段がないため受け取ったものをそのまま信じるしかないのです。
そこでよく聞くと思いますがチェックサムというデータをその系列の中に入れておいて、この場合なら 100 + 150 + 210 + 270 = 730 を付け加えて全部で 5 つのデータを送り、受け取った側で最初の 4 つの総和を計算して、730 になるかどうかをチェックすることで誤りがあったかどうかを検出することが出来ます。
この場合は 5 つのデータを送ることで、必要なデータ 4 つに対して一カ所までのデータ誤りが検出できるということで、80% の伝送効率でそういう性能を持つ、ということが言えます。
ただし、ここではその信頼性については触れていません。実際にはデータの符号間距離＝データが間違ったと認識できるデータの違いの議論が必要です。これについては今のところ上手く説明出来る気がしないので割愛します。専門書などを読んでみて下さい。
一言で言うと、前述の例では２番目のデータが 160 に化けたとして、それだけなら誤り検出できますが３番目のデータまで 200 に化けたら誤っていることすら分からない、というようなことです。
これだけでは訂正できないので、もう一つ冗長なデータを足して何とかしてみようと思います。
６番目のデータとして、100 x 1 + 150 x 2 + 210 x 3 + 270 x 4 = 2110 を加えます。
これを伝送した結果、150 が 160 に化けたとすると、チェックサムは 740 となって、送られてきた５番目のデータと比較するとどこかが 10 ずれたらしい。ということが分かります。６番目のデータを送られてきた必要なデータから作り直してみると、100 x 1 + 160 x 2 + 210 x 3 + 270 x 4 = 2130 となって送られてきた６番目のデータと比較すると 20 ずれていることが分かります。
よってエラーの場所は（６番目のデータ差分）／（５番目のデータ差分）= 2 ということで、結果として必要なデータの２番目が 10 ずれていることが求められます。
数値ではなく数式で一般化してもとめると、もとのデータを a, b, c, d、チェックデータは e, f とすると、
e = a + b + c + d
f = a + 2b + 3c + 4d
ここでエラーが b に発生して b' = b+p と伝送されたとすると、受け取ったデータは
a, b', c, d, e, f = a, b+p, c, d, e, f となります。
受け取ったデータの a, b', c, d から e', f' を計算すると、
e' = a + b+p + c + d
= a + b + c + d + p
= e + p
f' = a + 2(b+p) + 3c + 4d
= a + 2b + 3c + 4d + 2p
= f + 2p
ゆえに誤り量は e' - e = p
誤り位置は (f' - f) / (e' - e) = 2p / p = 2
ということで２番目のデータが p だけ違っているということになります。
ちなみにこの結果が 1 ならば、a が間違っている、2 ならば b、3 ならば c、4 ならば d という要領です。
では、チェックデータの方のどちらかが間違っていたとします。
伝送されたデータを a, b, c, d, e'=e+p, f とします。
チェックデータを再計算すると、元データは正しいので、e と f はそのままです。で、e と e' は違っていて、f はそのままですから e だけが p の分だけ間違っているということがわかります。f だけが誤っていた場合も同様です。
２カ所間違っていたとします。エラーの場所を m, n（いずれも 1 ～ 4、m < n）とすると、受け取ったデータは (a'), (b'), (c'), (d'), e, f ただし a', b', c', d' のいずれか二つは正しい、となります。
受け取ったデータから e', f' を計算すると、
e' = a + b + c + d + p + q
= e + p + q
f' = a + 2b + 3c + 4d + mp + nq
= f + mp + nq
これでは、p と q が分離できないので、誤り量も位置も分かりません。変数が m, n, p, q の４つで式が二つしかないからです。
さてここでどこからか密告が入ります。誤っているのは b, c だと。ただし値は分からない、とのことです。
そうなると e' と f' の式は連立方程式に早変わりします。m = 2, n = 3 ということになります。
f' の式において、p と q の係数が確定しているので、
p + q = e' - e
2p + 3q = f' - f
右辺は受信したデータとその計算結果から分かっているので、変数が二つで独立した式も二つと云うことで解くことが出来ます。
ここで分かったというか感じた雰囲気としては、２個の冗長なデータをチェックデータとして付け加えると、
・１個の誤りデータは検出できて訂正できるらしい。
・２個以上あるとエラーがあるらしい、ということが分かるかも知れない。（分からないことも十分あり得る）
・２個あってその位置が別の手段によって特定されていた場合は、訂正できるらしい。
３番目の誤り位置は誰が分かったのでしょうか。次回はその密告者を探してみようと思います。
私は「回想録」で書いたように光ディスクドライブの開発に携わっていたのですが、アナログ回路中心ながらもサーボをやったりデジタル部分もちょっとやったり I/F も少しいじったり、ディスクについて、光ピックアップについてと色々深さはともかく雑学的に手を出してきました。が、今回解説に挑戦する誤り訂正技術だけは数学的取り扱いが多いことからなかなか手が出ませんでした。
EXCEL：「頭が悪い？」
画蔵：「やかましい！」
そこで今一度本を読みながら自分なりに確かめてみて少しは理解が深まったようなので、解説してみようと思います。
数学的、理論的取り扱いはすでに良書がたくさん出ていると思うので、ここではどちらかというと使う側、設計する側の立場で見ていこうと思います。
さて誤り訂正技術はなぜ必要かということから簡単に説明します。
たとえばあるところに何かを表す信号があったとして、その信号を何らかの媒体を通じて伝えるとします。その媒体の信頼性が高くて信号を完全に正しく伝えてくれれば良いのですが、実際にはそうはいきません。媒体が電波ならばノイズが入ったり、光ディスクならばディスクのキズやゴミ、基板上で配線されているメモリや CPU 間の伝送ではノイズ、メモリ内部でのセル不良など信号を歪ませる要素はたくさんあります。
さらに今はそういった信号はデジタルデータだったりするものですから、一つのデータの伝送ミスが大変なデータ処理不能に陥ったりすることもありえます。アナログ信号の伝送ならその瞬間だけ変な信号が現れておしまいなんですけど。
M くん：「やっぱりアナログ信号処理の方が優れているのですね」
W 助手：「違う！」
ということでデジタルデータを伝送しようと思ったら、途中でデータの欠落やらデータ化けなどがあるという前提でシステム全体を考えなくてはいけません。システムも伝送経路、媒体の特徴を考慮してものでなくてはいけないのは言うまでもないことです。
この話はここまでということで乱暴に打ち切ってしまいますが、とにかくデータは伝送中に誤るものだということを理解しておいて下さい。
さて、非常に簡単な例で考えてみます。
送りたいデータが 100, 150, 210, 270 だったとします。一応正の整数とします。
これをそのまま 4 つのデータとして送ったらどうでしょうか。そしてこの中の一つにノイズか何かの影響で誤りが発生したとします。受信側ではどうやってその誤りを検出～訂正できるでしょうか。
ノイズ自身をデータとは別に観測できる機能があれば、もしかしたら誤り検出は出来るかも知れません。ですがデータを見ているだけでは検出も訂正も不可能です。
それはデータに冗長度がないので、どんな系列のデータかを推定する手段がないため受け取ったものをそのまま信じるしかないのです。
そこでよく聞くと思いますがチェックサムというデータをその系列の中に入れておいて、この場合なら 100 + 150 + 210 + 270 = 730 を付け加えて全部で 5 つのデータを送り、受け取った側で最初の 4 つの総和を計算して、730 になるかどうかをチェックすることで誤りがあったかどうかを検出することが出来ます。
この場合は 5 つのデータを送ることで、必要なデータ 4 つに対して一カ所までのデータ誤りが検出できるということで、80% の伝送効率でそういう性能を持つ、ということが言えます。
ただし、ここではその信頼性については触れていません。実際にはデータの符号間距離＝データが間違ったと認識できるデータの違いの議論が必要です。これについては今のところ上手く説明出来る気がしないので割愛します。専門書などを読んでみて下さい。
一言で言うと、前述の例では２番目のデータが 160 に化けたとして、それだけなら誤り検出できますが３番目のデータまで 200 に化けたら誤っていることすら分からない、というようなことです。
これだけでは訂正できないので、もう一つ冗長なデータを足して何とかしてみようと思います。
６番目のデータとして、100 x 1 + 150 x 2 + 210 x 3 + 270 x 4 = 2110 を加えます。
これを伝送した結果、150 が 160 に化けたとすると、チェックサムは 740 となって、送られてきた５番目のデータと比較するとどこかが 10 ずれたらしい。ということが分かります。６番目のデータを送られてきた必要なデータから作り直してみると、100 x 1 + 160 x 2 + 210 x 3 + 270 x 4 = 2130 となって送られてきた６番目のデータと比較すると 20 ずれていることが分かります。
よってエラーの場所は（６番目のデータ差分）／（５番目のデータ差分）= 2 ということで、結果として必要なデータの２番目が 10 ずれていることが求められます。
数値ではなく数式で一般化してもとめると、もとのデータを a, b, c, d、チェックデータは e, f とすると、
e = a + b + c + d
f = a + 2b + 3c + 4d
ここでエラーが b に発生して b' = b+p と伝送されたとすると、受け取ったデータは
a, b', c, d, e, f = a, b+p, c, d, e, f となります。
受け取ったデータの a, b', c, d から e', f' を計算すると、
e' = a + b+p + c + d
= a + b + c + d + p
= e + p
f' = a + 2(b+p) + 3c + 4d
= a + 2b + 3c + 4d + 2p
= f + 2p
ゆえに誤り量は e' - e = p
誤り位置は (f' - f) / (e' - e) = 2p / p = 2
ということで２番目のデータが p だけ違っているということになります。
ちなみにこの結果が 1 ならば、a が間違っている、2 ならば b、3 ならば c、4 ならば d という要領です。
では、チェックデータの方のどちらかが間違っていたとします。
伝送されたデータを a, b, c, d, e'=e+p, f とします。
チェックデータを再計算すると、元データは正しいので、e と f はそのままです。で、e と e' は違っていて、f はそのままですから e だけが p の分だけ間違っているということがわかります。f だけが誤っていた場合も同様です。
２カ所間違っていたとします。エラーの場所を m, n（いずれも 1 ～ 4、m < n）とすると、受け取ったデータは (a'), (b'), (c'), (d'), e, f ただし a', b', c', d' のいずれか二つは正しい、となります。
受け取ったデータから e', f' を計算すると、
e' = a + b + c + d + p + q
= e + p + q
f' = a + 2b + 3c + 4d + mp + nq
= f + mp + nq
これでは、p と q が分離できないので、誤り量も位置も分かりません。変数が m, n, p, q の４つで式が二つしかないからです。
さてここでどこからか密告が入ります。誤っているのは b, c だと。ただし値は分からない、とのことです。
そうなると e' と f' の式は連立方程式に早変わりします。m = 2, n = 3 ということになります。
f' の式において、p と q の係数が確定しているので、
p + q = e' - e
2p + 3q = f' - f
右辺は受信したデータとその計算結果から分かっているので、変数が二つで独立した式も二つと云うことで解くことが出来ます。
ここで分かったというか感じた雰囲気としては、２個の冗長なデータをチェックデータとして付け加えると、
・１個の誤りデータは検出できて訂正できるらしい。
・２個以上あるとエラーがあるらしい、ということが分かるかも知れない。（分からないことも十分あり得る）
・２個あってその位置が別の手段によって特定されていた場合は、訂正できるらしい。
３番目の誤り位置は誰が分かったのでしょうか。次回はその密告者を探してみようと思います。