京都大学 情報学研究科 知能情報学専攻 2020年8月実施 専門科目 S-4

Author

祭音Myyura

Description

記号の集合 をアルファベットとする記憶のない定常情報源 を考える。 における各記号の生起確率 は

とする。

設問1 情報源 のエントロピー を求めよ。

設問2 の各記号を下表の符号 により に２元符号化することを考える。符号 は一意に復号可能か、理由とともに示せ。

設問3 情報源 から得られる十分長い記号列を符号 で２元符号化した系列を考える。この２進系列から任意に 1 bit を取り出すとき、取り出した記号が１である確率を求めよ。

設問4 下の通信線路図によって与えられる非対称の２元通信路を考える。 の生起確率が設問3のように与えられるとき、相互情報量 を求めよ。

設問5 情報源 から得られる記号を下表の符号 で２元符号化し、設問4の通信路で伝送して で復号することを考える。復号された記号を事象 とするとき、相互情報量 を求めよ。

設問6 情報源 が生成する記号列を設問4の通信路で伝送する際の 2 bit の固定長２進符号として、符号 が最適かどうかについて論じよ。

Kai

設問1

設問2

符号 の反転した符号 を考える。

符号 のいずれの符号語も他の符号語の接頭になっていないため、符号 は瞬時符号である。 よって、符号 は一意に復号可能である。

したがって、情報源 から得られる記号を反転して符号 に基づいて符号化し、復号するときは、反転して符号 に基づく復号を利用することで，一意に復号することができる。

設問3

設問4

設問3の結果より、

与えられた２元通信路より、

より、

従って、

設問5

定常情報源 における各記号の生起確率より、

定常情報源 において が生起するとき、 の符号化方法を考えすると、

同様に、

よって、

が得られる。従って、

設問6

設問4の通信路は、入力が の場合は誤りがないため、平均符号長が最大の記号に極力多くの を割り当てるべきである。

2 bit の固定長2進符号の場合の平均符号長 を計算すると、

がわかる。よって、 に を割り当てるべきである。故に、 は最適ではない。