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

Author

Isidore, 祭音Myyura

Description

以下では、実数 が を満たすときに、 を すなわち 以上の最小の整数、と定義する。 たとえば、, である。

情報源アルファベットが であるような記憶のない定常情報源 を考える。 情報源 が記号 を発生させる確率を と表し、

と定義する。 さらに、 が成立していると仮定して、 の記号 と $$ による符号化 を

と定義する。 たとえば、 かつ であれば、 の 2 進表現は であり、 であるから、 である。 情報源 の情報量を , 平均符号長を で表す。

設問 1

記号数が であり、 が以下のように与えられている場合に符号 を求めよ。

設問 2

次の不等式が成立することを符号化 の定義を用いることによって示せ。

設問 3

記号数が であり、 が成立するような数列 をすべて与えよ。 また、与えた数列の中で が最小のものについて、符号 を与えよ。

設問 4

が成立し、かつ が成立するとき、 がハフマン符号になることを、 をハフマン符号として構成する過程によって示せ。

設問 5

が成立し、かつ、ある について

が成立するとき、 がハフマン符号になることを、 をハフマン符号として構成する過程を与えることにより示せ。

Kai

設問1

設問2

By the definition of , we have

since , we multiply both sides of the equation by ,

hence

that is

設問3

Sequences are:

The first sequence is the one that is minimized, the codes are

設問4

設問5