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

• 練習問題1
次の符号を符号多項式に置き換えたものを記述せよ。
1. 11001000
2. 01010101


1. $x^7+x^6+x^3$
2. $x^6+x^4+x^2+1$

• 練習問題2
次の符号多項式を8ビットの符号に置き換えたものを記述せよ。
1. $x^7+x^6+x^4+x$
2. $x^5+x^4+x^3+1$


1. 1101 0010
2. 0011 1001

• 練習問題3
符号多項式$A=x^3+x+1$, $B=x+1$ について、以下の演算の結果を記述せよ。
1. $A+B$
2. $A-B$
3. $A\times B$
4. $A÷B$ (商、余りの両方を求める)


1. $A+B=x^3+(1+1)x+(1+1)=x^3$
2. $A-B=x^3+(1-1)x+(1-1)=x^3$
3. $A\times B=(x^3+x+1)(x+1)=(x^4+x^2+x)+(x^3+x+1)=x^4+x^3+x^2+1$
4. 筆算すると次のようになるので、商は $x^2+x$、余りは1
   

• 練習問題4
上の例と同じ条件で、情報源符号「1110」に検査符号を付け加えたものを記述せよ。


1. 情報源符号は「1110」
2. 符号多項式に置き換えると $P\left(x\right)=x^3+x^2+x$ になる
3. $P\left(x\right)$ に $x^2$ をかけると $x^5+x^4+x^3$。それを $G\left(x\right)=x^2+1$ で割ると、余りは $1$。(これを $R\left(x\right)$ とする)
   
4. 3の結果から、$F\left(x\right)=x^{2}P\left(x\right)+R\left(x\right)=x^5+x^4+x^3+1$
5. $F\left(x\right)$ を符号に置き換えると「111001」になる。

• 練習問題5
練習問題4の符号を通信路に通し、途中で変化が起きなかった (つまり$\stackrel{\_}{F}\left(x\right)=F\left(x\right)$ ) 場合に、$\stackrel{\_}{F}\left(x\right)$ が $G\left(x\right)$ で割り切れることを確認せよ (筆算を書く)。

$\stackrel{\_}{F}\left(x\right)=x^5+x^4+x^3+1$ を $G\left(x\right)=x^2+1$ で割ると、次のように確かに割り切れる。

• 練習問題6
練習問題4の符号を通信路に通し、前から3番目のビットが変化した場合の $\stackrel{\_}{F}\left(x\right)$ を $G\left(x\right)$ で割った余りを求めよ (筆算を書く)。

3ビット目が変化して「110001」になると、それを符号多項式にしたものは $\stackrel{\_}{F}\left(x\right)=x^5+x^4+1$ になる。これを $G\left(x\right)=x^2+1$ で割ると以下のようになり、余りは $x$ で、割り切れなくなる。