Linear Algbra

Error-Detecting and Correcting Codes In this project, we examine how we can construct a method for detecting and correcting errors made in the transmission of encoded messages. It will turn out that the concepts learned on vector spaces, null spaces, rank, and dimensions are needed for this construction. When a message is transmitted, it has a potential to get scrambled by noise. This is true for all digital messages (e.g. email, texts, sound, video) that are sent to and from computers and mobile devices. This is also true of store scanners (bar code). By a digital message, we mean a sequence of 0s and 1s which encode a given message. Digital errors are often in the form of a 0 being received as a 1 or vice versa. What we will seek to do is to add more data to a given binary message that will help detect if an error has been made in the transmission of the message; adding such data is called an error-detecting code. We will also try to add data to the original message so that we can detect if errors were made in the transmission, and to figure out what the original message was from the possible corrupt message that we received. This type of code is an error-correcting code. 2 Vector Space of 0s and 1s In order to discuss error-correcting codes, we will restrict our attention to digital sequences: messages of 0s and 1s. We define the set Z2 to be the set {0, 1}. Addition and multiplication on Z2 are define in the following tables: + 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 One may check that these operations have the familiar properties of addition and multiplication of real numbers. Also, notice that since 1 + 1 = 0 then 1 = 1 in this setting. That is, 1 is its own additive inverse, and thus subtraction is exactly the same as addition in Z2. We now express messages as column vectors of elements of Z2. The message 1001 and 1101 would be expressed as 1 0 0 1 and 1 1 0 1

We will assume that each message is n digits long; we will call the set of all possible messages of length n digits, Z n 2 . In other words, Z n 2 is the set of all vectors with n elements taken from Z2. We will focus on n = 4, i.e. Z 4 2 . Since there are two choices {0, 1} for each position in the vectors of length 4, there are 24 = 16 different vectors. The set Z 4 2 contains the following 16 different vectors: 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 We can add these vectors just as we do in R n ; we can also multiple these vectors by scalars taken from Z2. Example 1: 1 1 0 1 + 0 1 0 0 = 1 0 0 1 and 1 1 0 0 1 = 1 0 0 1 In fact, if we use Z2 as scalars, and use the operations of vector addition and scalar multiplication as given in Example 1, then Z n 2 is a vector space. We say Z 4 2 is a vector space over Z2 to emphasize that the scalars we use are taken from Z2. Example 2: Find a basis for the column space, a basis for the null space, and the rank of the matrix, A = 1 1 0 0 1 0 1 1 0 1 1 1 We first row reduce A using Z2 arithmetic (remember that 1 + 1 = 0): 1 1 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 A basis for the column space of A is the pivot columns in A: Col(A) = 1 1 0 , 1 0 1 Thus the rank of A is 2. To find a basis for the null space of A, solve Ax = 0 and after row reductions get: 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0

This yields the equations, x1 = 1x3 1x4 x2 = 1x3 1x4 x3 = 1x3 x4 = 1x4 where x3 and x4 are free variables. Since 1 = 1, we rewrite the equations as, x1 = 1x3 + 1x4 x2 = 1x3 + 1x4 x3 = 1x3 x4 = 1x4 A basis for the null space of A would be Nul(A) = 1 1 1 0 , 1 1 0 1 We can list all of members of null space of A Nul(A) = 0 0 0 0 , 0 0 1 0 , 1 1 0 1 , 1 1 1 0 and note that the number of vectors in Nul(A) is 4 = 22 which is 2 raised to the dimension of the Nul(A). This is true for any subspace of Z n 2 . Fact: If W is a subspace of Z n 2 . with dimW = k, then the number of vectors in W is equal to 2 k . 3 Hamming (7,4) code Let us assume that our messages are 4 digits long. We will now describe the Hamming (7,4) code for detecting and correcting errors. Let the 7 columns h1, h2, . . . , h7 of the matrix H represent all of the non-zero vectors in Z 3 2 , H = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 As above, we can find a basis for the null space of H: Nul(H) = 1 0 0 0 0 1 1 , 0 1 0 0 1 0 1 , 0 0 1 0 1 1 0 , 0 0 0 1 1 1 1

Since the dimension of Nul(H) is 4, by our earlier fact Nul(H) contains 16 vectors. Notice that Z 4 2 also contains 16 vectors, so we can encode each vector in Z 4 2 using a different vector in Nul(H). For that reason we will call the null space of H the Hamming (7,4) code. To encode the vectors in Z 4 2 , we use a matrix A whose columns are the basis elements for Nul(H); the matrix A will be our encoding matrix. A = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 Example 3: To encode the message 1101, we compute x = A 1 1 0 1 = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 = 1 1 0 1 0 0 1 Notice that since the first four rows of A are the identity matrix, multiplication by A merely adds three digits to the original message. The matrix H was chosen because its nullspace has some very interesting properties which allows us to detect and correct single errors in transmitted messages. We assume at this point that any transmitted message has at most one error in transmission. If the probability of an error in transmission is small, then this is a reasonable assumption. We consider the standard basis vectors e1, e2, . . . , e7 in Z 7 2 : e1 = 1 0 0 0 0 0 0 , e2 = 0 1 0 0 0 0 0 , e3 = 0 0 1 0 0 0 0 , . . . , e7 = 0 0 0 0 0 0 1 Notice that adding one of these vectors to an encoded message vector x is equivalent to making a single error in the transmission of x. Notice also that the vectors e1, e2, . . . , e7 are not in the nullspace of H, since Hei = hi 6= 0. In fact, we have the following Theorem. Theorem 1: If H is the matrix given above and if x is in Nul(H), then x+ei is not in Nul(H)

Example 4: If we received the message 0100101, we can check that H 0 1 0 0 1 0 1 = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 = 0 0 0 Since our message vector is in Nul(H) we know that no single transmission error has happened. If a single error had happened, then the theorem tells us that the resulting message vector would not be in Nul(H). Example 5a: If we received the message 0111001, we can check that H 0 1 1 1 0 0 1 = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 = 0 1 0 6= 0 0 0 Thus (assuming that at most one error in transmission has been made) we know that a single transmission error has happened. So the Hamming (7,4) code is an error-detecting code. The following theorem will show us that it is also an error-correcting code. Theorem 2: If H is the matrix given above, and if Hx = hi , then x + ei is in Nul(H). Suppose we receive a message x that has had a single error in transmission. By Theorem 1, we know that Hx 6= 0, so Hx = hi for some i. The result of Theorem 2 implies that the single error in transmission must have occurred to the i th digit; change this digit (by adding ei to x) will give us a vector in Nul(H), and thus properly encode vector. Changing any other digit in x will not give us a vector in Nul(H). Example 5b: The message 0111001 was in error in Example 5a. In fact, we found that H 0 1 1 1 0 0 1 = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 = 0 1 0 = h2 By Theorem 2, the single error in transmission must have occurred at the second digit. Thus, the true message which was sent was 0011001.

could you please help me with these excersices ?

4 Exercises Exercise 1:(4 points) Prove Theorems 1 and 2, i.e. show that theorems are true Exercise 2:(3 points) Encode the following messages a) 1001 b) 0011 c) 0101 Exercise 3:(8 points) Write a program (i.e. lines of code) in Octave/Matlab, that takes as input a word (7 bits), of 0's and 1's where one of the bits might be wrong, and recovers the original data (we assume only one error). Hint: modular arithmetic command in Octave/Matlab can be done with the command mod, i.e. mod(x,2) where x can be a number, vector, or even a product of a matrix with a vector (i.e. you can use mod(H*x, 2)). Test your code on the following messages. Each of the following messages has been received and each had been encoded using the Hamming (7,4) code. During transmission at most one element in the vector was changed. Use your code to determine whether an error was made in the transmission, and if so correct it a) 0101110 b) 1000011 c) 0010111 d) 0101010 e) 0111100 4 Exercises Exercise 1:(4 points) Prove Theorems 1 and 2, i.e. show that theorems are true Exercise 2:(3 points) Encode the following messages a) 1001 b) 0011 c) 0101 Exercise 3:(8 points) Write a program (i.e. lines of code) in Octave/Matlab, that takes as input a word (7 bits), of 0's and 1's where one of the bits might be wrong, and recovers the original data (we assume only one error). Hint: modular arithmetic command in Octave/Matlab can be done with the command mod, i.e. mod(x,2) where x can be a number, vector, or even a product of a matrix with a vector (i.e. you can use mod(H*x, 2)). Test your code on the following messages. Each of the following messages has been received and each had been encoded using the Hamming (7,4) code. During transmission at most one element in the vector was changed. Use your code to determine whether an error was made in the transmission, and if so correct it a) 0101110 b) 1000011 c) 0010111 d) 0101010 e) 0111100