情報理論 第10回 通信路

変化と消失

通信路とは、送信者と受信者の間にある通信手段のことをいい、具体的にはLANケーブルやWi-Fiの電波などがこれにあたる。
通信路を通るのは0か1の情報だが、実体をもった「0」「1」というものが存在するわけではないので、例えば
のようにして通信路を通れる形にする。通信路を通すとノイズの影響でこの波形に乱れが生じるが、受信者はたとえば
と解釈することで、もとの情報と同じ0, 1を取り出すことができる (このほかにもデジタル情報に変える方法はいろいろある)。

ところが、まれにこの乱れが極端に大きくなり

のように、もともと0だったはずの信号が1に変わってしまう (またはその逆) ことがある。このような現象を変化と呼ぶ。

このような変化の影響を少なくするために、
という解釈のしかたをすることで、どちらなのか怪しい場合はあえて0, 1のどちらになるかを決めない方法もある。この方法では、乱れが大きい場合は

のようにときどき判定できない状態になる。こうなることを消失と呼ぶ。また、この方法で解釈する場合でも乱れが十分大きければ消失だけでなく変化も起こる。

通信路線図

概要

通信路への入力と出力の関係を図で表わしたものを通信路線図という。
描き方のルール
  • 左側に入力、右側に出力の値を書く。
  • 入出力のありうる組み合わせをすべて矢印でつなぐ。
  • 矢印の隣にその確率を書く。

例えば「確率 \(p\) で0から1に変化し、確率 \(q\) で1から0に変化する」という通信路なら
  • 入力が0で出力が0の確率:\(1-p\)
  • 入力が0で出力が1の確率:\(p\)
  • 入力が1で出力が0の確率:\(q\)
  • 入力が1で出力が1の確率:\(1-q\)
になるので、通信路線図は

のようになる。

消失がある場合は、入力は0, 1の2通り、出力は0, x, 1の3通りになる。例えば「入力が0, 1のどちらでも確率 \(p\) で消失し、変化は起こらない」という通信路なら、通信路線図は

のようになる。

課題1

全く変化も消失も起こらない通信路の通信路線図を描け。

課題2

「入力が0のときは確率 \(p\) で変化、確率 \(q\) で消失し、入力が1のときは確率 \(r\) で変化、確率 \(s\) で消失する」通信路の通信路線図を描け。
  • 入力が0の場合は「0のまま」「1に変化」「消失」の3通りの結果がある。「0のまま」の確率は問題文には書かれていないが、3通りの確率を足せば1になることから確率は求められる。入力が1の場合も同様。

通信路行列

概要

通信路への入力と出力の関係を行列の形で表わしたものを通信路行列という。
書き方のルール
  • 行列の左側に「 \(T=\) 」を書く。
  • 入力と出力の組み合わせの確率を行列の要素とする。
  • 横方向を入力、縦方向を出力とする。

消失がない通信路で、
  • \(p_{00}\):入力が0で出力が0になる確率
  • \(p_{01}\):入力が0で出力が1になる確率
  • \(p_{10}\):入力が1で出力が0になる確率
  • \(p_{11}\):入力が1で出力が1になる確率

と書くとすると、通信路行列は
\( T= \begin{bmatrix} p_{00} & p_{01} \\ p_{10} & p_{11} \end{bmatrix} \)

のようになる。例えば通信路線図の例で挙げた「確率 \(p\) で0から1に変化し、確率 \(q\) で1から0に変化する」という通信路では、通信路行列は
\( T= \begin{bmatrix} 1-p & p \\ q & 1-q \end{bmatrix} \)

のようになる。

消失がある場合は、出力が0, x, 1の3通りなので、通信路行列は2行3列になる。入力が0, 1のときに消失する確率をそれぞれ \(p_{0x}\), \(p_{1x}\) と書くことにすると、通信路行列は
\( T= \begin{bmatrix} p_{00} & p_{0x} & p_{01} \\ p_{10} & p_{1x} & p_{11} \end{bmatrix} \)

となる。例えば通信路線図の例で挙げた「入力が0, 1のどちらでも確率 \(p\) で消失する」という通信路なら、通信路行列は
\( T= \begin{bmatrix} 1-p & p & 0 \\ 0 & p & 1-p \end{bmatrix} \)

となる。

課題3

課題1の通信路の通信路行列を記述せよ。

課題4

課題2の通信路の通信路行列を記述せよ。

入出力情報を表わす事象系

概要

「0が入力される」「1が入力される」という事象から事象系 \(X\)、「0が出力される」「1が出力される」という事象から事象系 \(Y\) を作ることができる。
\(X\) は情報源の性質を表わすものであり、0, 1それぞれが入力される確率を \(p_0\), \(p_1\) とすると
\( X= \begin{bmatrix} x_0 & x_1 \\ p_0 & p_1 \end{bmatrix} \)

のように書ける。一方、通信路行列が
\( T= \begin{bmatrix} p_{00} & p_{01} \\ p_{10} & p_{11} \end{bmatrix} \)

なら、0が出力されるのは
  • 入力が0で(そうなる確率は \(p_0\))、0のまま変化しなかった(そうなる確率は \(p_{00}\))
  • 入力が1で(そうなる確率は \(p_1\))、0に変化した(そうなる確率は \(p_{10}\))
の2つのケースの合計で、確率は \(p_0p_{00}+p_1p_{10}\) になる。

同様に、1が出力されるのは
  • 入力が0で(そうなる確率は \(p_0\))、1に変化した(そうなる確率は \(p_{01}\))
  • 入力が1で(そうなる確率は \(p_1\))、1のまま変化しなかった(そうなる確率は \(p_{11}\))
の2つのケースの合計で、確率は \(p_0p_{01}+p_1p_{11}\) になる。

つまり、出力の事象系は
\( Y= \begin{bmatrix} y_0 & y_1 \\ p_0p_{00}+p_1p_{10} & p_0p_{01}+p_1p_{11} \end{bmatrix} \)

となる。

ところで、\(X, Y\) の下の行だけを取り出したものを \(P_x, P_y\) と置くと、
\(P_x=\begin{bmatrix}p_0, & p_1\end{bmatrix}\)
\(P_y=\begin{bmatrix}p_0p_{00}+p_1p_{10}, &p_0p_{01}+p_1p_{11}\end{bmatrix}\)

のように書ける。これも行列の一種だが、1行だけなので要素の区切りがわかりやすいように、例外的にコンマで区切って書く。
行列の掛け算のルール (掛け算の左の行列上を左から右に、右の行列上の位置を上から下に移動しながら要素をかけたものを足し合わせる) に従って \(P_xT\) を計算すれば、
\( \begin{eqnarray} &&P_xT\\ =&&\begin{bmatrix}p_0, & p_1\end{bmatrix} \begin{bmatrix} p_{00} & p_{01} \\ p_{10} & p_{11} \end{bmatrix}\\ =&&\begin{bmatrix}p_0p_{00}+p_1p_{10}, &p_0p_{01}+p_1p_{11}\end{bmatrix} \end{eqnarray} \)

となる。これはまさに上で求めた \(P_y\) に等しい。つまり、\(Y\) の下の行は行列の掛け算で求められる。
\( P_y=P_xT \)

課題5

送信側の事象系が \( X= \begin{bmatrix} x_0 & x_1 \\ \frac{1}{2} & \frac{1}{2} \end{bmatrix} \) であるとき、課題2 (課題4と共通) の通信路を通った出力の事象系 \(Y\) を記述せよ。

消失も起こるので、出力の事象系は \( Y= \begin{bmatrix} y_0 & y_x & y_1 \\ ? & ? & ? \end{bmatrix} \) という形になる。
\(P_x=\begin{bmatrix}\frac{1}{2},&\frac{1}{2}\end{bmatrix}\) と、課題4で求めた \(T\) の積を計算すれば \(Y\) の下の行が求められる。
事象系なので、3つの確率を足した値は1になるはず。
inserted by FC2 system