代写EEE8099 - INFORMATION THEORY & CODING 2024代写C/C++语言
- 首页 >> DatabaseEEE8099 - INFORMATION THEORY & CODING
RESIT
PROBLEM-SOLVING EXERCISES
AUGUST 2024
Specific instructions:
(a) This assignment is open book, which means that you are allowed to use your lecture notes to answer questions.
(b) Be concise in your answers. What is important when answering a question is to demonstrate your understanding of a particular topic by focusing your explanations on its key aspects only.
Therefore, as a rough guideline, the length of each answer should not exceed half of an A4 page, including any drawing, diagram, and equation.
(c) Please make sure that your submitted PDF file is very clear and easy to read.
(d) You can use drawing(s) and/or equation(s) in your answers, if you wish to do so. However, remember that the length of your answer for any specific question should ideally not exceed half of an A4 page, including any drawing, diagram, and equation.
Question 1
All linear block codes can be defined using a parity-check matrix. In other words, the operation of any linear block code can be described using a Tanner graph that connects a set of bit nodes to another set of check nodes.
In this question, assume transmission over a binary symmetric channel (BSC) with an error probability p.
Also assume that the bit-flipping algorithm is used to decode a particular linear block code over this BSC.
We have seen in class that the bit-flipping algorithm is going to work well provided that each check node in the Tanner graph of this linear block code is fed with, at most, one wrong bit.
(a) Consider a particular check node connected to l bit nodes c0 , c1 , c2 , … , and cl−1 .
Find the expression of the probability that this check node receives two or more wrong bits.
Simplify the equation thus obtained by assuming that p ≪ 1. [10 marks]
(b) By using the result obtained in (a), determine a condition that must be satisfied for successful decoding of a linear block code using the bit-flipping algorithm. [10 marks]
Question 2
Consider the convolutional encoder depicted in Figure 1. At each time n . T, where T and n denote the encoder period and an integer, respectively, the encoder is fed with an information bit dn and generates two coded bits xn and yn .
(a) Draw the trellis diagram for this encoder.
Use this trellis diagram to determine the free distance, dfree , for this encoder.
Show the path(s) in the trellis that correspond(s) to this free distance. [10 marks]
(b) Find the expression of the bit error probability obtained at high SNR using this convolutional code over a BPSK, AWGN channel.
What is the value of the asymptotic coding gain over uncoded BPSK? [5 marks]
(c) We now use the convolutional encoder depicted in Figure 1 to design a turbo encoder, as shown in Figure 2.
The turbo encoder input is a k-bit message M. This message is encoded into three k-bit binary words. The first one is the message M itself.
The second binary word is the sequence P1 of parity bits produced by the first convolutional encoder. Finally, the third binary word is the sequence P2 of parity bits produced by the second convolutional encoder which is fed by an interleaved version of M.
Find the expression of the first term of the union bound for this turbo code.
To save time and space on your answer sheet, you are allowed to use some results given in the lecture notes, without having to demonstrate them again. [10 marks]
(d) The turbo encoder studied in (c) is designed using convolutional encoders that are non-recursive.
Based on the analysis performed in (c), would you recommend using non-recursive convolutional codes for the design of turbo codes?
Justify your answer. [10 marks]
Question 3
Consider the linear block code defined by the generator matrix
(a) Determine the minimum distance, dmin , between codewords for this code. [10 marks]
(b) Find the expression of the bit error probability obtained at high SNR with this code. Assume transmission over a BPSK, AWGN channel and the use of maximum-likelihood (ML) decoding.
What is the value of the asymptotic coding gain over uncoded BPSK? [5 marks]
(c) Find the parity-check matrix H for this code. [5 marks]
(d) Draw the Tanner graph for this code. [5 marks]
(e) Assume transmission over a binary symmetric channel (BSC),
and that the received word is R = (111110). Use the bit-flipping algorithm to decode R.
Comment on your result. [5 marks]
(f) Perform a slight modification of the Tanner graph determined in
(d) in order to improve the error-correction capability of the code when bit-flipping decoding is used.
As an illustration, use the modified Tanner graph to decode the received word R = (111110).
Comment on your result. [5 marks]
Question 4
We propose to design a channel code, called C1,2 , by combining two linear block codes C1 and C2 .
The parameters of C1 are k1 , n1 , and dmin, 1 , whereas the parameters of C2 are k2 , n2 , and dmin,2 , where k1 and k2 denote the message lengths, n1 and n2 designate the codeword lengths, and dmin, 1 and dmin,2 are the minimum Hamming distances between codewords.
The encoding algorithm is explained below.
Each message composed of k1 ×k2 information bits is stored in a two- dimensional (2-D) array of size k1 ×k2 bits. This array thus has k1 columns and k2 rows.
At the first step of encoding, each row of this array is encoded into a codeword of length n1 bits using C1 . The row encoding results in a 2- D array composed of n1 columns and k2 rows.
At the second and final step of encoding, each of the n1 columns is encoded into a codeword of length n2 using C2 . The column encoding results in a 2-D array composed of n1 columns and n2 rows. This array is the codeword associated with the k1 ×k2 -bit array present at the encoder output.
(a) The minimum Hamming distance, dmin , between codewords for
C1,2 is the product of dmin, 1 and dmin,2 . In other words, we can write dmin = dmin, 1 ∙ dmin,2 .
How would you demonstrate this result? [5 marks]
(b) How would you decode the code C1,2 in practice?
To illustrate your explanations, feel free to draw the decoder structure that you propose. [5 marks]