Video 6-3: §6.3 Hamming codes introduction

0:02 in the next section we will look at upper bounds for these codes concrete constructions that give you certain error detecting and error correcting codes and we'll of course hold them against the definitive lower bounds we've just seen which are impossibility results they show we cannot do better than certain things so we know what to aim for now uh but let's get there step by step the first simple trick that most of these codes are based on I think all the codes I know are in a way based on it is is this simple trick it's the parody bit and you can formulate it two ways uh we add one extra bit and in this bit we put well one bit of information either zero or one uh depending on whether all the other bits overall have an odd or an even number of ones now there's one way there's two ways to explain this either is you take the x or of all the bits and that's that's the extra bit you sent the other option to Define it is the whole the whole thing with the parody bit added has to be an even number of of ones irrespective of what the message was and so uh in that sense the parity bit makes sure that everything is in

1:20 pairs or is even uh pick whatever you find more intuitive if you look at that from the Block code angle it gives you a code of distance two because there's always uh one one if you flip one bit you definitely destroy the parody right if you started with an even number of ones no matter whether you flip a one to zero or zero to a one you'll end up with an odd number of ones afterwards and that's not a valid code word so in in our code here um not on the slides

2:05 let me add it valid code words are those with even number of ones right and every other code word is like that so you always have to flip at least two bits to get from one to the next and that means the code distance is two and amazingly they can detect single bit errors because uh if you flip a single bit it makes the parody off and you can detect that by just summing up the number of ones now I can do more um any odd number of flips has of course the same effect but uh if you flip an even number of bits it goes unnoticed now this is so um so fundamental that many pieces of Hardware use this uh as a sanity check in between uh it's not um well uh without getting in into further details I mean this is this is often used as a sanity check and what you do if you detect an error is a different question depends on the application that's not our Focus here it's very very simple and cheap you can do this exp or operation easily in Hardware that's why it's often used at this lowest level uh but of course um it has a code distance too so what does that mean from

3:25 our lower bound section well if anything it can only detect one bit eror and it does and it can two Min can potentially correct how many bits flipped well 2 minus 1 divided by two rounded down so that's zero you can correct zero bit flips amazing so it cannot correct any errors can only detect

3:55 things um so we've had that question and I just want uh to show your votes in uh from previously uh for the recording but also I guess you now have a a different answer I locked this one so you can't change it uh but I have uh the question

4:20 again so if you want you can put your new answer one so that was cute uh the error detection we kind of handled in one slide error correction is a bit more interesting and I want to motivate why this um why is it why this is a really useful thing so a typical uh a real world application for error correcting codes is is computer main memory now simple cheap devices or well cheap but most of your laptops and mine won't have this because the assumption is your laptop doesn't run for months and months in one go uh so if there is an occasional rare event of an of a flip in your in your memory ah you'll you'll just reboot and it'll be fine now if if you want to dig into this a bit deeper uh some person wrote a very lovely blog post where they they did some nerdy Unix tricks to figure out what happened there was a program crashing and they nailed it down to um a one bit difference between the copy of that program in main memory and the program on disk and so it's kind of clear there that what must have happened is that the flip the bit in memory has been flipped by something H and indeed uh Sun storms and

5:55 cosmic rays can do this uh remember these are super small Nano scale uh charges and it doesn't take so much to flip them we're close to the quantum world so things are not as deterministic as our abstraction uh treats them like and so these are these are very real and if you have a heavy dter server with lots of bits in its main memory running for months on on and on is actually a reasonable chance that one of the bits will be flipped at some point it's very unlikely that you will see two bits flipped but one is a a real thing right so um that's why heavy duty server Ram U has an error correcting code built in to recover from that gracefully without rebooting and so

6:47 on now um that said um how would we possibly do this and we'll focus very much on this this kind of um motivation where two bits flipped at the same time and closed to each other is super unlikely that would mean really uh uh winning the lottery twice in a row but winning the L Lottery once if you buy millions of tickets remember main memory is big is actually a billions not not Millions maybe more uh is is occasionally happening okay so how could we possibly do this there actually a very simple solution maybe you thought about this I don't know uh you can just store everything three times if one of the copies is corrupted you have two other copies so whenever you asked to uh decode a bit in memory you just take the majority vote of three bits and that's your answer that corrects any one bit error right uh and again if if you have more than one bit flipped uh let's let's suppose that's so unlikely that we don't care now that's great so actually error correcting codes aren't so hard the only uh slight downside is um that it it triples the cost you can only use a third of your main memory and that costs money and it costs

8:12 energy U maintaining the Integrity of your main memory is is one uh energy hungry part in keeping computers running I mean on a laptop it's often the screen that eats most and then the CPU is is often if it's doing something is a lot a lot of the energy but if if the CPU is idling then main memory might be the next next biggest energy consumption and so we don't want to Triple the main memory right that's just uh that would be too much and what I'll show you in this uh cute little section uh does the same thing with 11% of redundancy so instead of tripling the cost we U multiply the cost by 1.1 that sounds more modest 1.11 that sounds sounds reasonable paying 10% extra for recovering from occasional Sun storms seems a reasonable price and that's why this price is paid where it

9:19 matters um again I locked the question but let me show uh what you thought back then for correcting things uh unfortunately slider doesn't do doesn't do a good job of averaging this uh that was the question why I was telling you yesterday tell me how many bits you need to correct a one bit error although the slider question said detect so uh hopefully not too much confusion arose and well at least some person said 11 that's great and we got all sorts of numbers bigger and smaller um what you could have figured out yesterday from first principles is that 200 bits should be enough right this tripling sending everything three times that definitely works um so we never need something crazy like this uh but of course then otherwise it was it was probably just uh guessing that you could do so let's see how this works all

10:27 right amazingly we'll use parody bits again um but we need several of them so that we can narrow down what happened more and the core idea will be uh we take parody bits not of the whole message there's no no use in doing that several times over instead we'll use uh well chosen subsets of the bits in the message and cover them with one parity check and from the combination of these parody bits You can conclude things all right

10:58 uh now okay um you have to be prepared that also the parody bits can be flipped so you have to make uh make sure that it works in that case too here's a concrete setup that we'll focus on where the message has seven bits that's the block size that we sent sorry not not the message the the block size has seven bits um and the the three colors show the subsets that we use for parity checks it will always be four positions the the blue one takes the first four then the green one takes the first two and these two and this one takes every other starting with the first and then the way we we Define them as as for parody checks before we set uh we we we Define that summing up all those in X or should get zero so we should have an even number of ones in the four blue the four green and the four magenta

11:57 bits okay that's definition for now so every valid codee word right so um a seven bit string is a code word if and only if it satisfies these four constraints uh three

12:22 constraints some simple observations um if we send these seven bits and nothing happens then all of the these are zero right and then um I can treat these three bits as one number as a binary number and it comes out as zero now um let's suppose that there's one bit flipped so I sent these seven bits and one bit gets twisted um any preferences which one shall we flip shout a

12:56 number five uh I mean either Works let's let's take that one if that one gets flipped it will affect the the blue and the magenta one flipped so if I decode the this this uh string C I get one1 if I read that in binary that's a five oh cool that's the uh thing that we flipped and um I mean I made it sound like that's a surprise but it was constructed like this if you think about how these are selected the the blue exactly select the the four ones that's those where the first bit in the binary representation of the index has a one the second is the one where the second bit of the binary representation has a one these are these these two and the last bit is is easy to see because it alternates uh all the odd indices have the magenta thing included that's 1357

14:21 okay so what this means is if we get such a seven bit string and it originally had this constraint satisfied and we flip one bit then um this this checking code C tells us exactly what bit was flipped but that's amazing because then we can undo the flip right it's just one position that we flip back and then we know what the original Seven bit string was and because this works for every of the seven positions um these are all all possibilities covered the eighth possibility is that no bit is flipped which we can also detect then C is already zero so that's a cute definition of code words it's not a code yet right so I I haven't told you how to take a source message and encode it using this code but we're actually not far away from that to turn this into the into a code and this is called Hamming code it's a specific instance of a Hamming code uh we'll come back to that but I think it's uh if you understand this one you'll understand the concept so that's again just copied from the last slide this def this definition of checking bits now if you um if you pay close attention there's some of these bits that occur in only one constraint this

15:39 one this one and this one it happens to be those at indices powers of two uh so instead of saying we have this constraint and they have to be zero we can set those three bits so that the constraint is satisfied because they're independent the they're always just included in one of the constraints I can independently make every constraint satisfied and so that's what we do for the hemming code for the encoding step we're given four bits that's our message length and uh we'll put uh some color uh let's do these in green so I put these at these

16:26 positions that's the first step then I comp compute the parody bits for each of these position so that that is satisfied which just means for the blue one I take the parity of these X or those three together if that's a one then I put a one at this point otherwise a zero that's indicated here with these lines I think the picture looks wilder than the construction actually is so you do this for all the three then the checking checking bit string is zero then you can send that and the decoding we basically already covered you determine the C and if that's not zero you know one bit where you have to flip and uh then you just pick these four positions and ignore the parody bits that's the

17:25 decoding so spelled out if we receive a block of seven bits we P see two slides back if that is zero we're happy otherwise we flip exactly that one bit that is determined by C and we have to pick out the right positions to

17:50 return let's see if you digested this um that might need a a minute to Think and I'll go back to that slide is I think that has all the information on it somewhere that you need to answer

19:31 we 80 is people earlier or did it go up further than that actually wow 114 let's at least wait for 80 roughly uh I don't have a question otherwise that I asked only

20:47 well there's a a clear majority for the right answer uh so let's just briefly unpack why that's true maybe on this slide is is cleanest uh the thing is you have to make C

21:02 back to zero before you find another code word and um for that you have to flip uh three bits because um it's not actually obvious to prove maybe but because you can correct one bit errors uh you kind of could work backwards that you need at least three um and you can also say there are code words of distance three because I can flip these three bit um but most these are uh I can flip three bits and get back to another code word

21:59 um yeah I guess that's the worst case so you flip one bit you have to correct two other counting bits it's actually a bit tricky to prove uh let's not prove it on the spot but three is the code distance of this Hamming code now let's uh compare this with our lower bounds from

22:30 before we at the in Bound earlier and then there we said um we related these these as follows so I add 2 to the N has to be greater or equal 2 to the K and then you sum up the number of flip bits from0 up to uh D minus one2 round it down and then n choose F so what do we have to put here the length of the the blocks is seven the number of the bits in The Source thing is four and the distance is three as we just uh convinced ourselves uh so if you work this out in this example you get exactly two to the S and uh that means you have exactly as many code words as code words are in the size uh in all the balls summed up so there's nothing actually left you're using every 7 bit string in a radius three Hamming radius three distance ball around all your code words um so uh you exactly cover the space of seven bit strings with with your balls that's the the tight case uh it often doesn't work out like this if you have other parameters but here it does and we can correct one bit errors as we've seen if you you're thinking about doing more with the same

24:01 code um we could potentially detect at least two bit errors right three bit errors are out of the question with a distance three but maybe we can detect two bit errors now uh if two bits are flipped we will know that something has been flipped but what actually happens is that our decoder happily decodes it to another source message thinking that it is a one bit error because because of this tightness it means whenever you start at a code word and you flip three bits um you must end up with another code word because the whole Space is covered or at least you must be in the ball of one other code word so if you do uh if you do two two bits sorry so situation is like this the distance between those is at most three so if you flip two

24:59 you enter the ball of another code word and so instead of going from here two bits you will correct it towards that one so we can't really see whether two bits were flipped we would mistake it as a different one bit error uh there's a variation that people often use where you add an eighth bit which is just the parity of the overall block that you send um and that allows you to detect two bit errors as well but you can't correct them so it's kind of a it's a bit of a a hack on top of the Hamming code um but it can be useful to at least detect these very much more unlikely two bit errors but at least know that something went wrong okay now I said this uh this 7 comma 4 Hamming code is is one specific instance of a general recipe actually the code of just tripling a single bit is also is the trivial version of a Hing code and in general you can do the same thing maybe let me just motivate this from the picture here uh we took the positions of powers of two and used those for parody bits that's what happened here and you can do this in general that's what that slide

26:24 says um the overall number of bits in your block is one less than a power of two uh because we need to be able to encode every position with the checking bits plus the zero case where no bit was flipped then we can use the L bits at indices at a power of two as the parody bits and the rest we can send as data bits so that's the the general recipe um ours corresponds to L equals 3 and L equals 2 is just the triple everything and you can make L bigger that's how I came up with these 11 % uh if you set L to seven you can correct any one bit error in 100 tra2 bits and a standard computer memory word would be uh

27:12 64bit so if you want to want to protect that you need this 11% overhead even though you're not actually using all the data bits you have so overall um haming codes are still very simple simple enough to encode to the Implement them in in Hardware um and they massively reduce this overhead from just tripling everything that's why where they're fairly widely

27:42 used a brief comment on what is what is not so easily possible uh so the generalized hemming codes that we've seen are called perfect codes because they exactly match the hemming lower bound so we have a matching a matching lower bound we can't possibly do better and we have an upper bound that achieves it so um everything great so we cannot possibly do better if well the message length has a specific form that comes from the construction and we want to do specifically correct one bit errors if you uh if you re uh go away from any of these two assumptions it's not clear um Hamming codes might not be the best possible choice and you might not even know a code if you want want to correct more errors uh and for many of the parameter choices the search is basically still open it's still an open research question to find POS find best possible error correcting codes uh there's a a fun a fun fact that I won't get into is a is an old proven result you may know Claude Shannon for um as the Founding Father information theory he proved this basically in his first uh first Trea of the of the topic uh if you um in a certain way

29:01 choose your code words randomly so the code words in the space of two to the n n bit strings if you choose those randomly with a little bit of a cleanup you usually get a good code in the sense of good distance but um if you pick arbitrary code words there's no clean encoding procedure that gives you a way to get from your message to that code word and back in a in a pass way so in a way we know there's reasonably good codes close to the respective lower bounds but they're useless because they're too slow and they're hard to find um and so people are are still looking at uh tricks for specific parameter choices to do better than