2017-07-28

情報通信システム　其の十　20170621

情報通信システム 3年科目

いきなり定理から入っていきます．

定理4.1　通信路符号化定理

通信路容量 $\displaystyle C$ があり、この時 $\displaystyle R\le C$ であれば任意の正定数 $\displaystyle \epsilon$ に関して

　 $\displaystyle P_e\le\epsilon$

にすることができる情報速度 $\displaystyle R$ の符号が存在．大数の法則から証明できるものだが、完全にわかっていないので割愛．後で更新いたします．

ということで５章に入っていきます．

単一パリティ符号

　符号語の $\displaystyle 1$ の数が偶数個になるように符号語の後ろに $\displaystyle 1$ か $\displaystyle 0$ を付け加えた符号語．
　この符号は１個の誤りまで検出できる符号で、誤り検出符号と呼ばれている．(訂正はできない)

(7,4)ハミング符号

　もともと４要素の符号をある規則によって７要素の符号語に変換したもの．規則を下に書いときます．

　　 $\displaystyle \begin{cases}c_1&=&&i_1&+&i_2&+&i_3&&&\\c_2&=&&&&i_2&+&i_3&+&i_4&\\c_3&=&&i_1&+&i_2&+&&+&i_4&\end{cases}$

　この検査記号 $\displaystyle c_1,c_2,c_3$ を符号語の最後に付け加えることによって(7,4)ハミング符号が出来上がる．１つの誤りであれ100％復号することができるという特徴がある！

証明メインだったんで今回はここまで。次回からシンドロームとか、ハミング重みとか書いていきます。

2017-07-04

情報通信システム　其の九　20170615

3年科目情報通信システム

加法二元通信路の通信路容量

前回紹介した誤り源からの信号と入力信号との排他的論理和を出力信号にするという通信路モデルにおける通信路容量を考えていきます．
結論から言うと

　 $\displaystyle C=1-H(E)$

になります．
ではその証明を…

　 $\displaystyle \begin{eqnarray} I(X;Y)&=&H(X)-H(X|Y)\\&=&H(Y)-H(Y|X)\\&=&H(Y)-H(X+E|X)\\&=&H(Y)-H(E|X)\\&=&H(Y)-H(E)\end{eqnarray}$

こんな感じに式変形ができます．ここで、 $\displaystyle H(Y)$ の最大値を考えることにより、通信路容量がわかります．
では、最大値は何なのか…？
$\displaystyle \vec{p}=(\frac{1}{2},\frac{1}{2})$ とするならば、誤り確率 $\displaystyle E$ がどんな値をとろうとも出力確率分布は $\displaystyle \vec{q}=(\frac{1}{2},\frac{1}{2})$ になり一定．このとき $\displaystyle H(Y)$ は最大値 $1$ をとるので、