動画の解説を参照
反復符号を使うと、そのまま送信するよりも誤り率を下げられますが、送るデータの量が増え、効率が悪くなってしまいます。
反復符号ほどはデータ量を増やさずに誤り率を下げる方法の一つに、
パリティ検査符号があります。
パリティ検査符号では、符号を規定の数ごとに区切り、その内容に応じて別の符号を付け加えることでも誤り検出を行います。
送信側でやること
元の符号を \(k\) bitごとのブロックに区切る
ブロック中の 1 の数が偶数個なら後ろに 0 を付け加える
ブロック中の 1 の数が奇数個なら後ろに 1 を付け加える
結果として追加後のブロック中の 1 の数は偶数個になります。
通信路で変化が起こらない限りブロック中 1 の数は必ず偶数個です。
受信側でやること
元の符号を \(k+1\) bitごとのブロックに区切る
ブロック中の 1 の数をカウントする
1 が偶数個 → ブロックの最後の符号を削除して情報源符号を復元
1 が奇数個 → 変化があったと判定し、再送信を要求
つまり、前回の「誤り検出」の手順を行うことになります。
\(k=3\) のパリティ検査符号が付け加えられたという前提で、受信側が受け取った
の情報源符号を書いてください。
ただし、変化したものが含まれると思われるブロックの部分は (再送信要求) と書いてください。
課題2解説
※ この問題では 1 箇所だけ変化した符号を入れてあります。
動画の解説を参照
前項で見たように、パリティ検査符号では検査符号を加えたあとの \(k+1\) 個のブロックの中の 1 の数が偶数であるかどうかで変化の有無を判定します。
そのため、ブロック中で偶数回の変化が起きてしまうと「変化はなかった」と判定されてしまうことになります。
\(k=3\) のパリティ検査符号を加え、変化する確率が \(p\) の2元対称通信路を通した場合に誤り検出を行うケースを考えてみましょう。
送信側で「000」を送ろうとした場合は、検査符号も「0」なので「0000」を通信路に通すことになります。
この場合、受信側が受け取るものをまとめると以下の表のようになります。
| 変化の回数 |
受け取るもの |
パターン数 |
確率 |
判定 |
| 0 |
0000 |
1 |
\((1-p)^4\) |
変化なし |
| 1 |
0001～1000 |
4 |
\(p(1-p)^3\) |
変化あり |
| 2 |
0011～1100 |
6 |
\(p^2(1-p)^2\) |
変化なし |
| 3 |
1110～0111 |
4 |
\(p^3(1-p)\) |
変化あり |
| 4 |
1111 |
1 |
\(p^4\) |
変化なし |
ほんとうは変化があったのに「変化なし」と判定してしまうのが灰色の部分です。
ただし、個々の情報源符号についていえば、この灰色に入った場合でも誤りにならないケースがあるので注意が必要です。
ブロック単位で変化が2回起きた場合の情報源符号「
000」の最初の 0 に注目すると、これが変化しているのは全6パターン中3パターンだけです。
0011
0101
0110
1001
1010
1100
他の情報源符号についても同様です。つまり、「ブロック中に2回の変化が起きたことによって1つの情報源符号が最終的に誤ったものになってしまう確率」は \(3p^2(1-p)^2\)
となります。
一方、ブロック単位で変化が4回起きた場合は、そのグループの情報源符号は確実に変化していることになります。
結局、1回の試行で誤った結果を復元する確率を \(p_c\) は
\(p_c = p^4+3p^2(1-p)^2\)
となります。
これに対して、1回の試行で正しい情報源符号を得る確率 \(p_a\) は
\(p_a = (1-p)^4\)
となります。そのため、誤り率は反復符号の場合と同様にして以下のようになります。
\(p_e=\)\(\Large{\frac{p_c}{p_a+p_c}}\)\(=\)
\(\Large{\frac{p^4+3p^2(1-p)^2}{(1-p)^4+p^4+3p^2(1-p)^2}}\)・・・(1)
\(k=3\) のパリティ検査符号を加え \(p=\)
の2元対称通信路を通した場合の誤り率を求めてください。
結果は四捨五入し、1.00～9.99 の範囲の小数第2位までの小数と10の累乗の積の形で書いてください。
課題3解説
※ \(p\) が 1 より十分に小さければ、(1) 式の分子の第1項は第2項に比べて無視できるほど小さく、分母は 1 に近づきます。
そのため、\(p_e\) は \(3p^2\) に近い値になります。
動画の解説を参照
普通のパリティ検査符号では、ブロック中で変化がおきたかどうかを調べることはできますが、ピンポイントでどこが変化したかを知ることはできません。
しかし、以下のようにすれば変化が起きた場所を特定し、誤り訂正を行うことができます。
送信側でやること( \(k=3\) の場合)
- 情報源符号を3桁×3の形に並べる
「001101111...」なら
- それぞれの行の右と列の下にパリティ検査符号を追加する (右下端の符号は「その上の3つ」「その左の3つ」のどちらで作っても同じ値になります)
| 0 |
0 |
1 |
1 |
| 1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
1 |
| 0 |
1 |
1 |
0 |
- 上から1行ずつ順に送信する
この場合なら送るのは「0011 1010 1111 0110」
受信側では、受け取ったものを2と同様の形に並べ、縦と横について1の数をカウントし、すべて偶数になっているかどうかをチェックします。
もし通信路で図のような変化が起こったとすると、左の列と上から2番目の行で1の数が奇数個になります。
すると、変化した場所が「左から1番目、上から2番目」であることを特定でき、それが本当は 1 だったことがわかります。
そのため、再送信を要求しなくても情報源符号を復元できます。
| 0 |
0 |
1 |
1 |
| 1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
1 |
| 0 |
1 |
1 |
0 |
通信路↓
| 0 |
0 |
1 |
1 |
| 0 |
0 |
1 |
0 |
| 1 |
1 |
1 |
1 |
| 0 |
1 |
1 |
0 |
誤り訂正↓
| 0 |
0 |
1 |
1 |
| 1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
1 |
| 0 |
1 |
1 |
0 |
検査符号削除↓
↓
この方法で誤り訂正ができるのは、ひとかたまり((\(k+1)^2\) bit) の中で1回だけ変化が起きたときだけです。
例えば上のケースで図の2箇所に変化がおきると、1行目と3行目、1列目と3列目で1の数が奇数になります。
| 1 |
0 |
1 |
1 |
| 1 |
0 |
1 |
0 |
| 1 |
1 |
0 |
1 |
| 0 |
1 |
1 |
0 |
この場合、受信者側では変化が起こった場所が左図の2箇所なのか、それとも右図の2箇所なのかを知る手段がありません。
\(k=3\) の水平垂直パリティ検査符号が付け加えられたという前提で、受信側が受け取った
の情報源符号を書いてください。
課題4解説
※ この問題では 1 箇所だけ変化した符号を入れてあります。