シャノンの通信符号化定理について紹介します。
まず、通信において、メッセージを送ろうとすると
送る途中でかならずノイズが入りメッセージの一部がおかしくなる。
という背景があります。
これに対処する方法としてメッセージを0とか1とした場合、この０、１をわざと
000とか111とかと表現(通信符号化)しておくってやれば、途中で一部がひっくり返っても
001とかであって、これはまあ000のことであろうと予想がつくわけです。
０００、１１１を符号語と呼びます。このとき、符号化長は３であるといいます。
符号語の数から求まる自己エントロピーを全パターンでわったものが符号化率です。
今の場合、(log2)/2^3 = 1/8となります。
このように符号語を入れたときにどんな出力が得られるのかというのは
入力と出力の関数的なものとなるのですが、ノイズのために確率的になります。
よって、関数ではなく条件付き確率で記述されることになります(通信行列)。
この条件付き確率から相互情報量を計算したものを通信容量と呼びます。
ここで最大誤り率という誤り率を計算することができるのですが
シャノンの通信符号化定理によると(通信行列が無記憶であるという仮定では)
通信容量が符号化率より大きい場合、符号化長を十分大きく
とることで最大誤り率をゼロに近づけることができる(そのような符号化が存在する)というものです。
その証明には代表系列とランダム符号化という手法を使うのですがそれは違う機会に紹介したいと思います。
今月、これを知ってこれはとても非自明な結果だと感銘を受けました。
これは古典通信の結果ですが、この量子計算については現在でも議論があるようです。
入会申込
ログイン
