\(k=2\) のパリティ検査符号を使い、2元対称通信路を通した場合に誤り検出を行うケースを考える。
1ブロック中に変化が1回起こったときは、受信者がブロック中の1の数をカウントすると奇数個になるので、「変化があった」と判定することになる。
変化1回
|
00
|
付加 → |
000
|
変化 → |
001
|
|
00
|
付加 → |
000
|
変化 → |
010
|
|
00
|
付加 → |
000
|
変化 → |
100
|
ところが、1ブロック中で2回変化が起きてしまうと、ブロック中の1の数が偶数個になってしまうので「変化なし」と判定され、誤ったものが復元されてしまう。
情報源符号(元の符号)は2つとも変化することもあるし、片方だけが変化することもある。
変化2回
|
00
|
付加 → |
000
|
変化 → |
011
|
削除 → |
01
|
|
00
|
付加 → |
000
|
変化 → |
101
|
削除 → |
10
|
|
00
|
付加 → |
000
|
変化 → |
110
|
削除 → |
11
|
1ブロック中で3回変化が起きると、ふたたびブロック中の1の数は奇数個になるので「変化あり」と判定される。
変化3回
|
00
|
付加 → |
000
|
変化 → |
111
|
反復符号で誤り検出を行った場合と同様に、変化の検出に応じて再送信を要求すると図のような流れで結果が決まる。
情報源符号「00」にパリティ検査符号を加え、入力が0, 1のどちらでも確率 \(p\) で変化し、消失が起こらない通信路を通すと、1回の送信で起こることは下の表のようになる。
| 変化の回数 | 受け取るもの | 確率 | 判定 | やること |
|---|---|---|---|---|
| 0 | 000 | \((1-p)^3\) | 変化なし | 00を復元 (正しい) |
| 1か3 | 001, 010, 100, 111 | 変化あり | 再送信を要求 | |
| 2 | 110, 101, 011 | \(p^2(1-p)\) | 変化なし | 11, 10, 01を復元 |
「ブロック単位で考えて」正しい結果を復元する確率を \(p_a\), 再送信になる確率を \(p_b\), 誤った結果を復元する確率を \(p_c\) とすると、
\( \begin{eqnarray} p_a&=&(1-p)^3 \hskip1em\cdots(1)\\ p_c&=&3p^2(1-p) \cdots(2) \end{eqnarray} \)
となる ( \(p_b\) は誤り率の計算には不要なので表には書いていない)。最終的に「ブロックとして誤った値を復元してしまう確率」\(p_{e0}\) (誤り率とは異なる) は、反復符号の場合とまったく同様に
\( p_{e0}= \begin{eqnarray} \frac{p_c}{p_a+p_c}\cdots(3) \end{eqnarray} \)
となる。誤り率は「1ビットの符号が誤ったものに復元される確率」で、この値そのものではない。
ブロックとして誤った値が復元されるケースは11, 10, 01の3通りで、先頭の1ビットだけに注目すると、誤ったものになるのは11, 10になったときの2通りだけである。つまり、誤り率は \(p_{e0}\) の2/3になるので、
| \( \begin{eqnarray} p_e&=&\frac{2}{3}\frac{p_c}{p_a+p_c}\cdots(4) \end{eqnarray} \) |
となる。これに(1), (2)式の右辺の形を入れると、誤り率は以下のようになる。
| \( \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)^2+3p^2}\cdots(5) \end{eqnarray} \) |