第10回 反復符号

初めに必ず連絡事項を確認してください。

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

概要

解説動画

今回以降の授業では、第5~7回とは異なり「符号」という用語は「0」「1」 (符号アルファベット) を指すものとする。
通信路にそのまま符号を入れると、受け取った側では受け取った符号に変化があったかどうかを知る手段がない。そこで、一般的にデジタル通信では変化が起こったかどうかを知るための符号を追加してから送信を行う。追加の符号の作り方にはいくつかのタイプがあるが、ここでは反復符号について学ぶ。

反復符号
送信側 : もとの符号をそれぞれ \(n\) 倍に増やす
受信側 : 受け取った符号を \(n\) 個ずつに区切り、それぞれのブロックで多い方の符号を1つ残す

例 (3倍の反復符号)
元の符号
001011
000 000 111 000 111 111
↓ 通信路での変化
復元された符号
001011
000 010 111 000 111 110

こうすることで、通信路で変化が起こっても元の符号を復元できる。ただし、3倍の反復符号でうまく復元できるのは、受け取った1ブロックの符号のうち変化したものが1個までの場合に限られる。例えば「000」を送ったときに3個中2個が変化してしまうと
元の符号
0
000
復元された符号
1
011
のように、誤ったものが復元されてしまう。このように、最終的に間違った結果になってしまう確率を誤り率という。

3倍の反復符号について、具体的に誤り率の値を計算してみる。通信路行列 \( T= \begin{bmatrix} 1-p & p \\ p & 1-p \end{bmatrix} \) で表わされる通信路では、もとの符号が0だった場合に受信者が受け取るものは000~111の8通りあり、このうち0に復元されるのは000, 001, 010, 100の4通りで、それ以外では1になってしまう。

表1
変化の回数 受け取るもの 確率 復元されるもの
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_e\) は、受け取ったものが (111である確率) + (110である確率) + (101である確率) + (011である確率) なので、

\( p_e=p^3+3p^2(1-p)\cdots(1) \)

になる (1を送ったときに0が復元されてしまう確率も同じ)。

5倍の反復符号で同様のことをすると、

表2
変化の回数 受け取るもの 確率 復元されるもの
0 00000 \((1-p)^5\) 0 (正しい)
1 00001~10000 (5通り) \(p(1-p)^4\) 0 (正しい)
2 00011~11000 (10通り) \(p^2(1-p)^3\) 0 (正しい)
3 00111~11100 (10通り) \(p^3(1-p)^2\) 1 (誤り)
4 01111~11110 (5通り) \(p^4(1-p)\) 1 (誤り)
5 11111 \(p^5\) 1 (誤り)
誤った結果になってしまうのは変化が3回以上起こる16通りのケースなので、この場合の誤り率は

\( p_e=p^5+5p^4(1-p)+10p^3(1-p)^2\cdots(2) \)

となる。

課題1

入力が0, 1のどちらの場合も確率 \(p=0.01\) で変化する通信路で3倍の反復符号を使い、誤り訂正を行った場合の誤り率 \(p_e\) を求めよ (四捨五入せず、最後の桁まで書くこと)。

課題1ヒント
求めた値が意味するもの
反復符号を使わずにそのまま送信した場合は、通信路での変化率 0.1 がそのまま誤り率になる。課題1の結果はこれよりも小さい。
これは「手間をかけた分だけ間違いを減らせた」と解釈できる。

課題2

入力が0, 1のどちらの場合も確率 \(p=0.01\) で変化する通信路で5倍の反復符号を使い、誤り訂正を行った場合の誤り率 \(p_e\) を求めよ (四捨五入せず、最後の桁まで書くこと)。

課題2ヒント
求めた値が意味するもの
課題1, 2の結果を比較すると、課題2の方が小さい値になる。
これは「手間を増やしたおかげでさらに間違いを減らせた」と解釈できる。

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

概要

解説動画

上で見たように単純に多数決で元の符号を復元すると、通信路で変化が多数起こった場合に誤ったものが復元されてしまう。 そこで、変化が起こったと思われる場合は送信者側に再送信を要求し、改めて符号を送りなおさせる手法がある。これを誤り検出という。
反復符号では変化がなければ1ブロック分の符号はすべて同じになるはずなので、「001」や「101」などの「不揃いなもの」を受け取ったときは通信路で変化が起きたと判定する。 ただし3回変化がおきると「111」になってしまい、受け取った側はこれを「変化なし」と判定してしまうので、誤ったものが復元されてしまうことになる。
この手法を使ったときの誤り率の求め方は多少複雑になる。1回の送信では「正しいものを復元」「再送信」「誤ったものを復元」の3つのケースが発生するが、「再送信」になったときの次の送信でも再びこれらの3つのケースが発生するので、図のような過程を繰り返して最終的に下のグループに入ったものが「誤り」となる。

1回の送信について考えたときに、正しい結果を復元する確率を \(p_a\), 再送信になる確率を \(p_b\), 誤った結果を復元する確率を \(p_c\) とすると、誤り率は

\(p_c \hskip0.9em\) (1回目の送信で誤った結果を復元する確率)
\(p_bp_c\) (1回目は再送信となり、2回目の送信で誤った結果を復元する確率)
\(p_b^2p_c\) (2回目までは再送信となり、3回目の送信で誤った結果を復元する確率)
\(p_b^3p_c\) (3回目までは再送信となり、4回目の送信で誤った結果を復元する確率)
\(\cdots\)

を足し上げたもの、つまり

\( p_e=p_c\left(1+p_b+p_b^2+\cdots\right)=p_c\displaystyle \sum_{i=0}^\infty p_b^i \)

になる。 ここで数学の公式 \( \begin{eqnarray} \displaystyle \sum_{i=0}^\infty x^i=\frac{1}{1-x} \end{eqnarray} \) を使えば、

\( p_e= \begin{eqnarray} \frac{p_c}{1-p_b} \end{eqnarray} \)

のように書ける。さらに、1回の送信では「正しい結果を復元する」「再送信を要求する」「誤った結果を復元する」のどれかになるので、\(p_a+p_b+p_c=1\) が成り立つ。これを変形すると \(p_a+p_c=1-p_b\) になるので

\( p_e= \begin{eqnarray} \frac{p_c}{p_a+p_c}\cdots(3) \end{eqnarray} \)

とも書ける。
(3)式は数学の公式を使っても求められるが、「東西方向の土手の上を西から東に流れる水路があり、つねに北と南に \(p_a : p_c\) の比で水が流れ落ちて、東の果てで水がなくなる」というイメージで考えれば、最終的に北と南に流れ落ちた水の量の比も \(p_a : p_c\) になる。つまり、南に落ちた水は全体の \(p_c/(p_a+p_c)\) になることがわかる。

これを踏まえ、3倍の反復符号で誤り率を具体的に求めてみる。変化の回数と判定の結果をまとめると

表3
変化の回数 受け取るもの 確率 判定 やること
0 000 \((1-p)^3\) 変化なし 0を復元 (正しい)
1~2 000, 111以外 変化あり 再送信を要求
3 111 \(p^3\) 変化なし 1を復元 (誤り)

のようになる (変化の回数が1~2回になる確率も計算できるが、誤り率を求める計算には必要ないので空欄にしてある)。要するに \(p_a=(1-p)^3, p_c=p^3\) で、これを(3)式に入れると誤り率は(4)式のようになる。

\( p_e= \begin{eqnarray} \frac{p^3}{(1-p)^3+p^3}\cdots(4) \end{eqnarray} \)

同様に5倍の反復符号では表4のように場合分けされるので、

表4
変化の回数 受け取るもの 確率 判定 やること
0 00000 \((1-p)^5\) 変化なし 0を復元 (正しい)
1~4 00000, 11111以外 変化あり 再送信を要求
5 11111 \(p^5\) 変化なし 1を復元 (誤り)

\(p_a=(1-p)^5, p_c=p^5\) となり、これを(3)式に入れれば、誤り率は (5)式のようになる。

\( p_e= \begin{eqnarray} \frac{p^5}{(1-p)^5+p^5}\cdots(5) \end{eqnarray} \)

課題3

入力が0, 1のどちらの場合も確率 \(p=0.1\) で変化する通信路で3倍の反復符号を使い、誤り検出を行った場合の誤り率 \(p_e\) を求めよ。ただし、四捨五入して小数第5位までにすること。

課題3ヒント

課題4

入力が0, 1のどちらの場合も確率 \(p=0.1\) で変化する通信路で5倍の反復符号を使い、誤り検出を行った場合の誤り率 \(p_e\) を求めよ。ただし、四捨五入して小数第5位までにすること。

課題4ヒント

電卓での計算結果が「\(1.????\times10^{-5}\)」や「\(1.????E-05\)」のようになることがある。これはどちらも「\(1.????\)かける\(10\)のマイナス5乗」という意味。それを踏まえ、題意に合った書き方 (0.0000?) で回答すること。

提出

ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
課題提出用フォーム
※ 締切は11/23(土) 正午です。提出によって出席・点数がつきます。