## Subtitles section Play video

• One of the most common error detection techniques used in data communication

• And storage is the CRC the cyclic redundancy check and it's similar to a checksum and in fact in some cases

• You'll hear a call to checksum but it's but it's not a sum like this you're not adding up all of the the different characters

• And coming up with some sort of check sequence here instead

• What you're doing is instead of representing it as a bunch of individual numbers and adding them up

• you're representing your entire message essentially as one big long binary number and

• Then what we can do is we can do math on on that one big number to try to come up with some sort of

• Check sequence. So just as an example, and this isn't exactly how CRC works

• We'll get to that in a minute here

• But just to kind of get you a sense of where we're headed with this

• I've got two messages here

• And the only difference is just these two letters have change to the Oh change to an N and the R change to an S

• so essentially we subtracted one from the O we added one to the s and this is an interesting change because this is something that

• The checksum wouldn't catch because if we're subtracting

• One number and then adding another that doesn't change our overall sum so we wouldn't catch that with a checksum

• But if we represent our entire message is one big long binary number. It does change that number

• And just to give you a sense like this binary number can also be represented as a decimal equivalent

• And so this is actually what that what that is for these two messages and so you can see this is just this big long

• Number this is the decimal equivalent of this big long binary string

• And you can see because we've got two changes here the number is very different

• And in fact, if we do some just some basic math to it. You'll see some other differences

• so for example if we divide both of these by

• 251 well, then we get some big long answer here

• But then there's a remainder as well of 50 if we divide this other number which represents this other message by the same thing 251

• Then we get a different answer, but we also get a different remainder

• And so you can imagine what we might do is send our message

• Along with this remainder and then on the other end when we receive the message if we receive the message and it has some corruption

• Like this when we do that same division and compute the remainder

• We can see that the remainder is different and we can use that to detect that there was an error in receiving our message. So

• This simple division like this is actually a bit simpler than the way CRC really works

• But I think it's going to be a useful analogy to walk through an example of before we actually get into how CRC really works

• So let's take a simpler example here instead of hello world. We'll just use the message. Hi exclamation

• So it's just three bytes that way are our numbers that we're dealing with. They're a little bit smaller

• That's what we want to do is we want to transmit our message

• Hi, and then we also want to transmit some sort of check sequence

• So what I'm going to do is actually add a few extra bytes actually two extra bytes here

• so sixteen bits of all zeros

• And what we're going to do is we're going to fill these extra bytes in here with our check sequence

• So our overall thing that we're sending is going to be this this big long number

• But we're gonna change some of these zeros to actually get the full message

• But if we leave these as zeros for now

• We can convert this entire long thing into a decimal number and we end up with this this number here

• so again

• We're treating our entire message as just a number

• and

• so what we can do is we can then divide this this number divide our message by some other number and so I'm gonna I'm

• going to divide it by six five five to one and

• It's actually sort of

• important what number you choose to divide by and it might be interesting to think about why that is but but we'll get back to

• That in a minute here

• but if we divide this message as

• Represented by this number by six five five to one and look at the remainder when we do that division

• The remainder we get is two six seven six nine

• and

• So it's this remainder that we're going to use to sort of form the check sequence that we're going to add on to our message

• But we don't want to just stick that to six seven six nine in there

• What we want to do is actually something a little bit more clever

• which is take the number we divided by six five five to one and subtract that and

• we end up with this difference here and if what we do is we use that difference then and

• add that to our original message we get this new number and

• You might be wondering well, why are we doing all this?

• well

• The reason we would do this is because this new number that we get is now going to be a multiple of six five five

• To one and it's going to be a multiple of six five five to one because we took this other number and we figured out

• what the remainder was and we tacked on the extra bit to get from that remainder to the next multiple of six five five to

• One and so basically this this number is just the next multiple of six five five 21 after our message

• and in order to get there we needed to add on this extra thirty eight thousand 752

• but what that means is we can take this three eight seven five two and

• Encode that in these last two bites here

• So remember we had all zeros here

• If we encode that three eight seven five two in there

• then that gives us our entire message now equals this thing which is now a multiple of six five five two one and

• so now what we get is we get this entire message that we can send that has the message we want hi as

• Well as some extra bit here

• But the entire thing if we think of it as just a single number when we divide that number by six five five to one

• the remainder will be zero and that's

• what we can do to

• Check or to verify that we receive the message correctly because of any of these bits changes

• Then it's very likely that it will no longer

• That the overall thing will no longer be divisible by six five five to one and that's whether one of the bits in our message

• Changes or one of the bits in our little check sequence over here changes if any of those bits changes

• Then there's a pretty good chance that it'll no longer be divisible by six five five to one

• And so if we receive a message

• That's not divisible by six five five to one. Then we can come to the conclusion that something might have been corrupted

• So for example, if our message changes from hi to ho

• Because these two bits here changed and corrupted our message into something different than what we wanted to send

• Then we'd be able to detect that because if we then take this new big long binary number and we take the value that it

• Represents and divide it by six five five to one again. The remainder is not zero. It's something else

• It's just twenty three zero four zero

• and because that remainder is not zero because this message is not divisible by the

• magic, six five five to one number

• Then we can conclude that the message got corrupted and that the message ho is not the message that we intended to send

• Now you might be wondering

• Why did we choose 6 5 5 to 1 2 divided by like why that specific number and doesn't it doesn't even matter

• Can you just divide by anything?

• Well it definitely matters

• It matters a lot actually and the thing that you choose to divide by here

• Has some bearing on the types of errors you're able to detect or at least the specific error patterns that you're able to detect

• So to sort of understand why that's the case

• Let's look at this same example here, but break it down a little bit

• You can imagine we have our transmitted message here, which is high along with the correct sort of division

• you check some thing that we're using here and we get this number and

• Then we have the received message down here at the bottom, which has the two bits flipped and that's this other number

• But one way to think of this relationship here is that the received message is equal to the transmitted message plus whatever error occurred

• So in this case, these two bits got flipped

• so what happens is this these two bits flipped equals this other number and so you can think of the the received message as being

• The transmitted message plus that error

• And this is kind of a helpful way to think of it because we know that our transmitted message is divisible by

• Whatever number we're dividing by so 4 divided by 6 5 5 2 1 in this case

• we know that our transmitted message is divisible by that and

• So for the receive message to be divisible by that in or in order to receive it correctly

• The transmitted message plus the error have to be divisible

• well

• We know the transmitted message is already divisible by that so we can almost sort of ignore that and so what this is telling us

• is that as long as our error is not divisible by in this case 6 5 5 to 1

• Then we'll detect that there was an error

• So in this case our error is this is this number here or you know this binary number here if you wanna think of it

• that way

• That's not divisible by 6 5 5 to 1. So we're able to detect that error

• But if instead of 6 5 5 to 1 we had some other number, let's imagine. We were dividing by 256

• Well, we're dividing by 256

• This would be a multiple of 256 anything where the last 8 bits are zeros is a multiple of 256

• So there's lots of multiples of 256

• So almost any error that we would have in in our entire message would not be detected if we were dividing by 256

• So that would be a terrible choice of something to divide by

• Where as 6 5 5 2 1 is maybe a much better choice? It happens to be a prime number and

• It's actually the largest prime number that fits in 16 bits

• So that makes it a better choice, but ideally what we'd want to be able to do is think you know

• Mathematically and very rigorously about what are the multiples of of the number we're dividing by and what are those bit patterns look like?

• and that's actually very hard to do because you can imagine if

• We were intending to send the message ho H. Oh and this is what our message look like

• Our checksum here is a little bit different right because it's a different message

• And so the overall message numbers going to be different

• But if what happened was our message ho got corrupted the other way into high

• So there's one's turned to zeros. Then the error that we I guess essentially would add

• Kind of in this in this equation here to get to our new message

• Would be a very different sort of bit pattern than the bit pattern

• that we had here even though it's the same two bits that are flipping and

• so this ends up being actually pretty hard to reason about so if we're trying to think of like

• What is the best thing to divide by here in order to catch the sorts of errors that we might expect so maybe?

• Maybe we expect something like this. We know that our transmission medium works a certain way

• There's certain types of errors that are that are likely to occur and one of those types of errors that's likely to occur

• He has two bits in a row get flipped

• Well here we have an example of that two bits in a row get flipped and our error here is just two bits

• And so then we can think about okay, what are all of the possible sort of two bit?

• Values that are in here and then we can think about what number might we choose

• where none of those two bit patterns is a multiple of that number and if we can actually find a number that matches that then

• You think well, maybe we maybe we can actually guarantee that any two-bit error

• We were able to catch like that or any two bits in a row or whatever type of error we might expect

• But here we have two bits in a row that get flipped, but our error has a whole bunch of bits that are flipped

• And so the problem we're having here is actually related to place value, right?

• Because if we add one plus one we get zero and then carry a one over here

• and then add one plus one we get zero again and carry a 1 over here and

• We just end up with this sort of rippling effect that leads to this this whole mess here then even though only two bits actually

• Got flipped between our transmitted message and our received message. It's not necessarily easy to just look at that error component and see a