# Homework 1

Due: Thursday, September 18, 1997
• Problem 1.
Form a maximum-likelihood decoding table fot the binary code consisting of the four code words 0000, 0011, 1100, and 1111,
```

a) Assuming the binary symmetric channel,
b) Assuming the binary erasure channel.

```

• Problem 2.
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 3
Show that the minimum Hamming distance at least 2t+1 between code blocks is necessary and sufficient for correcting all combinations of t or fewer errors.

Hint. Use the triangle inequality.

• Problem 4.
Consider the kxn matrix
```

G = [ I, P ]

```
over a field F, where I denotes the kxk identity matrix, and where P is a kx(n-k) matrix over F. Let V be the vector space over F spanned by the rows of G, and let VPERP denote the vector space over F which is the orthogonal complement of V , i.e.,
```

VPERP = { v in Fn | v.u = 0 for all u in V },

```
where v.u denotes the inner product of vectors u and v . Prove that VPERP is the row span of the matrix
```

H = [ -PTranspose, I ],

```
where, in this case, I denotes the (n-k) x (n-k) identity matrix.

Hint: See Chapter 2, Section 6 of Peterson & Weldon.