情報理論第8回　パリティ検査符号 (2)　練習問題解答例

p

誤り率 = \frac{p_{c}}{p_{a}+p_{c}} \times \frac{2}{3}

\frac{3p^{2}(1-p)}{{(1-p)}^{3}+3p^{2}(1-p)} \times \frac{2}{3} = \frac{2p^{2}(1-p)}{{(1-p)}^{3}+3p^{2}(1-p)} = \frac{2p^{2}(1-p)}{{(1-p){(1-p)}^{2}+3p^{2}}} = \frac{2p^{2}}{{(1-p)}^{2}+3p^{2}}

\frac{2p^{2}}{1-2p+4p^{2}}

p = 0.01

p

\frac{2p^{2}}{{(1-p)}^{2}+3p^{2}} = \frac{2\times{0.01}^{2}}{{0.99}^{2}+3\times{0.01}^{2}} = \frac{2}{99^{2}+3} = \frac{2}{9804} = 0.00020... ≅ 0.0002

\frac{0.0002}{0.01} \times 100 = 2

(%)

k = 3

p

\frac{1}{2}

\frac{p_{c2}}{p_{a}+p_{c2}+p_{c4}} \times \frac{1}{2} + \frac{p_{c4}}{p_{a}+p_{c2}+p_{c4}} = \frac{\frac{p_{c2}}{2}+p_{c4}}{p_{a}+p_{c2}+p_{c4}}

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

p

p_{a} = {(1-p)}^{4}

p_{c2} = 6 p^{2} {(1-p)}^{2}

p_{c4} = p^{4}

\frac{3p^{2}{(1-p)}^{2}+p^{4}}{{(1-p)}^{4}+6p^{2}{(1-p)}^{2}+p^{4}}

\frac{p^{2}(3-6p+4p^{2})}{1-4p+12p^{2}-16p^{3}+8p^{4}}

p = 0.01

p

\frac{3\times{0.01}^{2}\times{0.99}^{2}+{0.01}^{4}}{{0.99}^{4}+6\times{0.01}^{2}\times{0.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

\frac{29404}{96118408}

\frac{0.0003}{0.01} \times 100 = 3

(%)

3倍の反復符号では、同じ通信路なら誤り率は

p^{3} + 3 p^{2} (1 - p) = {0.01}^{3} + 3 \times {0.01}^{2} \times 0.99 = 0.000298 ≅ 0.0003

で、いま求めた値と同程度の値になる。
3倍の反復符号では情報源符号1ビットに対して2ビットの検査符号がつくのに対して、

k = 3

のパリティ検査符号では、情報源符号1ビットに対して1/3ビットで済み、なおかつ同程度まで誤り率を下げられる。
つまり、「

k = 3

のパリティ検査符号」は「3倍の反復符号」の6倍程度の効率で誤り率を下げられていることになる。

k = 4

0101 0011 1001 1110

0010 0110 1101 0110

1111 0101 1010 0011