MAT 1000 Mathematics in Today's World Winter 2015 Last Time Identification numbers often include check digits: extra digits that allow us to catch errors. There are several different methods for finding check digits used in practice. We looked at sytems which are used for UPC codes, credit card numbers, and ISBNs as well as bar codes. Today Binary codes are strings consisting of either 0s or 1s. We will look at a specific way to encode binary messages using Venn diagrams Then we consider a more general method, called “parity check sums” Binary codes Binary codes are messages which are represented using only the digits 0 and 1. Some examples of binary codes of length three are 101, or 110, or 000 Computers use binary codes internally. Binary codes We can append extra digits to binary codes to help catch errors. In fact, we can either identify where the error occurs, or we can fix the error. This requires appending more than a single digit. Binary codes One advantage to binary codes: each position is either a 1 or a 0, so there are only two possible errors: 0 can be received as 1 1 can be received as 0 Venn diagram encoding If our binary codes have length 4, there is an encoding/decoding system which uses Venn diagrams. Use three circles in the following configuration: Venn diagram encoding Note that we have four sections of overlap: Our four digit binary message will be placed in these 4 spaces, in this order. Then we append three digits, based on the other 3 spaces. Venn diagram encoding Example Let’s encode the message 1011 First, fill in the numbered spaces in the Venn diagram using the digits of the message, in order: 1st digit in the 1st space, 2nd digit in the second space, and so on. Venn diagram encoding Example We have three more spaces to fill: We will put either a 1 or a 0 in each of these. Venn diagram encoding Example To decide whether to put in a 0 or a 1, we choose whichever makes the total number of 1s in each circle even: 1 0 0 Adding these three extra digits (in order) gives 1011 010 Venn diagram encoding Example Now we will see how to correct errors using this method. Suppose our message 1011 010 is mistakenly received as 1010 010 When we fill in the Venn diagram, we can see there is a mistake because some of the circles have an odd number of 1s in them. Venn diagram encoding Example The upper left circle has an even number of 1s: Venn diagram encoding Example But the other two circles both have an odd number of 1s: Venn diagram encoding Example But the other two circles both have an odd number of 1s: Venn diagram encoding Example Which digit is incorrect? The incorrect digit must appear in both of the circles with an odd number of 1s, but it is not in the circle with the correct number of 1s. This tells us exactly where the error must be: Venn diagram encoding Example Moreover, once we know the location of the error, we can fix it. After all, this is a binary code: if 0 is not the correct digit, then 1 must be. Fixing the mistake recovers our original message: 1011 010 Venn diagram encoding Some disadvantages of this method: • Only works on messages of length four • If there are two or more errors, they may go undetected, or they may be fixed incorrectly Let’s see an example that shows how two errors can be fixed incorrectly. Venn diagram encoding Example The original message is 0110. Encode this message. 1 0 0 So the encoded message is: 0110 010 Venn diagram encoding Example Suppose the message is received with two errors as 0100 011 What happens when we decode this message? Venn diagram encoding Example The two upper circles have an odd number of 1s in them, but the lower circle has an even number of 1s. So the method tells us there is an error in this place: Venn diagram encoding Example This gives the “corrected” message 1100 011 Of course this is not actually the correct message. That was 0110 010 So this method may fail when there are two or more errors in the message. Parity Check Sums Here are some possible improvements on the Venn diagram method: 1. Longer messages 2. Correct more errors To describe these improved methods, we need to look at the Venn diagram method in a different way, using “parity check sums” Parity Check Sums The parity of a number is whether it is even or odd. Suppose we have a four-digit binary message 1 2 3 4 We decide to append three digits, 1 , 2 , 3 We choose 1 to have the same parity as the sum 1 + 2 + 3 This means that If 1 + 2 + 3 is even, 1 = 0 If 1 + 2 + 3 is odd, 1 = 1 Parity Check Sums We choose 2 to have the same parity as the sum 1 + 3 + 4 And 3 will have the same parity as the sum 2 + 3 + 4 Parity Check Sums Example Use these parity check sums to encode the message 1011. The first check sum is 1 +2 + 3 which is 1 + 0 + 1 = 2. So the first appended digit is 0 The next check sum is 1 +3 + 4 which is 1 + 1 + 1 = 3. So the second appended digit is 1 The last check sum is 2 + 3 + 4 which is 0 + 1 + 1 = 2. So the third appended digit is 0 This makes the message: 1011 010 Parity Check Sums If you compare this method with the Venn diagram method we used earlier, you will see that they are identical (for any four digit message they give the same code) The advantage of parity check sums over Venn diagrams is that we have more flexibility: • we can now work with longer messages • we can add more digits (which can catch more errors) Parity Check Sums Example In addition to the digits 1 , 2 , 3 defined above, we could add another digit 4 using the sum 1 + 2 + 4 (which was not used in the Venn diagram method) Parity Check Sums Example For a message of length five 1 2 3 4 5 we could use check digits 1 , 2 , 3 , 4 which have the same parity as 1 + 2 + 3 + 4 2 + 3 + 5 1 + 2 + 4 1 + 3 There are lots of other possibilities. Parity Check Sums If we encode a message with parity check sums, how should we decode it? The method used is called “nearest neighbor” decoding. To use this, we have to discuss the “distance” between binary strings. Parity Check Sums The distance between two binary strings is the number of places in which they differ. Example: 101010 and 111010 have a distance of 1 Example: 101010 and 011011 have a distance of 3 Example: 101010 and 101010 have a distance of 0 Note if two strings have different lengths, it doesn’t make sense to talk about their distance. The distance between 101010 and 11101 doesn’t make sense Parity Check Sums Nearest neighbor decoding: Receive an encoded message, which may have some errors. Find the nearest correct message (meaning the one which is the smallest distance from the received message). Do not decode if there is a tie. Parity Check Sums In order to use nearest neighbor decoding, we need to make a list of every possible correct message. In the next example, we will take a parity check sum method, list every possible correct message, and then use that list to decode a message. Parity Check Sums Example Messages will be of length three 1 2 3 . We will add three parity sum digits using the sums 1 + 2 + 3 and 1 + 3 and 2 + 3 Messages 1 + 2 + 3 1 + 3 2 + 3 Coded Messages 000 0 0 0 000 000 001 1 1 1 001 111 010 1 0 1 010 101 100 1 1 0 100 110 110 2 1 1 110 011 101 2 2 1 101 001 011 2 1 2 011 010 111 3 2 2 111 100 Parity Check Sums Example Decode the message 000101. We will find the distance from this message to each valid message: Coded Messages Distance 000 000 2 001 111 2 010 101 1 100 110 3 110 011 4 101 001 3 011 010 5 111 100 4 The message is decoded to be 010 101 Parity Check Sums We have lots of choice for different parity check sums. How many should we use? Which ones should we use? We will see next time how to analyze different choices of parity check sums.