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
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?
So if I just sort of expand this out?
This is the same the same number and what we're doing when we convert that to 72 is we're just saying each of these
Each of these bits has a place value
so this bit all the way here on the right has a place value of 1 2 to the 0 is 1 right this
Here has a place value of 2 4 8 16 32 64 and 128, right?
those are just powers of 2 and what we do is we just multiply each of those powers of 2 by the
Bit value whether it's a 0 or 1
So in the case of 0 we simply just ignore that term in the case of 1 then we have a 2 to the 6
plus
2 to the third and to the 6 to 60 4 to the third is 8 and if we add those together we get 72
So this is this is just how we get 72
This is how binary numbers work
You know one property of this is if we add another 8 to this here
We wouldn't have two x to the third because two eights here makes it 16
right
So you'd carry that 16 over into the next place and t2 have 1 2 to the fourth instead of 2 to the Third's
Right, and because you have that carrying between places here
That's basically how you can get lots of bits changing here in the mathematical difference
If you subtract even though only two bits actually changed, you know that the carrying effect
So a trick that crc uses to avoid carrying is basically do the same thing
But replace all the powers of two with powers of X
Now each term is truly independent. If we add another one to this term here. It doesn't carry over
We just get 2 X to the 3rd
it doesn't touch the X to the fourth term and just like before we can simplify by getting rid of all the zero terms and
end up with just X to the sixth plus X to the third and
So this is just a different way of representing this same binary string
It certainly looks a little bit weirder than just a number but it's you know, it's another expression
It's a way to represent the same the same binary message here the same binary string
you might be wondering you know, what the X is or what it represents and
It's sort of weird. It doesn't really represent anything
I mean, I guess I mean you could plug two in here and you get 72 you get the same thing
But the idea is that doesn't have to be - or really does have to be anything
So X doesn't really represent anything. It's just part of this trick that we're doing that just gives a different way to represent our message
But the important part is that even though X doesn't really represent anything real
this expression we end up with still in algebraic expression just like 72 is
So we can still do math to it
and in fact
We can still divide it by stuff and get remainders and you know everything else we were doing before
It just looks a little bit weirder and so we can do the same thing with a bigger message like our message
hi, so we have our message hi, and then we have
1600 ver here and this is where our checks are actually eventually this is where a CRC check is going to go
But we can convert this to a polynomial like this the same way and this is what we get
And so what you see is if you sort of count over here from you know, zero one, two, three
This is the sixteenth bit. And that's a one and then you go 17 18 19 20 21
So that's why we have the X to the 21 term
22 23 24 we have our X to the 24 term and so on. So each of these ones turns into a
Term and our polynomial in the appropriate position
And so maybe it was a little bit weird at the beginning of the video to think of this message
This entire message is just one big long number and maybe it's even weird or still to think of this message as a polynomial
But it's a perfectly reasonable way to represent the message and because it's a perfectly good
Algebraic expression we can do math to it so we can even divide it by something. So for example
It looks a little Messier here. But here's our here's our polynomial right here under our division. That's the same thing
That's our message and we can divide it by you know
some other numbers so or some other polynomial actually in this case and
Again, it it does matter what you divide by and we'll get to how you might choose that
And what that actually means but it is going to impact what types of errors you can detect but for now
We'll just use this one that I've got here
and if we divide our message by that polynomial you get some answer and it's some big long messy polynomial and
then you can multiply these two together and you get
some other thing and if you subtract that you get a remainder and so this
Remainder down here is is in fact the remainder when you divide our message by this polynomial
And that's the exact same thing. We were doing at the beginning of the video, right?
We have our message here represented as number. We divide our message by some magic number and we get a remainder here same thing
We've got our message
Represented as a polynomial we divided by some magical polynomial and we get a remainder
and then we can use this remainder then to kind of fill in the the
Remainder as it were of our message here so that our entire message then is divisible by our magical polynomial
But unfortunately, we've got a bit of a problem here
I don't know if you've noticed here
but if we want to take this polynomial and
Use that to determine the little remainder bit here to fill in the check sequence in our message
We've got to figure out how to convert this polynomial back to a binary representation
And say so, okay. Well you just look at each position here. So in the 15th bit position, that's here. We put a six
What wait a minute?
There's no such thing as six. This is a binary number
So we've got a bit of a problem here. Yeah, you know, how do we what do we do with this six?
You know, we've got like negative numbers in here
Well, you know the fifth bit position is I want a negative one and we've got two over here
So it looks like we've got a problem here, but fortunately there's another mathematical trick that we can use that will help us out
And so the mathematical trick we can use is this thing called finite fields?
And so we do a quick sidetrack into what what finite fields are and so to understand what that is
Let's talk about algebra here for a minute algebra is basically the set of rules that you can use to manipulate symbols
So for example if we want to solve this for X
We can apply some rules we can add five to both sides and we can sort of simplify this and we get x over two
equals twelve
maybe we want to multiply both sides by two and that gives us x equals 24 and
So even if we're just solving for x, you know, anytime we're doing any algebra. We're just applying a series of rules
And so this rule here where you're adding the same thing to both sides. It's called the additive property of equality
And there's this rule here. We can multiply both sides by the same thing. That's the multiplicative property of equality
And so there's all these different rules that algebra has and by applying the rules you can manipulate
Expressions in different ways to solve problems and so algebra is just a bunch of rules that all work together and produce consistent results
But one thing that you'll notice that maybe you never even really thought about is that whenever you're doing algebra you're using numbers
And the numbers that you use when you're you when you're doing algebra make up what's called a field
and so if you've ever done
You know any kind of algebra like this before you've probably done it with the field of real numbers, you know
These are certainly all real numbers
And so as long as all the numbers that you're using are real numbers then you know
We can apply all the rules of algebra and whatever
Manipulations we get when we use those rules are valid and we can use those to solve problems but algebra works for other fields
Too so, you know, maybe you've used complex numbers and complex numbers are just a different field
but all the rules of algebra as you know work just as well, but
we're interested in a finite field and
As the name would imply instead of having an infinite number of numbers like the real numbers or the complex numbers a finite field
Uses a finite number of numbers, but still all the rules of algebra work just the same
So, how does that work? So what is the field?
so a field is basically just a set of numbers and then a definition of how you add those numbers together and how you multiply
those numbers and that's basically it but
Your field has to obey certain rules in order to be a valid field in order for algebra to still work if you use that
Field and so there's certain field axioms
So for example, there's this axiom of socit if ax t so, however, you define your addition and multiplication
It has to be associative. It also needs to be commutative
So a plus B has to equal B plus a and same with multiplication you have to have identities
So there has to be an additive identity there has to be some number so you've got this set of numbers that that are in
Your field you've got one of those numbers has to be an additive identity so that if you have a plus that number
usually zero you get a
same thing for multiplying essentially you need a 0 and a 1
You also need to have an additive inverse
So something where if you add a number to its inverse you get zero, you need a multiplicative inverse
which is some number 1 over a for example, if you multiply a number by its inverse you get 1
And finally your rules of addition and multiplication have to have to be distributable
They have to follow this rule of a times B plus C equals a times B plus a times C
and
So within these rules you can come up with any set of numbers in any
definition that you want to of multiplication and addition and as long as it meets all these rules as long as you definition of
What numbers are and what?
Multiplication means and what addition means as long as those rules meet these axioms then your field your set of numbers and your rules
Will work with all of the rest of algebra, which is pretty cool
So in our case, what we want to do is we want to be able to do algebra like this
where instead of getting you know 6 and negative 1 & 3
All we get is just ones and zeroes so that we can then nicely convert that back into a binary string here
So what we really want is a field
An algebraic field that we can do algebra with that only has a material and 1 in it
So can we do that? Well, it turns out yes we can and this is how we would define that field. So
Our field only has two numbers in it 0 & 1 and then we can define addition like this
It's easy enough to define addition because there's only two numbers and so we could just list out every possible addition problem
And there's you know, there are some weird things in here
So 0 plus 0 equals 0 you'd expect that 0 plus 1 1 plus 0 equals 1
You know you expect that but then 1 plus 1 we're defining that as equal to 0
Ok
It turns out by doing that then we actually meet all of our our axioms
With respect to how we're defining addition same thing with multiplication works pretty much the way you'd expect
Anything times 0 is going to be equal to 0 1 times 1 equals 1 and just by defining addition to multiplication like this
We're meeting all of the field axioms
And so this is a valid field even though there are a couple sort of weird counterintuitive things that you might not expect
So for example, we need to have this additive inverse. So you have to say a plus negative a always equals zero, so
Normally you'd think of like ok, five plus negative five equals zero
That's that's sort of the way that that would work with the real numbers but in our world
The additive inverse of a number is the number itself. So the add of an inverse of zero is zero
so zero plus zero equals zero that works and the additive inverse of 1 is also 1 so one plus one equals zero because we've
Defined this that way then we can kind of check off that axiom there
And so you may want to you know, pause the video and convince yourself that our definition meets all of these axioms
But but it does this definition here does meet all those axioms and there's just a couple weird things
but we've defined all the weird thing in just the right way so that they meet the axioms and so again,
You might you may want to pause or sort of convince yourself that that's the case
But because this is a valid field that means we can use these numbers just zero and one only those two numbers
with this definition of addition and this definition of
Subtraction multiplication division and all of the rules of algebra will just work in a consistent way, you know
Even though there are some unintuitive definitions in here. So if we go back to this, you know gnarly
Polynomial division that we've got going on here if we use the finite field when we do this division
We won't end up with all these weird coefficients these you know, the six and those negatives and the two and so forth
We'll end up with just ones and zeroes as our coefficients
So let's actually work through this division problem using our finite field to see exactly how how this all plays out
Ok. So again, this is the message. We're gonna send hi
Exclamation and we only have 16 bits here at the end to fill in our CRC
And because we're leaving 16 bits the thing we want to divide by this is called generator polynomial
I'm going to use a 16th degree
Polynomial so that we're able to make use of at least all of those all 16 of those bits. So the message itself
Shifted over is this polynomial here, and I'm going to divide it by this same generator polynomial here
And again, I'll talk about how you go about choosing a generator, you know
A good generator polynomial in a little bit and so I set this up as this long division problem
And in fact, we are going to do long division. That's very similar to the long division
You might remember from from grade school. And so the way we start is we basically look for
how many times X to the 16th goes into X to the 38 and
That happens to be X to the 22nd times right? Because X to the 16 times X to the 22nd is X to the 38th
in fact
we can do that multiplication now now that we've come up with a term here in our in our quotient we can multiply X to
The 22nd times our polynomial here and so X to the 22nd times X to the 16th is X to the 38th plus
X to the 22nd times X to the 12th is X to the
34th and then X to the 22nd times an X to the fifth is X to the
27th and then X to the 22nd times 1 is just X to the 22nd
So I just multiplied X to the 22nd times our divisor here this Janner your polynomial to get this right here
And so now just like normal long division I'm gonna subtract
It so we have X to the 16th - nothing that's going to be X to the 16th
X to the 21st - nothing. Is it going to be X to the 21st?
and here we have nothing - X to the
22nd and so you might think well that's going to be negative x to the 22nd because we're subtracting this right this
Subtraction we're doing here, but that's not true
Right because we're using our finite field and in our finite field
remember that 0 - 1 equals 1 because we don't have a negative 1 we only have a
0 and a 1 so this is actually going to be a positive
X to the 22nd or the coefficients going to be 1 I guess because our coefficients can only be 0 or 1
That's the whole point of using this finite field
and of course you might wonder well if we only have 0 & 1 well
How come we can have 22 here and this isn't 22, I guess in terms of being a number that we're operating on
This is really just 22 X's multiplied together
And so we can do that because we could just write out 22 X's all multiplied together
But in terms of the coefficients that we have the actual numbers in our expressions
We're only using 0 & 1 & we're using our special addition and multiplication rules
Okay, so moving along X to the 24th - nothing is going to be X to the 24th X to the 27th - X to
the 27th, you know again, that's that's the coefficient 1 minus 1 and so one minus one is is 0
We're not not doing anything weird there
Right 1 minus 1 is 0 so nothing nothing special. Nothing crazy there that just cancels out
So X to the 29th - nothing is X to the 29th
X so xxx - nothing to the 30th and then this term here we have 0 minus 1 times X to the 34th again
That's going to be plus X to the 34th because again, even though we're subtracting
We don't have a negative 1 in our finite field that we're using. Okay moving along X. So 35
Minus nothing is going to be X to the 35th and the next to the 38th minus X to the 38th
That's 0 so that cancels out
So that's the first step of our long division here, right?
we figured out that our polynomial here divides into our message X to the 22 times and has a remainder of
This thing down here, but we're not done yet
Right because X to the 16th, we can divide that into X to the 35th as well and that go x2 the nineteenth times
So we can keep going now and we're gonna basically just repeat this process and go through this entire polynomial here
So now we're going to multiply X to the 19th times our polynomial write that down here subtract and keep moving
So again, we can say that our message
Divided by this generator polynomial equals x to the 22nd plus X to the 19th, and it has this remainder
But we're still not done yet
Right because X to the 16th goes into X to the 34th as well and that goes X to the 18th times
So we'll add an X to the 18th up here
And now we'll multiply X to the 18th by our generator polynomial and subtract that off
And now this is our new remainder
But we're still not done right X to the 16th goes into X to the 31st X to the 15th times
So we'll put an X to the 15th up here add that into our quotient and multiply that
And we'll go ahead and subtract. All right, still not done
Next to the 16 goes index to the 29th now X to the 13 times
And now multiply X to the 13th times our generator polynomial
and then subtract
And now this is our remainder
The reason I'm doing this by hand
And I would encourage you if you really want to understand this try doing a problem like this by hand
Is that by doing it by hand? We start to see some patterns emerging
So one pattern is that we you know continue to subtract essentially this the same polynomial
So we're subtracting something that's very similar to this polynomial but shifted and then kind of each time through it's it's shifting over
but if you look at sort of the I don't know that the spacing I guess here you can kind of think of that as
the the terms
It's shifting each time we subtract and then the other thing is that the way the subtraction works is
It's almost kind of like an X or going on right?
Which is that when we do subtraction here?
If one term or the other is there then we see the term in the result of our subtraction
But if both terms are there, then we don't see the result or you know
Obviously if neither term is there we don't see the result. And so that's actually very similar to an XOR operation
so if we look at our subtraction, you can almost see I mean this is essentially I mean
Well, not essentially this is the truth table for an or gate
So it's kind of interesting that there are xor operations happening in here and it's kind of interesting that we see
This kind of shifting
So I'll just mention that I'm noticing
some of those patterns emerge as we're doing this division because actually both of those observations are going to be very important when we
Want to try to do all of this Ian's Hardware because obviously shifting and XOR. Those are things we can do in our dwyer
So well, we'll get to that though
But anyway, we're not quite done yet
In fact, I think we're about halfway through so I'll go ahead and finish up the rest of this division
And
So now finally X to the 16 does not go into X to the 13. So this is our remainder
and so because we use the finite field when we did this whole
Division process what you'll see is that all of our coefficients are either 0 or 1, right?
We don't have any of those sixes or twos or negative numbers anything like that in here. It's all just zeros or ones
So we could actually convert this remainder now to a binary number but also because we're using a finite field the algebra is consistent
So one way you could check that is you could actually multiply the generator polynomial here
Times the quotient that we got when we divided two this sort of answer that we got up here if we multiply those two together
and then add the remainder you should actually wind up with our message because again,
The finite field even though it's kind of weird and we had to redefine some of the addition and multiplication
A little bit algebra still works and that's the whole that's the whole reason to use it
So anyway, we we get a remainder down here and we can convert this remainder now to a binary number
So this is the sort of X to the zero place here
It's just the 1 so that's going to be a 1 and we're just looking at coefficients
So now the x place the coefficient is a 0 there's no X term it's just an x squared
So that's a 0 the x squared term. Is there X cubed term is there you know each of these terms
Is there X to the 9th term not there these terms are not there. So those coefficients are 0 X to the 12th
Term, is there X to the 13th term is there and then we can fill in the rest
14 15 16 and so now we have this 16 bit remainder
And in fact, this is precisely the remainder that we can now include in our message here as the crc
In fact, this is a crc. We've computed a crc using this generator
So to see how to include that if we start with our message here which you know
We left 16 bits over here of zeros to leave space for the CRC
We can represent that message as this as this polynomial and we can call that M of X
so so M is our message and then when we divide that by this generator polynomial
That's what we just did and we end up with this remainder here at the bottom
And so what we can do is we can actually subtract that remainder from the message to get the transmitted message
Now notice I said that we're subtracting
The remainder from the message that that might seem a little bit strange because it looks like what we did is added it here
right because we've got our message which is this part here and you know, this message is
represented right here doesn't change and then this part over here is
The remainder right this X to the 13 X to the 12 the X to the 8 and so on down here - x squared
Plus 1 that's the remainder
And so it looks like what we're doing is we're just adding that remainder on to our message
but technically what we're doing is we're subtracting the remainder from the message and now it looks the same because again,
We're using this finite field where it turns out that addition and subtraction look like identical operations, which is admittedly a little bit weird
But remember, you know, as long as we're following these field axioms
All of our algebra is going to work
And so that's why I say what we're doing here is we're subtracting the remainder from our message to get this transmitted message
And the reason to do that to say that we're taking our message
Divided by our generator taking that remainder and subtracting it from the message
Is that so that the overall transmitted message is then divisible by the generator, right?
Because you know just imagine we have you know
instead of this polynomial if we have a number 1 2 3 4 if we divide that by 10
We're gonna get 1 2 3 with a remainder of 4
All right
So we have this remainder of 4 if we take 1 2 3 4 and we subtract 4, we're gonna get 1 2 3 0
Right, so by subtracting the remainder we get something that is now divisible by 10
Well, same thing here our message here that you know
You think of that like the 1 2 3 4 if we subtract the remainder from the message?
Then what we end up with this 1 2 3 0 now is divisible by 10 same thing
Our transmitted message is now divisible by our generator polynomial
And that's very handy because then we can send that transmitted to our receiver. Of course, we can encode the transmitted message
In binary and you know the first three bytes are going to look the same
So we actually you know, we have our message retained in there
But then these last two bytes that started out as all zeros now, we're filling in the the CRC
and so now if we transmit this over to our receiver and the receiver receives that
if the receiver divides that transmitted message by the same generator polynomial then it's going to get a
Remainder of zero and that's how it validates that it received the message correctly
But of course the receiver might not receive the transmitted message, you know T exactly correctly right? There might be a transmission error
So we might have a couple bits that get flipped like this
so in this case what's received is actually
This this polynomial that has a couple terms inserted this X to the 26 and X 150
Bits got turned on and so those terms get inserted into the polynomial
So now when the receiver divides this polynomial that was received by the generator polynomial
And performing this same check. The remainder is not going to be zero and so it'll it'll detect this error
It's another way to think about this is we've got our transmitted message t and then when it's transmitted there's an error
That is sort of added to it so we can have this other function
We'll call a of X which is the error
so in this case
It's these two bits the 26 bit and the twenty-fifth bit that that got flipped on
And so really what the receiver is doing is the receiver doesn't know the transmitted message
All it knows is the transmitted message plus whatever error was introduced
So the receiver is going to take the transmitted message plus error divide that by this
Generator polynomial and then check if that's equal to zero
And if it's not then it's going to detect an error
So just to look at another example real quick
Here's an example where again the message for transmitting is still high
But well received as the message ha in this case instead of two zero bits flipping two ones
We have a bit that's supposed to be a one that flips to a zero
and
So the polynomial that we receive is actually missing a term
Right the the X to the 27th term that we should have has gone missing because that bit flipped to a zero
so in that case
What is if we if we think about in these terms like what is that error look like well
It turns out that error just looks like X to the 27th
which is very convenient because it represents a single bit flipping in the 20 the position which is which is what happened and this
math still works the same way our transmitted message plus our error which is which is what the receiver receives if we
Divide that by our generator polynomial we can check to see if the remainder is zero
And in this case again, it's going to turn out that it's not zero, so we'll detect this error
And so even though the the bit flipped from a one to a zero
We don't have a problem with
Any sort of place value here because we're using polynomials
And we can still represent this error polynomial as being added because we're using the finite fields
And so those those mathematical tricks give us this nice ability to represent this error polynomial as just a collection of the bits that flipped
Nothing more nothing less and it doesn't matter whether they were flipped from a zero to one or a one to a zero
Okay. So at this point, you're probably wondering where does this generator polynomial come from?
You know, I just kind of threw this out here as this thing that we're dividing by without a whole lot of explanation
You know, but why divided by this particular polynomial, you know, where does this come from?
Well, it depends what errors we're trying to detect, you know, so the receiver is doing this check here, right?
It's taking that whatever it receives the transmitted message plus whatever errors course doesn't know the difference
It's just receiving something it's taking what it receives and it's dividing it by that generator polynomial
If we get a remainder other than zero, then we know that there's an error. That's how we detect errors now
We also know that the transmitted message without errors divided by the generator polynomial does divide in evenly
So really the question, you know
As far as whether this generator polynomials going to detect errors or not is whether the errors are evenly divisible by the generator polynomial
So if we know what this what these errors might be the you know, that is you know
We know what errors we we want to try to avoid then we can try to be clever and come up with a generator
polynomial that doesn't divide into any of those likely errors that we suspect we're gonna get
Let me show you an example of how we can sort of reason about what our generator
Polynomial might need to be in order to detect certain types of errors
So for the simplest case, let's say we're just trying to detect single bit errors
What type of generator polynomial might be able to do that? Well, let's think about what that error looks like
So we kind of generalize here
So the error in this case that we're trying to detect is X to the I where I could be any value
So for example in this case where our message was corrupted
We had a single bit error like our error was X to the 27th, right?
because it was the 27th bit position from the right that
That had the error
Well, if we want to detect any one bit error, then it's you know X to the I or I could be anything
so in order to detect this we need to come up with a polynomial that is not a multiple of X to the I
that wouldn't divide index to the I
Well, that's easy, you know any any generator polynomial with at least two terms won't divide into X to the I so
You know X plus one is kind of the simplest example X plus one doesn't matter
What I is X plus ones not going to divide into it
So if we use this as our generator polynomial we're guaranteed to detect any single bit errors
Now how about detecting two bit errors, this is a little bit more complicated
But we're essentially thinking about it the same way
We're gonna we're gonna think about what is the error that we're trying to detect in this case
It's well
It's two bits X to the I plus X to the J where hi and J could be anything
And this is you know an example here we see
Where we had two bits to change our error was X to the 26th plus X to the 25th
So that fits this pattern here, but it could be any two bits
That's that's the idea is that the goal is come up with a generator polynomial that is not a multiple of this expression
It's a little bit harder, but you know, we can rewrite the error like this
We just sort of factoring out an X to the J here
And so now we have two factors X to the J is the same as before, right?
That's that's X to the I so we're no we're not going to find a multiple of that as long as our generator has at
Least two terms and so that just leaves us with with this term over here
which we can just rewrite as X to the k plus one where you can think of K is sort of the distance between the
Two bits that have errors and it's a little bit hard to come up with polynomials that won't divide into this
But there are some simple polynomials that won't divide into this unless K
Gets gets really big
So for example this polynomial that we've been using here works as long as K is less than you know
32,000 7:51 turns out and
So in practice what that means is that this polynomial will detect any two-bit errors
As long as the two bits are within this distance from each other
Which if your overall message is smaller than this then that's guaranteed to be
So if you if you have a message that's less than 32 K
Then this particular polynomial will be able to detect any two-bit errors within that message and that's the power of this method, you know
We can rigorously mathematically prove that certain patterns of error. We'll always be detected
it just might involve little caveats about the message size and it obviously requires a bunch of math, but
With that in mind you'll work guaranteed to detect certain patterns of errors
And if we know what errors are likely in our inner transmission
We can try to find a polynomial that's gonna be best at detecting those errors
Now in practice you probably won't come up with your own polynomial
there are lots of different ones that have become international standards and
You can see a bunch of them here on Wikipedia and I've been using this one called CRC 16 ccitt
This X is 16 plus X to the 12 plus X to the fifth plus 1
And you can see it's pretty popular to using a whole bunch of different things
Bluetooth and you know many other things you may have heard of another really maybe even more popular one is CRC 32
Which is you know as the name would suggest a 32-bit polynomial and you might imagine why I haven't been using this as an example
Plus division problem would have been real fun with this one, but this is used in all kinds of things including Ethernet. 802 3
Standards, so this will include all of your Wi-Fi all kinds of things as well as again many other things PNG things
you've probably heard of
These are relatively old standards, but they're pretty good and and they're used in everything and so I would recommend just using them
But they aren't technically the best you can get, you know
Finding good polynomials is actually quite a bit of effort. So it took many years for for people to find better ones
For example, you can see here. There's a couple of newer
Crc32 variants that are better than the crc32 that everyone uses. In fact, you can see these were discovered by Philip Koopman
Who is a professor at Carnegie Mellon and he's done a bunch of research into the best?
CRC's and maintains a webpage here with his findings
This is what he calls the the best CRC polynomials and he breaks them up into the size of the CRC
So we've been looking at 16-bit crcs, but you know, we can go down here and look at 32-bit crcs
He represents them in kind of a different format here
He represents them in hex, but basically what he's saying here is for 16-bit CRC's
What is the best CRC in terms of giving you a certain Hamming distance for a particular size message?
If you remember in my last video
I talked about Hamming distance and having distance as the minimum number of bits that you'd have to change between two messages in order to
Not detect an error
So in this case a Hamming distance of four means that you can change any three bits in the message and guaranteed to detect it
And he says this particular CRC will give you that and it'll give you that for messages up to 32 K long
You can get higher Hamming distances, but you see the message size gets smaller if you use these other CRC's
But the neat thing is you go to look at the the 32-bit CRC as you know, some of these are really quite good
I mean 32k message
you can have a Hamming distance of 6 so guaranteed to catch at least 5 or any 5 errors in a in a
32,000 byte message that's not bad for only having to add 32 bits, you know
Just four bytes to your message 0.01% overhead to protect a message like that's not too bad
But random one-off single bit errors are not the only type of error that you might want to detect, you know
One of the most common errors in data transmission is burst errors
And one of the most important properties of CRC is that they're really good at detecting burst errors
So what is a burst error? Well, it's a bunch of potentially errored bits here in a row like this
And technically the way we define it is
It's an error bit followed by some number of bits that may or may not be heard followed by another error bit
and then the distance between the first aired bit and that last errored bit is the length of the burst and it's important that the
Ones in the middle may or may not be aired
So for example, if you just had all ones in here that would still be a burst error, right?
Because the first bit is is a one when it shouldn't be the last bit is a one when it shouldn't be in the middle
bit, some of them should be one some of them shouldn't
But if they were all ones
Then that would be a burst here and that's you know an error that could happen in transmission
You can have just some glitch that causes nothing but ones to be received
Same thing with all zeros, that could be a burst error as well
so mathematically the way we look at this is with this expression here, which is you know,
this thing with two factors
The first is this X to the I and that shows how far from the right the burst error occurs
X to the I and then K is the length of the burst
so like we saw before if if our generator has more than one term then
Then this X to the I is not gonna be a factor. So we need to worry about that
We just need to worry about this factor here this polynomial this this K degree color K minus one degree polynomial
As long as this K minus one degree polynomial
The degree of that polynomial is less than the degree of the power generator polynomial then the remainder can never be zero
So let's say K is 16. This is a 16-bit burst, which is which is what it is K minus 1 would be 15
So this term here or this factor here, I guess this polynomial here
This K minus 1 is going to be a 15th degree polynomial
Well, if our generator is a 16th degree polynomial that's not going to divide into that
And so it doesn't even matter what our generator as long as it's a 16th degree polynomial
It's not gonna divide into that and then it's not gonna divide into this
Factor here if it's got more than one term as we saw before
so this
Polynomial effect pretty much any CRC polynomial is gonna have this property where it's guaranteed to detect burst errors that are smaller than or equal
to the size of that polynomial or the degree of that polynomial
Some practice any 16-bit crc is always going to protect against 16-bit burst errors
A 32-bit CRC is always going to protect against at least 32-bit burst errors and and so forth
So now if you take a step back and look at all of this together
I hope what you're starting to see is that CRC gives us this really powerful tool for
Detecting errors and being able to analyze the types of errors that we're able to detect
So we have this tool to be able to model the types of errors
We're detecting and and even generalize that and then we have these mathematical tools to be able to evaluate whether a particular generator
Polynomial or you know, there's a particular implementation of crc
Well detect that type of error or how well it will detect that type of error
and it's also happens to be the case that the types of errors that we would detect in a
Communication network or something like that are also the types of errors that CRC is able to detect quite well
So this is all well and good and everything. But you know, this seems like quite complex
You know and and and tedious to have to do all of this
Computation and everything to to figure out what that CRC is or to evaluate whether CRC was received correctly
if we go back to where this video series started, you know, we're trying to send data from one computer system to another and
Evaluate whether we receive that correctly
And so when we looked at parity, you know, that was actually quite simple to implement in hardware like this
If we look at CRC, this is way more complex
You know
How are we gonna go about implementing something like this?
In hardware or even you know in software, it seems like it might be a bit of work to get this working
Well, it turns out and this is one of the coolest things is that in addition to all the mathematical rigor that you get with
CRC it turned out to be quite straightforward to implement in hardware and to do all of this
You know tedious math that we've seen to do that in hardware quite straightforwardly and so in the next video
I'm going to show how we can do all of this math that we just looked at in hardware and
Come up with the same answer because it turns out that with just a couple chips. We're able to do all of this math and
as you can see the answer we come up with here is
The same answer that we that we got when we did all of this complicated
Division and this is this is in fact the CRC that we computed for the same message here
And so in the next video, we'll go through how to build this hardware and more importantly why it works
You