Error Detection and Flipping the Bits - Computerphile

Key Takeaways

at Sacramento at your listening station you hear 010 and you say that can't be right what's the simplest thing to do to try and find out what the weather really is because you know that an error has occurred we've talked about the most compact way to transmit this information there are four possible patterns you can have two zeros you could have 0 1 1 Z and one one however we've got to be careful here because what we've done and referring back to what I've said previously about compression methods what I've done here is devised a code which has no redundancy at all we've talked about how to squeeze redundancy out of text files and pictures which is what compression is is getting rid of unnecessary information there's nothing unnecessary here every one of those bits is vital and you better hope they don't get lost or distorted on the way unfortunately they might get lost or distorted on the way so the next thing we have to say is these codes are beautiful but they rely on you having clean noisess communication across your telephone wire what would go wrong if that wasn't the case just occasionally one of these zero bits that's signified by a short Boop for a dot might get turned into a one because partway to Sacramento suddenly an electrical storm occurred and just hit a tel wire so what was received at Sacramento was not it was like that a longer second bit and the people oh that's 01 it's sunny in San Francisco no it isn't it's foggy so you can see very quickly there is no possibility for recovering from error in these if you get an error people will receive apparently a good pattern but it will be for the wrong weather condition how could you add something extra to these to give them a bit of protection against noisy telephone lines a simplest way one of the simplest it's been used in telecommunications and indeed within computers for years and years now you put in a parity check bit so here's a code with a check bit and all I'm going to do here I will take every 2bit code and turn it into a three bit code but the rule will be that in the overall three bit code I must have an even number of one bits so this is called an even parity system so here we go zero zero there are no ones in that so therefore at the right hand end here I'm going to add in the parity check bit and because we're on even parity it's a zero viewers of number file will have to forgive me I think there is a video on there questioning whether zero is an even number I'm sorry I'm just a computer scientist people have a delayed reaction people are not sure whether zero is an even number that's even as far as I'm concerned okay how about this one 01 well overall it's got to be even parity which means an even number of ones so my bit I add at the right hand end is a one equally here for clouding one and zero there it is two of them 101 rainy that's easy there an even number of ones already so I put a zero at the end now those codes with the check bit they help a lot in helping to detect whether an error has occurred just suppose that when this 0000 0 was sent it got distorted again an electrical disturbance just happen to chew up one of the zero bits lengthen it and make it look like 0 one0 if any of these got distorted a n turned to a one or a one turned to a zero it looks like a valid different weather State here it doesn't because look at the valid codes three Z's 011 1 01 1 1 0 I sent this and it arrived at the other end as 01 0 is this a code that in this set no it isn't if you try with these just changing any one of the bits and flipping it either a one to a zero or a zero to a one you end up with something that isn't in this list of good valid codes you could say well there's bad codes there's things that don't correspond to any of these and of course with three bits 2 to ^ 3 is eight so there's eight possible combinations what we've done here is split them up in into four good codes that are meaningful and four bad ones but the bad ones give you a protection against errors in transmission your listening station you hear 0 one0 and you say that can't be right what's the simplest thing to do to try and find out what the weather really is because you know that an error has occurred well the simplest thing is to send back to San Francisco a simple one bit message either a notter or one you either say acknowledge in other words I got it it's a good code or not acknowledge here I would send back a not acknowledge often called a knack for not acknowledge I send back a one bit which says not acknowledged got garbage and the sending end would say okay let's keep it simple just send it again not not not next time you hope it's going to get through without Distortion so this is the basis of this system in that it can detect that a single error has occurred the only trouble is that it can't tell you where the error occurred just consider the following I have got 0 one0 here by changing the middle zero into a one but it could have happened that it came from this one via Distortion it could have been that the bit that got distorted was not that one or that one but that one that trailing one bit might have got turned back into a zero there's an error but I don't know whether it came from this one or from this one so this kind of code then can detect one error but it can't correct it it can't tell you where it occurred suppose I had a even noisier line and that in one of these three bit codes you hope most of them are going to go through cleanly you hope that the ones that aren't clean will have at most one error in them what happens if I send one Z1 and there are two errors in it not just one the errors just so happen that it turns a long blip into a short one there and there that would then give you Z 0 Z two errors oh Calamity again this is received at the receiving station they say hey fantastic 0000 0 it's foggy in San Francisco no it isn't it's cloudy but it got two errors so it looks like it was foggy so the point here is it's resilient against one error it can detect it it can't correct it but against two errors there isn't resilience it distorts it into a good-looking code again so for this reason this system is called a distance to code because what it's saying is if you flip two bits it changes in into another good code if you flip one bit it's discernably garbage and you can say an errors occurred it's 80 megabytes and let me say again 80 megabytes not 80 gigabytes and it's in this huge package combination of Art and Science that goes into making a game is an extraordinary thing