Tutorial 7 for CSC 310 This tutorial is about the [7,4] Hamming code, and the product of two [7,4] Hamming codes. The [7,4] Hamming code is described in the last slide of the 10A collection of slides from the web page. The set of parity check equations there can be put into the following parity check matrix (see 10B): 1 1 1 0 1 0 0 H = 0 1 1 1 0 1 0 1 0 1 1 0 0 1 Notice that this is in systematic form - the right end is an identity matrix. Are any other systematic forms of the parity check matrix for this code? Answer: No, you can't get another systematic form using row operations. Are there any other systematic forms for a code that is EQUIVALENT (ie, like this code except for bits being permuted)? Answer: Yes. Eg, swap the third and the fift column, giving the following: 1 1 1 0 1 0 0 H' = 0 1 0 1 1 1 0 1 0 0 1 1 0 1 then add the first row to both the second and the third rows, giving the following: 1 1 1 0 1 0 0 H'' = 1 0 1 1 0 1 0 0 1 1 1 0 0 1 Going back to the original parity check matrix, H, can we find a generator matrix for the code from this? Answer: Yes, we can get a systematic generator matrix by putting the transpose of the left end of the parity check matrix to the right of an identity matrix: 1 0 0 0 1 0 1 G = 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 How could we use this generator matrix to encode a four-bit vector? Answer: Just multiply the (row) vector on the right by this matrix. Notice how the result is a seven-bit vector in which the first four bits are the original message, and the last three bits are parity checks on subsets of the original message bits. Would this encoding process produce the same result if we had started with the parity check matrix, H''', for the equivalent code we found above? Answer: No. The final three bits would be parity checks on different subsets of the message bits (actually the first parity check would be the same, but the order of the other two would be swapped. Other equivalent codes might differ in the checks themselves, not just in their order.) Now let's look at the receiver. How can the receiver check whether what is received is a codeword? Answer: multiply the row vector, r, of received bits on the left by H, and see if the result, Hr, is all 0s. What should the receiver decode as the message if the received data is a codeword? Answer: the message can be obtained from the first four bits received. Is this decoded message guaranteed to be right? Answer: No. It's possible (though unlikely) that there were so many errors that the message was changed into a completely different valid codeword. Let's suppose now that exactly one bit was received in error. When the receiver computes Hr, what are the possible results? This looks complicated, since it seems like we need to consider all possible messages and all possible errors. But we can write r as t+n, where t is the codeword sent and n is the error vector, which is all 0s except for a single 1. Now, what is Hr? Answer: Since t is a codeword, Ht=0. It follows that Hr = H(t+n) = Ht+Hn = 0 + Hn = Hn. So we can find the possible values of Hr by just considering the seven possible values of n, computing Hn for each. What do we get for n=1000000, n=0100000, etc.? Answer: the seven results are the seven columns of H, which are all distinct. These seven possible results of Hr corresponding to the seven possible single errors allow us to correct any single error. How? We just identify which position for an error corresponds to the value of Hn. What will happen if there is more than one error? Answer: we will probably find that Hr is non-zero, and then "correct" what we think is a single error, but this will probably make things worse, since it's probably not an actual error position. If there's still time, you can show how one could encode the product of two [7,4] Hamming codes. Product codes are discussed in Question 2 of Assignment 3, and in the lecture notes for 2002 (see link at bottom of web page), section 11B (which also discusses Hamming codes). To encode a 16-bit message, we first arrange it in a 4-by-4 array. Next, we fill in the left side with the check bits on each row for a [7,4] Hamming code. Finally, we fill in at the bottom with the check bits on each of the seven columns for a [7,4] Hamming code. Look now at the lower-right 3-by-3 area. For a produc code, these should BOTH be the correct check bits for the rows to the left AND be the correct check bits for the columns above. Is this so? (Yes.) Why? After all, we computed them based on the rows, so why should they be right for the columns too. (See the slides for the answer.)