Video 8-3: §8.3 Hamming codes introduction

0:00 Intro

0:03 in the next section we'll look at hamming codes we've seen just before that some things are not possible so we can't always hope for an ideal code that gets all the errors corrected without spending extra bits and hamming codes will be some concrete examples where you can can give a concrete recipe that corrects certain errors and we'll we'll see how close we can get these

0:29 first off we need a little bit of uh of ingredients and the first simple one is a parity bit it's a simple idea that you may have seen before it's maybe arguably the sinkless the simplest possible error error detecting code it doesn't correct errors but it detects errors so you have some some message here it's just many others nine bits who does nine bits well uh you have a message of a certain length and you add one extra bit and that extra bit is computed as the xor of all the bits or if you prefer it's one if they're num if the number of ones is odd and zero if the number of ones is even you could also say you add up all the digits and take that modulo two it's all the same thing you may know that xor is the same as addition modulo two so that's a very easy way to add an extra bit of information one bit of redundancy

0:30 Parity Bit

1:36 and if if you now were to change one of the bits if i were to flip this to zero say uh every single bit flip changes the parity of the number of ones because it turns a one to zero or zero to a one so if it was even before it becomes odd and vice versa so if i were to do that i would also see that the parity bit flips so by by computing the parity afresh so you take the first nine bits and compute the parity and if that doesn't match the parity bit you know something has gone wrong another way to say what i what i've shown here is if i flip any single bits i also have to flip the parity bit that means the code distance of this code is two what are the code words of this of this code the code words are all bit vectors that satisfy this equation down here in the general way where you put variables so the code words are all the bit strings where if i add up all the bits leaving out the last one modulo 2 i get the last bit that's not all bit strings it's only half of them and so whenever i take a code word and i change

2:54 one bit i leave the set of code words but if i change another bit namely the the parity bit at the end or one of the other ones then i'm back into the set of code words so there's some nice symmetry also going on here so the code distance is two and from the lower bound section that means we already can say what this means um if the code distance is two we can correct we can detect at most a d minus one bit error so one bit error and indeed we can do this here as you can check flipping any bit changes the parity and so you can detect if that happens if the error is the parity bit itself you would also detect that

3:38 and also it's not strong enough to correct any error because d minus one half rounded down is zero two minus one is one half of that is one half rounded down to zero so this code cannot possibly correct any error it can only detect a single bit error it's actually a bit conservative to say that it detects more errors than just the single bit but we can't guarantee that it doesn't detect all three bit errors

4:15 oh well at least um it does detect all three bit errors doesn't it uh well what we can't guarantee is that it doesn't detect any uh change with at most three flips because if you flip two bits it wouldn't recognize the change

4:34 okay parity bits are are used in many places because they make detection of these very simple bits these very simple errors flipping a single bit possible and they're very very cheap to check in hardware so they're used in many in many uh buses and caches and unreliable memory uh usually in the scenario where you are able to correct the mistake through other means especially these communication buses if something goes wrong they can just retransmit i don't know how they did this with main memory they detect an error in the main memory and then what i'm not sure about that

5:16 so it's it's nice because it's simple and cheap it's not very powerful brings me back to the question from before shall we do the game again if i have 100 bits and i want to detect a single bit error how many bits do i have to add

5:45 i think i'll leave that just open for you well looks like there are some some different guesses uh the answer is one okay you need one extra bit namely the parity bit that's enough to detect one one bit errors

6:11 i find this surprisingly good like uh it's a single extra bit if you if you know the solution it's kind of obvious but if i i did ask you before how many bits do you think you need and many said 5 or 100 or something like a substantial extra number and for detecting a single bit one one extra bit is enough it's kind of cool okay but it's not very powerful so if we want to correct errors then we have to go further and a typical application where this is real is a real concern it's not something i made up if you have a server that's supposed to run indefinitely any downtime is really expensive so even though some events are super rare if they if you keep a server running for years it's kind of happening there's a nice blog post where someone did the math oh you can't see that's a good point now you can

7:04 Error-correcting codes

7:12 a typical application for our correcting codes is this server that runs forever supposedly um and there's a nice nice blog post where someone did the math and also tried to diagnose a mistake so where he could pin down a crash to the fact that a binary a program that he had on on disk and in memory as operating systems usually do that if you start a program they copy that into main memory so that it's faster to access and there was a one bit distance difference between those two so it's very likely that it was a cosmic ray that twisted a single bit in his main memory these things happen they're very rare but if you run for a very long time they do occur so instead of rebooting that server or crashing in some in some absurd way it would be much better to have an error correcting code and these things can these are these exist but they come at an expense so let's see um if if you think about this for the first time what could you possibly do to correct errors

8:24 how should we possibly be able to do this because it an error can be anywhere so it seems like we have no no big chance of of correcting this

8:37 but the trick of course is what type of error are you able to tolerate what type of error is is likely if we ask for a single bit then a single a simple solution is let's just store every bit three times if you do that then whenever you read a bit you have actually three bits that you read and you do a majority vote take the one that's more frequent it's either zero or one it will be one of those two so if you ever only flip a single bit it cannot compromise the majority of three and so you can correct this error so it is in principle possible it's it's a very simple construction you can easily scale this up if you wanted to tolerate more errors you just add more duplicates of the same bit but of course like it tripling the memory is probably not what you want if building this uh error tolerant main memory means you triple the cost of the server you might get uh you might get trouble financing this but it turns out with a little um more thought you can achieve is this scenario with uh 11 of overhead so you need 11 extra bits or something like this scenario instead of the the 200 overhead is if you triple

10:02 it right that's where we're going and this is what hamming codes will eventually give us how can we approach this if we want to correct an error it means flipping a bit back that's easy to do if we know which bit to flip back so it kind of reduces to locating the errors that happened so how can we do that the only thing we've learned in this lesson in terms of constructions is the parity bits so it kind of probably has to do with that one but interestingly that's also enough if you use several parity bits in a smart way you can nail down where the error occurred

10:14 How to locate errors?

10:56 now you can't take several parity bits for the same whole set of bits they would all be the same so that's pointless instead what you do is hit half parity bits for different subsets of the of the bits in the message and then by taking the combination which ones are are corrupted you can work out where an error occurred

11:23 so that's the the rough idea and the concrete construction um can look like this so the yeah there's the cave at that you can also flip the parity bits but um let's just look at a solution for this

11:43 uh we have um a message of seven bits and uh i have three constraints so this is similar to the parity bits there was one constraint i wanted that the sum of the first of the the bits up to the last one is the same as the last one modulo two that was the parity constraint in this case we add three parity constraints not just one and so there's the blue subset of bits the first four bits they should be zero if you add them up modulo two and similar for this green subset which happens to take these two and these two and also for the magenta one why these three subsets maybe you can spot the pattern it happens to be a good a good choice of subsets

12:38 simple observation if we don't observe if there's no bits flipped then by recomputing these these three checking bits taking the different positions and xoring them up we can check that no error occurred then no error means all these checking bits are zero okay what happens if some bit is twisted though let's say we flip this one

13:08 so there's a violation in all the constraints that involve this bit because now i go from b3 to not b3 wherever this occurs i now get a violation so this one will become one

13:34 that's the checking bits i get if i flip b3 the beauty of this is i don't have to do concrete examples with zeros and ones i it works the same for all for all bit patterns

13:48 and you may recognize that this happens to be three in binary zero one one and that's indeed a general pattern in this with this construction no matter which bit you flip the checking bits will tell you in binary what position was flipped

14:13 and now maybe you see why these numbers work out well we have seven positions i can encode seven different things with three bits but i can actually encode eight different things with three bits but i also have to leave one out for the the case that nothing was flipped

14:34 okay that's that's kind of the the general recipe so this defines code words i have bit strings that satisfy these three parity constraints these are my code words what i haven't told you yet is how to turn this into a code so given your message how can you compute these and how can you detect errors in these things

15:03 let's have a look at this so that's the the constraints we had how do we turn this into a code and what comes out of this is called the the four plus three hamming code or seven comma four hemming code i called it four plus three because four bits are the message and we add three redundancy bits

15:28 notice that these the colored bits here they occur in exactly one constraint this one only incurs the blue this one only the green this one only the magenta so instead of computing the checking bits what we can do is we fill the other four bits the seven six five and three and then we compute those colored bits from the parity constraints there's a single choice for these bits that makes these constraints true

16:10 we put in the message bits we can send four bits with this hemming code and then we axe all together different combinations of three of these bits so for the blue one we take the first three for the green one we take these two and this one and for the magenta we take this this and this okay so here is spelled out with the indices that way we compute the ps which are called parity bits

16:43 and then you take this alignment of the bits and send that that's the encoding step um i think it's a good idea to do a small example for that i'll try to squeeze it both maybe i can zoom out instead try to squeeze it on one side

17:22 who sent me a message four bits doesn't matter too much anyone what's your favorite four bit string four ones and so we take these and put them at these positions so i position seven six five and three four two one are left and i have to take the xor of different sets of these but because they're all one the xo will always be one

18:03 should we slightly modify the message so that this becomes a zero now the blue one is the xor of the first three and that's one zero and stays at zero

18:27 this one the green one is this and the first two otherwise known as leaving out the five there's one one and one that would give me a one and the last one leaves out the six this one but that gives me zero right

18:54 i should probably have written these names then you can just follow the recipe up here ah there's the the ball three one zero okay i don't want to make a silly mistake otherwise it won't work out so these are the parody bits that we generate

19:26 and then that's that's the the message that we sent okay for decoding we use the checking bits as before so we receive this code uh seven bits and we compute the checking bits the ones from the first slide and the checking bits will tell us in binary which position is twisted or none if it's zero so let's do this on our example and say we flip one bit which which one shall we flip

19:44 4+3 Hamming Code - Decoding

20:23 uh we had this one before i think let's let's flip this one and we have to find the checking bits now uh i don't think there's any way i can squeeze that on the same slide but here's the the formula for the checking bits so the first one is taking the four left most so we take i could try to do this in the colors

20:58 if i take the axer of all of these i get zero for the green one we have to take the first two and then these two that's now a one

21:23 because i flipped this bit and the magenta one is every other bit this one this one so here every other on that row i get that bit at position 2 is flipped and that's the right one right the number one up to seven okay and so if i know which bit was flipped i could just revert the flip and then i get the original message back and this works no matter which bit is flipped

22:15 so as a procedure again you receive this you compute the checking bits if it's zero you're good otherwise you know which bit to flip again and then you can return the the message part by just stripping out the parity bits

22:29 Clicker Question

22:33 let's try to connect this with what you learned before about the lower bounds and this code distance i think for that i have to maybe leave you a minute or two

23:05 remember the code distance is how many bits do you have to flip if you started one code word before you can possibly get to another code word see if we get this up to the 31 we had previously

25:04 does it look like there's more answers coming anyone's still busy thinking well leave it open and i'll show you the votes so we got a peek for some numbers three four seven and of course the usual game um

25:29 so the distance can't be more than than seven because any two seven bit strings are at distance at most seven uh so that's an easy one um not sure if there if any other conclusion is completely trivial so what are the code words first of all i might have mentioned this but the code words are all the seven bit strings that fulfill the three parity constraints that we have now if i flip if i flip one of the bits we know we've just seen we can correct it if i flip a second bit we haven't really talked about what happens then uh but if i if i flip two bits there will always be a third parity constraint that fails so if i flip just two bits i will not get to a code word again because it still can only satisfy two out of the three constraints at most if i flip three bits i might get into the the region where i get into another code word because then i could for example flip a bit and the two parity constraints that that bit is involved in and then i'm back

26:51 uh so yeah the answer the answer is is three because that wasn't wasn't clear now from what i said um you can find two code words that are three bits apart

27:04 and the fact that we can correct one bit errors shows that it also must be at least three because if d is three that's the for the first time where d minus one divided by two rounded down is no longer zero okay

27:22 4+3 Hamming Code - Properties

27:27 good let's um let's have a brief look at what we achieved with this with this code and evaluate this against the hamming bound we've seen in the previous previous section there are two to the four different messages and each of these get translated into a seven-bit code word so there's just these these 16 different code words really

27:59 any of these code words if i flip one of the seven possible bits i can convert it correctly back i can correct that error and get the same code word back and hence the same message back so each of these code words is really covering eight seven bit strings which are all uh in the in its basin of attraction if i multiply this out i have so many code words and so many spit strings that it's it attracts i get exactly two to the seven which means i'm covering the exact the entire space of seven bit strings so it's not only that uh each code word has so many bit strings that are close to it if i take all these balls that non-overlap that don't overlap this also the opposite property any seven bit string is part of exactly one of these balls so for the hamming codes they exactly partition the space of the the code words the blocks into equally sized balls that all have one code word as their representative

29:15 so code distance is three we can correct one bit errors um can we say anything intelligent about two bit errors uh the thing is what would happen in the code like i sketched it is we can definitely see that something's wrong with two-bit errors we don't get another code word but if you're two away from your code word you're one away from another code word and so you would correct towards this other code word so the code would happily say oh that was a one bit error and i know how to correct it here's the correct result if actually two bits were flipped there's a variant where you add an eighth bit so that this doesn't happen then you can detect two bit errors but not correct them and you can still correct every one bit error so both both of these variants the one i presented and the one with the eighth extra bit to also detect two-bit errors both are in white use

30:17 Hamming Codes - General recipe

30:22 lastly what i showed you is is one instance of a general recipe it's the smallest such code if you want in general we can start with that number of bits so we have a a block size that's one less than a power of two why that because then we can use these checking bits to address any position in there plus the one that we need to say no error occurred

30:51 so we can use these l bits um we we can use l bits as the checking bits to say which uh bit was flipped and we can also conveniently use in the block all the positions that are a power of two as the parity bits maybe that's something in hindsight that is obvious here but let me show this again the parity bits here are positions four two and one that's the powers of two less than seven and these these are convenient if you write the index of these in binary you you notice that whenever we had a one they participate in one of the parity constraints so it's a very regular construction

31:43 and then the remaining n minus l bits you can use for the message if we choose a specific size l equals 7 then we get something that might be useful for main memory we get a 64-bit um

32:05 memory uh well we can cover the 64-bits in in these n minus l message bits actually a bit more uh and the overhead is just 11 as you can see here you crank up l n gets much bigger because here's a 2 to the l so you add one more extra parity bit and you almost double the block the the message length

32:33 so arguably the hamming codes are still fairly simple they're definitely efficient to code whether you do that in hardware or software and they are much more space efficient than maybe one would have expected after this uh initial example of just tripling every bit

32:54 uh if you look at this um more closely you will notice that these these choices for the message length as they come out of this recipe they're somewhat special these are the ones where this nicely works out where the construction can exactly partition the space of 2 to the n around these code words and people have called this the a perfect code because it exactly matches the hemming lower bound and so we cannot possibly use fewer bits if we want to correct one bit errors in this scenario

33:03 Outlook

33:32 the problem is that it is it is restricted to a certain subset of possible message lengths these are not necessarily the most convenient uh we like in computer science we like things as powers of two and powers of two are never among those apart from the four so it's um

33:53 for these for these specific sizes of messages the problem is solved and the best possible solution if you want to correct one bit errors is the hamming code but in many other cases is is quite open how to do this well um and there's an interesting result from from the theory that says in a sense if you choose your code words just randomly randomly throw them in the space you have a large probability of finding a good code uh but these codes are inefficient there's no no nice procedure like for the hamming code compute these parity bits and then you're good that doesn't exist if you just use random code words so in in several ways we we know that it's possible to get good codes or other scenarios if you want to correct more bits or if you want other message lengths but we don't know how to do it there's only a theoretical result that they exist but it's it's relatively useless as such because you can't really encode and decode these codes and there's still some some research going on into concrete constructions that try to push the the frontier on these two things

35:15 that's all i want to say about error correcting codes just to tie this up with the compression unit the two really go together even though it seems like they're doing opposite things compression takes redundancy away and here we add redundancy back in but really what you want to do in communication is both you first have data that might have redundancy built in you compress it to remove that useless redundancy and then you add controlled redundancy back in through error correcting codes to protect the compressed data from errors during the transmission and the thing is that you don't add the same type of redundancy in it feels like you're going just back and forth but but really the redundancy from compression is often not in the sense that it protects the data from manipulation so you want to get the redundancy out in a way that can be inverted and then sprinkle in redundancy in a convenient way tailored to the communication medium and that's what the error correcting codes are about