第4章 離散的通信路の符号化(2)

加法的通信路のモデル

雑音源からの情報をEx-ORで加算する。

雑音源が記憶のない情報源
→二元対称通信路
雑音源が記憶のある情報源

通信路符号化の基本的性質

雑音のない場合

雑音のない通信路に対する符号化定理＝情報源符号化定理
\frac{H(L)}{\log r} \le l \lt \frac{H(L)}{\log r} + \varepsilon

雑音のある場合

シャノンの第2基本定理：通信路符号化定理

(1)RCであれば、任意の正数εに対しあいまいさをR-C+εまで小さくして伝送することができるが、R-Cより小さなあいまいさでは伝送できない。

(証明しました)

通信路符号化法

誤り検出・訂正の原理＝ハミング距離


ハミング距離は距離の三公理を満たす。

  • d(x1,x2)≧0
  • d(x1,x2)=d(x2,x1)
  • d(x1,x2)+d(x2,x3)≧d(x1,x3)

ハミング重み
0でない成分の数（0からの位置）

  • d(x1,x2)=w(x1-x2)

ただし引き算はex-or

ハミング符号は
情報ビット＋検査ビット
r重誤り訂正可能ならばdmin≧2r+1
符号語の個数M \le \frac{2^n}{\sum_{i=0}^r _nC_i}