The Art of Error Detection and Correction using Hamming Codes

One of the most fascinating topics in computer science is error detection and correction, particularly when it comes to digital communication systems. In this article, we will explore the concept of Hamming codes, a method developed by Richard Hamming that allows us to detect and correct errors in digital messages.

The Basics of Hamming Codes

---------------------------

Hamming codes are a type of linear code that is designed to detect single-bit errors that occur during transmission. The code works by adding redundancy bits to the original message, which enables the receiver to detect and correct errors that affect only one bit. This is done using mathematical operations such as bitwise XOR (exclusive OR) and addition.

The Process of Encoding

------------------------

To encode a message using Hamming codes, we first need to identify the parity bits that will be added to the original message. The parity bits are calculated based on the powers of two, which serve as a check on the encoded list. For example, if we want to add parity bits to the list 1-2-3-4-5, we would calculate the parity bits using bitwise XOR and addition.

For instance, let's consider the message "01010101". We need to identify the positions of the parity bits. According to Hamming codes, bits three and five must be even, which means that their sum must be zero or even. Since three is 1+2=3 and five is 4+1=5, we know that both bits are odd. However, this creates a problem because the rules of parity specify that all bits in an even position should have an even sum. Therefore, to make it work, we must change bit one from zero to one.

This process may seem complex, but with practice and experience, you'll become proficient in identifying the positions of parity bits and applying the necessary operations.

Detecting Errors

----------------

Once we've encoded the message using Hamming codes, we need to check for errors. The receiver can do this by performing a series of checks on the encoded list, including checking the parity bits. If any bit fails a parity test, the system will recognize that an error has occurred and take corrective action.

In the case of the original message "01010101", let's assume it was received as "11111111". The receiver would then perform a check on each bit in the list to determine if an error had occurred. When they get to bits two, three, and five, they realize that these bits don't match their expected values.

Here's what happens when we receive "11111111" instead of "01010101":

* Bit 2 checks out because it is equal to the expected value.

* The parity bit at position 3 fails because its sum with bit 4 (and bit 5) doesn't meet parity requirements, meaning that parity at this point was odd and should be even. So, bit three is wrong.

* Bit 4 checks out on itself and with bit five.

The list two has passed the test because all values there are equal to expected ones but now the list four fails because one of the sums is odd while it should be even. This tells us that a parity bit was flipped from zero (1) to one, which means we've got an error in our received transmission at position 4.

Correcting Errors

-----------------

Now that we know where the error occurred, we can correct it by flipping the wrong bit back to its original value. In this case, we would flip bit four back to zero.

Here's what happens when we correct the error:

* The parity bits are recalculated based on the corrected list.

* The new list 1-2-3-4-5 is checked for even and odd sums in all positions (except the positions with incorrect values).

* If a position fails its parity check, we know that an error still exists.

By applying this process of detection and correction, Hamming codes can accurately transmit digital messages while maintaining data integrity.

"WEBVTTKind: captionsLanguage: enwhat we're searching for today is very simple it's the answer to how do we decode the uh wonderful code that we created just about what a week ago now something like that let's just remind ourselves where we were with this code it was a five bit code coding theorists will talk about this code which I'm going to write out as being a 523 code I'll fill in the details and then I'll refer what I've written down to this remember also that these are the exact powers of two that's 2^ SAR the number two position is 2 to the^ one the number one position well that's two to the^ Z but that leaves bit three and bit five for the actual message bits two bits bit three bit five two bits four combinations possible and those were the four San Francisco go weather States so I've sometimes refer to these as info bits message bits it comes to the same thing that's the message you're trying to get across that's the message that these parity bits are there to check out and make sure it's okay and we ended up with one code word if you remember that's the in phrase for these things the zero zero state in message terms I think we said was foggy this time around and here's the protection of the parity bits there we are all written out again now coding theorists would call this a 523 code how does that work well it's a five bit code that's what the first number means it means total number of bits the two means the number of message or information bits and this if you remember is this business called the distance how many bits differ between these rows so the distance in this technical usage of the term here the number of bits that differ between that line and that line is three and to get one of these codes working you need a minimum distance of three and what do we mean by working what we mean is that a distance three code can correct a one bit error and for those of you just yelling at me but what's the general formula then for what you can correct for a given distance in that watch carefully it's a one lineer more or less FLW of D -1 / 2 and remember Flor of means round down so let's do it for distance three 3 - 1 2 2 / two one round down one it's already rounded down so that's telling you using the Flor of function it's saying for distance three you can detect and correct one error so bearing that in mind if we see things in future with different distance properties at the end we can always apply this to find out how many things they could correct the powers of two and the parity check bits what sequence of numbers were they used in checking up on this first block the one bit checks it self and three and five two bit checks itself and three and the four bit checks four and five where do those come from how do you get those lists and uh I think last time perhaps didn't make this quite crystal clear so let me explain that those come from effectively saying for all of the things that aren't powers of two how could you build them up from adding together powers of two one you don't have to build it up that's itself one is one similarly two is a power of two and it's just itself where you really have to start doing this powers of two add them together to build them up thing is with three the most compact way to represent three as sums of pow of 2 is 1 + 2 what about four no problem four is itself it's a power of two but then when you get to five you say ah the most compact way to do this is 1 + 4 pow of two six 2 + 4 seven quite complicated now but if you think about it sum of powers of two that add up to seven in the most compact way you can do it 1 plus 2 plus 4 so really these lists that we had previously about what checks for what is as a result of writing these out first and then say but if we were going backwards where does the digit one appear it appears in itself it appears in the formula for three it appears in the formula for five it appears in the formula for seven so that's where that first list came out here that one checks up on one 3 5 7 9 11 all the odd numbers because one would appear in the sums of powers of two that build those up two yes two appears obviously in its own list but it appears first of all next door in three has been 1 plus two does it appear in four no four is all on its own it's power of two what about five would two appear in five no it's 1 + 4 so the next place that two would appear is six which is 2 + 4 so I hope if you so if you had a six-bit code with two have to check on on one extra bit yes it would similarly four checks on four it checks on five it also checks on six because 6 is 2 + 4 so if you're building up these lists for making them longer to do more complex codes then if you're encoding and decoding in this by hand method you need to keep up to date your sums of powers of two for all the new positions unless they're exact powers of two and then go backwards and say ah but these are my checklists that I build up from that so just to remind you then of what happened was that on this one here let's take the second one the information or message bits are zero and one but it tells us here that's bit three and bit five but it says here that bits one three and five taken together must be even well three and five notal one add them together that's one so therefore bit one which we will be filling in has to be one make it even we're going to say because you all want to know how to decode it and detect errors and correct them this one here is going to be badly transmitted instead of 1 0 0 one one it is received as one one one one so straight away whoever gets that is going to say that isn't right they're going to say that that isn't right because there's so few of these there's only four of them you get to know them like old friends but you imagine if you got 64 of the SOS can you guarantee that you'll be able to memorize every single one uh no you need an algorithm and what we do here is a reverse of what we did when we encoded we say let's look at the list that follows on and is checked from one one three five and so on that's what we received but one is one bit three is one one and one is zero bit five is one zero and one is one it's supposed to be even parity wrong it came out as odd parity bit two checks out on itself and on bit three it doesn't occur in bit five because five is 1+ 4 not 2+ 4 so you look at bits two and bits three zero exclusive or or added if you like to one it's a one it's odd parity it's wrong okay now you look at the four bit and you say bit four checks out four and five four and five one and one it's zero hooray it passed the test yeah we failed two tests we can work out from that now yes you can very simply because the headers of these lists are the powers of two that they check up on in all of those lists and if the two one has gone wrong and the one one has gone wrong then the wrong bit was 1 + two ordinary addition this time not binary addition one and two makes three bit three is wrong so then we flip bit three and we've got the right fli bit three 1 Z one one one that's the bad bit it's received as a one it's wrong so it must have been a zero 1 0 0 one one magic does that look familiar that's what you correct it back to and it's entirely done by getting these lists of powers of two doing another check on them almost like it's exactly the same as when you were encoding it's just you're doing this again say that's wrong you know do add up so so you simply reversed the process I mean does that always work then yes for for any of those bits for the ah now that's a good thing if you if you're thinking oh but that's a message bit oh no come on uh something really went wrong there because what was transmitted to 01 that's Sunny wasn't it has turned out as um rainy one one wasn't it you you turn to rainy oh yeah that's fine but what about if he hits a parody bit surely that messes everything up no it doesn't it's actually dead easy and I want to leave as an exercise for you to do is this time one 011 don't hit a message bit hit that parity bit at position four change it to zero do the checks and you'll find out that the one list passes with flying colors nothing wrong with it the two list passes with flying colors the only one that fails is the four list so if it's the only one that fails that's it four is four nothing to add to it you've done the homework for them I've done the homework but yeah so do it for yourself on any bit you like and convince yourself that it doesn't matter if it's message bit or parity bit this method will come in on it I have built this up and I've explained to you now you can go into a Pub full of coding theorists and say hey like I've got this 523 code and they will say well you realize that you derived it using Richard hamming's algorithm but it's not a true proper Hamming code because it's not perfect and you say perfect what's perfect I think we have to go to another video Sean and I know they hate cliff but yes real Hamming codes are perfect they really are now the only sort of if you like slide health warning to say about this just to round this off now is by all means do it by hand if you want to code it up as a program great you'll learn a lot but don't run away with the idea that this is the most efficient way to do itwhat we're searching for today is very simple it's the answer to how do we decode the uh wonderful code that we created just about what a week ago now something like that let's just remind ourselves where we were with this code it was a five bit code coding theorists will talk about this code which I'm going to write out as being a 523 code I'll fill in the details and then I'll refer what I've written down to this remember also that these are the exact powers of two that's 2^ SAR the number two position is 2 to the^ one the number one position well that's two to the^ Z but that leaves bit three and bit five for the actual message bits two bits bit three bit five two bits four combinations possible and those were the four San Francisco go weather States so I've sometimes refer to these as info bits message bits it comes to the same thing that's the message you're trying to get across that's the message that these parity bits are there to check out and make sure it's okay and we ended up with one code word if you remember that's the in phrase for these things the zero zero state in message terms I think we said was foggy this time around and here's the protection of the parity bits there we are all written out again now coding theorists would call this a 523 code how does that work well it's a five bit code that's what the first number means it means total number of bits the two means the number of message or information bits and this if you remember is this business called the distance how many bits differ between these rows so the distance in this technical usage of the term here the number of bits that differ between that line and that line is three and to get one of these codes working you need a minimum distance of three and what do we mean by working what we mean is that a distance three code can correct a one bit error and for those of you just yelling at me but what's the general formula then for what you can correct for a given distance in that watch carefully it's a one lineer more or less FLW of D -1 / 2 and remember Flor of means round down so let's do it for distance three 3 - 1 2 2 / two one round down one it's already rounded down so that's telling you using the Flor of function it's saying for distance three you can detect and correct one error so bearing that in mind if we see things in future with different distance properties at the end we can always apply this to find out how many things they could correct the powers of two and the parity check bits what sequence of numbers were they used in checking up on this first block the one bit checks it self and three and five two bit checks itself and three and the four bit checks four and five where do those come from how do you get those lists and uh I think last time perhaps didn't make this quite crystal clear so let me explain that those come from effectively saying for all of the things that aren't powers of two how could you build them up from adding together powers of two one you don't have to build it up that's itself one is one similarly two is a power of two and it's just itself where you really have to start doing this powers of two add them together to build them up thing is with three the most compact way to represent three as sums of pow of 2 is 1 + 2 what about four no problem four is itself it's a power of two but then when you get to five you say ah the most compact way to do this is 1 + 4 pow of two six 2 + 4 seven quite complicated now but if you think about it sum of powers of two that add up to seven in the most compact way you can do it 1 plus 2 plus 4 so really these lists that we had previously about what checks for what is as a result of writing these out first and then say but if we were going backwards where does the digit one appear it appears in itself it appears in the formula for three it appears in the formula for five it appears in the formula for seven so that's where that first list came out here that one checks up on one 3 5 7 9 11 all the odd numbers because one would appear in the sums of powers of two that build those up two yes two appears obviously in its own list but it appears first of all next door in three has been 1 plus two does it appear in four no four is all on its own it's power of two what about five would two appear in five no it's 1 + 4 so the next place that two would appear is six which is 2 + 4 so I hope if you so if you had a six-bit code with two have to check on on one extra bit yes it would similarly four checks on four it checks on five it also checks on six because 6 is 2 + 4 so if you're building up these lists for making them longer to do more complex codes then if you're encoding and decoding in this by hand method you need to keep up to date your sums of powers of two for all the new positions unless they're exact powers of two and then go backwards and say ah but these are my checklists that I build up from that so just to remind you then of what happened was that on this one here let's take the second one the information or message bits are zero and one but it tells us here that's bit three and bit five but it says here that bits one three and five taken together must be even well three and five notal one add them together that's one so therefore bit one which we will be filling in has to be one make it even we're going to say because you all want to know how to decode it and detect errors and correct them this one here is going to be badly transmitted instead of 1 0 0 one one it is received as one one one one so straight away whoever gets that is going to say that isn't right they're going to say that that isn't right because there's so few of these there's only four of them you get to know them like old friends but you imagine if you got 64 of the SOS can you guarantee that you'll be able to memorize every single one uh no you need an algorithm and what we do here is a reverse of what we did when we encoded we say let's look at the list that follows on and is checked from one one three five and so on that's what we received but one is one bit three is one one and one is zero bit five is one zero and one is one it's supposed to be even parity wrong it came out as odd parity bit two checks out on itself and on bit three it doesn't occur in bit five because five is 1+ 4 not 2+ 4 so you look at bits two and bits three zero exclusive or or added if you like to one it's a one it's odd parity it's wrong okay now you look at the four bit and you say bit four checks out four and five four and five one and one it's zero hooray it passed the test yeah we failed two tests we can work out from that now yes you can very simply because the headers of these lists are the powers of two that they check up on in all of those lists and if the two one has gone wrong and the one one has gone wrong then the wrong bit was 1 + two ordinary addition this time not binary addition one and two makes three bit three is wrong so then we flip bit three and we've got the right fli bit three 1 Z one one one that's the bad bit it's received as a one it's wrong so it must have been a zero 1 0 0 one one magic does that look familiar that's what you correct it back to and it's entirely done by getting these lists of powers of two doing another check on them almost like it's exactly the same as when you were encoding it's just you're doing this again say that's wrong you know do add up so so you simply reversed the process I mean does that always work then yes for for any of those bits for the ah now that's a good thing if you if you're thinking oh but that's a message bit oh no come on uh something really went wrong there because what was transmitted to 01 that's Sunny wasn't it has turned out as um rainy one one wasn't it you you turn to rainy oh yeah that's fine but what about if he hits a parody bit surely that messes everything up no it doesn't it's actually dead easy and I want to leave as an exercise for you to do is this time one 011 don't hit a message bit hit that parity bit at position four change it to zero do the checks and you'll find out that the one list passes with flying colors nothing wrong with it the two list passes with flying colors the only one that fails is the four list so if it's the only one that fails that's it four is four nothing to add to it you've done the homework for them I've done the homework but yeah so do it for yourself on any bit you like and convince yourself that it doesn't matter if it's message bit or parity bit this method will come in on it I have built this up and I've explained to you now you can go into a Pub full of coding theorists and say hey like I've got this 523 code and they will say well you realize that you derived it using Richard hamming's algorithm but it's not a true proper Hamming code because it's not perfect and you say perfect what's perfect I think we have to go to another video Sean and I know they hate cliff but yes real Hamming codes are perfect they really are now the only sort of if you like slide health warning to say about this just to round this off now is by all means do it by hand if you want to code it up as a program great you'll learn a lot but don't run away with the idea that this is the most efficient way to do it\n"