情報理論 第10回　符号多項式による検査符号 (2) 練習問題解答例

• 練習問題1
上と同じ条件で、以下の情報源符号に検査符号を加えたものを記述せよ。
1. 0110
2. 1111


1. 0110
$x_5=1\oplus 1=0$
$x_6=1\oplus 1=0$
$x_7=1\oplus 0=1$
なので 0110 001 になる。


2. 1111
$x_5=1\oplus 1\oplus 1\oplus 0=1$
$x_6=1\oplus 0\oplus 1\oplus 1=1$
$x_7=1\oplus 1\oplus 0\oplus 1=1$
なので 1111 111 になる。

• 練習問題2
$k=4$, $G\left(x\right)=x^3+x^2+1$ の場合に、1000, 0100, 0010, 0001に検査符号を追加したものを記述せよ。また、それらの結果を使い、練習問題1の2つの情報源符号に検査符号を追加したものを求めよ。

最初の例と同様、1000, 0100, 0010, 0001を符号多項式に置き換えて $x^3$ をかけたものはそれぞれ$x^6$, $x^5$, $x^4$, $x^3$ になる。これらを $G\left(x\right)=x^3+x^2+1$ で割ると
　
　

となるので、この余りを検査符号に使うと、検査符号を付け加えたものは

• 1000 → 1000 110
• 0100 → 0100 011
• 0010 → 0010 111
• 0001 → 0001 101

となる。これらを組み合わせれば

1. 0110
$x_5=0\oplus 1=1$
$x_6=1\oplus 1=0$
$x_7=1\oplus 1=0$
なので 0110 100 になる。


2. 1111
$x_5=1\oplus 0\oplus 1\oplus 1=1$
$x_6=1\oplus 1\oplus 1\oplus 0=1$
$x_7=0\oplus 1\oplus 1\oplus 1=1$
なので 1111 111 になる。

• 練習問題3
上と同じ条件で、以下の符号を受け取ったときの情報源符号を記述せよ。ただし、変化は1回以下であるものとする。
1. 1111000
2. 0101110


1. 1111000
① : $x_1\oplus x_2\oplus x_3=1\oplus 1\oplus 1\ne 0$ ($x_5$ と等しくならない)
② : $x_2\oplus x_3\oplus x_4=1\oplus 1\oplus 1\ne 0$ ($x_6$ と等しくならない)
③ : $x_1\oplus x_2\oplus x_4=1\oplus 1\oplus 1\ne 0$ ($x_7$ と等しくならない)
で、3つとも成り立たない。どれか1つだけが変化してこうなるのは、3つの式すべてに存在する $x_2$ が変化したときだけ。つまり、受け取るはずだった符号は 1011000 であり、情報源符号は 1011。


2. 0101110
① : $x_1\oplus x_2\oplus x_3=0\oplus 1\oplus 0=1$ ($x_5$ と等しい)
② : $x_2\oplus x_3\oplus x_4=1\oplus 0\oplus 1\ne 1$ ($x_6$ と等しくならない)
③ : $x_1\oplus x_2\oplus x_4=0\oplus 1\oplus 1=0$ ($x_7$ と等しい)
で、①と③が成り立つので$x_1$, $x_2$, $x_3$, $x_4$, $x_5$, $x_7$ が等しいことが保証される。残った $x_6$ が変化した符号。受け取るはずだった符号は 0101100 であり、情報源符号は 0101。

• 練習問題4
練習問題2の条件で、①～③に相当する関係式を求めよ。

練習問題2の結果から、
$x_5$ = $x_1$ ⊕ $x_3$ ⊕ $x_4$ ・・・①'
$x_6$ = $x_1$ ⊕ $x_2$ ⊕ $x_3$ ・・・②'
$x_7$ = $x_2$ ⊕ $x_3$ ⊕ $x_4$ ・・・③'
となる。