Problem 3: Where in Computer Science, IOE or your major are error-correcting codes used? Error-Correcting Codes. We now discuss basic concepts of error correcting codes, and then make the connection to finite fields and linear algebra. Alice and Bob anticipate that they are going to want to communicate through an unreliable method where some part of the message may be garbled. Precisely, Alice expects that she will want to send one of N possible messages, which she will do using n characters from an alphabet of size p. She is concerned that as many as d1 of the characters may be received wrong. She will therefore try to choose N of the possible p^n strings, in such a way that no string can be turned into any other by changing fewer than d characters. That is, any d 1 errors should be detectable. For example, take N = 8, p = 2, n = 7. Alice could choose the following N codewords to represent the messages she might send: 0000000 Hello. 1001101 Goodbye. 0101011 The water is fine. 1100110 I have met an unusual animal. 0010111 Bring an umbrella. 1011010 I just saw a rainbow. 0111100 Im ready to return. 1110001 Send help immediately! A code is called linear when the list of code words is a linear subspace of F^np . Let VHamming be the list of codewords above. Problem 4 Give a basis of VHamming, and give a matrix GHamming whose image is VHamming. The matrix G is called the generator matrix. Let V be a linear code and let d be the smallest number of nonzero bits of any nonzero vector v in V . For VHamming, we have d = 4. The number d is called the distance of the code.

Error-Correcting Codes. We now discuss basic concepts of error correcting codes, and then make the connection to finite fields and linear algebra. Alice and Bob anticipate that they are going to want to communicate through an unreliable method where some part of the message may be garbled. Precisely, Alice expects that she will want to send one of N possible messages, which she will do using n characters from an alphabet of size p. She is concerned that as many as d1 of the characters may be received wrong. She will therefore try to choose N of the possible pn strings, in such a way that no string can be turned into any other by changing fewer than d characters. That is, any d1 errors should be detectable. Problem 3 Where in Computer Science, IOE or your major are error-correcting codes used? For most of the rest of this project we will take p=2 and work over F2. This is particular natural for applications to computer science, because computers like to communicate using an alphabet with 2 symbols. 2 The Hamming code. For example, take N=8,p=2,n=7. Alice could choose the following N codewords to represent the messages she might send: A code is called linear when the list of code words is a linear subspace of Fpn. Let VHamming be the list of codewords above. Problem 4 Give a basis of VHamming, and give a matrix GHamming whose image is VHamming. The matrix G is called the generator matrix. Let V be a linear code and let d be the smallest number of nonzero bits of any nonzero vector v in V. For VHamming, we have d=4. The number d is called the distance of the code. Problem 5 Explain why, if u and v are different code words in V, then there are at least d bits where u and v differ