第12回 反復符号とパリティ検査符号 (1) 課題解答例

課題1

入力が0, 1のどちらの場合も確率 \(p=0.1\) で変化する通信路で3倍の反復符号を使い、誤り訂正を行った場合の誤り率を求めよ。

(1) 式の \(p\) に0.1を入れると、誤り率は
\( \begin{eqnarray} p_e&=&p^3+3p^2(1-p)\\ &=&0.1^3+3\times0.1^2\times0.9\\ &=&0.001+0.027\\ &=&0.028 \end{eqnarray} \)
となる。
この値は、反復符号を使わない場合の誤り率0.1に比べれば28%にあたり、間違いが起こる確率が減っていることがわかる。

課題2

入力が0, 1のどちらの場合も確率 \(p=0.1\) で変化する通信路で5倍の反復符号を使い、誤り訂正を行った場合の誤り率を求めよ (四捨五入して小数第3位まで)。

変化の回数に応じて表をつくると
変化の回数受け取るもの確率復元されるもの
000000 \((1-p)^5\) 0 (正しい)
100001, 00010,...(5通り) \(p(1-p)^4\) 0 (正しい)
200011, 00101,...(10通り) \(p^2(1-p)^3\) 0 (正しい)
300111, 01011,...(10通り) \(p^3(1-p)^2\) 1 (誤り)
401111, 10111,...(5通り) \(p^4(1-p)\) 1 (誤り)
511111 \(p^5\) 1 (誤り)
のようになる。このうち誤った結果になるのは変化の回数が3, 4, 5回の場合なので、誤り率は
\(\begin{eqnarray} p_e&=&10p^3(1-p)^2+5p^4(1-p)+p^5\\ &=&p^3\left(10(1-p)^2+5p(1-p)+p^2\right) \end{eqnarray} \)

と表わせる。ここで \(p\) に0.1を入れると、
\(\begin{eqnarray} p_e&=&0.1^3\times\left(10\times0.9^2+5\times0.1\times0.9+0.1^2\right)\\ &=&0.001\times(8.1+0.45+0.01)\\ &=&0.00856\\ &≒&0.009 \end{eqnarray} \)
となる。
この値は、反復符号を使わない場合の誤り率0.1に比べれば9%で、3倍の反復符号のときと比べても間違いが起こる確率が減っていることがわかる。

課題3

入力が0, 1のどちらの場合も確率 \(p=0.1\) で変化する通信路で3倍の反復符号を使い、誤り検出を行った場合の誤り率を求めよ (四捨五入して小数第5位まで)。

(5) 式の \(p\) に0.1を入れると、誤り率は

\( \begin{eqnarray} p_e&=&\frac{0.1^3}{0.9^3+0.1^3}\\ &=&\frac{0.001}{0.729+0.001}\\ &=&\frac{0.001}{0.73}\\ &=&0.001369...\\ &≒&0.00137 \end{eqnarray} \)

となる。
反復符号を使わない場合の誤り率0.1と比べると、これは1.37%。誤り訂正の場合と比べて、さらに誤りを減らせている。
5倍の反復符号で誤り訂正を行ったときと比べてもこの値は小さい。つまり、「手間をかけた分だけ、余計な水増しをしなくても間違いを減らせる」ということになる。

課題4

入力が0, 1のどちらの場合も確率 \(p=0.1\) で変化する通信路で5倍の反復符号を使い、誤り検出を行った場合の誤り率を求めよ (四捨五入して小数第5位まで)。

5倍の反復符号では、(5) 式に相当するものは \(p_e=\begin{eqnarray}\frac{p^5}{(1-p)^5+p^5}\end{eqnarray}\) になる。この \(p\) に0.1を入れると、誤り率は
\( \begin{eqnarray} p_e&=&\frac{0.1^5}{0.9^5+0.1^3}\\ &=&\frac{0.00001}{0.59049+0.00001}\\ &=&\frac{0.00001}{0.5905}\\ &=&0.000016...\\ &≒&0.00002 \end{eqnarray} \)
となる。
反復符号を使わない場合の誤り率0.1に比べると、これはわずか0.02%。

課題5

符号「011110001111」にパリティ検査符号を追加したものを記述せよ。ただし \(k=4\) とする。

「0111 1000 1111」のように区切ると、それぞれのブロックには前から順に奇数個、奇数個、偶数個の1が含まれるので、パリティ検査符号はそれぞれ1, 1, 0になる。
パリティ検査符号を追加されたものは 01111 10001 11110 になる。

課題6

パリティ検査符号追加済みの以下の符号を受け取ったとき、通信路で変化があったかどうかを判定し、以下のものを解答せよ。ただし \(k=3\) とする。
  1. 101001110101
  2. 001110011111
  1. 101001110101
  2. \(k=3\) なので、検査符号追加済みの符号は4つずつに区切る。「1010 0111 0101」のように区切ると、2つ目のブロックの1の数は奇数。→変化あり
    (「0111」のうちどれが変化したのかを知る方法はない。情報源符号の4~6番目は「111」「001」「010」「011」のはずだが、特定はできない)

  3. 001110011111
  4. 同様に4つずつ区切ると「0011 1001 1111」となり、どのブロックの1の数も偶数個なので、変化なしと判定される。
    情報源符号はこれらのブロックの最後のビットを除いた001 100 111 となる。
inserted by FC2 system