# Section 3.5: Error-Correcting Codes Math for Liberal Studies Section 3.5: Error-Correcting Codes Transmission Problems Problems can occur when data is transmitted from one place to another The two main problems are transmission errors: the message sent is not the same as the message received security: someone other than the intended recipient receives the message

Transmission Error Examples Party tonight, bring chipd Transmission Error Examples Party tonight, bring chipd We detect the error because chipd is not a word in our dictionary Transmission Error Examples Party tonight, bring chipd We detect the error because chipd is not a word in our dictionary

Can we correct the error? Transmission Error Examples Party tonight, bring chipd Even though chipd is not the correct word, we can assume that the correct word is close What words are one letter away from chipd? After considering the possibilities, chips is the most likely correction Transmission Error Examples Party tonight, bring sofa This time, all of the words are in the

dictionary, but we still suspect something is wrong (unless its a furniture party) Transmission Error Examples Party tonight, bring sofa This time, all of the words are in the dictionary, but we still suspect something is wrong (unless its a furniture party) Again we can change a single letter to change sofa to soda, which seems likely to be the original intended message

Transmission Error Examples Party tonight, bring sedr Identifying the error is easy: sedr is not a word However, this time, changing a single letter doesnt get us a word that makes sense Transmission Error Examples Party tonight, bring sedr We can change two letters, but that gives us two viable options: sedr sodr soda

sedr bedr beer It is impossible to tell which of these was the original intended message Error Correction Principles Errors can be detected when the message isnt in a dictionary of valid messages We can try to correct errors by finding valid messages that are close to the message we receive (but this doesnt always work) Digital Languages

Machines communicate with each other using a language entirely made of 0s and 1s The same kinds of errors we studied earlier (substitution, transposition) can occur when these digital signals are sent We can use special techniques to detect and correct these errors Sending Signals to Mars As an example, consider the Mars rovers, which landed in

2004 NASA sends signals to the rover to command it to perform various tasks, like movement These signals are sent in binary Sending Signals to Mars Suppose these messages are 4 digits long That makes 16 possible messages NASA could send: 0000

0100 1000 1100 0001 0101 1001 1101 0010 0110 1010 1110 0011

0111 1011 1111 Sending Signals to Mars Suppose NASA sends the message 0110, which might be telling the rover to move backwards to avoid a crater If, over the vast distances between planets, the message is garbled and received as 0010, this could be disastrous

Sending Signals to Mars If the garbled message is interpreted as move forward, this could mean the end of a very expensive mission To avoid this problem, we will add check digits to the message, just like we did for ID numbers Parity Checksums Many of the check digit schemes we studied involved adding up the digits of our ID number

Well do something similar here, but keep in mind that since every digit of a binary message must be 0 or 1, our check digit must be 0 or 1 also Parity Checksums A checksum is just a check digit that is based on a sum of digits in the message The parity of the sum is 0 if the sum is even, and 1 if the sum is odd Another way to think about parity is that it is

the remainder when the sum is divided by 2 Adding a Parity Checksum Digit Lets go back and add a parity checksum digit to each of these messages 0000 0100 1000 1100 0001 0101

1001 1101 0010 0110 1010 1110 0011 0111 1011 1111 Adding a Parity Checksum Digit For example: 1011

The sum of the digits is 3, which has parity 1 So the code word is 10111 0000 0100 1000 1100 0001 0101 1001 1101

0010 0110 1010 1110 0011 0111 1011 1111 Adding a Parity Checksum Digit Doing this for each of the messages gives us the code words shown below

00000 01001 10001 11000 00011 01010 10010 11011 00101 01100 10100 11101

00110 01111 10111 11110 Testing the New System Now when NASA wants to send the message 0110, they send the code word 01100. Now see what happens when there is a substitution error: 00100 We can detect the error because this is not a

valid code word Testing the New System Can we correct the error? Using the ideas from before, we want to look for the valid code word that is closest to the message we received What does closest mean? We have to define the idea of distance between code words Distance

The distance between two code words is simply the number of digits in which they differ For example, the distance between 01101 and 10111 is 3 Using Distance To correct the error in our message, we will compare it to every valid message and find the one that is closest (in the sense of having the smallest distance) This is called the minimum distance decoding

method Using Distance We compare the message we received (00100) to the valid code words: Code Word Distance Code Word

Distance Code Word Distance Code Word Distance 00000 01001 10001

11000 1 3 3 3 00011 01010 10010 11011 3 3 3

5 00101 01100 10100 11101 1 1 1 3 00110 01111 10111

11110 1 3 3 3 Using Distance Unfortunately, there are 5 code words that are tied for the closest Code Word Distance

Code Word Distance Code Word Distance Code Word Distance

00000 01001 10001 11000 1 3 3 3 00011 01010 10010 11011

3 3 3 5 00101 01100 10100 11101 1 1 1 3

00110 01111 10111 11110 1 3 3 3 We have no way of knowing which one is correct! What Went Wrong? Why didnt our checksum allow us to correct

this error? If we look closely at our list of code words, we see that some of them are at a distance of 2 from each other What Went Wrong? Distance 2 is significant because it means that if there is a single error, the new message is now 1 away from the original, but also 1 away from a new code word What Went Wrong?

If we can create a code system where the minimum distance between code words is 3, then we will be able to correct any single digit error More Checksums! Our solution is to add more checksums to our messages Lets call the four digits of our message M1, M2, M3, and M4 So for the message 0110,

M1 = 0, M2 = 1, M3 = 1, and M4 = 0 More Checksums! This time we will have three checksums, which well call C1, C2, and C3 C1 is the parity of M1 + M2 + M3 C2 is the parity of M1 + M3 + M4 C3 is the parity of M2 + M3 + M4 Lets try it on an example: 0111 More Checksums! Our message is 0111 C1 is the parity of M1 + M2 + M3 = 2, which is 0 C2 is the parity of M1 + M3 + M4 = 2, which is 0

C3 is the parity of M2 + M3 + M4 = 3, which is 1 So the code word is 0111001 A New List of Code Words Doing this for each of our 4-digit messages, we get a new list of 7-digit code words: 0000000 0100101 1000110 1100011 0001011 0101110 1001101

1101000 0010111 0110010 1010001 1110100 0011100 0111001 1011010 1111111 Minimum Distance This time, the minimum distance between

code words is 3, which means that we can detect any single error Minimum Distance If we start with a valid code word and there is a single error, we are 1 away from where we started, and at least 2 away from anywhere else Minimum Distance Also, we can detect any two errors using this code, since after 2 errors, we are still at least 1 away from any valid code word

Using Minimum Distance In general, if we know that the minimum distance between code words is D: the code can detect D 1 errors the code can correct (D 1)/2 errors, rounded down In our examples, when D = 2, we could detect 1 error, but could not correct any When D = 3, we can detect 2 errors, can correct 1