第13回 パリティ検査符号 (2) 課題解答例

課題1

上記のケースでの誤り率を \(p\) の式で記述せよ。

(1), (2), (4) 式より
\( \begin{eqnarray} p_e&=&\frac{2}{3}\frac{p_c}{p_a+p_c}\\ &=&\frac{2}{3}\frac{3p^2(1-p)}{(1-p)^3+3p^2(1-p)}\\ &=&\frac{2p^2(1-p)}{(1-p)^3+3p^2(1-p)}\\ &=&\frac{2p^2\cancel{(1-p)}}{\cancel{(1-p)}\{(1-p)^2+3p^2\}}\\ &=&\frac{2p^2}{(1-p)^2+3p^2} \end{eqnarray} \)

となる。

課題2

課題1の結果から、\(p=0.01\) の場合の誤り率を求めよ (四捨五入して小数第4位まで)。

課題1で求めた式の \(p\) に0.01を入れると、誤り率は

\( \begin{eqnarray} p_e&=&\frac{2p^2}{(1-p)^2+3p^2}\\ &=&\frac{2\times0.01^2}{0.99^2+3\times0.01^2}\\ &=&\frac{2}{99^2+3}\\ &=&\frac{2}{9804}\\ &=&0.00020...\\ &\simeq&0.0002 \end{eqnarray} \)

となる。これは検査符号を使わない場合の誤り率0.01に対して2%にあたる。

課題3

\(k=3\) のパリティ検査符号について、上記と同じ通信路を通した場合の誤り率を \(p\) の式で記述せよ。

情報源符号が「000」の場合の結果の表
変化の回数受け取るもの確率判定やること
00000 \((1-p)^4\) 変化なし000を復元 (正しい)
10001,... (4通り) \(p(1-p)^3\) 変化あり再送信を要求
20011,... (6通り) \(p^2(1-p)^2\) 変化なし001,...を復元
30111,... (4通り) \(p^3(1-p)\) 変化あり再送信を要求
41111 \(p^4\) 変化なし111を復元

から、変化が0, 2, 4回起こる確率は \(p\) を使って

\( \begin{eqnarray} p_a&=&(1-p)^4\\ p_{c2}&=&6p^2(1-p)^2\\ p_{c4}&=&p^4 \end{eqnarray} \)

のように表わされることがわかる。これらを (5) 式に代入すると、誤り率は

\( \begin{eqnarray} p_e=\frac{3p^2(1-p)^2+p^4}{(1-p)^4+6p^2(1-p)^2+p^4} \end{eqnarray} \)

となる。
\( \begin{eqnarray} p_e=\frac{p^2(3-6p+4p^2)}{1-4p+12p^2-16p^3+8p^4} \end{eqnarray} \)

課題4

課題3の結果から、\(p=0.01\) の場合の誤り率を求めよ (四捨五入して小数第4位まで。スマホの電卓機能などを使ってもよい)。

課題3の結果の \(p\) に0.01を入れると、誤り率は

\( \begin{eqnarray} p_e&=&\frac{3\times0.01^2\times0.99^2+0.01^4}{0.99^4+6\times0.01^2\times0.99^2+0.01^4}\\ &=&\frac{3\times99^2+1}{99^4+6\times99^2+1}\\ &=&\frac{2.94...\times10^4}{9.61...\times10^7}\\ &=&0.00030...\\ &≒&0.0003 \end{eqnarray} \)

となる。
3行目の正確な値は \(\begin{eqnarray}\frac{29404}{96118408}\end{eqnarray}\) だが、小数第4位まで残す前提だと有効桁数は1桁なのでそこまで計算しても意味がない。
検査符号を使わない場合と比べると、これは3%程度で、3倍の反復符号で誤り検出を行ったときとほぼ同程度の値。
3倍の反復符号では情報源符号1ビットに対して2ビットの検査符号がつくのに対して、\(k=3\) のパリティ検査符号では、情報源符号1ビットに対して1/3ビットで済み、なおかつ同程度まで誤り率を下げられる。
つまり、「\(k=3\) のパリティ検査符号」は「3倍の反復符号」の6倍程度の効率で誤り率を下げられていることになる。
課題2の結果と比べると、誤り率はほぼ5割増しになっている。元の符号を○、検査符号を●で表わすと
\(k=2\) のパリティ検査符号 : ○○●
\(k=3\) のパリティ検査符号 : ○○○●
のように、検査符号の割合が少なくなっていることを考えると、この結果は理屈に合っている。

課題5

以下の水平垂直パリティ検査符号追加済みの符号 (\(k=4\)) を受け取った。この情報源符号を記述せよ。ただし、変化はいずれも最大1回しか起こっていないものとする。
  1. 01010 00110 10010 11101 00011
  2. 00101 01100 11011 01110 11110
  3. 11110 01010 10100 00110 00010
  1. 5x5の形に並べてみると、どの行・列も1が偶数個あるので、変化なしと判定される。
  2. 01010
    00110
    10010
    11101
    00011
    情報源符号は右の列と下の行を取り除いて並べ直した
    0101 0011 1001 1110
    となる。

  3. 4行目と4列目に変化があったことがわかる。この交差した場所の「1」は本来0だったもの。
  4. 00101
    01100
    11011
    01110
    11110
    情報源符号はここを0に変えて右の列と下の行を取り除いて並べ直した
    0010 0110 1101 0110
    となる。

  5. 5行目と3列目に変化があったことがわかる。つまり、この交差した場所の「0」は本来1だったもの (ただし、結局これは取り除かれる)。
  6. 11110
    01010
    10100
    00110
    00010
    情報源符号は右の列と下の行を取り除いて並べ直した
    1111 0101 1010 0011
    となる。
inserted by FC2 system