Homework 3

Due: Monday, October 11, 1999

Reading Assignment
MacWilliams & Sloane, Chap. 2
Peterson & Weldon, Chap2. 1-3

Problem 1. A "metric" function is defined as a real-valued function having the following three properties:
a) d(x,y) = 0 iff x=y (Reflexivity) b) d(x,y) = d(y,x) (Symmetry) b) d(x,y) =< d(y,z) + d(x,z) (Triangle Inequality)
Show that the Hamming distance is a metric function.
Hint.
H(x,y) = Wt( x (+) y ), where H(x,y) denotes the Hamming distance between x and y, where Wt(v) denotes the Hamming weight of v (i.e., the number of 1's in v, and where (+) denotes componentwise addition mod 2.

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. 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 4. Let V be a binary linear code given by the generator matrix

                        [  101011  ]
                G =     [  011110  ]
                        [  000111  ]

a) Find a parity check matrix H of V .
b) Use the generator matrix to create a list of all code vectors of V. Then use this list to determine the minimum distance of V.

Problem 5. Prove that GF(7) is a field.
Hint. Assume that GF(7) is a ring. Then use the addition and multiplication tables for GF(7) to prove that GF(7) is a commutative ring with identity. For example, multiplication is commutative because the multiplication table is symmetric about the diagonal. Next prove that each non-zero element of GF(7) has a multiplicative inverse either by inspecting the multiplication table for GF(7) or by listing the multiplicative inverses for all non-zero elements of GF(7).

Last Modified: October 3, 1999