Subtitles section Play video Print subtitles 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