情報理論 第8回 パリティ検査符号 (2) 練習問題解答例
練習問題1
上記のケースでの誤り率を
p
の式で記述せよ。
④、③より
誤り率
=
p
c
p
a
+
p
c
×
2
3
であり、これに①, ②の形を代入すれば、誤り率は
3
p
2
(
1
-
p
)
(
1
-
p
)
3
+
3
p
2
(
1
-
p
)
×
2
3
=
2
p
2
(
1
-
p
)
(
1
-
p
)
3
+
3
p
2
(
1
-
p
)
=
2
p
2
(
1
-
p
)
(
1
-
p
)
{
(
1
-
p
)
2
+
3
p
2
}
=
2
p
2
(
1
-
p
)
2
+
3
p
2
となる。
※ 展開すると次のような形になる。どちらの書き方でも正解。
2
p
2
1
-
2
p
+
4
p
2
練習問題2
練習問題1の結果から、
p
=
0.01
の場合の誤り率を求めよ (四捨五入して小数第4位まで)。また、それが「検査符号を使わずにそのまま送った場合の誤り率」に対して何%の値であるかを求めよ。
練習問題1で求めた式の
p
に0.01を入れると、誤り率は
2
p
2
(
1
-
p
)
2
+
3
p
2
=
2
×
0.01
2
0.99
2
+
3
×
0.01
2
=
2
99
2
+
3
=
2
9804
=
0.00020...
≅
0.0002
となる。また、検査符号を使わない場合の誤り率0.01に対するこの値の百分率は
0.0002
0.01
×
100
=
2
(%)
となる。
練習問題3
k
=
3
のパリティ検査符号について、上記と同じ通信路を通した場合の誤り率を
p
の式で記述せよ。
誤り率 = ⑤ ×
1
2
+ ⑥
の⑤と⑥に本文中の形を代入すると、誤り率は
p
c
2
p
a
+
p
c
2
+
p
c
4
×
1
2
+
p
c
4
p
a
+
p
c
2
+
p
c
4
=
p
c
2
2
+
p
c
4
p
a
+
p
c
2
+
p
c
4
となる。また、
変化の回数
受け取るもの
確率
判定
やること
0
0000
(
1
-
p
)
4
変化なし
000を復元 (正しい)
1
0001,... (4通り)
p
(
1
-
p
)
3
変化あり
再送信を要求
2
0011,... (6通り)
p
2
(
1
-
p
)
2
変化なし
00
1
,...を復元
3
0111,... (4通り)
p
3
(
1
-
p
)
変化あり
再送信を要求
4
1111
p
4
変化なし
111
を復元
の表から、この式に使われる確率は
p
を使って
p
a
=
(
1
-
p
)
4
p
c
2
=
6
p
2
(
1
-
p
)
2
p
c
4
=
p
4
のように表わされることがわかる。これらをさっきの式に代入すると、誤り率は
3
p
2
(
1
-
p
)
2
+
p
4
(
1
-
p
)
4
+
6
p
2
(
1
-
p
)
2
+
p
4
となる。
※ 展開すると次のような形になる。どちらの書き方でも正解。
p
2
(
3
-
6
p
+
4
p
2
)
1
-
4
p
+
12
p
2
-
16
p
3
+
8
p
4
練習問題4
練習問題3の結果から、
p
=
0.01
の場合の誤り率を求めよ (四捨五入して小数第4位まで。スマホの電卓機能などを使ってもよい)。また、それが「検査符号を使わずにそのまま送った場合の誤り率」に対して何%の値であるかを求めよ。
練習問題3の結果の
p
に0.01を入れると、誤り率は
3
×
0.01
2
×
0.99
2
+
0.01
4
0.99
4
+
6
×
0.01
2
×
0.99
2
+
0.01
4
=
3
×
99
2
+
1
99
4
+
6
×
99
2
+
1
=
2.94...
×
10
4
9.61...
×
10
7
=
0.00030...
≅
0.0003
となる (正確な値は
29404
96118408
だが、小数第4位まで残す前提だと有効桁数は1桁なのでそこまで計算しても意味がない)。また、検査符号を使わない場合の誤り率0.01に対するこの値の百分率は
0.0003
0.01
×
100
=
3
(%)
となる。
3倍の反復符号では、同じ通信路なら誤り率は
p
3
+
3
p
2
(
1
-
p
)
=
0.01
3
+
3
×
0.01
2
×
0.99
=
0.000298
≅
0.0003
で、いま求めた値と同程度の値になる。
3倍の反復符号では情報源符号1ビットに対して2ビットの検査符号がつくのに対して、
k
=
3
のパリティ検査符号では、情報源符号1ビットに対して1/3ビットで済み、なおかつ同程度まで誤り率を下げられる。
つまり、「
k
=
3
のパリティ検査符号」は「3倍の反復符号」の6倍程度の効率で誤り率を下げられていることになる。
練習問題5
以下の水平垂直パリティ検査符号追加済みの符号 (
k
=
4
) を受け取った。この情報源符号を記述せよ。ただし、変化はいずれも最大1回しか起こっていないものとする。
01010 00110 10010 11101 00011
00101 01100 11011 01110 11110
11110 01010 10100 00110 00010
それぞれ5×5の形に並べてみると
1.
2.
3.
0
1
0
1
0
0
0
1
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
0
1
0
1
0
1
1
0
0
1
1
0
1
1
0
1
1
1
0
1
1
1
1
0
1
1
1
1
0
0
1
0
1
0
1
0
1
0
0
0
0
1
1
0
0
0
0
1
0
となる。
どの行・列も1が偶数個あるので、変化なしと判定される。
情報源符号は右の列と下の行を取り除いて並べ直した
0101 0011 1001 1110
となる。
4行目と4列目に変化があったことがわかる。この交差した場所の「1」は本来0だったもの。
情報源符号はここを0に変えて右の列と下の行を取り除いて並べ直した
0010 0110 1101 0110
となる。
5行目と3列目に変化があったことがわかる。つまり、この交差した場所の「0」は本来1だったもの (ただし、結局これは取り除かれる)。
情報源符号は右の列と下の行を取り除いて並べ直した
1111 0101 1010 0011
となる。