Homework 6, EEL 6509


Due Monday, April 23, 2001

Spring 2001

1.
([1], Ch. 4, prob. 1, p.96)
Consider the binary code C composed of the following four code words.


\begin{displaymath}\mathbf{C}= \left\{ (00100), (10010), (01001), (11111)\right\}
\end{displaymath}

(a)
What is the minimum distance of this code?
(b)
What is the maximum weight for which the detection of all error patterns is guaranteed?
(c)
What is the maximum weight for which correction of all error patterns is guaranteed?
(d)
Is this code linear? Prove your answer.
2.
([2], Chap. 5, prob. 5.4, p. 309)
Calculate the improvement in probability of message error relative to an uncoded transmission for a (24, 12) double-error-correcting linear block code. Assume that coherent BPSK modulation is used and that the received Eb/N0 is 10 dB. Also find the performance improvement in dB (i.e., how much would Eb/N0 have to increase for the uncoded system to achieve the same error probability as the coded system).

3.
Consider the rate 1/2, constraint length 3 convolutional code with generator sequences 7 and 5 (in octal notation).

PART I

(a)
Draw a block diagram of the encoder.

(b)
Draw the state diagram.

(c)
The minimum free distance, dfree, is defined as the minimum number of ones in the encoded bits on any path that starts and ends in the all-zeros state. Find the minimum distance by tracing paths throughh the state diagram. Sketch the path as a set of state transitions. What is the free distance?
(d)
Suppose the all-zeros sequence is sent. What is the minimum number of bit errors that must occur in the received sequence for the path you found with distance dfree to be selected over the all-zeros path?

(e)
If the path you found with distance dfree is selected over the all-zeros path, what is the number of bit errors that occur in the information sequence?

PART II

Generate two information sequences from

\begin{displaymath}I_1=10 \mbox{ (ten)}
\end{displaymath}


\begin{displaymath}I_2= \mbox{last digit of your student ID number}
\end{displaymath}

Convert I1, I2 into 4-digit binary representations. For example, I1=1010.

Convert I1, and I2 into 6-digit binary sequences by inserting a 1 before and after the original 4-digit sequence. For example, I1=110101. These sequences will each be input to the rate 1/2, constraint length 3 code. Append the minimum number of 0's to I1 and I2 that ensure the encoder will end in the all-zeros state.

For each of the information sequences you created:

(a)
Determine the 16-bit encoded sequences, E1 and E2. For example, the first few bits of E1 are 11,01.

(b)
Suppose errors occur in the 3rd, 4th, and 7th bits of sequence 1 and in the 3rd and 5th bits of sequence 2. Write the received sequences, R1 and R2.

PART III Use the Viterbi algorithm to decode each of the received sequences. You may find it helpful to use the Java-based Viterbi decoder at
http://lcmwww.epfl.ch/APPLETS/VITERBI/Viterbi.html For each of the received sequences you found above, write the bits that appear at the output of the decoder after it has reached the following decoding depths. For example, if you use the Java-based Viterbi decoder, at a decoding depth of 4, there will be 4 bits in the decoded: line. Also, list the number of bit errors that would occur in the bits that have been decoded if decoding were stopped at that point.

(a)
Decoding depth 4
(b)
Decoding depth 6
(c)
Decoding depth 8



 

John Shea
2001-05-08