誤り訂正符号とは情報通信の際に生じるノイズを除去するための理論で、 情報に付加的なものをつけ加えることによってこれを実現する。
最も簡単なのは、同じ情報を繰り返し送ることである。 例えば YES と NO を 0 と 1 で表すことにし、 0 を送りたいときに、単に 0 を送るのではなく 00 と送る。 受信者は 01 または 10 を受け取ったときに、それは 00 または 11 のはずであるから、 誤りが生じたことが分かる。 000 を送ったときには 001, 010, 100 を受け取ったとき、 単に誤りが生じただけでなく 000 であった可能性が高いことが分かる。 信頼度を上げるためには繰り返しの回数を多くすれば良いが、 この場合、通信量が増えるというデメリットがある。
ここで説明するハミング符号は長さ 4 の 0 または 1 の 列を、長さ 7 にすることによって、そのうちに高々 1 つの誤りが含まれたときに 誤りを訂正できる。 二つ以上の誤りに対しては誤った答を返すことになるが、 これは繰り返し送る場合でも同じことで、 確実に正しい答を得る方法は理論的に存在しない。
ここで用いる数は 0 と 1 だけである。 1+1=0 と考えれば、他の四則演算は通常のように行うことが出来る。
長さ 4 の 0 または 1 の列は行ベクトルと考え、 それに (4, 7)-行列をかけることによって長さ 7 のベクトルを得る。 実際には
{{1,0,0,0,0,1,1},
{0,1,0,0,1,0,1},
{0,0,1,0,1,1,0},
{0,0,0,1,1,1,1}};
という行列をかける。
得られたベクトル、またはそれに誤りが加わったベクトルに
{{0,0,0,1,1,1,1},
{0,1,1,0,0,1,1},
{1,0,1,0,1,0,1}};
の転置行列を右からかけると、長さ 3 のベクトルが得られる。
これを 2 進数と見る。
この値が 0 であるならば誤りはないと考える。
この値が a であったならば、a 番目に誤りがあると判断し、
その 0 と 1 を入れ替える。
この様にして得られた長さ 7 のベクトルのはじめの 4 つの成分が、
はじめに与えたベクトルである。
実際のプログラムを見てみよう。
#include <stdio.h>
int G[4][7] =
{{1,0,0,0,0,1,1},
{0,1,0,0,1,0,1},
{0,0,1,0,1,1,0},
{0,0,0,1,1,1,1}};
int H[3][7] =
{{0,0,0,1,1,1,1},
{0,1,1,0,0,1,1},
{1,0,1,0,1,0,1}};
int main(int argc, char *argv[])
{
int word[4], codeword[7], syndrome[3], i, j, p;
printf("input a vector of length 4 : ");
for (i = 0; i < 4; i++)
scanf("%d", &word[i]);
for (j = 0; j < 7; j++) {
codeword[j] = 0;
for (i = 0; i < 4; i++)
codeword[j] += word[i] * G[i][j];
codeword[j] = codeword[j] % 2;
}
printf("code word is ");
for (j = 0; j < 7; j++)
printf("%d ", codeword[j]);
printf("\n");
printf("input a position for an error : ");
scanf("%d", &p);
if (p != 0)
codeword[p-1] = (codeword[p-1] + 1) % 2;
printf("recieved word is ");
for (j = 0; j < 7; j++)
printf("%d ", codeword[j]);
printf("\n");
for (i = 0; i < 3; i++) {
syndrome[i] = 0;
for (j = 0; j < 7; j++)
syndrome[i] += codeword[j] * H[i][j];
syndrome[i] = syndrome[i] % 2;
}
printf("syndrome is ");
for (j = 0; j < 3; j++)
printf("%d ", syndrome[j]);
printf("\n");
p = 0;
for (i = 0; i < 3; i++) {
p *= 2;
p = p + syndrome[i];
}
if (p != 0) {
printf("the word contains an error at %d\n", p);
codeword[p-1] = (codeword[p-1] + 1) % 2;
printf("the original word is ");
for (j = 0; j < 4; j++)
printf("%d ", codeword[j]);
printf("\n");
} else {
printf("the word is correct\n");
printf("the original word is ");
for (j = 0; j < 4; j++)
printf("%d ", codeword[j]);
printf("\n");
}
return 0;
}
以下は実行例である。
home$ ./a.out input a vector of length 4 : 1 0 0 1 code word is 1 0 0 1 1 0 0 input a position for an error : 6 recieved word is 1 0 0 1 1 1 0 syndrome is 1 1 0 the word contains an error at 6 the original word is 1 0 0 1誤り訂正が行われている様子が確認できると思う。
課題 11.01
上のプログラムではベクトルを表示するためのループがたくさん書かれている。
関数を用いることによってプログラムを分かり易くせよ。
課題 11.02
上のプログラムをベクトルと行列の掛け算を行う関数を用いるように書き換えよ。
ベクトルの入力を受け取る部分も関数にせよ。
課題 11.03
上のプログラムでは 0 と 1 を反転させるのに
a = (a + 1) % 2 という記述を用いた。
これは排他的論理和 XOR を用いて
a = a ^ 1
のように書くことができる。
これを試せ。
また 1 以外の数で同様のことを試し、2 進数を考えて、その動きを考察せよ。
例えば 11 ^ 3 などを試せ。
同様に 11 & 3 と 11 | 3 も試せ。