京都大学 情報学研究科 通信情報システム専攻 2020年8月実施 専門基礎A [A-5] Author SUN
Description Answer all the following questions.
(1)
A stationary memoryless information source
(a) Find a binary Huffman code of
(b) Describe the definition of instantaneous codes.
(c) Find the expected codeword length per symbol of the code in Question (a).
(d) Find the entropy of
(2)
Answer the following questions related to channel coding. Let
(a) Determine whether
is a codeword polynomial of
(b) Find the codeword polynomial of
in a systematic form.
(c) Find the minimum distance of
(d) Find how many bit errors
(e) Explain the advantage(s) and disadvantage(s) of
(f) Explain how to correct errors with
Kai (1)
(a)
Huffman Tree Structure:
(b)
Instantaneous codes satisfy the Prefix condition , which ensures that no codeword is a prefix of another. This property allows the decoder to identify and decode each symbol uniquely and immediately upon its reception, without the need for a look-ahead or causing ambiguity.
(c)
L = 2.2 \text{ bits / symbol}
You can't use 'macro parameter character #' in math mode #### (d) Entropy Calculation H(S) = \sum_i P_i \log_2 \frac{1}{P_i} = \frac{2}{5} \log_2 \frac{5}{2} + \frac{1}{5} \log_2 5 + \frac{8}{25} \log_2 \frac{25}{4} + \frac{2}{25} \log_2 \frac{25}{2}
H(S) \approx 2.1 \text{ bits / symbol}
You can't use 'macro parameter character #' in math mode ### (2) #### (a) Check if the given polynomial is a codeword using polynomial division: ```text x^6 + x^5 + x^2 _____________________________________________ x^4 + x + 1 | x^10 + x^9 + x^7 + x^6 + x^5 + x^3 + x^2 + 1 x^10 + x^7 + x^6 ----------------------- x^9 + x^5 x^9 + x^6 + x^5 ----------------------- x^6 + x^3 + x^2 + 1 x^6 + x^3 + x^2 ----------------------- 1 (Remainder) ``` **Conclusion:** Since the remainder is $1 \neq 0$, this is **not** a codeword polynomial. #### (b) Given $m(x) = x^3 + x^2 + 1$: C(x) = x^4 m(x) + r(x) = x^7 + x^6 + x^4 + x^2
\Rightarrow r(x) = x^2
You can't use 'macro parameter character #' in math mode #### (c) $G_1(x)$ is a **primitive polynomial**, so $C_1$ is a Hamming code. For a Hamming code, the minimum distance is $d_{min} = 3$. #### (d) 2t + 1 \le d_{min} \Rightarrow 2t + 1 \le 3 \Rightarrow t = 1
You can't use 'macro parameter character #' in math mode $C_1$ can correct up to **1 bit** error. #### (e) $C_2$ has more parity bits compared to $C_1$. Therefore, $C_2$ can detect and correct more errors, but its **coding efficiency** (rate) is lower than $C_1$. #### (f) 1. Use $G_2(x)$ to derive the corresponding parity-check matrix $H$. 2. Calculate the syndrome $S = H R^T = H(m^T + e^T) = H e^T$. 3. Use a pre-calculated error mapping table or a decoding algorithm (like Meggitt decoding) to find the error pattern $e$ corresponding to the syndrome $S$. 4. Correct the error: $C = R + e$. 