Homework 1
Due: Monday, February 9, 1998

Reading Assignment
Peterson, Wesley, and E.J. Weldon,
Jr., "ErrorCorrecting Codes," MIT Press (1981), pages 110 & 3235.
This book is on 3 hour reserve in Kuhn Library.

Problem 1.
Form a maximumlikelihood 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_{1},
x_{2},
... 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