情報理論を簡単に説明する。（第二章　情報理論の問題）

勉強 情報理論

この記事は、「今井秀樹(1984) 『情報理論』昭晃堂」の第二章を勉強した内容を記録した自分用のノートです。詳しい内容が気になる方は、元の教科書を買ってみてください！

第一章はこちら↓

slimelimestech.hatenablog.com

2.1 問題の提起

ここでは、2元通信路という通信路を使って説明します。2元通信路とは、0か1かという情報のみを伝達する通信路です。 さて、情報として{A,B,C,D}の4文字を伝える場合を考えます。この{A,B,C,D}のような情報源から発生する記号を情報源記号といいます。2元通信路では、時々0と1が誤って伝達されてしまうことがあります。今回はこの誤り率を10-4とします。そして、それぞれの情報源記号の発生確率が下の表のとおりであったとします。このとき次の二つの要請を満たす符号化の方法を考えてみたいと思います。

情報源記号 発生確率
A 0.6
B 0.25
C 0.1
D 0.05


(1) 2元通信路で送った文字数に応じて使用料金がかかるので、送る文字数をできるだけ小さくしたい。
(2) 送られた情報{A,B,C,D}が誤って送られる確率をできるだけ小さくしてほしい。（今回は少なくとも10-6以下にするとする。）


はじめに、次のような符号化C1を考える。
C1:{A,B,C,D}={00,01,10,11}
これは、A,B,C,Dに同じ長さの系列を割り当てる方法です。一般に、情報源符号(今回は、{A,B,C,D})に割り当てられた系列（今回は01,10など）を符号語といい、符号語全体の集合を符号と言います。また、符号語に用いられる記号の集合を符号アルファベットといいます。符号アルファベットの元の数がq個のとき、q元符号と呼びます。（今回は、符号アルファベットは{0,1}で２つ元からなるので、2元符号です。）

しかし、今回の場合{A,B,C,D}の発生確率には大きな差があります。そこで、これらの発生確率に応じて、次のような符号化C2を考えます。
C2: {A,B,C,D}={0,10,110,1110}
この符号化では、系列の長さは異なりますが、全ての系列は必ず末尾に0が来るため、連続して送っても区切れ目がわからなくなる心配はありません。
1情報源記号を送るのに、必要な0,1記号の平均値をLとすると、C1では、L = 2に対して、C2では、
L = 1×0.6 + 2×0.25 + 3×0.1 + 4×0.05 = 1.6
となり、C2の方がより少ない使用料金で送ることができます。

次に(2)の問題を考えます。C1 またはC2の方法でそのまま送っても(2)の条件を満たさないので、なんらかの符号化を行う必要があります。ここでは、同じ数字を3回ずつ送るという方法をとります。すると3つの記号うち1つまでは、誤りが許容されることとなり、（例えば、101は1とみなします。）１つの記号あたりで復号を誤る確率は、（復号誤り率という）は、例えばC1で送る場合は、
3C 2×(10-4)2(1-10 -4) + 3C 3×(10-4)3=2.9998 × 10-8
となり、各符号語には、2つ記号があることから、複合誤り率は、5.9996×10 )-8となり、条件を満たします。また、C2で送る場合も、途中計算は冗長になるため省略しますが、およそ10 -7程度となり、条件を満たします。
ここで問題となるのは、これより効率の良い符号化はないのか？この符号化は、どの程度良い符号化なのか？といったことです。情報理論では、これらを主な問題として扱います。

2.2 問題の設定

今後特に断りがない限り情報源、通信路はデジタルであるとします。

2.2.1 問題の整理 前節で具体例を用いて説明したように、情報理論の中心課題は、(1)通信路使用の効率の向上、(2)信頼性の向上、の二つです。一般に効率と信頼性はトレードオフの関係になっています。そこで、符号化をする際は、(1)と(2)を同時に検討することが望ましいですが、これは普通非常に難しいタスクです。それゆえ、(1)と(2)の要請に対する符号化を、それぞれ、情報源符号化、通信路符号化として分けて考えてきました。まず、情報源符号化を行い、続いて通信路符号化を行うのです。（誤りが生じるのは通信路であるため、逆の順序ではうまくいきません。）このように問題を分割して、独立に考えることで、見通しがよくなります。

2.2.2 情報源符号化の問題 まず前提条件として、情報源符号化を行う際には、通信路で誤りが起きる確率は、十分小さいと仮定します。 情報源符号化とは、情報源から発生する情報源記号の系列（情報源系列といいます。）を通信路の効率化のための別の系列（符号系列といいます。）に変換する操作のことをいいます。
情報源符号化の第一の問題は、
【問題Ⅰ】できるだけよい情報源符号化法および復号法を見つけ出すこと
です。
ここで、よいというのは、1情報源当たりの符号系列の長さの平均値（ 1情報源記号当たりの平均符号調）ができるだけ小さいものという意味です。これが、情報源符号化の最も基本的な評価基準です。
また、他の評価基準としては、実際の装置化の簡単さ、符号化、復号にかかる時間の長さなどが挙げられます。
ここでは、情報源符号化として可逆なもの（可逆符号化あるいは情報無損失符号化といいます。）ばかりを考えてきましたが、場合によっては、復号結果が元の通報と多少違っていても許される場合があります。（非可逆符号化あるいは情報損失符号化といいます。）この場合は、1情報当たりの平均符号長をさらに短くできる可能性があります。非可逆符号化における、元の通報と復号の違いのことをひずみといいます。非可逆符号化の場合には、ひずみが許容範囲内に収まり、1情報源記号 当たりの平均符号長が小さく、しかも装置化が簡単な符号法がよい符号化ということになります。
さて、ある情報源符号化を考えたとそれがどの程度よいものなのかを知ることは重要です。そこで、情報源符号化の第二の問題として、
【問題Ⅱ】情報源符号の限界を知ること
があります。
これは、ある情報源と通信路が与えられたときに、1情報源記号当たりの平均符号長をどこまで小さくできるかという問題です。この問題についても歪みが許される場合とそうでない場合、すなわち、可逆符号化の場合と非可逆符号化の場合に分けられます。

2.2.3 通信路符号化の問題

通信路符号化の問題を考える際には、情報源と情報源符号化をまとめて新たな情報源として考え、情報源復号とあて先をまとめて新たな後先として考えます。
さて、符号系列（通信路符号化された通報）が通信路を経て相手側に届く際、通信路においては誤りが生じうるため、通信路の出力系列は入力系列と必ずしも一致しません。そこで、この出力系列のことを受信系列といいます。そして通信路復号とは、この受信系列から元の情報源系列を推定することをいいます。

【問題Ⅲ】 できるだけよい通信路符号化および復号法を見つけ出すこと

ここでも"よい"という言葉の意味を明確にする必要があります。誤りに対処するためには、余分な符号、すなわち、冗長性を付ける必要があります。逆に言えば、冗長性を付けることによって初めて、信頼性の向上が可能になるのです。しかし、符号化法によっては、付加した冗長性が、信頼性向上にはあまり有効には働かず、無駄に費やされてしまう場合もあります。したがって、よい符号化の最も重要な条件として、付加した冗長性が信頼性の向上にできるだけ有効に用いられることがあげられます。　　 またこのほかにも、装置化や符号化、復号に対する遅延時間の問題も極めて重要です。通信路符号化の場合は、一般に、符号化よりも復号の方が、複雑となるので、特に、復号の装置化の簡単さは符号化法の重要な評価基準となります。


【問題Ⅳ】 通信路符号化の限界を知ること

これは例えば、復号して得られた情報源記号が誤っている確率（復号後の記号誤り率といいます）を、ある値以下に抑えた時に、付加すべき冗長度をどこまで短くすることができるかという問題です。

2.3 問題の発展

これまで、情報源符号化と通信路符号化は分けて考えてきました。その方が問題を簡単に考えられるためです。しかし、本来両者は深くかかわっており、両者を統合して考えることにより、よりよい符号化方式が得られる可能性があります。
情報源符号化においても通信路符号化においても歪みを許容することによって、効率を上昇させることができます。そこで、全体としての効率を最大にするためには、全体として許されるひずみをそれぞれの符号化にどのように割り振るかという問題を考える必要があります。従来、デジタル通報に対しては、情報源符号化のひずみを０として、通信路符号化の部分だけひずみの発生を認めることが多いです。多く場合この割り振りで最適となることが知られていますが、情報源符号化にある程度歪みを割り振った方が効果的な場合もあります。 もう一つ、情報源符号化と通信路符号化の関わりにおける問題として、情報源符号化はそれが有効なものであればあるほど、誤りに足して弱くなるという問題点です。 これらのような問題を扱うには、情報源符号化と通信路符号化を統合する必要がありますが、その研究はあまり進んでいないというのが現状です。