What is error correction? Hamming codes in hardware

perhaps you've heard of error correcting memory or error correction in communications well in this video i'm going to show you how that works i'm going to walk through building a circuit that allows us to encode a message as a series of bits and and have that message encoded in such a way that if one of those bits gets flipped and here i can we can flip a bit off or flip a bit on but the message is encoded in such a way that even if we do that even if we flip one bit we're still able to decode the message back to whatever the original is by by correcting the error that we've introduced and i'll explain how that works but if you want a more thorough and truly beautiful explanation of the math behind this my friend grant over at the channel three blue one brown made a video walking through that that you should really check out well to get a sense of how error correction is even possible at all you can think of the absolute most simple case which is error correction of a single bit we could just store a copy of the bit and that would let us detect errors because if we store a zero zero but read one zero well then we know there was an error here if we store one one and read one zero we also know there was an error but either way we're reading one zero and we don't know from that what the original bit was supposed to be whether it was a zero or a one so if we want to be able to automatically correct the error and not just detect it well we could store a second copy of the bit and that way you know if we read one zero zero we would know okay well if we take kind of two out of three here you know if we're assuming that errors are rare enough that we probably only ever have one at a time then you know reading something like one zero zero probably means the original bit was supposed to be a zero and if we read something like one zero one well then same thing sort of two out of three we figure well it's probably uh probably supposed to be a one so that's a really basic error correction but it's not at all efficient to store three copies of every bit so can we can we do better well it turns out we can do a lot better but we have to think about these extra bits not as copies of the original bit but as parity checks for it so what is a parity check well i've got some other videos on parity checks but basically if you have a bunch of binary data you can add a bit that will ensure that the data has an even number of ones so here we've got one two three four ones here so in this case it already has an even number of ones so we could add a parity bit of zero but if it had an odd number of ones we could add a one there to the end so that in total all of this has an even number of ones that lets us detect an error because if any single bit changes then it won't have an even number of ones anymore and we'll know that there was an error so this is obviously very efficient in terms of detecting a single bit error because you could have as many bits as we'd like and only a single parity bit to protect them all and that will detect or detect i guess any single bit error but it won't let us correct it so another way to think about this scheme where we're storing three copies of the bit is to actually think of storing two parity checks for the bit because that's actually going to let us extend it to two more bits but in this case it looks the same right because with a one bit message plus a parity bit you either have uh no ones in this case um so or you have two ones in this case and those are those are really the only two options with two bits to have an even number of ones and then of course the the second parity bit here is just a second check so the nice thing about thinking about these as parity bits is it lets us extend this a little bit so what i'm showing here is we've got you know our data bit and we have our two parity bits and i'm just showing here uh what the different groups are that we're using to compute the parity bits so we're saying that the data bit 1 and parity bit 1 are used in a combination and we need to have an even parity between those two so either they're both zeros or they're both ones and then same thing between the data bit and parity two they're either both zeros they're both ones but we can extend this by adding another parity bit and that lets us add another data bit but the neat thing here is we don't actually need to add two more parity bits to get another data bit we only need to add one because we can reuse that first parity bit so now what parity bit 1 is is doing is parity bit 1 is saying that we have an even parity between data 2 data 1 and parity one so between these three bits we're going to have an even number of ones and we'll just set parity one to be whatever it needs to be in order for that to be true and then if any one of these bits gets corrupted we can perform these three different parity checks and actually figure out which bit it is because depending on which parity checks either pass or fail that will uniquely identify one of these bits for example if the first parity check between these three bits fails but the other two pass well then we know assuming that only one bit was corrupted we know that it must be parity bit one because if it was one of these other two you know data two or data one then well one of these other parity checks would have also failed same thing if only the parity two check fails that would tell us that you know the parity two bit maybe got corrupted but all the other bits are fine but if this first data bit uh gets corrupted then both the the first parity check of these three bits and the second parity check of these two bits the both of those parity checks will fail and if both of those parity checks fail then that tells us well it must be this data bit that got flipped and we can kind of keep doing that right so databit 2 it would be the first and third parity checks that would fail and the second one would would be fine but there's actually even more combinations in here and so we can add a third data bit that is protected by the second and third parity bits and we just kind of get that for free because that's another unique combination and in fact there's one more which is we could have another data bit that's a part of all three parity groups and still if any single bit gets flipped then a unique combination of these three parity bits will be will be wrong and based on what combination that is then we would know exactly which bit got corrupted and so this technique of being able to have four data bits and add just three bits of parity to it and encode that you know in such a way that we're able to detect any single bit flip and not only detect that the bit flip happened but actually know exactly which bit was flipped and and of course because a bit can only be two values either one or zero we know how to flip it back so we can actually correct the error well this scheme is called hamming 74 is developed by richard hamming in the 1940s actually and it's called seven four because it's seven bits and we're able to encode with that four actual bits of data but this scheme i mean you can extend it as much as you want if we add a fourth parity bit we can actually add seven more data bits and we'd still have unique combinations of parity bits for all of those and so it becomes even more and more efficient as it scales up now of course there's a trade-off because it can only detect a single bit error so if you have a really big block that you're trying to protect with this you know the likelihood of having more than one bit error if you have more bits is going to be higher so there's a trade-off there but nevertheless it's a pretty cool way of being able to detect errors and certainly way better than having to store every bit three times okay so how do we actually do this in hardware well the nice thing about this scheme is that because it uses parity bits we the hardware is actually pretty straightforward because you can compute a parity bit basically just using xor gates and that's because if you look at the truth table for an xor you can see that you know whatever inputs you get the output gives you something so that you know the inputs and outputs together always give you an even number of ones and that's actually true no matter how many inputs you have and the other nice thing is if you have multiple inputs like this you can chain xor gates together to sort of get more inputs if you only have a two input xor gate so this here with these two xor gates we've got these three inputs coming in and that's going to exor together these three signals data four data two and data one right which data four data two data one is uh makes up a parity group with the parity bit one over here and so this generates that parity 1 based on whatever you know data 4 data 2 and data 1 happen to be coming in over here and we're basically just doing the same thing with xor gates to generate parity 2 based on data 1 data 3 and 4 and then parity bit 3 is based on data 2 3 and 4. and that's really it to create this circuit so that whatever data is coming in here it'll generate the appropriate parity bits so that we're guaranteed to have even parity across these four bits across these four bits and across these last four bits so let's go ahead and build this circuit and see how it works okay so we're going to need a bunch of exor gates and for that we can use the 74ls 86 which is just a chip that has four xor gates on it just configured like that so i'll use a couple of these chips since we'll need a bunch of xor gates and then for the inputs i'll just hook up some dip switches so we can set whatever input we want i'll have one side of the dip switches tied high through these 1k resistors and then the other side of each switch i'll just tie directly to ground that way on this side we'll have 5 volts through the resistor but then when we turn the switch on which is actually pushing it down then it'll connect it through to the ground and bring this top side here to 0 volts so we'll either be at 5 volts if the switch is up or 0 volts if it's down and so that's how we can set our four bits now i just need to wire this up just like this so i'll take uh the first couple xor gates and well i guess the first xor gate will be this one so i'll tie it to uh d1 and d2 which will just be uh switch one and switch two here and actually before i forget let me hook up the power and ground to each of these chips as well so they're powered those are two two inputs of an xor gate and then the output of that will go into the input of another xor gate there's the output going around to another input and then the second input of that goes to d4 and so that's these first two xor gates hooked up we've got uh d1 d2 and d4 all xored together to get us that first parity bit so you can see d1 d2 and d4 are hooked together and that first paradiddle bit will be on the output of this xor gate right here so now i'll go ahead and hook up the other xor gates to be able to generate the other two parity bits so parity bit 2 is going to be hooked up to d1 d3 and d4 and parity bit 3 is hooked up to d2 d3 and d4 okay and that's it so we've actually got all of these xor gates hooked up and we've got our inputs over here on the switches so somewhere in here we've got uh our four uh four data inputs as well as our three parity bits are kind of in a couple different places here coming off these chips so now what i'll do is hook up uh some leds so we can actually see what all seven of these bits look like a little bit easier so this will be the four data bits as well as the three period bits in in the same configuration here so we can easily see what's going on so first i'll get the four data leds hooked up so the green leds are data and those are those are hooked up through to those dip switches so this should just show us exactly what we're inputting on the dip switch and then i'll hook up the three parity bits to the outputs of the those final three xor gates okay so now we've got this entire circuit hooked up and we've got the leds over here so we can actually see what the outputs are so now i'll hook up five volts power this up so we can start to play around with it and kind of get a sense for how it works so if we start setting these dip switches you'll see you know as i flip these dip switches around the output changes and of course the the green leds the four green leds just match up directly with the four dip switches so whatever i set these dip switches to you'll see i've got one one zero one over here i've got one one zero one if we just look at the green leds but then the red leds will just sort of change around to match whatever they need to to have the correct parity for these different parity groups like we talked about so just to get a sense of how that works you know if we look at the first parity bit over here on the right this parity bit is covering um these four bits if we look at every other bit so if we look at you know d4 d2 d1 and then the parity bit we see we have zero zero one and then the parity bit is a one and remember the goal is that the parity bit should should be either on or off to ensure that there's an even number of ones within that group so we we we have zero zero so we have a one uh we have one one here so we need another one in order to have two ones in that group uh so that two is an even number and we have the even parity so that's why that parity bit is on to ensure that that's true now if we look at parity two that covers these two bits and these two bits and so we look here between these two bits we've got one that's on and then if we add in this bit we've got a second one that's on so the parity doesn't need to be on in order to ensure an even number of ones and even number of bits that are on within that group so that parity bit's off and then parity bit 3 covers just these last 4 over here on the left and so we have 0 1 0 and so because we have one led on there we need to turn on the second one in order to ensure that there's an even number of ones within within that group and because of the way we've wired up these xor gates you know as we as we switch these on and off and you know adjust our inputs the output's going to change automatically to to ensure that this is always true and what this does for us is that if we have some sort of bit error so let's say like this this bit here is supposed to be a one it's on right now but let's say there's some kind of error uh we in our storage or transmission or whatever we're doing with the this data where that bit you know it's a little bit flaky and maybe maybe it's actually accidentally off you know there's some there's some kind of bit error that that has happened and so that bit is off well we can still uh with this information alone recover the original message which is one zero one zero and the way we do that is we just check each of the parity bits so parity bit 1 here on the right covers every other bit so if we look at every other bit we've got a 1 0 0 0. okay so that right there is suspicious because within that group we should have an even number of ones so we should either have zero ones or we should have two ones or four ones but we shouldn't have one one right and so there's a problem so we have one zero zero zero so we only have one one within that group so parity bit one seems to be wrong but let's keep going so parity bit 2 is on but let's see if it's supposed to be so with parity group parity bit 2 we're looking at these two bits as well as these two bits that actually looks right because we've got a 1 0 0 1 and so we've actually got two ones within within that group so parity bit two should be on and so that seems fine but now let's look at parity bit three so parity bit three is these last four bits so we have one zero zero zero well that's wrong because we only have a single one within that group that's in a single one is not a an even number because one is odd so so that parity bit three is is wrong so we've concluded that parity bit one is wrong and parity bit uh three is wrong the only case that's covered by parity bit 1 and 3 being wrong plus parity bit 2 being right is this case here so if both of those are wrong the parity 2 is right then we can conclude that d2 this bit right here is is wrong that's the that's the culprit so if we look at that bit we know that that's wrong well if we look at it we can see that it's a zero so if we know that it's wrong and we see that it's a zero then we can correct it by just flipping it to a one and so if we assume that okay this really should be a one then our true data is one zero one zero and that in fact of course is right one zero one zero so that's how this hamming code error correction works but of course the next question is okay we went through this whole process by hand to figure out that there was an error and then which bit it was and then of course you know to flip it but how can we do that in hardware as well but actually before we get into decoding this first we actually need a way to easily insert some errors here without just sort of like unplugging things so i have this other circuit here that i that i built ahead of time and it's actually you know pretty straightforward so let me just explain what it does i've got seven inputs coming in over here and those inputs go into xor gates each one going into one side of an xor gate and then the other side of that same xor gate i've got seven switches here that i can toggle and the way that an xor gate works if you look at it is if if one input is off so let's just look at the top half here where a the a input both of those are zero well you can see the output just follows whatever the b input is but if we toggle that first input on then you can see the output is the opposite of whatever b is and so that's basically what i'm doing here is i've got an xor gate where the a input you can think of is these dip switches and so if they're all off then the outputs of the xor gate is going to be whatever the input is so i've got seven inputs here i've got seven outputs the outputs are gonna be the same as the input but if i toggle one of these then it will flip that particular bit and if the bit was supposed to be a zero it'll flip it to a one if it was supposed to be a one it'll flip it to a zero so this lets me pretty easily just flip bits so i'll hook up the seven inputs of this to the outputs of the hamming encoder that we just made so there we go and then also just connect the power here power and ground through except i'll hook it up the right way around and there we go so what we should see is we should see this be the exact same so whatever we've got here in the top we should see here except that i can flip a bit so if i want to flip let's say this first data bit here or bit three just flip it and that'll turn it on if i want to flip the second bit i can flip it off just by flipping the switch here so this circuit just lets me introduce whatever error i want so we can test out the error correction that we're about to build and the way the error correction is going to work is we want to be able to basically compute each of these parity bits and see which of them are wrong because it was by checking each of the three parity bits that we were able to determine um you know based on the combination of which parity bits are are wrong if any of them are it was from that combination that were able to determine which bit was was off but we need to first compute those parity bits and figure out if any of them are incorrect and so the way to do that is more xor gates because xor gates are great at computing parity so what we'll do is we'll have three sets of them to compute the three different parity bits so this first set here is for parity bit one and it's going to have four inputs here and basically what this is going to do is xor them all together and so if there's an even number of one bits coming in here on the left then the output will be a zero but if for some reason there's an odd number of ones coming in here so basically either one of these or three of these are ones well then the output here is going to be a one and so a one on any of these things indicates that that parity bit was was wrong or there's some some kind of problem that involves that that group and so we just do that for the three different groups and so you can see this one is uh you know hooked to the same you know every other bit like like this so you can see it's just hooked to every other bit this second set of xor gates is is this uh set here on parity two and it's it's these two and these two and so you can see it's uh you know those two and then those two and then finally parity bit three is coming around and hooked to to these xor gates here and you can see it's just these these four here so it's those four being xored together so this will compute those three parity bits and if there hasn't been a bit flipped then these should all be zeros but if any of these are a one then that means that that something has been flipped and then depending on which combination of them are ones well we can figure out which actual bit exactly was flipped so let's go ahead and build this and then we can play with it and i'll show you exactly how it works all right so here we've got some more exor gates and i'll get the power and ground pins hooked up on each of these chips i'll start by hooking up this this last group here because that'll be the sort of the last four bits which you know have been on the left kind of the way we've been laying things out so i'll put that on the left here so those bits will just come into you know two of them will come into the input of one xor gate and then the next two will come into the import input of another and then the output of the first xor gate will come around to one of the inputs of of another xor gate up here on the top and then the output of the other xor gate down at the bottom will go around to the second input of the x or gate at the top and then the output of that xor gate we can just hook up to an led and that'll let us see what's going on there that's this bottom one here so we've got those four inputs coming in going through two xor gates and then the outputs of those going through a third xor gate and then we've got this led looking at the output so next lock up these xor gates and so two of the inputs are these two and then the other two inputs are the next two here hook those up there like that and then again the outputs of these two xor gates on the bottom are going to go around to the inputs of an xor gate on top and then the output of that xor gate on top we'll stick an led here so we can see what's going on with that and so now that's this uh the second one here that's yeah the second one here so it's going to those two inputs same same two inputs there and then these these two inputs here so lastly we'll do this one which is just going to look at every other input and so that's every other bit being input into those two and again we'll take the outputs of these two xor gates around to the two inputs of an xor gate on the top and hook an led up to that one so there we go so now we will get an output on these three leds to show us which of the three parity bits is uh if any i guess if is incorrect based on the input that we've got so let's hook all this up to what we've got already so hook this up to the output of that error injector circuit thing that i just showed you so now i've got all that hooked up let's hook up power to this final circuit down here and there we go and let's see we have a problem with this bit here yep it's funny i knew exactly which wire was uh it was wrong which i'll explain in just a minute here but what this is showing now is it's showing the the parity bits so right now we don't have any errors injected so all of the parity bits check out but let's say we were to inject an error let's say we're going to we're going to inject an error into bit 3. so right now bit you know d3 the second bit here is off let's say that some sort of error occurs that that flips that on well that's going to screw up these two parity checks here the parity check for bit 2 and parity check for bit 3. so so let's let's do that so if we flip that we see we flip that on now we see that those two parity bits are wrong and so we know that if we know that those two parity bits are wrong that's you know this one and this one if we know that those two wrong the only case where you know both of those could be wrong is if bit d3 is flipped so if we look at what we've got here we can see bit d3 is a one so if that's been flipped then we know it should be a zero so if we flip that around and look at that as a zero well then we end up with the correct answer which is what we've got up at the top so just by checking those parity bits we're able to to figure that out so if i flip another bit here so in this case only one of the parity bits is is wrong and that's a parity bit three so that's that's this case here so in this case the error is actually parity bit three the data is fine the only bit that's been flipped is parity bit 3. let's say i flip a different bit well in this case i see parity bit 1 and 2 are wrong so in the case where parity bit 1 and 2 are wrong that's this case here so 1 and 2 are wrong that must be that d1 has been flipped so d1 shouldn't be a 1 it should be a 0. so at this point we're actually able to detect any single bit error so in this case you know this is going to be that d3 again d2 we can detect any single bit error just by looking at which parity bits are wrong and of course if they're all off well then that means that there's no error and what we're receiving here is is correct that matches what what is being sent or what we're reading is matches what was stored if we're doing uh you know error correcting memory or something like that now obviously the one caveat is if there are two bit errors then all bets are off so in this case what we're seeing is we're seeing parity bit 1 and 3 are wrong so the case where parity bit 1 and 3 means the d2 must be wrong so if we try to do error correction here well if we flip d2 you know we'd get one one and then that would be a zero one well you know the data was you know one zero one zero so we're not going to get the right answer in that case but that's because we've got two errors i've injected an error on d1 and d3 so we're not able to correct two errors but if there's any single bit error no problem we're able to detect it and we're able to figure out from what parity bits are set we're able to figure out which bit was was flipped and so presumably we can build a further circuitry here to actually flip it back around the right way but before i get to that one thing that you might have noticed is that the way that this is laid out perhaps you've wondered why i sort of interleaved you know parity 3 in the middle here why it's kind of grouped like this well it's grouped like this because the way this is laid out the actual parity bits here read out exactly which bit is wrong so if we look at this in binary you know we see zero one one well that's three well three is one two three the third bit d1 so three is in fact the bit that was flipped and it's you know the same for for any bit here so here i see one one zero well one one zero in binary is a six so that must mean that bit six was flipped and in fact it was so whatever bit i flip i flip bit five i get one zero one that's a five in binary and that's actually why you know funny enough when i first hooked this up you remember i had this wire just off by one like that and i immediately knew just by looking at this and i was like wait a minute something's wrong with bit one so did i hook bit one wrong and i did i hit it i had it off by a little bit so that's i guess the the nice thing about working with uh error correction circuits is that if you have an error in your circuit it tells you about it and not only that it tells you how to correct it so told me that the bit 1 was was hooked up wrong so there we go but anyway now that we are able to figure out okay bit three is wrong the next thing you want to do is you know if we're using this in some circuit presumably if we stored this particular data one zero one zero we want to be able to read one zero one zero from somewhere so we we've got this error you know this data with an error in it and we know where the error is so the next thing we want to do is build a circuit that actually takes the information about where the error is and uses it to actually correct the error so how do we do that how do we use that three bit binary position of which bit has the error to actually flip that bit back to the correct value well we can use a circuit like this so what this is we've got our four data bits coming in and if we just look at one of them we've got that data bit coming in and it's going through an xor gate and remember with an xor gate if the other input is a zero then the output's just going to be whatever the input is but if that input is a one then the output's going to be the opposite of whatever the the second input is so that's what we're doing here is we're taking the the bit and if this other input this bottom input is a zero well then the bit just passes through if the body of input is a one then it flips the bit and so then what we just need to do is we just need to figure out does that bit need to flip like does is that the bit with the error and the way to do that is with a simple decoder circuit and that's that's what these and gates are so these are and gates that say okay if all three inputs are ones then the output is going to be a one otherwise the output's a zero so if all three of these inputs are a one then it flips this bit otherwise it doesn't flip the bit and then we can position an inverter on whichever inputs we want to be able to use this and gate to select a particular value from these three bits so in this case we're selecting the value one one zero or actually i think it's the other way around i think it's 0 1 1 yeah so 0 1 1 which is a binary 3 and so that's actually going to select that first bit position right so if we have a 3 coming in here so 0 1 1 that means that we have an error in the third bit position which is d1 and we want to flip d1 this and gate here we have 1 0 1 and 1 0 1 is 5 in binary so 5 is going to be the fifth bit position so one two three four five that's d2 so we have that one zero one we're gonna flip d2 we're gonna flip flip that fifth bit position here we have a one one zero so in the case that we've identified our error is is in in bit 6 1 1 0 then we'll flip uh d3 we'll flip the 6 bit position 1 2 3 4 5 6. and then of course if we are 1 1 1 that's the 7th bit position and we'll flip this this last bit so this decoder circuit will let us use the binary information we have so in this case we we see that the error is at 0 1 1 so 0 1 1 is bit position 3 so that means that the the error here is in bit position three which will activate this and gate course none of these others will be activated because because they're selecting for for different combinations of values but this one will be on and so that will tell this xor gate to flip its input and the other ones won't flip their inputs so they'll just pass through but this one will flip which will have the effect of correcting the bit that was uh that was incorrect so let's go ahead and build this part of the circuit okay so to build this out we need some xor gates some and gates and some inverters for the inverters i'm going to use the 74 ls04 which has got six inverters on it we only need three and for the and gates i'm going to use the 74ls 11. which is this three input and gate and there's three of them per chip we need a total of four inconveniently so i guess we'll need two of these chips and then finally more xor gates so the 74 ls 86 again so go ahead and power all these up and then finally the output here i just want to hook up some leds and it's getting pretty tight over here on the on the edge of this breadboard but i think i can squeeze in four leds just to be able to see the four data bits that we started with and then connect each one up to the four different outputs of the 74 ls 86 so there's the there's four xor gates in this last chip here and i'll just connect uh one of these leds up to the outputs of each of those uh four xor gates and i'm connecting them through just a 220 ohm resistor so there's some extra current limiting through the leds and i think what i'll do is just kind of work backwards connect these inputs from the four xor gates to the outputs of the four and gates so there we go we've got the four outputs of the end gates hooked to the four inputs or four of the inputs of the four x or gates so then i've got a bunch of these connections here on the inputs of the and gates to hook up and a lot of them are kind of hooked to each other you know kind of two inputs connected to each other so i'm gonna try to hook these up as efficiently as i can here okay so that's all of these connections i think we're seeing all of these leds on except for the last one which i think makes sense because we don't have any of these four connections hooked up yet so i think these inputs are going to all default to ones except for this one well it's going to default to a 1 but it's going to be flipped because that's the bit where you've introduced the error if we don't introduce that error then it's all going to default to ones so i think everything's working so far we just need to hook up that second input for each of those xor gates which are these original data bits and then it'll flip the one that's wrong so here is data bit four that stays on that makes sense data bit three data three goes off that sort of makes sense databit two is here that one's on that uh that makes sense that matches what it should be and then finally data bit one and we hook that up that's off which is not what it is here but it is what it is here so it is uh correcting that and so if we start introducing other errors what we see is that regardless of which bit error we introduce the output remains the same and of course if we change the input that'll change the output and the the output will always match the input but if we have any single bit error what we see is that our output doesn't change we're correcting that error of course if we have two bits of error well then the output changes but you know that's just not something that the circuit guarantees this is only able to to correct a single bit error and of course that is the inevitable trade-off that always exists that's the trade-off with this particular scheme is that we can add more and more bits and the more bits we add the fewer sort of relative parity bits we need so we could expand this by adding one more parity bit and we get to add seven more data bits but it would still only be able to correct a single bit error so if you expand this too much then the probability of having two bit errors goes up goes up more than it would if we just kept it smaller like this but you know that's the trade-off between efficiency of covering more data with fewer parity bits overall versus uh you know the accuracy of being being more likely i guess to be able to correct an error though one thing you might have noticed with this particular scheme is that um the way it works is like the most efficient scenarios here are always like one less than a power of two so what we've got here is we've got seven bits and seven is kind of a weird number in computer science and in computer engineering you usually expect a power of two you expect eight bits so why why don't we have that extra bit well the reason is that it wouldn't really work because if we did have an extra bit here the indication that there's an error with that bit would be if all of the parity bits pass so like we wouldn't be able to distinguish between this situation here where we have zero zero zero indicating an error in position zero versus zero zero zero indicating that there's no error which is which is of course what it indicates now so a common thing to do uh is you know usually when you're storing stuff you know you have eight bits to work with you wouldn't have seven bits or if we expand this out you'd have 16 bits to work with you wouldn't have 15. common thing to do is to use this extra bit as a parity bit for all of the bits and it doesn't help you with error correction at all but what it does do is it gives you a second check so that if you have an error that you're able to correct and you have another bit that's wrong then that extra parity bit will tell you if you have a two-bit error so that's a very common use of that extra bit now i won't build all the circuitry to add that but you can use your imagination there but that means that in practice this uh this hamming code scheme will usually let you correct one bit errors and detect any two-bit errors and if you want to learn more about how that works or if any of this was in any way interesting i strongly recommend checking out grants videos over at 3blue1brown he's got a beautiful video that explains hamming codes from a different perspective and another video coming soon that discusses a really elegant software implementation so definitely go check out three blue one brown and of course as always thanks to all my patrons your continued support helps make these videos possible so thank you

Channel: Ben Eater

Views: 171,317

Keywords:

Id: h0jloehRKas

Length: 36min 46sec (2206 seconds)

Published: Fri Sep 04 2020

Reddit Comments

[u/NormandaleWells]

Be sure to also check out the 2 videos by 3blue1brown that go into some of the mathematical detail of Hamming codes.

https://www.youtube.com/watch?v=X8jsijhllIA

https://www.youtube.com/watch?v=b3NxrZOu_CE

[u/kiss_my_what]

Ben just throwing this out there to see which of you nerds is going to work it into their 8-bit build.