京都大学 情報学研究科 通信情報システム専攻 2020年8月実施 専門基礎A [A-5]

Author

SUN

Description

Answer all the following questions.

(1)

and are independent and stationary memoryless information sources.
generates information symbols and with probabilities and , respectively, while generates and with probabilities and , respectively. Answer the following questions. , , and may be used.

(a) Find the value of the entropy of .

(b) Consider the th extension of . Find a binary Huffman code for the second extension () of and the expected codeword length per symbol.

(c) Compare the entropy in Question (a) and the expected codeword length per symbol in Question (b). Explain which should be larger and the reason.

(d) Explain whether the expected codeword length per symbol in Question (b) increases or decreases as in Question (b) increases and the reason.

(e) An information source has two states and generates information symbols by following and when its state is and , respectively.
transits from a state to the other state when it generates . Draw the state diagram of .

(f) Find the stationary distribution of in Question (e).

(g) Find the value of the entropy of in Question (e). Round down to one decimal place.

(2)

Answer the following questions related to channel coding. Let be the binary cyclic code of length that has generator polynomial

(a) Determine whether is a codeword polynomial of or not.

(b) Find the codeword polynomial for the message polynomial in a systematic form.

(c) Find the minimum distance of .

(d) Find the maximum number of error bits corrected by .

(e) Consider communications with through a memoryless binary symmetric channel with crossover probability . Evaluate the probability of decoding failure assuming that any correctable errors are corrected.

(f) Explain the channel coding theorem.

Kai

(1)

(a)

(b)

The symbol probabilities are:

Construct Huffman Code:

Average Code Length ():

Average Code Length per Symbol ():

(c)

.

According to Shannon's source coding theorem, the entropy of a source provides the ultimate lower bound on the average length of any lossless code for that source.

The source doesn't meet with dyadic distribution (powers of ), so the Huffman coding will never reach the lower bound exactly.

(d)

The expected code length per symbol decreases as block length increases. According to Shannon's source coding theorem for the -th extension of a discrete memoryless source (DMS), the average codeword length per source symbol satisfies:

As increases, the length per symbol will approach the entropy bound.

(e)

(f)

Let the stationary probabilities be .

(g)

Substitute into :

---

(2)

(a)

A polynomial is a codeword if it is divisible by the generator polynomial .

So this is a codeword polynomial.

(b)

The systematic form is given by . Given message . Degree of is .

1. Shift: .
2. Modulo: .
   • So remainder .
3. Codeword: .

(c)

For cyclic code:

• .
• , .
• Since is a primitive polynomial, the cyclic code is a Hamming code.
• Minimum distance .

(d)

The maximum number of correctable error bits is 1.

(e)

Probability of error occurring in a codeword (assuming correction of 1 bit):

(This represents the probability of having 2 or more errors).

(f)

• Achievability: For any data transmission rate (channel capacity), it is possible to design a coding scheme that allows for communication with an arbitrarily low probability of error.
• Converse: If , it is impossible to achieve arbitrarily low probability of error.