第12回　反復符号とパリティ検査符号 (1)

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

概要

通信路にそのまま信号を入れると、受け取った側では受け取った信号に変化があったかどうかを知る手段がない。そこで、一般的にデジタル通信では変化が起こったかどうかを知るための符号を追加してから送信を行う。追加の信号の作り方にはいくつかのタイプがあるが、ここでは反復符号について学ぶ。

反復符号
送信側 : もとの信号をそれぞれ \(n\) 倍に増やす
受信側 : 受け取った信号を \(n\) 個ずつに区切り、多い信号を採用する

例 (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
のように、誤ったものが復元されてしまう。

通信路行列 \( T= \begin{bmatrix} 1-p & p \\ p & 1-p \end{bmatrix} \) で表わされる通信路では、もとの符号が0だった場合に受信者が受け取るものは000～111の8通りあり、このうち0に復元されるのは000, 001, 010, 100の4通りで、それ以外では1になってしまう。

変化の回数受け取るもの確率復元されるもの
0000 \((1-p)^3\) 0 (正しい)
1001, 010, 100 \(p(1-p)^2\) 0 (正しい)
2110, 101, 011 \(p^2(1-p)\) 1 (誤り)
3111 \(p^3\) 1 (誤り)

結局、0を送ったときに元と違う1が復元されてしまう確率 \(p_e\) は、受け取ったものが (111である確率) + (110である確率) + (101である確率) + (011である確率) なので、

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

になる (1を送ったときに0が復元されてしまう確率も同じ)。このような「元の符号1ビットが最終的に誤ったものになる確率」のことを誤り率という。
(反復符号を使わずに元の符号をそのまま送った場合は、通信路で変化する確率がそのまま誤り率になる)

課題1

入力が0, 1のどちらの場合も確率 \(p=0.1\) で変化する通信路で3倍の反復符号を使い、誤り訂正を行った場合の誤り率を求めよ。
  • (1) 式の \(p\) に0.1を入れて計算するだけ。

課題2

入力が0, 1のどちらの場合も確率 \(p=0.1\) で変化する通信路で5倍の反復符号を使い、誤り訂正を行った場合の誤り率を求めよ (四捨五入して小数第3位まで)。
  • 5倍の反復符号で誤ったものが復元されてしまうのは、1セットで3回以上変化が起きたとき。
  • 5倍の反復符号での (1)式にあたるものを求めるには、変化の回数0～5の場合について上の表のようなものを書いてみるとよい (「受け取るもの」は全部書く必要はない)。
  • 1回変化するパターンは00001, 00010, 00100, 01000, 10000の5通り。2回変化、3回変化するパターンを数え上げるのは面倒だが、「パスカルの三角形」の5段目を使えばパターン数はすぐにわかる。
求めた値が意味するもの
課題1, 2の結果を比較すると、課題2の方が小さい値になる。これは、「手間をかけた分だけ最終的に間違ったものを復元してしまう確率を減らせた」と解釈できる。

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

概要

上で見たように単純に多数決で元の符号を復元すると、通信路で変化が多数起こった場合に誤ったものが復元されてしまう。そこで、変化が起こったと思われる場合は送信者側に再送信を要求し、改めて信号を送りなおさせる手法がある。これを誤り検出という。反復符号では、変化がなければ1セット分の符号はすべて同じになるはずなので、「001」や「101」などの「不揃いなもの」を受け取ったときは通信路で変化が起きたと判定する。もとの符号が0なら
変化の回数受け取るもの確率判定やること
0000 \((1-p)^3\) 変化なし0を復元 (正しい)
1001, 010, 100 \(p(1-p)^2\) 変化あり再送信を要求
2110, 101, 011 \(p^2(1-p)\) 変化あり再送信を要求
3111 \(p^3\) 変化なし1を復元 (誤り)

のように、1回または2回変化が起きた場合は再送信を要求する。ただし、3回変化がおきると受け取った側はこれを「変化なし」と判定してしまうので、誤ったものが復元されてしまうことになる。
この手法を使ったときの誤り率の求め方は多少複雑になる。1回の送信では「正しいものを復元」「再送信」「誤ったものを復元」の3つのケースが発生するが、「再送信」になったときの次の送信でも再びこれらの3つのケースが発生するので、図のような過程を繰り返して最終的に下のグループに入ったものが「誤り」となる。


最終的に誤った結果になるのは
  • 1回目の送信で誤った結果を復元
  • 1回目は再送信となり、2回目の送信で誤った結果を復元
  • 2回目までは再送信となり、3回目の送信で誤った結果を復元
  • \(\cdots\)
となる確率をすべて足し合わせたものになる。

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

\( \begin{eqnarray} p_a&=&(1-p)^3\cdots(2)\\ p_c&=&p^3 \hskip2.5em \cdots(3) \end{eqnarray} \)

となる。また、1回の送信ではこれらの3通りのどれかになるため \(p_a, p_b, p_c\) の和は1になるので、\(p_b\) は

\( p_b=1-(p_a+p_c)\cdots(4) \)

のように表わせる。これらを使って考えれば、

\(p_c\) (1回目の送信で誤った結果を復元する確率)
\(p_bp_c\) (1回目は再送信となり、2回目の送信で誤った結果を復元する確率)
\(p_b^2p_c\) (2回目までは再送信となり、3回目の送信で誤った結果を復元する確率)
\(\cdots\)
を足し上げたものが誤り率になる。

\( p_e=p_c\left(1+p_b+p_b^2+\cdots\right) \)

ここで数学の公式

\( \begin{eqnarray} 1+x+x^2+\cdots=\frac{1}{1-x} \end{eqnarray} \)

を使えば、

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

となり、(4)を使えば

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

で、(2), (3)を使えば結局

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

という形で表わせる。

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

課題3

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

課題4

入力が0, 1のどちらの場合も確率 \(p=0.1\) で変化する通信路で5倍の反復符号を使い、誤り検出を行った場合の誤り率を求めよ (四捨五入して小数第5位まで)。
  • (2)～(5) 式の「3乗」が「5乗」に変わるだけ。
求めた値が意味するもの
課題1と3, 2と4の結果を比較すると、課題3, 4の方が小さい値になる。これは、「再送信の手間をかけた分だけ最終的に間違ったものを復元してしまう確率を減らせた」と解釈できる。また、当然ながら反復回数の多い課題4の方が課題3の誤り率よりも小さくなる。

パリティ検査符号

概要

符号を規定のビット数ごとに区切り、その内容に応じて別の符号を付け加えることでも誤り検出を行うことができる。パリティ検査符号では、情報源 (送信側) では
  • 元の符号を \(k\) ビットごとのブロックに区切る
  • ブロック中の1の数が偶数個なら後ろに0を付け加える
  • ブロック中の1の数が奇数個なら後ろに1を付け加える

という処理を行う。こうすることで、追加後の \(k+1\) ビットのブロックの1の数は常に偶数個になるはずなので、通信路で変化が起こらない限りこの条件は満たされる。そこで受信者は
  • 受け取った符号を \(k+1\) ビットごとのブロックに区切る
  • ブロック中の1の数が偶数個なら変化がなかったと判定して最後の符号を削除 (元の符号を復元)
  • ブロック中の1の数が奇数個なら変化があったと判定して再送信を要求
のような処理を行う。

例 ( \(k=4\) の場合)
変化がなければ
奇数　偶数　奇数偶数個　偶数個　偶数個
元の符号
0010 0110 1110
→
00101 01100 11101
↓ 変化なし
復元された符号
0010 0110 1110
←
00101 01100 11101
偶数個　偶数個　偶数個
のように復元できる。







通信路で変化がおきると、受信者側で1が奇数個含まれるブロックがみつかる。その場合は再送信を要求する。
元の符号
0010 0110 1110
→
00101 01100 11101
↓ 変化
00101 01100 10101
偶数個 偶数個 奇数個→再送信を要求

「チェック用に追加した符号」(この例ではそれぞれのブロックの5ビット目) のことを検査符号、もとの符号のことを情報源符号という。
この呼び名は今回の前半で見た反復符号でも同様で、「0」を「000」にするケースでは最初の0が情報源符号、後ろの00が検査符号にあたる。

課題5

符号「011110001111」にパリティ検査符号を追加したものを記述せよ。ただし \(k=4\) とする。

課題6

パリティ検査符号追加済みの以下の符号を受け取ったとき、通信路で変化があったかどうかを判定し、以下のものを解答せよ。ただし \(k=3\) とする。
  • 変化があった場合 → 「変化あり」と解答
  • 変化がなかった場合 → 情報源符号を記述
  1. 101001110101
  2. 001110011111
inserted by FC2 system