Subtitles section Play video Print subtitles In the last video we saw how Parody could be used to detect any single bit error that occurs when transmitting from one system to another And we can inject an error here too to sort of demonstrate that but the limitation of parity is if there's more than one error That occurs in your message, then it may not detect it. And actually in this case that seems to be what has happened here So, for example, we have a comma in our you know hello comma world Over here no comma so there was definitely an error and of course I injected an error you saw that but I received parity is is even which Indicates that we did not detect a parity error Even though there was an error and that's just a limitation of parity is if there's one bit error You'll you're guaranteed to catch it But if there's more than one depending on how many errors there are you basically have a 50/50 chance of catching them And then at the end of the last video I showed you some potential ways to work around this by potentially adding more parity bits So if we have our message here hello world when we can convert that to binary we've got the the binary representation of what we're sending and You know, just four four basic parity. We have a single parity bit and in this case if we count up all the ones in this message, there are like 49 ones and In order to send this with even parity. We want to send either 48 or 50 We want to send an even number of ones so we have 49 ones We need to add another one so that we send an even number of ones But if we change any two bits in here, for example, we just change any any two ones to zero So instead of having 50 ones we'll have forty-eight ones that's still an even number and so we won't detect a parity error So one way to work around that is to add more parity bits So instead of having a single parity bit for the entire message We can have a separate parity bit for each byte And of course the trade-off is if we're sending a parity bit for each byte then we're sending more data overall Because we're essentially adding 12 percent overhead to our entire transmission and maybe that's worth it because you want to catch errors But even here you still may not catch every error because if you have multiple errors in a single byte Then you may not catch that with the parity bit And so you could keep going you could say well send a parity bit for every four bits or a parity bit for every two Bits or even a parity bit for every bit which essentially just means you're sending the entire message twice But all of that just adds more overhead and so it seems like there's this trade-off, right? so in this video I want to talk about some ways to sort of do better than this too to get a better air detection But lower over that's sort of our goal here And one thing to keep in mind is just the types of errors that we might that we might expect So it's actually not true that it's equally likely for every bit to just randomly flip errors tend to happen in certain patterns So for example the error that we had here where you know We were supposed to be receiving hello comma world but we received hello and then and then two spaces That error happened because of two bit flips. So if we look at the difference between a comma and a space It's just these two bits, right? It's 0 0 1 0 In both cases and then it's either 1 1 0 0 or 0 0 0 0 and so what happened while we were transmitting this is I just hit this button to Drop those two bits and that that's what injected the error and because it was 2 bits that flipped We didn't catch it with the parity, but we wouldn't catch you here either, right? because if those two bits flipped Then this parity bits still gonna be a 1 right because we'd go from 3 ones in here to just one one in Here and that's still an odd number. So we'd still have a 1 out here as our parity bit So we still wouldn't catch it with even this scheme and in fact this this type of error where you have multiple bit errors in a row is called a burst error and it's quite Common because you might imagine some sort of thing interfering with your with your signal Maybe it's not a button like this. But but some sort of interference that happens It's gonna happen, you know over or maybe some short period of time and corrupt a couple different bits in a row So one thing we could do with parity. That's actually much better at catching Burst errors is instead of using a parity bit to protect a sequence of bits in a row have the parity bit protect an interleaved Sequence of bits so one way to do that is something like this where we have the same data here But instead of computing a parity bit for each byte is essentially compute a parity bit for each column here Which is sort of each each bit position within the byte So for example, if we look at the first bit of every byte, well this case they're all zeros So the parity bit is a 0 And we just do that for every bit position at the end here. We're gonna have Another another essentially another byte of 8 parity bits and so we send our message and then we send these eight parity bits and this is Much less susceptible to burst errors so for example if we change both of these bits here like we did in our message where we lost our comma we would detect that because both Of these parity bits down here would be invalid now This still has limitations, of course, so just like here if we change two bits in a row We wouldn't necessarily detect that here If you change two bits in a column, you wouldn't detect that and so there's this trade-off between you know Parity bits per row versus parity bits per column and which one you might choose depends on the types of errors you might expect and in most communication systems burst errors are actually pretty common and so something like a a Parity bit per column here might be a better choice But know that you you may not catch multiple bit flips in a column So that's the trade-off that you're making but maybe we don't need to make that trade-off you know a few of you suggested in the comments on the last video using a checksum and The term checksum can can technically refer to any additional little bit of information that you attach to your message to validate that it's correct But it can also literally mean a sum So if we take the the characters in our message and get their ASCII numerical equivalent We just add those up and in the case of hello world We get 11 61. And so what if we just send our message and we send this number 11 61 Well, then you'd think well if anything in here changes, well, then the sums probably going to change. So is that better or As good or worse than these parity things we've been looking at well to figure that out it actually helps to look at this addition in binary because you know We can do the addition in decimal like we did here we could do the same addition in binary We should get the same answer And in fact, you know, this answer we get here is 11 61 in in binary But if we look at the way this addition works, there are actually a lot of similarities to parity going on here and so we we can actually sort of compare what's going on here to what's going on with Parity scenario where we were taking a parity bit for every column Well, it turns out that actually for this first column here on the right It's the same Because if we just count up how many ones there are which I guess is the same as adding them We got 1 2 3 4 5 and so the sum there would be 5 of course. There is no 5 in binary so the way you represent 5 is 1 0 1 so You would put a 1 down here. And then we carry a 1 0 over into these next columns So the 5 here is 1 0 1 we actually look at this one that we're putting down here at the bottom this is Identical to a parity bit for this column because if you add up this column or you count the ones however you want to think about it if the answer is even then it's a multiple of 2 and In binary a multiple of 2 is going to have a 0 in the last place Yeah, just like in decimal if you think about a number that has a zero in the last place It's going to be a multiple of 10 when binary phase 2 if you have a 0 here it's a multiple of 2 and if it's not a zero, which I mean in binary The only other option is that it's one then it's not a multiple 2 which means that it's odd So this bit here essentially is a parity bit for this column And then the next column works the same way, right? We add these up and there's 1 2 3 4 So there's 4 ones in that column or you can think of the sum being a 4 That's even so you put a 0 there if we're doing parity but if we're adding then 4 is 1 0 0 so you put the 0 there and carry the 1 0 so 1 0 0 and you carry, but what's going on that's different than parity here It shows up when we get to the third column here when we add this up in the third column We got 1 2 3 4 5 6 7 8 9 ones But it's actually 10 ones because we we have this one that we carried from the first column and so because it's 10 That's was it 1 0 1 0 so we put a 0 down here and carry the 1 0 so It's 1 0 1 0 and so it's interesting now is that this number here is not the parity bit For this third column from the right as it as it was originally it's the parity bit of the 3rd column from the right plus What was carried in from these other additions over here on the right? and So in some sense you can think of what we're doing here with this addition as being very similar To computing a parity bit for each column But we're kind of holding on to some extra information when we do that and then that extra information is percolating over into the columns to the left and So in some sense, we're getting kind of the best of both worlds here Which is that if we have a burst error and several bits change within a single row here Then we'll catch that in our checksum down here. But also if several bits change in a column, we may catch that as well So for example, if both of these ones were to change to 0 the parity wouldn't change still be a 1 down here but it would be a 1 because the the sum of this column instead of being 5 would be 3 and So while this wouldn't change what we carry does instead of carrying a 1 0 1 4 a 5 it would just be 1 1 4 3 So that would change the parity of these next two columns or the sum if you want to think of it that way of these Next two columns and so we're able to catch that type of error here Now in practice you may not actually send the entire trek sound like this because if we're sending 8-bit words Oftentimes what you'll do is you'll just chop off This first part here and just send eight bits of the checksum and that's that's a pretty common thing to do and you can think Of that as essentially being equivalent to sending the remainder of a division problem here So if you add it up you get 1161 if we divide by 256 we get four which is the part on the left there And then the remainder 137 is the part on the right and we just send that as our essentially is our checksum That's a pretty common way to do this because if you're already sending 8-bit words It may not be so easy to just send an extra 11 bits but of course the drawback of lopping off this lose leftmost bits is you know What we just talked about this sort of information that percolates over to the left here you'd end up losing some of that And so one thing that's done Fairly commonly is to do an end-around carry where you take this extra bit that you you've had there and you essentially add it back To your original checksum, so you just sort of lop that off Move it around here and then add it and then you you end up with with this number here And essentially what that does is that you're doing this sort of end around carry So when you're adding these leftmost columns here instead of carrying off to the left you're essentially sort of carrying back around to the right here and Taking this extra information and holding on to it over here on the right side of your addition problem here And so this ends up kind of retaining some of that information