情報理論第7回　反復符号とパリティ検査符号 (1)

反復符号を使った誤り訂正

反復符号

n

n

T = [\begin{matrix} 1 - p & p \\ p & 1 - p \end{matrix}]

変化の回数	受け取るもの	確率	復元されるもの
0	000	${(1-p)}^{3}$	0 (正しい)
1	001, 010, 100	$p {(1-p)}^{2}$	0 (正しい)
2	110, 101, 011	$p^{2} (1 - p)$	1 (誤り)
3	111	$p^{3}$	1 (誤り)

p^{3} + 3 p^{2} (1 - p)

誤り率

p = 0.1

p

p = 0.1

求めた値が意味するもの
練習問題1, 2の結果を比較すると、練習問題2の方が小さい値になる。これは、「手間をかけた分だけ最終的に間違ったものを復元してしまう確率を減らせた」と解釈できる。

反復符号を使った誤り検出

誤り検出

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

p_{a}

p_{b}

p_{c}

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

p_{c} = p^{3}

p_{a}

p_{b}

p_{c}

p_{b}

p_{b} = 1 - {(1-p)}^{3} - p^{3}

$p_{c}$	(1回目の送信で誤った結果を復元する確率)
$p_{b} p_{c}$	(1回目は再送信となり、2回目の送信で誤った結果を復元する確率)
${p_{b}}^{2} p_{c}$	(2回目までは再送信となり、3回目の送信で誤った結果を復元する確率)
${p_{b}}^{3} p_{c}$	(3回目までは再送信となり、4回目の送信で誤った結果を復元する確率)
・・・

p_{c} (1 + p_{b} + {p_{b}}^{2} + {p_{b}}^{3} + \dots)

1 + x + x^{2} + x^{3} + \dots = \frac{1}{1-x}

\frac{p_{c}}{1-p_{b}}

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

p = 0.1

p = 0.1

求めた値が意味するもの
練習問題1と3, 2と4の結果を比較すると、練習問題3, 4の方が小さい値になる。これは、「再送信の手間をかけた分だけ最終的に間違ったものを復元してしまう確率を減らせた」と解釈できる。また、当然ながら反復回数の多い練習問題4の方が練習問題3の誤り率よりも小さくなる。

パリティ検査符号

k + 1

k = 4

検査符号

情報源符号

k = 4

k = 3