前回は４つのデータに２つのチェックデータを付けることで、一つの誤りを発見して訂正できる、もし位置が分かっていれば二つまで訂正できるらしい、ということを非常に原始的な例で解説しました。
要は１つ誤りがあると、誤っている量と誤りがある位置の二つの情報が訂正するためには必要なので、変数が２つという連立方程式を解くために二つのチェックデータが必要だと云うことです。誤り位置が分かっていれば誤り量だけ分かれば良いので、冗長なデータとして二つあれば誤り量を計算できる、という大ざっぱな感触をもってもらえば良いかな、と思います。
さて前回の宿題で、誤り位置が分かれば二つの誤りデータを訂正できるとしましたが、どうやって誤り位置が分かったのかを考えてみます。
たとえば伝送データがアナログ的な波形とみて、そこにノイズが乗ってエラーが出ているのであれば、ノイズが出た場所が伝送されたデータのどこか分かれば誤り位置情報として使えるかも知れません。
ただ不確かですね。他にも色々考えられますが論理的により確かな方法を考えてみます。
たとえばこんなのはどうでしょうか。
伝送データ
a0, b0, c0, d0, e0, f0 (e0 = a0 + b0 + c0 + d0, f0 = a0 + 2b0 + 3c0 + 4d0)
a1, b1, c1, d1, e1, f1 (e1 = a1 + b1 + c1 + d1, f1 = a1 + 2b1 + 3c1 + 4d1)
a2, b2, c2, d2, e2, f2 (e2 = a2 + b2 + c2 + d2, f2 = a2 + 2b2 + 3c2 + 4d2)
a3, b3, c3, d3, e3, f3 (e3 = a3 + b3 + c3 + d3, f3 = a3 + 2b3 + 3c3 + 4d3)
s0, s1, s2, s3, s4, s5
(s0 = a0 + a1 + a2 + a3, s1 = b0 + b1 + b2 + b3, s3 = c0 + c1 + c2 + c3,
s4 = d0 + d1 + d2 + d3, s5 = e0 + e1 + e2 + e3, s6 = f0 + f1 + f2 + f3)
４つ一組のデータに対して、さらにこれらを４組（いくつでもいいが）組み合わせて、先頭から縦方向にチェックサムを付けてみます。
そうしておいて、今回のように b0 と c0 にエラーが発生したとして、a0 ～ f0 でデータをチェックしたらエラーはあるらしいが訂正が出来ない、となって他の行は大丈夫だったとします。そこで s0 ～ s6 と実際に受け取ったデータと比較してみたら、s1 と s2 がおかしかったということで、どうやら２番目と３番目のデータに誤りがあるということが分かります。
そこで１行目に戻って、２番目と３番目のデータが誤りがあるという情報に基づいて連立方程式を解くと、b0 と c0 の誤り量が分かったので、訂正できるということになります。
ではもっとたくさんチェックデータを付ければ、たくさんのデータが訂正できるようになるのか、というとこれは出来ます。もちろんその分有効なデータが減ります。
こんな感じになります。
a, b, c, d, e, f, g, h
ただし、
e = a + b + c + d
f = a + 2b + 3c + 4d
g = a + 4b + 9c + 16d
h = a + 8b + 27c + 64d
こういう要領で４つのチェックデータを付けてみました。４つありますから４つの連立方程式を作ることが出来て位置が分からない誤りなら２つの誤りまで、位置が分かっていれば４つのデータ誤りまで訂正できると思われます。
g, h における a, b, c, d の係数が位置番号のべき乗にしてありますが、適当に思いついたというか本などの解説を元に作ってみたというか、手計算したらべき乗にしておくと結果が得られやすそうだとか、そんな理由です。ずっと後に符号化についての解説を考えていますが、そこではべき乗が出てきます。なんか良いことがあるようです。
さて、このデータ系列の有効部分 a ～ d のいずれか二つに対して、p, q なる誤りが発生したとします。位置番号はそれぞれに対して m, n (1 ～ 4、整数、m < n ）とします。
受け取ったデータを元に e', f', g', h' を計算します。
ここで式の変形はやめますが、既知の数値で m を表すことができるので、以下頑張れば解くことは出来ます。
ですが、もっと簡単に考えれば m, n ともに正の整数で 1, 2, 3, 4 であり、m < n ですから、(8)式の m に 1 から順番に入れていって整数の n が求まればそれが答えとしても良さそうです。実際の誤り訂正のプロセスでもそういった解析的でない方法が使われます。
プログラムで解くならばそういう方が速いのではないかと思います。
さて、以上の例は概念というか雰囲気を感じてもらう程度のもので抜けだらけです。本質的な流れはだいたいこのようなものですが、このままでは実用に耐えられません。というか使えません。
どんなことが課題になるか挙げてみます。
１．実際のデータに制限が必要。
２．制限があるなかで四則演算が何らかの定義されていないといけない。
３．演算の結果も上述の制限の中に入っていなくてはいけない。
１は何かというと実際のデータは、どのくらいの値になるのか、有効数字とかが何でもありです。しかしながらたとえば例で挙げた程度の方法でも入ってくる値（ユーザデータということにします）は何らかの範囲に制限されていないと計算の結果オーバーフローしたり、形式の違うデータを演算することになると思われます。電卓で手計算している分にはあまり実感がないとは思いますが。
とはいうものの、そういったものはコンピュータとしては何らかの符号化によって一般的にはバイト単位の集まりで表しているので、直接悩むことはないと思います。
ところがバイト単位でデータを処理するとすると、２の四則演算をどうするか、という問題に突き当たります。例でも連立方程式を解いたり、べき乗が入ったりしているのでもしこういった計算が実際に必要ならば（本当に必要です）、バイトデータとしてどう計算するか定義しなくてはいけません。
３ではその計算結果もバイト単位である必要があるということです。
単純に 00h - FFh のデータを 0 - 255 の整数値と解釈すると、その中で加算が行われただけで 255 をはみ出しますし、減算をすれば符号はマイナスになりえますし、掛け算は桁上がり、割り算は小数点以下が必要になります。こういった結果が出てしまうと誤り訂正の計算が間違えることになりますので、四則演算の工夫と同時にバイトによる数値表現になんらかの工夫が必要になります。
これらの問題を解決するために（元々は違うと思いますが）ガロア体や原始多項式とその根、シフトレジスタなどという非常にわかりにくい工夫が入ってきます。
ここではこれらにはすぐには触れないで、実際の誤り訂正の応用例を解説しながら、徐々にそういった数学的な内容に進んでいこうと思います。
要は１つ誤りがあると、誤っている量と誤りがある位置の二つの情報が訂正するためには必要なので、変数が２つという連立方程式を解くために二つのチェックデータが必要だと云うことです。誤り位置が分かっていれば誤り量だけ分かれば良いので、冗長なデータとして二つあれば誤り量を計算できる、という大ざっぱな感触をもってもらえば良いかな、と思います。
さて前回の宿題で、誤り位置が分かれば二つの誤りデータを訂正できるとしましたが、どうやって誤り位置が分かったのかを考えてみます。
たとえば伝送データがアナログ的な波形とみて、そこにノイズが乗ってエラーが出ているのであれば、ノイズが出た場所が伝送されたデータのどこか分かれば誤り位置情報として使えるかも知れません。
ただ不確かですね。他にも色々考えられますが論理的により確かな方法を考えてみます。
たとえばこんなのはどうでしょうか。
伝送データ
a0, b0, c0, d0, e0, f0 (e0 = a0 + b0 + c0 + d0, f0 = a0 + 2b0 + 3c0 + 4d0)
a1, b1, c1, d1, e1, f1 (e1 = a1 + b1 + c1 + d1, f1 = a1 + 2b1 + 3c1 + 4d1)
a2, b2, c2, d2, e2, f2 (e2 = a2 + b2 + c2 + d2, f2 = a2 + 2b2 + 3c2 + 4d2)
a3, b3, c3, d3, e3, f3 (e3 = a3 + b3 + c3 + d3, f3 = a3 + 2b3 + 3c3 + 4d3)
s0, s1, s2, s3, s4, s5
(s0 = a0 + a1 + a2 + a3, s1 = b0 + b1 + b2 + b3, s3 = c0 + c1 + c2 + c3,
s4 = d0 + d1 + d2 + d3, s5 = e0 + e1 + e2 + e3, s6 = f0 + f1 + f2 + f3)
４つ一組のデータに対して、さらにこれらを４組（いくつでもいいが）組み合わせて、先頭から縦方向にチェックサムを付けてみます。
そうしておいて、今回のように b0 と c0 にエラーが発生したとして、a0 ～ f0 でデータをチェックしたらエラーはあるらしいが訂正が出来ない、となって他の行は大丈夫だったとします。そこで s0 ～ s6 と実際に受け取ったデータと比較してみたら、s1 と s2 がおかしかったということで、どうやら２番目と３番目のデータに誤りがあるということが分かります。
そこで１行目に戻って、２番目と３番目のデータが誤りがあるという情報に基づいて連立方程式を解くと、b0 と c0 の誤り量が分かったので、訂正できるということになります。
ではもっとたくさんチェックデータを付ければ、たくさんのデータが訂正できるようになるのか、というとこれは出来ます。もちろんその分有効なデータが減ります。
こんな感じになります。
a, b, c, d, e, f, g, h
ただし、
e = a + b + c + d
f = a + 2b + 3c + 4d
g = a + 4b + 9c + 16d
h = a + 8b + 27c + 64d
こういう要領で４つのチェックデータを付けてみました。４つありますから４つの連立方程式を作ることが出来て位置が分からない誤りなら２つの誤りまで、位置が分かっていれば４つのデータ誤りまで訂正できると思われます。
g, h における a, b, c, d の係数が位置番号のべき乗にしてありますが、適当に思いついたというか本などの解説を元に作ってみたというか、手計算したらべき乗にしておくと結果が得られやすそうだとか、そんな理由です。ずっと後に符号化についての解説を考えていますが、そこではべき乗が出てきます。なんか良いことがあるようです。
さて、このデータ系列の有効部分 a ～ d のいずれか二つに対して、p, q なる誤りが発生したとします。位置番号はそれぞれに対して m, n (1 ～ 4、整数、m < n ）とします。
受け取ったデータを元に e', f', g', h' を計算します。
ここで式の変形はやめますが、既知の数値で m を表すことができるので、以下頑張れば解くことは出来ます。
ですが、もっと簡単に考えれば m, n ともに正の整数で 1, 2, 3, 4 であり、m < n ですから、(8)式の m に 1 から順番に入れていって整数の n が求まればそれが答えとしても良さそうです。実際の誤り訂正のプロセスでもそういった解析的でない方法が使われます。
プログラムで解くならばそういう方が速いのではないかと思います。
さて、以上の例は概念というか雰囲気を感じてもらう程度のもので抜けだらけです。本質的な流れはだいたいこのようなものですが、このままでは実用に耐えられません。というか使えません。
どんなことが課題になるか挙げてみます。
１．実際のデータに制限が必要。
２．制限があるなかで四則演算が何らかの定義されていないといけない。
３．演算の結果も上述の制限の中に入っていなくてはいけない。
１は何かというと実際のデータは、どのくらいの値になるのか、有効数字とかが何でもありです。しかしながらたとえば例で挙げた程度の方法でも入ってくる値（ユーザデータということにします）は何らかの範囲に制限されていないと計算の結果オーバーフローしたり、形式の違うデータを演算することになると思われます。電卓で手計算している分にはあまり実感がないとは思いますが。
とはいうものの、そういったものはコンピュータとしては何らかの符号化によって一般的にはバイト単位の集まりで表しているので、直接悩むことはないと思います。
ところがバイト単位でデータを処理するとすると、２の四則演算をどうするか、という問題に突き当たります。例でも連立方程式を解いたり、べき乗が入ったりしているのでもしこういった計算が実際に必要ならば（本当に必要です）、バイトデータとしてどう計算するか定義しなくてはいけません。
３ではその計算結果もバイト単位である必要があるということです。
単純に 00h - FFh のデータを 0 - 255 の整数値と解釈すると、その中で加算が行われただけで 255 をはみ出しますし、減算をすれば符号はマイナスになりえますし、掛け算は桁上がり、割り算は小数点以下が必要になります。こういった結果が出てしまうと誤り訂正の計算が間違えることになりますので、四則演算の工夫と同時にバイトによる数値表現になんらかの工夫が必要になります。
これらの問題を解決するために（元々は違うと思いますが）ガロア体や原始多項式とその根、シフトレジスタなどという非常にわかりにくい工夫が入ってきます。
ここではこれらにはすぐには触れないで、実際の誤り訂正の応用例を解説しながら、徐々にそういった数学的な内容に進んでいこうと思います。