第13回 パリティ検査符号 (2)

パリティ検査符号を使った誤り検出

概要

\(k=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回の送信で起こることは下の表のようになる。
変化の回数受け取るもの確率判定やること
0000 \((1-p)^3\) 変化なし00を復元 (正しい)
1001, 010, 100 \(p(1-p)^2\) 変化あり再送信を要求
2110, 101, 011 \(p^2(1-p)\) 変化なし11, 10, 01を復元
3111 \(p^3\) 変化あり再送信を要求

「ブロック単位で考えて」正しい結果を復元する確率を \(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\) は「1回変化する確率」+「3回変化する確率」だが、求める必要はない)。最終的に「ブロックとして誤った値を復元してしまう確率」\(p_{be}\) (誤り率とは異なる) は、反復符号の場合とまったく同様に

\( p_{be}= \begin{eqnarray} \frac{p_c}{p_a+p_c}\cdots(3) \end{eqnarray} \)
となる。

誤り率は「1ビットの符号が誤ったものに復元される確率」で、この値そのものではない。
ブロックとして誤った値が復元されるケースは11, 10, 01の3通りで、先頭の1ビットだけに注目すると、誤ったものになるのは11, 10になったときの2通りだけである。つまり、誤り率は \(p_{be}\) の2/3になるので、
\( \begin{eqnarray} p_e&=&\frac{2}{3}\frac{p_c}{p_a+p_c}\cdots(4) \end{eqnarray} \)
となる。

課題1

上記のケースでの誤り率を \(p\) の式で記述せよ。
  • (4) 式の \(p_a, p_c\) に (1), (2) 式の形を入れる。

課題2

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

3倍の反復符号では、情報源符号1ビットに対して検査符号のビット数は2ビットだった。
\(k=2\) のパリティ検査符号では、情報源符号2ビットに対して検査符号を1ビット使う。
つまり、前者に対して検査符号の割合は1/4で済む。
\(p\) が大きいときはパリティ検査符号では反復符号ほど誤り率を下げることはできないが、送る符号のビット数はそれほど膨らませずに済む。
\(p\) が小さくなると、パリティ検査符号のほうが反復符号よりも誤り率を下げられるようになる。

課題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を復元

\(p_a\):変化が全く起こらない確率
\(p_b\):変化が奇数回起こる確率
\(p_{c2}\):変化が2回起こる確率
\(p_{c4}\):変化が4回起こる確率

とすると、「最終的にブロック中に2つ誤りがある確率」\(p_{be2}\) は

\( \begin{eqnarray} p_{be2}=\frac{p_{c2}}{p_a+p_{c2}+p_{c4}} \end{eqnarray} \)

「最終的にブロック中の符号がすべて誤りである確率」\(p_{be4}\) は

\( \begin{eqnarray} p_{be4}=\frac{p_{c4}}{p_a+p_{c2}+p_{c4}} \end{eqnarray} \)

となる。前者では4ビット中2ビットが変化しているはずなので、どれか1つのビットに注目すると、実際に変化する確率は \(p_{be2}\) の1/2になる。
一方、後者のケースになった場合は確実に変化する。結局、誤り率は

\( \begin{eqnarray} p_e&=&\frac{1}{2}p_{be2}+p_{be4}\\ &=&\frac{p_{c2}+2p_{c4}}{2\left(p_a+p_{c2}+p_{c4}\right)}\cdots(5) \end{eqnarray} \)

で求められる。

課題4

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

水平垂直パリティ検査符号

概要

普通のパリティ検査符号では、ブロック中で変化がおきたかどうかを調べることができるが、ピンポイントでどこが変化したかを知ることはできない。しかし、以下のようにすれば変化が起きた場所を特定し、誤り訂正を行うことができる。
送信側でやること( \(k=3\) の場合)
  1. 情報源符号を3桁×3の形に並べる
  2. 「001101111...」なら
    001
    101
    111

  3. それぞれの行の右と列の下にパリティ検査符号を追加する (右下は「その上の3つ」「その左の3つ」のどちらで作っても同じ値になる)
  4. 0011
    1010
    1111
    0110

  5. 1行ずつ順に送信する
  6. この場合なら送るのは「0011 1010 1111 0110」

受信側では、受け取ったものを2と同様の形に並べ、縦と横について1の数をカウントし、すべて偶数になっているかどうかをチェックする。
もし通信路で図のような変化が起こったとすると、左の列と上から2番目の行で1の数が奇数個になる。
すると、変化した場所が「左から1番目、上から2番目」であることを特定でき、それが本当は1だったことがわかる。
そのため、再送信を要求しなくても情報源符号を復元できる。
0011
1010
1111
0110
通信路↓
0011
0010
1111
0110
誤り訂正↓
0011
1010
1111
0110
検査符号削除↓
001
101
111
→ 001 101 111

もっとも、これはひとかたまり((\(k+1)^2\) ビット) の中で1回だけ変化が起きたときにしか使えない。
例えば上のケースで図の2箇所に変化がおきると、1行目と3行目、1列目と3列目で1の数が奇数になる。
1011
1010
1101
0110

この場合、受信者側では変化が起こった場所が左図の2箇所なのか、それとも右図の2箇所なのかを知る手段がない。
×  
 
×
 
 
 × 
 
×
 

課題5

以下の水平垂直パリティ検査符号追加済みの符号 (\(k=4\)) を受け取った。この情報源符号を記述せよ。ただし、変化はいずれも最大1回しか起こっていないものとする。
  1. 01010 00110 10010 11101 00011
  2. 00101 01100 11011 01110 11110
  3. 11110 01010 10100 00110 00010
inserted by FC2 system