九州大学 システム情報科学府 情報理工学専攻 2018年8月実施 情報理論

Author

Yu

Description

【問 1】

情報源アルファベットが の離散無記憶情報源があり, 記号 の出現確率 が以下の表で与えられている。ただし, とする。

以下の問いに答えよ。

(1) この情報源のエントロピーを の関数として求めよ。

(2) のときのこの情報源に対する 元ハフマン符号を つ求めよ。

(3) (2)の符号の平均符号長 (符号長の期待値)を の関数として求めよ。

(4) のときのこの情報源に対する 元ハフマン符号の平均符号長を求めよ。

(5) この情報源に対する 元ハフマン符号の平均符号長を とおく。 に対する のガラフをかけ。

【問 2】

アルファベット 上の 情報源 の遷移確率行列が

で与えられているとき, 次の各問に答えよ。ただし, は のもとで となる条件付き確率を表す。

(1) の固有値の一つが であることを示せ。

(2) 行ベクトル が固有値 に対応する の左固有ベクトルであり, その要素の総和が であるとする。 の持つ意味を述べよ。ただし, 固有値 に対応する の左固有ベクトルとは, を満たすゼロでない行ベクトル のことである。

(3) 固有値 に対応する の右固有ベクトルを求めよ。ただし, 固有値 に対応する の右固有ベクトルとは, を満たすゼロでない列ベクトル のことである。

(4) 任意のベクトル について, でその要素の絶対値の総和を表す。行ベクトル について, を示せ。

(5) の任意の固有値の絶対値は 以下であることを示せ。

Kai

【問 1】

(1)

(2)

(3)

(4)

(5)

【問 2】

(1)

(2)

はマルコフ情報源の定常分布

(3)

(4)

(5)