Video 8-4: §8.3 Hamming codes

0:00 Intro

0:03 we left off last time here uh announcing that um there are error correcting codes that don't have this massive uh 200 overhead of the duplication code the simple one where we uh send each bit three times instead of just once um and so the the announcement was that we can get this with eleven percent of overhead for a reasonable block size instead of 200 i'm sure you are all curious to find out how that should work so here it goes the the conceptual idea is we want to use parity bits not just one that can't be enough but several of them and we want to somehow use the parity bits to locate errors if we have a single bit error then it's basically enough to know where the bits error occurred then we can just reverse the flip flip it again and that that undoes the mistake the only question is how do we use parity bits in a smart way to achieve that and that seems not quite obvious how to do

1:18 parity bits

1:22 but it turns out this is uh this is entirely possible with the following setup i'll go through this in a second i just want to point out this one here we cannot rely on the bit flip to occur in the data bits it can also be one of the parity bits and we have to live and cope with that uh just just as well

1:46 so without um without further ado and without motivating this on on that side of things much more here is essentially the solution uh we use seven bits in this example so these are these seven bits uh but they are not allowed to be arbitrary bit patterns we want that whenever we have seven bits b1 up to b7 that these checking bits c2 c1 and c0 are all well 0 modulo 2 there the xor of all those bits is always 0. and how does that work well the the blue checking bit just takes the first 4 position and takes their parity remember taking acts or first of all it's it's associative so you can do this in any order you want as long as you grouping the same same bits at the end um and xor um has the feature that if you acts or a certain number of bits together the result is exactly the parity it's uh zero if the number of ones in that collection was even and it's one if the number of ones was odd so c1 does that for the first four bits the highest four bits c2 the green one does it for the first two plus these uh well fifth uh well counting from below it's these two and these two and then we

3:25 have the magenta one which does it for every other bit starting from the outermost that looks like a very curious pattern what you might already see is uh i wrote here some bit strings and you might might be able to figure out what the pattern with those is but let's first of all uh just take this as a given so we have seven bits and we enforce that uh certain subsets of bits have even parity that means certain bit strings are no longer possible

4:08 a first observation if no error occurs if all seven bits are correct we can find out we can check for this by computing the checking bits and if these are all 0 then that's our signal that's what we use to mean no error has occurred and let's just observe what happens if we flip one bit um let me see i i want to do an example for this first let's say we we start with a a combination of bits that has um the proper parity

4:48 and and then we flip say b3 okay um so this one's different now this one used to be one say and now it's zero what that means is that both the magenta and the green checking bit will also flip its parity

5:21 c2 is not affected because it only takes the blue positions here and b3 is none of these so there's no change in parity but c0 and c1 they both flip to 1 because they were even before and now we flip a single bit that must change the parity and now notice that if you write 0 1 1 that is exactly writing the number 3 in binary uh and if you uh take all the other numbers one through seven then you see uh the colors or which checking bits a certain bit is taking part pardon is exactly encoding the index in binary so that's what's also written on the slide now in in general this holds for any of these bits if the chaff bit is flipped um that means we get a represent if the i bit is flipped sorry then we get a representation that the the checking bits the chafe checking bit is is one now indicates a mistake if the chafe bit in the binary appreciation of the index i is one the index that we flipped okay

6:49 and that is the essence of of the hamming code we use this this set of constraints here to enforce a certain structure on these seven bits that allow us uh to find out if an error happened and if so where because whenever some some mistake happens the checking bits essentially tell us where was the bit flip it's pretty ingenious and also quite simple but if you start from scratch thinking about this i find it i find it intriguing that it's possible to do this very simple trick to find out where where the mistake had happened so the checking bits simply encode the position of the one bit error and we allow zero to signal no error that's why the bits are numbered from one to seven here conveniently so that the zero as a code for the checking bits can indicate no error has happened

7:53 let's now turn this into an actual code so far we've said there's these seven bits they just fall from the sky and they're magically happen to satisfy these constraints that's not how coding works we start with some message bits and we want to add some extra bits of redundancy to turn that into an error correcting code how can we do this for the seven bit constrained the constraints seven bits that we did here the core observation is that four of these bits namely those ones

8:31 they only occur in a single checking bit right the magenta blue and green one and that means we can define these based on the rest so we can keep those um the bits at these indices three five six and seven we can treat them as the input and then choose b4 b2 and b1 so that the checking bits are all zero that's the idea and it nicely works out that these are the powers of two so their binary representation has a single one that's exactly why that is the case and you might be you might already see how to generalize this picture but for now um we'll stick to the four plus three hamming code where we have seven bits in total three are used as parity bits so the four remaining ones are the message so if we start with a message of arbitrary four bits we take those four bits and put them in order into the positions that are not powers of two whose index is not a power of two

9:51 and then we compute the other um the remaining bits so i called this here p1 to p2 up 0 to p2 the parity bits um but they're really just chosen so that the c's are zero okay so we have four different types of bits now um just to to get that picture clear let me repeat that part in the the world above here in the upper world uh we have a seven bit string that's the b's this one and we have the checking bits and these are just the the bits come from somewhere and i can compute the checking bits and then either i say i like this code no error occurred or some error occurred and i can tell you where that's just that's the mathematician's point of view it's a definition and i can say something about it but this is not an algorithm the bottom part uh this one here we have the d bits that's the input and we have the p bits that's the output we compute the piece from the d's uh shown by the shown by this formula so we we compute the parity of certain data bits um and it's just another way of saying if you take the d bits and the p bits and you uh

11:12 interleave them as shown and treat them as the b bits and then compute the c bits the c bits will be zero okay so that's maybe a more complicated way of saying what's written here the algorithm for encoding and hamming codes is very simple you take your four bits of the message you put them in the right positions for the b's and you compute the piece with that formula and put them at the remaining positions that will automatically make your c zero

11:52 that's the encoding step that gets from a four bit message it turns into uh how can i do seven seven bit into a seven bit uh block a block code that's what you transmit over your unreliable communication channel and that channel might flip a bit or it might not flip a bit and then we receive some bits and have to decode it so that's what we will have to do next first we only have we've only seen how can i produce the code now i have to also uh get back to um to decoding this

12:33 okay i forgot this this last i i forgot that i have this interleaving step explicitly here it's also in the picture we talked about this how can we decode this so that's the the second algorithmic part is uh you're given this um encoding basically was from the bottom world to the top world we got the d's we computed the p's and therefore we computed the b's and now we try to go the other way around um we receive from our channel these bits um b the the seven bits and we don't know what happened uh but we can compute c just using the formula from above and using the xors and then we know if c is zero probably no error has occurred now to be precise the statement here is that no detectable error has occurred now of course that's that's important to note because it can happen that more than one bit flips if the communication is really unreliable we could have that situation but no code can possibly detect if your channel completely randomly flips the bits there's no way you can decode this this is something you can prove so we'll assume again that bit flips only happen rarely so again if c is zero no detectable error occurred and we'll talk at the end

12:39 decoding

14:01 of the of this subsection a bit about what that means what what are the detectable errors otherwise if your c is not zero you know exactly which of the bits was twisted and so you just flip that again undo the mistake and that's it then you're back to a code word that has c0 so it's a valid code for for the hamming code and then you just have to take out the appropriate subpositions that's the message bits from your hamming code that's the decoding step it's fairly simple and fairly easy to compute so this is a an efficient algorithm um just pointing this out because i'll come back to this to this question of how to decode

14:55 if you have any questions so far [Music] that would be the right moment to ask them we've seen how to encode we've seen how to decode now i'd like to move on to discuss the properties of this of this error correcting code i'll give you a second for asking your questions but if you don't have one if you don't have any questions then we'll move on

15:36 it doesn't look like you have pressing questions at the moment so let me move on to this uh nice question if you remember from the lower bound chapter we talked about code distance

15:46 code distance

15:54 um this is something it was it was last week it would have been nicer to have this in one session then memories would have been fresher but please head over to slido um what i did is i just set this up as a as a tag cloud answer so again you can just freely type a number but really the answer should be just a number and uh code distance that was um this notion of hamming distance if you take any two code words that are valid in the code what is the hamming distance between those code words and that had to do with the ability of a code to detect and correct a certain number of of flipped bits um i'll give you a second to answer this but yeah i think we should really get 20 votes before we move on because this is a an important point and it also is a great way to connect to the maybe more theoretical lower bound section

17:11 okay as the answer is slowly coming in i think we can do at least 20. there were 23 votes for the opening question about the programming puzzle which maybe i didn't leave open very long so maybe a few people missed it but we should be able to get 20. if you have if you have no idea just i don't know um type no idea

17:37 uh it's that's also fine you might want to go back uh and and check the definition of code distance um that might be something i could do really would like to see a few more results on the poll time to wake up guys if you have no idea type no idea that's that's fine don't be ashamed i know it was last week when we talked about this and this came out of the blue now

18:52 well are we really so few people today i can see you know we've seen there's at least 17 people in the stream so we should at least get the 17.

19:06 and don't you turn off the youtube stream now oh it actually dropped to 16. someone i scared someone away by saying this okay so let's let's keep it with the 16. uh here are the um here are the results and you see some peak for three that's good there's also a lot of other answers okay let me lock this in now here's the slide from from last week when we discussed this uh first of all remember the distance of a code was defined like this you take any two code words maybe let me make it a bit bigger you take any two code words x and y so and code words again is everything you can get by taking a valid message and encoding it without any mistakes okay this is all the uh n-bit strings you can actually get if you take a valid if you take a message an arbitrary message apply the code and don't do any mistakes yet uh that's all the code words that we get so in our huffman in our hamming code that's you take your four bit message you add the three parity bits and that's it that's that's your code word if whenever c is zero the checking bits are zero um and then uh what's the what's the distance how

19:34 code words

20:27 many bits change if you uh change one message bit well it turns out every message bit is part of all three checking bits uh so in general these all change um but uh

20:42 some might might flip twice we get the the same we get a okay this is if you if you flip several bits in the message you might flip um only one bit in the parity bits but it turns out three is the the right answer

21:00 okay um and uh it's good to have that slide here because um we discussed about what the implications of a certain code distance are for the detection and correction of mistakes so first of all if d is three that means we can at most hope to detect two bit errors detect there's no way we can detect three bit errors because that might have been already taking us to the next valid code word and we can correct at most that number of bits so if you insert three that works out to one and that's what hamming codes promise to achieve okay

21:42 lower bound

21:48 that's just for the record uh put the number here so uh three is the right answer and uh well there are many ways to work this out uh let's also recall the lower bound that we had for hamming codes or for for general codes uh we had this lower bound on [Music]

22:11 how big the distance can be with a certain combination of message length and block length so here we have two to the four different valid code words because that's the number of messages we have four bits for the message to the four different combinations and we create seven bit code words okay any of these seven bit errors uh is corrected towards the valid code word uh if we change any of the seven bits then our checking bits indicate which one was flipped and we can reverse that flip okay what that means for a single code word is that it covers it uh it is reached by eight different seven bit strings when i transmit when i when i receive seven arbitrary bits um there are always eight combinations of seven bit strings that map to each code word namely one where the code word itself is sent and seven combinations of changing a single bit okay now if you multiply these two things we have so many code words and each covers so many 7-bit strings you obtain exactly all 7-bit strings so hamming codes entirely cover the 7-bit strings it never happens that you receive a code and you think you don't know what to do with it whenever you receive a 7-bit string

23:41 you will correct either one bit error one a flip bit or you will declare there is no error okay that means we can always correct a single bit error that's great the distance works out to be 3 [Music]

24:00 and we can briefly think about what happens to two-bit errors uh we can definitely not correct them that's what the the lower bound the theory already tells us but maybe we can detect two-bit errors the problem here is um so if if two bits are flipped we definitely notice that something has happened because the checking bits cannot be all zero if we flipped two bits but uh the decoder will eagerly mistake this two-bit error as a one-bit error from a different code word and correct that one bit error taking us actually further away from the original message so in in this case uh hamming codes fall short of achieving everything that the theory predicts might be possible they can always correct one bit errors but they cannot detect two-bit errors they can only detect and correct one bit errors that's obvious but if two bits are flipped you correct that in the in another direction there is a small variation if you add another extra bit another parity bit for the entire block you can actually detect all two-bit errors but then you also use one extra bit so in a sense you you don't get both with hamming codes you don't get the exact coverage of the the 7-bit strings of of the entire

25:34 space of possible bit strings and the best possible detection so that's just a minor remark we will our ford plus three hamming code this will be the variant that we discussed in detail encoding and decoding uh and this this addition might be called four plus four or four plus three plus one i don't know uh this is only um for your interest but um it will not play a further role in this in this class

26:09 general recipe

26:10 now we've seen this example of the four plus three humming code you can generalize the same recipe to larger messages or larger blocks and the general recipe is as follows it only ever works if your desired block length is a power of two minus one in our case we had l equals three which works out to n equals 7 that's 8-1

26:43 and you can generalize this code to other powers so you can choose l that's a parameter for you to pick you use the l bits as parity as parity check um well as parity bits as part of the making the checking constraints zero and you use exactly those that are at a power of two because then their binary representation is only a single uh a single one and so you can define them based on the other bits and the other bits well that's n minus l in the general case all that you didn't take and and that's that's pretty much it so uh i mean the you you generalize the the checking and parity bit formulas from what i've shown um basically uh you take this binary representation of every index in your in your block and uh for every position in the binary representation you have one checking bit so just to make this very clear let's go back to this again this picture here if we have seven bits in total i can represent all those numbers with three bits in binary or three digits in binary and that means i have three checking constraints three checking bits and the the last one takes the last bit in the binary representation whenever that is a

28:20 one i include that bit into my constraint and notice that these are all the odd numbers because the odd numbers have a one in the binary representation at the last position then i have the next position is whenever the second bit is a one and that happens to be those four numbers and finally the last one for the the most significant digit is the the upper half of the code and you can generalize this if you have 15 bits instead of seven you have a fourth position in the front so you would use a fourth constraint for the for the new most significant digit

29:05 example

29:08 that's that's how you generalize this and now uh we have the parameters n and l to play with and here's here's my example from before if we want this 11 overheads what we can do is choose l equals 7. then we can encode 64 bits that's one word of memory in our usual architectures eight bytes so you can encode that as one block together and every uh any single bit error in in one word of memory is then correctable now uh you might notice that 2 to the 7 minus 7 to the 7 minus 1 minus 7 doesn't quite work out to 64. in fact we waste a lot of bits here because 64 is just about too big for choosing l equals six we could actually use the same hamming code could use 120 data bits but we can just leave some of them unused and pretend they're all zero but the important point is we use seven seven checking bits seven parity bits on top of the data so uh seven out of 64 hopefully works out to be roughly 11 okay and uh if you want if you want less space overhead you just make your l bigger um and then the space overhead becomes smaller

30:37 so in summary hamming codes are quite simple they're also very efficient to realize both in hardware or software and the overhead they they introduce is is really really low especially if you make the block size a little bit bigger than the 7-bit example we've seen

30:59 perfect codes

31:03 also hamming codes are in a certain way best possible and well in the coding theory uh literature this these are called perfect codes because they uh of this property that they cover exactly the entire space and they have not just um the maximal distance between code words is the minimal distance between code words if is three it also uh it's also basically true that uh code words there's there's no this there's no gap left uh not all code words have difference three but uh you basically have all possible code words covering the space perfectly it's probably the best way to say it and this is this is the the general pattern right this is uh this is your

32:00 message length and this is the number of of parity bits if we want this we cannot so because because these hamming codes are perfect it's not possible to go with fewer bits you won't be able to use fewer bits for this scenario

32:21 if so you cannot improve on hamming codes if the message length is like this the the formula from here and uh well we've seen the example for four in detail we've used the example with 120 bits where we just used 64 of it in the previous example with the 11 bit overhead you can take all these other numbers um uh that's that's message lengths um and we want to correct one bit errors only if if these two things are what you want then hemming codes are the perfect solution and there's no no possibility to improve upon those but um this is a this is a big but if either of these conditions is not exactly describing your situation the situation is not so clear for example suppose we want to protect these 64 bits and not 120 against one bit errors maybe there's a much smarter code than the hamming code that does it with with um just six parity checks um that might be possible because the for these message lengths it doesn't nicely cover the space um the hamming code doesn't nicely cover the space it overlaps and so that is a bit wasteful and in fact this is a fairly open research area designing good error correcting codes is still a challenge that's ongoing and there's

33:54 some interesting theory behind this that i don't want to go into but i want to just mention the the main result the gist of it information theory the same the same thing we used with entropy in the compression chapter there's a corresponding theory for error correcting codes and communication over over noisy channels and the theory basically tells you if you design a code by randomly choosing code words so you take all possible say 64-bit strings and you choose a subset of those as code words and come up with some way of encoding and decoding if you do this randomly it almost always works out to have very good properties in the sense that your your distance will be good and you can use this as an efficient code um filling the gaps that are left by hamming codes when the parameters don't work out so nicely but there's a big problem with these random codes they both basically need a full lookup table to encode and decode for hamming codes we have this nice little trick that you compute a few parity checks and then the checking bits tell you exactly where the bit flip was you just reverse that and you're done that was for decoding that was very very quick and easy these general random codes don't have

35:28 that and it's not known uh how to construct in general codes that both have good cor good distance properties and are efficient to decode so this is where still a lot of ingenuity and tricks are used and there's there's still a bit gap between the codes that we uh can use in practice because they're fast enough to use in practice and the theoretical possibility it's a large gap in that the currently used practical methods are not as good as they might be the theory predicts there are better codes out there but they still have to be found

36:12 with that little outlook i want to conclude this unit 8 on error correcting codes we've seen a few lower bounds a little glimpse of the theory behind this and we've seen the hamming codes a very nice little example where everything works out nicely they're clean they're efficient but unfortunately they only work for a small subset of that of the bigger task where you want to have a code that works with a given message length a bit a given guarantee of of how many bits you want to correct and that is still an unsolved open problem