1. Let C be the code consisting of all binary words of length 8 so that the number of ones in the first four bits is even, and the number of ones in the last four bits is even. (a) How many code words are there in C? (b) Is C linear? Prove your answer. (c) What is the minimum distance of C?
2. Hamming arrived at his idea for one error correcting codes by considering rect- angular codes. This works as follows: Given words of length k, where k = ab. To form the code word, write the word in rectangular form, as a rows of length b. Then, add a parity bit to each row and each column, so that the sum (modulo 2) of each row and column equals 0. If one error occurs, exactly one row and column will be affected, and the parity bits will identify this row and column, and thus the location of the error. For example, if k = 9, we can write the message 010110101 as

0 1 0

1 1 0

1 0 1

The corresponding code word is

0 1 0 | 1

1 1 0 | 0

1 0 1 | 0

_ _ _ _ _

0 0 1 | 1

which can be written as the word 0101101011000011, where the first 9 bits are the original message, and the parity bits are the last 7 bits.

(a) Suppose we want to encode words of length 40 using a rectangular code. The number 40 can be written as product in different ways, for example 40 = 2 · 20 or 40 = 4 · 10. Which is the best choice? Justify your answer. (b) What is the best way of encoding words of length 39 with a rectangular code? Justify your answer.