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
This guy is a gem. I love engineers who take the time to educate others. Far too many engineers offer "back of napkin" explanations. The whole "you're smart, you'll figure it out" mentality needs to die. We could be so much better if more of us took the time to teach one another with well thought out tutorials like this.
this guy rocks, using a paper and hiding relevant information with another piece of paper, no flashy visual effects