when I was first taught linear algebra I learned it was mostly about the sort of stuff you see here lines planes matrices and linear equations in this video I'd like to show you how linear algebra has really important applications for stuff like this compact discs QR codes computer memory and deep space communication what ties all of these things together is the need for error correction CDs get scratched camera images can be blurry and electromagnetic interference can corrupt information and electronics or corrupt signals being sent from space probes back to earth in the year 1977 NASA sent out the Voyager 1 and Voyager 2 space probes to study the solar system here you're looking at a time-lapse of images Voyager 1 took of the planet Jupiter in 1979 and here is another time-lapse of the planet Saturn in 1980 the Voyager probes had to transmit binary image data hundreds of millions of kilometres across space back to earth however if background electromagnetic radiation is strong enough it can sometimes turn a 0 into a 1 or turn a 1 into a 0 if left uncorrected this results in lower image quality meaning that images like these might not have been possible to capture this is where error correcting codes for ECC's come in error correcting codes are a way of applying linear algebra and abstract algebra to fix data transmission errors as in the case of the Voyager probes sending images from space back to earth in this video I'm going to discuss repetition codes which is the method you would probably use for error correction if you've never studied ECC's before I'll also talk about hamming codes which are a simple trick that can add a significant improvement to the efficiency in the error correction process the actual error correcting codes used by the Voyager probes are called polynomial codes unfortunately these are too complicated to explain in a single video but we'll work our way up to an understanding of them over the next three to four videos in any case a lot of the basic ideas behind error correction will still be covered in this video with Hamming codes and at the end of this video you should hopefully have a good understanding of how linear algebra is used in technology all around us everyday to fix errors the first type of error correcting code we're going to discuss is repetition codes this basically just means retransmitting the message multiple times for example if we transmit an image of the planet Neptune three times each copy of the image might get corrupted in different ways but for each individual pixel we can hope that two of the three copies of the pixel will be correct if you're familiar with standard digital images you'll know that every pixel in a grayscale image is represented by a number between zero which is pure black and 255 which is pure white I'm not sure if this is exactly the image format used by the Voyager probes but for the purposes of this video it's good enough and of course each of these numerical pixel values can be represented in binary as a long stream of ones and zeros so let's take a look at how repeating the image message multiple times can help us fix errors so we have our three copies of the image here and each one has been corrupted in different ways now if we zoom in on a small region of the image we find that the pixel values look like this so you'll notice that the first two copies agree with each other but in the third copy there has been an error and that's because in the binary stream of zeros and ones one of the zeros got flipped to a1 due to electromagnetic interference so let's pretend that we get all this data on earth how do we fix the mistake well we can just line up the 3 streams of zeros and ones and check if the three copies agree with each other so we see that these ones all agree here and so do these ones and the zeros agree but here we have a disagreement between the three copies we have two zeros and a one so we're just going to do a majority vote and take the best two out of three and assume that the should actually be a zero and that the third copy here contains an error and just writing out the other answers we find that we get a results where the error has been corrected so we've repaired this corrupted pixel so basically our procedure for correcting errors is to take the original message and create the repetition code where each binary digit gets repeated three times now as the message travels from the deep space probe back to earth some of the binary digits might get flipped but we can look at each block of three bits and any time there's a disagreement we just take the best two out of three so through this best two out of three voting procedure we're able to decode the message and recover the original transmission now it's important to remember that this procedure isn't perfect let's go through this process again but with a different set of corrupted bits so you'll notice that this time we don't actually recover the original message there are still errors in the message we decoded and that's because in some of these three bit blocks there was more than one error so it's important to remember that the error correction process has limits if too many errors happen we simply can't recover the correct data so with this best two-out-of-three repetition code that we're using if more than one error occurs in a three bit block we get the wrong answer so this means that we can only fix one error for every three bits moreover we need to repeat the message three times with this method so that's only a 33% efficiency because only 33% of the bits were sending are actually meaningful data so there's a couple problems with this method being able to fix one error out of every three bits transmitted is pretty good this means we can correct a lot of errors but there might be some situations where we don't need to be this good at correcting errors for example maybe we only expect one error out of every 100 transmitted bits if that's the case this best two-out-of-three method is kind of overkill another issue is the 33% efficiency for every one bit of real data we have to add to redundancy bits and transmit three bits in total so what if we want better efficiency can we get 50% efficiency or maybe 70% or maybe even 90% well to deal with both of these issues I'm going to introduce a new type of error correcting code called hemming codes specifically I'm going to talk about the hemming 7/4 code so the best two of three repetition code takes a 1-bit message and turns it into a three bit codeword by repeating it three times so the zero bit message gets turned into the codeword 0 0 0 and the 1 bit message gets turned into the codeword 1 1 1 now the Hamming 7-4 code takes a message of 4 bits and turns it into a 7 bit code word so the message 1 0 0 1 gets turned into the codeword 1 0 0 1 0 0 1 and the message zero zero one zero gets turned into the codeword zero zero one zero zero one one so to communicate a four bit message we need to transmit seven bits so that means that the Hamming 7-4 code has an efficiency of 4 over 7 which is 57.1% and this is a pretty big improvement over the 33% efficiency of the best two-out-of-three code that we used earlier so let's take a look at how this hamming 7/4 code works let's say that we have this binary message that we want to transmit using the Hamming 74 code the first step is to divide the message up into four bit chunks now for each 4-bit chunk we're going to add three extra redundancy bits and I'm calling these extra bits x y&z so how do we calculate x y&z well I'm going to call these first four bits ABC and D and the X Y Zed bits are given by these three equations here this circle plus symbol is called the exclusive or operator or the zuhr operator these or operator is very similar to ordinary addition but with a slight difference in these first three cases these or operator behaves exactly like ordinary addition but for one Zoar one this actually gives us 0 instead of 2 so you can basically think of these or operator as a special type of addition where if the answer is even we get 0 and if the answer is odd we get 1 so let's compute the XYZ redundancy bits for this 4-bit chunk 1 1 0 1 so x equals A's or B's or D so that's 1 plus 1 plus 1 which is equal to 3 which is odd and since we get an odd answer we get x equals 1 and y equals a zorse YZ or d and that's 1 plus 0 plus 1 which is 2 and that's even so the answer is even that means that y equals 0 and Z equals B's or C's or D which is 1 plus 0 plus and that's to which is even so Z equals zero so for this 4-bit chunk the redundancy bits are 1 0 0 and we can use this same technique to add the redundancy bits to all the 4-bit chunks in our message for the X bit we exhort abd for the Y bit wheeze or ACD and for these EDD bit wheeze or BCD and we can do this on and on for all the four bit chunks and get a bunch of 7 bit code words ready for transmission now let's see if we can correct some errors so let's say some 7 bit codeword gets transmitted from space and arrives on earth and on earth we receive the bits 0 1 0 0 1 0 1 so let's check these three redundancy bits here and see if they agree with these equations so X is these or of abd which is 1 so the X bit makes sense why is these or of a CD which is 0 so the why that makes sense and Zed is these or of BCD which is 1 so these ed that makes sense so the redundancy bits are consistent with the data bits and well that doesn't prove that no errors happened it does indicate that the bits are probably correct provided too many errors didn't happen now let's look at another example where the received bits are 1 0 0 1 0 1 0 so again we'll check the redundancy bits against these three equations so looking at X we get 0 looking at Y we get 0 and looking at Zed we get 1 so these redundancy bits are not what we expect so that means that we have errors so how can we correct this message well since the y&z bits are incorrect let's take a look at the y&z equations here now we notice that these equations contain both the SI bit and the D bit so that's an indication that either the SI bit or the D bit are probably wrong but notice that the X equation also has the D bit and the X bit was fine so that indicates that the D bit probably right so by the process of elimination we can conclude that the C bit was probably flipped so if we change this C bit from a zero to a one and check the XYZ bits again we find that they all check out correctly so using these three extra redundancy bits we were able to correct a one bit error in this seven bit chunk so let's just review the whole process of using the Hamming 7-4 code we break our message up into four bit chunks we add three redundancy bits to each chunk according to these equations then we transmit the message where noise can possibly flip some bits and give us errors then we check the three redundancy bits against these equations to detect and fix errors so here only the X pit is wrong which indicates the error was probably the X bit here the x y&z bits are all wrong and since the D bit is in all of these three equations for x y&z that indicates that the D bit is probably the one that was wrong so we can flip the D bit to fix the mistake and in this case the x y&z bits are wrong again this would normally make us think that the D bit is wrong however flipping the D bit doesn't actually give us the original message and that's because there were two errors in this seven bit chunk which is too many errors the hemming 7/4 code can only correct one error in every seven bit chunk so now we've covered the best two-out-of-three repetition code and the hemming 7/4 code the two out of three code has a data transmission efficiency of 33% and we can do one correction per three bits the hemming 7/4 code has a transmission efficiency of 57.1% and we can do one correction per seven bits even though we can't correct as many bits using the having 7/4 code it has a significantly better efficiency so we can send the same message using fewer bits and you know correcting one out of seven bits is still pretty good and in a lot of cases this will work out just fine now I've described the basic mechanics of the Hamming 7/4 code but at this point it probably just seems like a set of magical equations that someone invented while playing around with bits there's no real indication of how it was invented or why it works the way it does I'm going to finish this video by explaining where these formulas come from so if we look at this seven bit chunk here the stars of the show are really these X Y Zed bits these X Y Zed bits are what help us detect whether or not an error has occurred and with these three check bits we have a total of eight different possible combinations of zeros and ones that basically means these three XYZ bits have the ability to communicate to us one of eight possible states so if we can detect eight possible States what should those states be I'll show you the eight states that we'd like to detect here so this first state here we see that we have seven check marks and this indicates a state where all seven bits ABCD XYZ are all correct so this is the state where all seven bits were transmitted correctly and there were no errors with this state over here we see that all bits are correct except for the first one which is the a bit so this is the state where the a bit has an error and has been flipped this is the state where the D bit has an error and this is Sierra de error X error Y error and Zed error so the fact that these three error check bits can indicate 8 possible States is very useful it gives us one state for the no error case and seven states for the seven possible one bit errors that we might see this is why the Hamming 7-4 code can only correct one error per seven bit chunk the three error check bits only give us enough States for these eight cases if we wanted to correct cases with two bit errors we would need more check bits so that we could represent more error States now I've written these three check bits in the form of zeros and ones but that's not the best way to think about them we're all that when we're looking for errors what we're really doing is checking whether or not these three XYZ bits are consistent with the other bits in this case x y&z should all be 0 so that means that the Y bit is consistent and these X and z bits are not consistent so it's better to think of the check bits in terms of these correct and incorrect indicators the check marks and the X's instead of the plain zeros and ones so on the left here are the XYZ check bit states that we can calculate with some equations these check bit states are also sometimes called syndromes and on the right we have the actual error states and these basically give us instructions for correcting the errors if there are any so what we need to do is somehow connect the check bit States with the error states given a check bit state we need to know what error state we're in so that we can correct the error so I've written out all the eight check bit States here and we need to decide which error state they will represent so if all the check bits are correct it makes sense that this represents a state with no errors so all of the ABC XYZ bits are correct now these next three states are the cases where the X check bit is wrong the Y check bit is wrong and these edge tech bit is wrong and so it makes sense to associate these with the error states where the x y&z bits are wrong respectively finally there are these four check bit States here so these need to cover the four remaining error states for ABC a D but there's no single correct way to make the association between these check bit States and the remaining error states so I'm going to do the simplest thing and just write ABCD in order here so this check bit state will represent the a bit being wrong and so on and so forth now there's no reason I chose this particular order of error states I could have just as easily picked a different order like C DBA if I wanted but since any ordering works I'm just going to use ABCD so let's take a closer look at these four states with the ABCD bits so just as a reminder our goal is to invent some equations for the x y&z bits such that when we observe these check bit states they will correspond to these error states over here so this is the check bit state for the a bit being wrong this is the check bit state for the B bit being wrong and these are the check bit states for the C and D bits being wrong so reading this table if any of the a B or D bits have errors in them it should affect the X bit so we can write this equation here basically we pre compute the X bit upfront before we send the message and then after we transmit the message if any of the a B or D bits get corrupted there will be an inconsistency in the value of the X bit so when the X bit is incorrect that tells us that we could be in one of these three possible states where the a B or D bit isn't correct since the C bit is not in this equation the X bit being incorrect will not tell us anything about C likewise from this table we can see that the Y bit should be affected by a C and D so we can write this equation here and the Zed bit should be affected by D C and D so we can write this equation here so again we pre compute X Y Zed according to these equations and after transmitting a message say if the a bit gets flipped since a is present in the x and y equations the x and y check bits will be incorrect but the Zed check that will be fine since it isn't calculated with the a bit and this gives us the following check bit state which as we can see matches up with the error state of a being wrong so as we can see these three check bit equations come from this association between check bit States and error states and again there's nothing special about this particular association between the check bit States and the error States we could have just as easily changed things up and this would have given us different equations but the equations I'm showing now are the standard Hamming 7/4 code equations so with the hemming 7/4 code the numbers 7 & 4 are no accident if we have 7 bits where 4 bits are the original message that leaves 3 bits for the check bits three binary check bits will give us 2 to the power of 3 possible check bits States which means eight total check bit States and this matches up with one error state for each of the 7 bits plus one extra state where there are no errors and everything is fine so hopefully this video has given you a good introduction to error correction the naive method of error correction is just repeating the message multiple times but that's not very efficient we've seen how the Hamming 7-4 code adds redundant information in the form of three check bits and these three check bits can point us to one of eight possible error states which tell us how to correct errors in our message and this clever trick gives us a better data transmission efficiency rate with the ability to correct errors in the next video in this series I'm going to show you how linear algebra can give these linear equations geometrical meaning and also discuss other Hamming codes such as the hemming 15:11 code and the hemming 31:26 code and in a later video I'll discuss the actual polynomial codes used by the Voyager space probes