Coding Theory

Eighth Assignment, Convolutional Codes: due Wed. May 16

1. Find the inverse of 1 + x + x^3 as a formal power series. Explain how this question relates to convolutional codes.
2. CT 8.3.2 (Don't make the state diagrams, just find an infinite message and the corresponding finite codeword.)
3. (See CT 8.2.11, 12, 13; 8.3.3, 6) Consider the convolutional code, C with generator polynomials:
   g_1(x) = 1 + x + x^2 and g_2(x) = 1 + x^2 + x^3
   • a. Draw the convolutional encoder for C , the state diagram and the table showing the output for each state and choice of X_3.
   • b. Encode
     (i) 1+ x^3
     (ii) 1+ x + x^3
     (iii) 1+ x + x^2 + x^3+ ....
   • c. The following are codewords. Decode them.
     (i) ... 00, 01, 10, 01, 01, 10, 11, 10, 11
     (ii) ... 00, 01, 11, 11, 00, 11, 01, 00, 10, 01, 11
   • Show that the minimum distance of C is d=6. Find codewords with weight 6 (There are 5, up to shift).
   • We can correct e errors provided e is less than half of d . What size windows should be used to correct e=1 errors and to correct e=2 errors?
   • For each case, e=1 and e=2 , in the basic decoding algorithm how many paths do you need to keep track of?
   • Decode ... 00, 00, 00, 11 with the 1-error correcting algorithm.
   • Can you find an error pattern that will be correctly decoded by the 1-error correcting algorithm but not by the 2-error correcting algorithm?
4. CT 8.3.6