跳到主要内容

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

Author​

SUN, 祭音Myyura (assisted by ChatGPT 5.4 Thinking)

Description​

Answer all the following questions.

(1)​

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

  • (a) Describe the definition of compact code.
  • (b) Find the value of the entropy of .
  • (c) Find a binary Huffman code for the second extension of , and the expected codeword length per symbol.
  • (d) 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 1. Draw the state diagram of .
  • (e) Find the stationary distribution of in Question (d).
  • (f) Find the value of the entropy of in Question (d).

(2)​

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

  • (a) Find all codeword polynomials of .
  • (b) Find the codeword polynomial for the message polynomial .
  • (c) Draw a division circuit by .
  • (d) Explain how to detect errors by .

Kai​

(1)​

(a)​

A compact code is a uniquely decodable and instantaneous code with the minimum average codeword length.

(b)​

(c)​

                   [1.0]
                  /     \
               0 /       \ 1
                /         \
            P00=4/9       [5/9]
                         /     \
                      0 /       \ 1
                       /         \
                   P01=2/9       [3/9]
                                /     \
                             0 /       \ 1
                              /         \
                          P10=2/9     P11=1/9

            P00 = 0
            P01 = 10
            P10 = 110
            P11 = 111

Average length per extended symbol:

Expected codeword length per symbol:

(d)​

s_A --0 (2/3)--> s_A
s_A --1 (1/3)--> s_B

s_B --0 (4/5)--> s_B
s_B --1 (1/5)--> s_A

(e)​

(f)​

The entropy rate is the stationary weighted average of the entropies in each state:

We already have

Now

Using ,

so

Therefore,

(2)​

(a)​

Since and the code length is 7, the message polynomial has degree at most 2:

Each codeword is

Thus the 8 codeword polynomials are:

Equivalently, in 7-bit vector form (from to ):

(b)​

Over GF(2),

Its 7-bit vector form is

(c)​

The division circuit uses 4 delay elements because , and the feedback taps correspond to the nonzero coefficients of .

(d)​

Explain how to detect errors by :

Given a received polynomial (or 7-bit vector) , divide by over GF(2) and compute the remainder (syndrome)

If , then is a valid codeword (no error detected). If , then an error is detected.

目录