東京大学 情報理工学系研究科 電子情報学専攻 2023年8月実施 専門 第5問

Author

Josuke

Description

The source is a first-order Markov information source outputting and . is followed by with a probability of and is followed by with a probability of . The following may be used. . For the calculations, two significant digits are sufficient.

(1) Show a state transition diagram of the source .

(2) Obtain the probability of each and output from the source .

(3) Obtain the entropy of the source .

Assume the following four methods of coding to compress the output symbols of the source .

a. fixed-length coding of fixed-length symbol sequences

b. variable-length coding of fixed-length symbol sequences

c. fixed-length coding of variable-length symbol sequences

d. variable-length coding of variable-length symbol sequences

Consider the fixed-length symbol sequences as and , and the variable-length symbol sequences as and that are 's run lengths up to length . The variable-length coding is Huffman coding consisting of and .

(4) Obatain the probability of each of the fixed-length symbol sequences of and .

(5) In the case b , show the Huffman code and obtain the average code length per symbol of the sources .

(6) Obtain the probability of each of the variable-length symbol sequences of and .

(7) In the case c , obtain the average code length per symbol of the source .

(8) Show the Huffman code for the case d and obtain the average code length per symbol of the source .

(9) Arrange the methods of a , b , c , and d from the shortest to the longest in terms of the average code length.

Kai

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

d,b,c,a