Video 8-3: §8.3 Hamming codes introduction

0:00 Intro

0:03 after we've talked about lower bounds for error correcting codes i now want to talk about upper bounds and in this section we'll specifically talk about hamming codes the most well-known classic error correcting codes which which are practically usable useful and also just a beautiful piece of theory

0:25 Parity bits

0:29 but before we go to hemming codes we do the simplest possible thing that probably some of you have also thought about and that's adding a parity bit so we have our message of bits uh in this case it's nine bits and we add one more bit and that parity bit indicates whether in the nine previous bits the number of ones is odd or even in particular if the number of ones is odd then the parity bit is one it's the parity of the number of ones and otherwise it's it's zero you can also write this as xoring the the bits together which is another way of saying you add them up modulo 2. uh all turns out to be the same thing you could also say the parity bit is the bit that you have to add to a bit string so that the number of ones becomes even all the same thing all comes down to a very simple same simple idea

1:38 the distance of such a code is 2 because um well it's at most two because you only add one bit to any to an arbitrary bit pattern and it's actually uh exactly two because you only take the uh parity to the the even parity bit strings and if you flip a single bit you always change the parity okay

2:03 so the distance is 2 that implies it can detect any single bit error that comes from already from our result from before and that's pretty much all it can do because distance two is not enough for correcting any errors we cannot hope to get that but parity bits are ubiquitous in many applications especially because they're so simple they're built into hardware devices on many different levels

2:32 and it turns out they're also a building block for more sophisticated codes so they're very simple and cheap to do that just add a single parity bit and that also but well we cannot detect any errors but also that answers your question from before

2:57 so if i were to ask this question again now you would probably give a different answer and uh well maybe maybe this is too boring do we do we want to do it okay fine

3:16 okay okay i'm reaching the limit here so uh the round the right answer uh is one bit is enough if you just want to detect a single bit error you can do it with one extra bit uh that's all that's needed

3:32 Error correcting

3:36 now let's try to get error correcting codes and i want to mention a typical application of this and that's uh ram the working memory of a of a heavy-duty server where any downtime costs you a lot of money and uh if well you can you can read about this this background story here in short random bit flips in ram happen and they happen fairly frequently you will probably get one

4:07 one bit flipped in your laptop every couple of weeks and often nothing happens and that's due to many different reasons but you can read about some some guy tracking down exactly that it can only be a twisted bit in main memory that caused a crash on his on his laptop it's very interesting it's something we we tend to ignore most of the time memory is perfect in our in our mental models but it's actually not and these things are not so rare uh as they might occur the question becomes can we somehow correct a single bit without knowing where it occurred and whether it occurred and so this seems a bit of a of a fundamental question is there a way we can do this at all right and the answer is is definitely yes and it's actually very simple you can just store every bit three times if there's only a single bit flipped the two other ones will still indicate the right result so when you read you just do a majority vote of the three bits and you do whatever two or three say if you're only flipping one bit that will that will always uh be correct uh now the the problem with that is uh let me show this comment

5:33 if you have a manager who has to pay for this and you asking to triple the amount of memory you put into your server instead of giving it uh well whatever you can triple instead of giving it 16 gigabyte you have to pay three times the price of that he will probably sack you and uh the result that i'll show you in this section is you can actually do this with just 11 of overhead so you don't triple the cost you add 11 and that for um a better guarantee against potential downtime which can be costly on a very different scale that sounds like a very good compromise and a very good deal so this is what your boss will will like and that's why that's why you should learn about hamming codes