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

标签：

• Kyoto-University
• Channel-Coding

Author

Isidore, 祭音Myyura, itsuitsuki, sure

Description

以下ではすべて記憶のない定常情報源を考える。なお、解答には理由も明確に示すこと。

設問1

をアルファベットとし、各記号の生起確率が , で与えられる情報源を考える。 を変化させた時、この情報源のエントロピーの最大値と最小値を求めよ。

設問2

を正の定数とする。 をアルファベットとし、各記号の生起確率が次式で与えられる情報源を考える。

ただし、 とする。 を変化させた時、この情報源のエントロピーの最大値と最小値を求めよ。

設問3

をアルファベットとし、各記号の生起確率が である情報源を考える。 この情報源に対する 2 元ハフマン符号の平均長を求めよ。

設問4

を正整数とし、 とする。 をアルファベットとし、すべての記号の生起確率が である情報源を考える。 この情報源に対する 2 元ハフマン符号の平均長を求めよ。

設問5

次の通信路行列により定まる通信路の容量を求めよ。 なお、入力アルファベットのサイズは 2、出力アルファベットのサイズは 3 である。

設問6

次の通信路行列により定まる通信路の容量を とする。 なお、入力アルファベットのサイズは 、出力アルファベットのサイズは である。

すると、 に関する関数 を用いて、 と書ける。 を求めよ。

Kai

設問1

By solving the following equation

we have . Also,

Thus the maximum of is , the minimum of is .

設問2

By using the method of Lagrange multiplier, we have the Lagrangian for the entropy function:

Then, by solving the following equations,

we have

which implies . Substituting this into the third equation, we get , hence is maximized when .

By Q1 we know that the entropy is minimized when or .

If , then the entropy is minimized when

Comparing the two boundary values:$$\begin{aligned}

If , then and the minimum is .

設問3

設問4

Since we have symbols, by Huffman coding, the Huffman tree is a tree based on a full balanced binary tree of height , but the first leaf node is replaced by a 1-height tree with 2 leaves, forming leaves. The 2 leaves with depth have code lengths of , others ( symbols) having .

設問5

Define the input and output symbols as and respectively, and alphabets are and respectively.

Since

setting as the probability distribution vector, given ,

Hence .

From the recursivity property of Shannon entropy,

For ,

So

and when i.e. , i.e. when , reaches the capacity

設問6

Similarly define as ,

and

where

and when i.e. , the inequality reaches the equality i.e. finds the maximum value as

so

where .