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

relationship between

The error and and the actual bits that got flipped, you know

Like you might think there is if you just look at this one example here

And so all of that actually makes it much more complex

In fact, very complex to think about what number we would divide by to look for certain bit patterns in our error

And so because of this CRC does something different and actually quite clever

So CRC doesn't represent

The message as a number like this instead, it still represents it as a mathematical expression, but it represents it as a polynomial

So check this out. Let me show you an example of how that works. So

Here's the letter H. And here's how we'd rent that in binary

So if we're actually transmitting the letter H over a network

These are the actual bits that we would send and as we've been seeing we can think of that as an in this case 72

And the reason that we think of that as 72 is that each of these bits has a place value, right?