動画の解説を参照
今回以降の授業では、第5～7回とは異なり「符号」という用語は「0」「1」 (符号アルファベット) を指すものとします。
通信路にそのまま符号を入れると、受け取った側では受け取った符号に変化があったかどうかを知る手段がありません。
そこで、一般的にデジタル通信では
検査符号 (変化が起こったかどうかを知るための符号) を追加してから送信を行います。
追加の符号の作り方にはいくつかのタイプがありますが、ここでは反復符号について紹介します。
送信側と受信側で行う手順は以下の通りです。
送信側 : もとの符号をそれぞれ \(n\) 倍に増やす
受信側 : 受け取った符号を \(n\) 個ずつに区切り、それぞれのブロックで多い方の符号を1つ残す
具体的に3倍の反復符号について例を見てみましょう。
送信側は、「0」という符号を送りたいときは「000」、「1」を送りたいときは「111」というように、元々の符号を3倍に増やして送ります。
送られるもののうち「元の符号」を
情報源符号、付け加えられたものを
検査符号と呼びます。
0 → 000
1 → 111
送信側が「001011」という符号を送りたいときはこのようになります。
001011
↓
000 000 111 000 111 111
通信路で変化が起こらなければこれがそのまま受信側に届きますが、低確率ながらも変化は起こります。例えばこの2つが変化したとしましょう。
000 000 111 000 111 111
↓
000 010 111 000 111 110
受信者は3bitずつのブロックに区切って考え、多数決で残ったものを情報源符号とします。
この過程を
誤り訂正と呼びます。
000 010 111 000 111 110
↓
001011
こうすることで、通信路で変化が起きても受信側は情報源符号と同じものを得られます。
ただし、いつでもこのようにうまくいくとは限りません。非常に低い確率ですが、ひとつのブロックで2回変化が起こることもありえます。
上記と同じ「001011」を送ろうとしたときに、通信路でこのように変化した場合は、
001011
↓
000 000 111 000 111 111
↓
000 011 111 000 111 111
↓
011011
のように受信者はもとの情報源符号とは異なったものを得ることになります。
※ 準備 : 学籍番号を入れて「入力」をクリック (タップ) してください。
3倍の反復符号で、
を受け取ったものとして誤り訂正を行い、情報源符号を書いてください。
課題1解説
動画の解説を参照
前項の後半で見たように、反復符号で誤り訂正を行っても誤った結果を得ることがあります。
具体的にそのようなことが起こる確率を
誤り率と呼びます。
一般に、誤り率は \(p_e\) で表します。
以下の2元対称通信路で誤り率がどうなるか考えてみましょう。
\(\boldsymbol{T} =\begin{bmatrix}
1-p & p \\
p & 1-p
\end{bmatrix}
\)
情報源符号 0 を送る場合は、送信側で 000 にしてから送ります。
この3bitが通信路を通るときにそれぞれの桁で変化する可能性があるので、受信側が受け取るものは 000～111の8通りがありえます。
それが何であったかを多数決で判断すると、表のように 2, 3回の変化があった場合には誤った結果になります。
| 変化の回数 |
受け取るもの |
確率 |
復元されるもの |
| 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 = p^3 + 3p^2(1-p)\)・・・(1)
となります。
(ここで考えているのは2元対称通信路なので、1から0に変化する確率も \(p\) です。そのため、1を送ろうとした時の誤り率も (1) と同じになります)
5倍の反復符号、つまり情報源符号を5回ずつ繰り返して送る方法でも同様に考えられます。
この場合、多数決では「3つ以上」のものが採用されるので、0 を送るために 00000 を通信路に通すと
| 変化の回数 |
受け取るもの |
確率 |
復元されるもの |
| 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 (誤り) |
となるので、誤り率は
\(p_e=p^5+5p^4(1-p)+10p^3(1-p)^2\)・・・(2)
となります。
概要の通信路で、\(p\) =
の場合に3倍の反復符号で誤り訂正を行った場合の誤り率を求めてください。
結果は整数部分が1桁で、四捨五入して小数第2位までにした小数と10の累乗の形で書いてください。
課題2解説
課題2と同じ通信路で、5倍の反復符号で誤り訂正を行った場合の誤り率を求めてください。
結果は整数部分が1桁で、四捨五入して小数第2位までにした小数と10の累乗の形で書いてください。
課題3解説
検査符号が増えた分、誤り率は課題2の結果より小さくなるはずです。
動画の解説を参照
前項で見たように、単純に多数決で元の符号を復元すると、通信路で変化が多数起こった場合に誤ったものが復元されてしまいます。
そこで、変化が起こったと思われる場合は送信者側に再送信を要求し、改めて符号を送りなおさせる手法があります。これを
誤り検出といいます。
3倍の反復符号では変化がなければ1ブロック分の符号はすべて同じになるはずなので、「001」や「101」などの「不揃いなもの」を受け取ったときは通信路で変化が起きたと判定します。
ただし、3回変化がおきると「111」になってしまい、受け取った側はこれを「変化なし」と判定してしまうので、誤ったものが復元されてしまうことになります。
この手法を使ったときの誤り率の求め方は多少複雑になります。
1回の送信では「正しいものを復元」「再送信」「誤ったものを復元」の3つのケースが発生します。
このうち「再送信」になったときの次の送信でも再びこれらの3つのケースが発生するので、図のような過程を繰り返して最終的に下のグループに入ったものが「誤り」となります。
1回の送信について考えたときに、正しい結果を復元する確率を \(p_a\), 再送信になる確率を \(p_b\), 誤った結果を復元する確率を \(p_c\) と置きます。
何回目の試行でも、「正しいものを復元」と「誤ったものを復元」のグループに入る比率は
\(p_a : p_c\)
なので、最終的に「誤り」のグループに入る確率、つまり誤り率は「誤り / (正しい + 誤り)」の割合であり、
\(p_e=\)\(\Large{\frac{p_c}{p_a+p_c}}\)・・・(3)
となります。
0から1, 1から0への変化の確率が \(p\) の2元対称通信路で具体的に値を求めてみましょう。
前項と同様に 0 を送る場合について考えると、「正しい」「再送信」「誤り」のケースはこの表のようにまとめられます。
| 変化の回数 |
受け取るもの |
確率 |
判定 |
やること |
| 0 |
000 |
\((1-p)^3\) |
変化なし |
0を復元 (正しい) |
| 1～2 |
000, 111以外 |
|
変化あり |
再送信を要求 |
| 3 |
111 |
\(p^3\) |
変化なし |
1を復元 (誤り) |
つまり
\(p_a=(1-p)^3\)
\(p_c=p^3\)
です。これを (3) 式に入れると、誤り率は
\(p_e=\)\(\Large{\frac{p^3}{(1-p)^3+p^3}}\)・・・(4)
となります。
同様に5倍の反復符号では
| 変化の回数 |
受け取るもの |
確率 |
判定 |
やること |
| 0 |
00000 |
\((1-p)^5\) |
変化なし |
0を復元 (正しい) |
| 1～4 |
00000, 11111以外 |
|
変化あり |
再送信を要求 |
| 5 |
11111 |
\(p^5\) |
変化なし |
1を復元 (誤り) |
なので、誤り率は
\(p_e=\)\(\Large{\frac{p^5}{(1-p)^5+p^5}}\)・・・(5)
となります。
課題1～3と同じ通信路で、3倍の反復符号で誤り検出を行った場合の誤り率を求めてください。
結果は整数部分が1桁で、四捨五入して小数第2位までにした小数と10の累乗の形で書いてください。
課題4解説
手間が増えた分、誤り率は課題2の結果より小さくなるはずです。
課題1～4と同じ通信路で、5倍の反復符号で誤り検出を行った場合の誤り率を求めてください。
結果は整数部分が1桁で、四捨五入して小数第2位までにした小数と10の累乗の形で書いてください。
課題5解説
検査符号が増えた分、誤り率は課題4の結果より小さくなるはずです。