# Homework 3

Due: Monday, October 11, 1999

• 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).