**Coding Theory**

** Eighth Assignment, Convolutional Codes: due Wed.
May 16**

- Find the inverse of
*1 + x + x^3*
as a formal power series.
Explain how this question relates to convolutional codes.
- CT 8.3.2 (Don't make the state diagrams, just find an
infinite message and the corresponding finite codeword.)
- (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?

- CT 8.3.6

* *