MAT 246: Linear Algebra Name: CAP 13 Error-correcting Codes 1. Error-correcting Codes A Hamming code is a linear error-correcting code developed in the 1950s. It is a way to detect errors due to "noise" and correct them. For example, on a music CD (do they still exist?) there might be a scratch. An error-correcting code can recognize there is an error in the Os and Is read and, if the scratch hasn't distorted too much data, will be able to correct the error. One way these error-correcting codes work is by using redundant information. The more times something is repeted, the easier it can be to detect and airor. The more times something is repeated, the easier it can be to detect an error. The more times something is repeted, the easier it can be to detect an error. If there are redundant vectors, that means that some can be written as linear combinations of others. Before we look at this example, note that we are only using clock arithmetic with 0 and 1 (let's denote this Z2). 0 +0 =0, 1 +0 = 1,0 +1 = 1, and 1+1 =0. 1 Let H = 0 .. 0 0 1 1 0 (a) Express the null space (kernel) of H as the span of four vectors in Z (vectors in R' with entries of 0 or 1) of the form ( You have to find the values of the *). And remember that the values can only be 0 or 1. (b) Form the 7 x 4 matrix M = 2 U3 UA .Explain why Col(M) =Null(H). If i is an arbitrary vector in Zy, what is H(ME)? [Hint: The columns of M form a basis for the null space of H. ME is a vector that is a linear combination of the columns of M. (why?). ]