Error Correction - Computerphile

Key Takeaways

we've done a lot of work so far on weather scenarios for San Francisco and for Los Angeles I've put forward to you this um probability model some of you say it's not very realistic quite right this is a teaching example these are the probabilities because they suit me and that's what I say they are but what we did last time was to say if you're worried that these could get distorted in transmission what's the best thing to do what's the easiest thing to do well the easiest thing to do I introduced you to this idea of a check sum digit at the end what it meant was that as long as only any one of these bits got distorted in transmission you had a lovely situation of if you like good codes but if you said one bit gets distorted and so long as it's only one bit out of the three you could end up with something like this zero becoming a one you received Z 010 that's not in the list of valid codes there's an error has happened there and I think I covered also the fact that you may know that there is an error there this could arise in two or three different ways but you don't know how it occurred but at least it's nice to know that an error did occur and at the very end of the last discussion we said well if you want to say to San Francisco I didn't receive your data correctly you could send either an acknowledge or a not acknowledge signal and I postulated to you that we might decide that an acknowledge signal to send back to San Francisco meaning I got your three-bit code it makes sense to me I got 0000 0 it's foggy wonderful I like it if that is the case send back a zero on the other hand if I received a 0 one0 it's not in this allowed set of codes I would send back what's technical called a knack and we'd use a one bit for that many of you said what would happen if these acknowledgement codes got clobbered on their way back to San Francisco how on Earth would you then cope well armed with what we know now the simple approach instead of acknowledge being a single zero will make it a double zero instead of not acknowledged being a one let's make it a double one if one of these gets altered you might get a 1 Z you might get a 01 similarly here if just one bit of those gets altered you could equally end up with 01 or with one Z you expect if you're back in San Francisco you either see a clean double zero or a clean double one if you get these you know that an error has occurred in transmission but as ever you don't know how it occurred was it a distorted acknowledge signal sign or a distorted not acknowledged signal now this could go on forever if we're not careful you know San Francisco sending back to Sacramento um I've got to not acknowledge on your attempted acknowledge signal you just it's not good what you really like to do here and this is a very useful lead in for me to lead into Hamming codes let's see how we can build up a slightly more sophisticated system adding one extra bit more or if you do that you can not only detect that an error has occurred but you can actually correct it this gentleman Richard Hamming comes slightly after I think a person I mentioned already the great Godfather of information Theory Claude Shannon so those are the two big names around about this era shortly after the information Theory and optimal codes and so on but in noisess conditions Claude Shannon few years later comes rich Richard Hamming saying how can we detect errors and more to the point how could we begin to correct them you've put this on a plate for me because I can discuss it in terms of how to get an KN and a knack back to San Francisco so that you can decide and correct it if it gets clobbered from now on the a will be to send three zeros The Knack will be to send three ones suppose you send three why is that magic what does it do if it's a three bit pattern that you're sending then if those get varied for any reason of noise the total number of combinations in three bits as we know off by heart now is 2 power three eight combinations let me just pluck out of thin air the idea of representing those eight combinations possible as big being the corners of a cube let me not go through the algorithm for creating Hamming code but just pluck it out of thin air as I'm so fond of doing let's call this one up here our good code of 0 0 0 Let's call this one at the back lower corner of the cube one one one so that one if you like is representing a this one is representing Knack so so long as your properties of your line were such that errors were relatively infrequent and you got mostly one binary digit errors then fine here's what would happen you might send 0 0 0 and it ended up as being received as 0 one0 the middle bit got damaged you might send a 11 one one and it got received as a 1 one z a one got into a zero you might for example have sent three zeros but I'll represent over here that the left hand bit got hit and became looking like a one here's 101 this one is 01 and this one down at the bottom is 011 on let me just circle these are what was actually transmitted so can you see that what you're now in the lovely position of been able to say is if I receive three zeros that's bound to be good similarly if you receive 111 trust it it's a knack but if you receive a 0 one0 what then should you do the rule is maximum likelihood if I can spell that or nearest neighbor correction you can correct what you've received by saying the following I received a 010 I know that that is not on my list of good code words because the only good ones are three zeros and three ones what's the most likely way to correct 0 one 0 back into being something good well the answer is by going up this line here that's distance one away I change the middle bit back to a zero and I've corrected it to three zeros if I receive 00 01 the most likely thing that's happened with only one error taking place is that the trailing zero here got damaged into a one so my correction should be like this go distance one along the Cub's edges like that 100 corrects back to three zeros now same thing again look the majority of the bits here 1 1 0 2 out of three match up with 11 one therefore my best and most likely correction is to turn the zero back into a one how about 101 oh yeah obviously this was sent and it was the middle bit that got hit and turned into a zero so correct that one down here finally over here 011 again 2/3 of the bits are correct but the leading one got hit and turned into a zero I clearly have to correct to that so you can see looking at that that for all of the six corners of the cube that are not the good and damage codes you have with nearest neighbor maximum likelihood correction a distance one correction algorithm but the final thing to notice is that for this to work and you may remember going back to my original example of when you can detect but you can't correct the thing there was that the distance between the good codes was two notice that what we're doing here now is that between these good codes I should use yet another color if you want to get from 00 0 to 11 one you have got to take a journey involving one two three steps don't matter how you get there you could go one two three you could go one two three down there the good codes our distance three apart so this is the simplest example I can think of of what was generalized by Rich and Hamming into being Hamming codes the way you actually build them up algorithmically is a bit involved but I'll let you all look up about this if you want some more information essentially Hamming codes are really really good and absolutely definitive in their time for doing distance one Corrections okay for coping with things where only one bit was in error where things get massively mathematical utterly fascinating and deeply involved are the moment you start saying oh well I'd like to correct one bit but not just in a three bit pattern how about in a 32-bit pattern yeah okay well how many different ways can that go wrong and how are we going to keep all of these different one bit errors apart from one another how can we keep the good codes well apart in a much bigger big bit pattern and where things get really hilariously hairy is if you say h i don't want to correct just one bit I want to correct three bits up to four bits up to seven bits and that gets you seriously involved in stuff with names like field Theory rings groups co- sets and other lovely stuff like that what we thought we'd do is make them all sort 100 elements and see them side by side sped up a bit cuz some are quite slow hide in all the Computing business we're free to select from the different games that that I happen to have the cabinet design is based on the genuine Defender arcade machine developed by Williams in 1980 in fact the code for this was written over weekend