## Subtitles section Play video

• 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

• 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