IS2012 Homeworks 3
Due January 30

Homework 3

1. Write down all 16 valid codewords in the 4-3 Hamming Code. [Helpful hint: The compliment of a valid code word is also a valid codeword]
2. Determine whether the following 8-bit messages have 0, 1, or 2 errors. In the case of a single error, correct it. In the case of a double error, show (at least) 2 valid messages that are 2 bits away. 
    A.   0 1 1 1 1 1 1 0
    B.   1 1 1 0 0 0 1 0
    C.   1 0 0 1 0 1 1 0
3. In the 8-bit Hamming single-error correction, double error detection code, what is the probability that a random sequence of 8 bits is 
    A. a valid message?
    B. has a single (correctable) error?
    C. Has a double (detectable, but not correctable, error)?
4. Assuming n is odd, show that a Hamming Sphere of radius (n-1)/2, in a space of n dimensions has a volume 2**(n-1). [HINT: If you have trouble, consider the cases n=3 and n=5 in detail]
5. For each of the following sets of codeword lengths, compute the Kraft number for radix 2. If possible, design an instanteously decodeable code. (You can just show the decoding tree)
6. Repeat #2 for radix 3.