Homework 1

Due: Monday, February 9, 1998

Reading Assignment
Peterson, Wesley, and E.J. Weldon, Jr., "Error-Correcting Codes," MIT Press (1981), pages 1-10 & 32-35. This book is on 3 hour reserve in Kuhn Library.

Problem 1.

Form a maximum-likelihood decoding table fot the binary code consisting of the four code words 0000, 0011, 1100, and 1111, assuming the binary symmetric channel.

Problem 2.

Over GF(3), put the following matrix into echelon canonical form

                        [  0 0 2 2 0 2  ]
                        [  2 2 0 2 1 2  ]
                        [  1 1 2 0 2 2  ]
                        [  1 1 0 1 2 1  ]

Problem 3.

Suppose that the set if all received messages x, y, ... is S, and that a metric function d(x,y) is defined on the set S. Suppose that transmitted messages are in the same set. If x is transmitted and y is received, an error of magnitude d(x,y) is said to have ocurred. A code C is a subset of S, the idea being that in using a code C, only messages x₁, x₂, ... in C are transmitted.

(a) Show that a code C is capable of detecting any error of magnitude d or less if and only if the distance between messages in the code C is greater than d.

(b) Show that a code is capable of correcting any error of magnitude t if the minimum distance between code messages is greater than 2t.

Last Modified: January 28, 1998