The midterm will cover everything up to and including Golay codes. To prepare, first make sure you understand the assignment solutions posted on the web. It might be a good idea to review the lecture notes again. Solving problems, however, is the only sure way to be on top of the material. Here are some further suggestions: * Bring a highlighter pen if you have one. This can be helpful for multiplying a matrix by a binary vector: whenever the binary vector has a one in the jth position, highlight column j of the matrix. The ith row of the result is just the number of ones in the highlighted entries of the ith row (mod 2). * If you finish early, check that your proposed corrected vector really has syndrome zero. Codewords always have syndrome zero! * In writing your solutions, you may freely use any of the theorems and results we proved in class; you do not need to rederive these results. You do not need to mention the theorem number, just state what the theorem says or mention it by name. (See the online list of theorems for suggested names). A number of you asked for solutions to some specific problems from old midterms. Here they are: 1999 MIDTERM Question 1: Assume that C is a linear [6,k,5] code; i.e. C is a k-dimensional subspace of F_2^6 with d(C)=5. (a) Show that |C|=2; i.e. k=1. Since the code is linear, we know that one of the codewords is 00000 (this step isn't really necessary but it helps make the argument below explicit). We must have at least two vectors; otherwise the minimum distance of the code isn't even defined. We now show that we cannot have more than two vectors. Suppose that we had three vectors. The second vector can only have one 0. The second vector must also differ in 5 places with the third, and since all but at most 1 of those 5 places is a 1, we see that the third vector has at least 4 zeros in it, meaning that it is distance 1 away from 00000. This is a contradiction. (b) Find all possible C. Remember that a linear code includes the zero vector. Here are 2 possibilities for C. Can you find the other 3 possibilities? 00000 01111 00000 10111 ... Question 5 (see http://www.math.ualberta.ca/~bowman/m422/oldexams/99mt.pdf): (a) 00000 10011 01111 11100 d=3 (so we can use this error to correct one error) (b) The message ab is encoded as the codeword a(10011)+b(01111). (c) 01100 11010 11001 (d) For the parity check matrix given in (c), the syndromes are error syndrome 00000 000 <-- corresponds to the coset containing all 4 codewords 10000 011 01000 111 00100 100 00010 010 00001 001 Each syndrome corresponds to a coset. There are 4 codewords, so each coset must have 4 vectors in it. So there are 2^5/4=8 cosets in the vector space, each corresponding to one of the 2^3=8 possible syndromes. The other two cosets have coset leader weight 2 and correspond to the missing syndromes 101 (which could arise from a weight 2 error vector 00101 or 01010) and 110 (which could arise from a weight 2 error vector 00110 or 01001). (e) The syndrome of this vector is 110, so we cannot determine the original message, even if we assume that only one error has occurred! (f) Pcorr=(1-p)^5 + 5p(1-p)^4 + 2p^2(1-p)^3=(1-p)^3(1+3p-2p^2)=0.9992139 Note that the coefficients here sum up to 1+5+2=8, the total number of cosets. The probability that both bits of an unencoded message are correctly received (without using any error-correcting code) is much lower: Mcorr=(1-p)^2=0.9801 A good exercise to complete this example would be to write down the entire standard array for this code. 1997 MIDTERM 5. Write down a parity check matrix for Ham(2,7): (See pages 27 and the examples on 29 and 30 of the lecture notes.) You want to write down all columns of n distinct non-zero vectors in F_7^2 with first nonzero entry equal to 1 in a 2 x n matrix, where n=(7^2-1)/(7-1)=48/6=8: [0 1 1 1 1 1 1 1] [1 0 1 2 3 4 5 6] 1997 FINAL EXAM Question 2: H= 0 1 1 1 1 1 1 0 1 2 3 4 C' is linear: x' in C, y' in C => x'+y' in C' since the first part is a codeword of C and the sum of the first six digits of x'+y' is just the sum of the checksum for x' and the checksum for y'. Here is a parity-check matrix for C': H'= 0 1 1 1 1 1 0 1 0 1 2 3 4 0 1 1 1 1 1 1 4 The last equation says that c_1+c_2+c_3+c_4+c_5+c_6=c_7 That is, c_1+c_2+c_3+c_4+c_5+c_6+4c_7=0 The Hamming code C has minimum distance 3. The minimum distance of C' is thus either 3 or 4. But w=0010220 is a codeword of C since Hw=0, so the minimum distance must be 3. Use H' to decode 0111310 by finding the syndrome 212. This is just twice 131, the fifth column of H. So the decoded vector is 0111310-[0000200]=0111110. Note: to do syndrome decoding there is no need to row reduce H. The only time you need to row reduce H is to find the generator G. You may also wish to look at some of the problems from Hill (solutions are in the back). Here are a few problems that I can suggest: 2.4, 2.6, 2.7, 2.9 5.1, 5.4, 5.6, 5.10, 5.11 6.1, 6.2, 6.4, 6.6 7.5, 7.6, 7.11 8.1, 8.4, 8.6, 8.7, 8.8 9.1, 9.3, 9.8