情報理論 第8回　パリティ検査符号 (2)

• パリティ検査符号を使った誤り検出
$k=2$ の場合を例にとり、パリティ検査符号で変化を検出することを考える。
1ブロック中に変化が1回起こったときは、あて先でブロック中の1の数をカウントすると奇数個になるので、「変化があった」と判定することになる。
変化1回

元の符号 00 → 000 ↓ 001 奇数個

元の符号 00 → 000 ↓ 010 奇数個

元の符号 00 → 000 ↓ 100 奇数個


ところが、1ブロック中で2回変化が起きてしまうと、ブロック中の1の数が偶数個になってしまうので「変化なし」と判定され、誤ったものが復元されてしまう。
情報源符号(元の符号)は2つとも変化することもあるし、片方だけが変化することもある。
変化2回

元の符号 00 → 000 ↓ 11 ← 110 偶数個

元の符号 00 → 000 ↓ 10 ← 101 偶数個

元の符号 00 → 000 ↓ 01 ← 011 偶数個


1ブロック中で3回変化が起きると、ふたたびブロック中の1の数は奇数個になるので「変化あり」と判定される。
変化3回

元の符号 00 → 000 ↓ 111 奇数個


反復符号で誤り検出を行った場合と同様に、変化の検出に応じて再送信を要求すると図のような流れで結果が決まる。


情報源符号「00」にパリティ検査符号を加え、入力が0, 1のどちらでも確率$p$で変化し、消失が起こらない通信路を通すと、1回の送信で起こることは下の表のようになる。

変化の回数	受け取るもの	確率	判定	やること
0	000		変化なし	00を復元 (正しい)
1	001, 010, 100		変化あり	再送信を要求
2	110, 101, 011	$p^2(1-p)$	変化なし	11, 10, 01を復元
3	111	$p^3$	変化あり	再送信を要求


「ブロック単位で考えて」正しい結果を復元する確率を$p_a$, 再送信になる確率を$p_b$, 誤った結果を復元する確率を$p_c$とすると、
　・・・①
$p_c=3p^2(1-p)$ 　・・・②

となる ($p_b$ は「1回変化する確率」＋「3回変化する確率」だが、求める必要はない)。最終的に「ブロックとして誤った値を復元してしまう確率」は、反復符号の場合とまったく同様に

であり、$p_a$, $p_b$, $p_c$ の和が1であることから
　・・・③

と書くこともできる。

誤り率は「1ビットの符号が誤ったものに復元される確率」で、この値そのものではない。
ブロックとして誤った値が復元されるケースは11, 10, 01の3通りで、先頭の1ビットだけに注目すると、誤ったものになるのは11, 10になったときの2通りだけである。つまり、誤り率は次のようになる。


誤り率 = 「ブロックとして誤った値を復元してしまう確率」 × $\frac{2}{3}$ 　・・・④


• 練習問題1
上記のケースでの誤り率を $p$ の式で記述せよ。
※ ④式に③式を入れ、さらに①、②式を使う。


• 練習問題2
練習問題1の結果から、$p=0.01$ の場合の誤り率を求めよ (四捨五入して小数第4位まで)。また、それが「検査符号を使わずにそのまま送った場合の誤り率」に対して何%の値であるかを求めよ。

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



• 練習問題3
$k=3$ のパリティ検査符号について、上記と同じ通信路を通した場合の誤り率を $p$ の式で記述せよ。
※ 情報源符号が「000」の場合の結果は以下のようなグループに分かれる。

変化の回数	受け取るもの	確率	判定	やること
0	0000		変化なし	000を復元 (正しい)
1	0001,... (4通り)		変化あり	再送信を要求
2	0011,... (6通り)		変化なし	001,...を復元
3	0111,... (4通り)	$p^3(1-p)$	変化あり	再送信を要求
4	1111	$p^4$	変化なし	111を復元


$p_a$：変化が全く起こらない確率
$p_b$：変化が奇数回起こる確率
：変化が2回起こる確率
：変化が4回起こる確率

とすると、「最終的にブロック中に2つ誤りがある確率」は
　・・・⑤

「最終的にブロック中の符号がすべて誤りである確率」は
　・・・⑥

となる。先頭のビットに注目すると、前者では4桁中2桁が変化しているはずなので、実際にそのビットが変化する確率は⑤の1/2になる。後者のケースになった場合は確実に変化する。結局、誤り率は

誤り率 = ⑤ × $\frac{1}{2}$ + ⑥

で求められる。


• 練習問題4
練習問題3の結果から、$p=0.01$ の場合の誤り率を求めよ (四捨五入して小数第4位まで。スマホの電卓機能などを使ってもよい)。また、それが「検査符号を使わずにそのまま送った場合の誤り率」に対して何%の値であるかを求めよ。
$k=2$ のパリティ検査符号では、情報源符号2ビットに対して検査符号を1ビット使う。
$k=3$ のパリティ検査符号では、情報源符号3ビットに対して検査符号を1ビット使う。
つまり、前者に対して検査符号を2/3しか使っていない。
その分だけ誤り率が大きくなるはず。

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

0	0	1
1	0	1
1	1	1



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

0	0	1	1
1	0	1	0
1	1	1	1
0	1	1	0



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

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

0 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0

→ 通 信 路

0 0 1 1 0 0 1 0 1 1 1 1 0 1 1 0

→

0 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0

→

0 0 1 1 0 1 1 1 1

→

001 101 111


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

1	0	1	1
1	0	1	0
1	1	0	1
0	1	1	0


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

× 　 　 　 ×

× 　 　 ×




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