So we just have our clock and data coming in here, and we just have an ex or gate and a D flip flop.

And out the other side comes a parity bit that we can use to validate that our message was received correctly, or at least that certain types of errors didn't occur when we received our message.

But of course, the parity bit is not very robust.

There's all sorts of errors that might be injected into our message that apparently it won't catch.

And it's actually pretty pretty easy to inject an error like that.

And you'll see the parity bit is still matching on both sides, and so we haven't actually caught this error with parity bit.

So in other videos, I showed you things like check sums and see our seas that are much better at catching all sorts of different types of common errors that might occur in a communication network like this, but the downside of those is that they're much more complex.

So CRC, as we saw in the last video, the math behind that's fairly involved.

So we take our message, we converted to a polynomial.

We then divide that polynomial by this generator Palin UMA that we come up with and then that division, Uh, after we do all that long division that results in a remainder and then we subtract that remainder from our original message, and we get the actual polynomial the message that we're going to transmit, and then we can use the mathematical fact that that transmitted message is a multiple of our generator, and the receiver can do the math on the other side to determine if any errors occurred.

Now that's a lot more complex than our simple little parity bit here.

But what I want to do in this video is actually look at the math and a little more detail and look for some patterns that exist in this math that we're doing to calculate the CRC and show how we can use the patterns that are in here, too.

Actually distill this fairly intimidating looking computation into reasonably straightforward hardware.

Let's take a closer look at this process of computing the CRC and see what sort of patterns we confined.

So it all starts with the message that we want to send.

And so this here is the message we want to send.

And it's if we chuck this up in the little eight bit chunks, we've got an H there.

That's the ass Keefer in h.

R.

The binary representation of the asking value for an age that's an eye.

And then here we have an exclamation point.

So it's a chai.

A commission point high is our message, followed by 16 zeros and these 16 zeros is where we're gonna put our 16 bit CRC and that 16 that CRC comes from this Ah, Harry little division problem that we've got here and it comes from the remainder of that division problem.

So once we've done this whole division problem, we end up with the remainder.

Those 16 bits are the ones that we feel in here to complete our message, plus CRC.

But this whole division problem starts with the message itself, because the polynomial that we start with here that we're dividing is based on our message.

So each time we have a one in our message Here we have a terminar polynomial, and each time we have a zero in our message of the term is not in our polynomial.

And so that's what we start with.

And so how do we get from this polynomial we start with That represents our message down to this 16 bit value that is RC RC not as this process actually work.

Well, looks like we're doing a bunch of subtraction.

So each step along here were subtracting something.

So we start with this thing representing our message, and then we subtract something, and then we get something, and then we subtract something else from that and we subtract something else from that.

And we just keep doing the subtraction until we ultimately end up with her.

Searcy.

So what is it that we're subtracting?

Well, it's all multiples of the generator polynomial, right?

Because the way that we come up with what thing to subtract is based on the process of this long division that we're doing the first term here, we say, Well, how many times is extra?

16 go into extra 38 it goes X to the 22nd times, and then we take extra the 22nd we multiply it by the generator polynomial, and that's what we subtract.

It's another way to think of.

That is, if our generator polynomial is is this Exodus 16 plus X to the 12 plus X to the fifth plus one and we can line that up with the columns here.

But then we multiply this generator palomino by X to the 22nd which has the effect of simply moving at 22 places over to the left like this.

And so what we end up subtracting is a multiple of the generator polynomial.

And when we subtract because we're using this finite field, the result is that essentially what happens is each of these places where I've drawn these arrows essentially each of these places that lines up with the terms in our inner general polynomial.

We flipped the bit value there.

So if we have an extra 38 here, we flipped that, and we don't have it here.

So here the extra 34 term is not there.

And now it is.

We flipped that your ex 27 is there, we flip it.

And now it's not there.

Next to the 22nd is not there, and we flip it.

And it is the rest of the terms, Uh, stay the same.

So here, you know, these terms aren't there, and so they're not here down here.

Extra 30 plus x 29 or there they remain down here.

So we're only flipping thes four terms.

Then what we do is essentially you think of this sort of mechanically.

What's going on is you just slide this over until this exodus 16 arrow lines up with another term in this case, extra 35.

And then you flip those bits and you end up with this parliament down here is we just flip those four positions from this line here.

So this extra 35 got flipped off this exodus 31 got flipped on, um, and so forth for each of these two and everything else just stays the same, and then we just slide over to the right.

Let those four bits and we end up with a new polynomial here.

And then we could slide over to the right.

Keeps sliding.

Until this exodus.

16 lines up with a term and then flip those bits and we end up with another polynomial.

We just keep doing this sliding, flipping those bits, sliding, flipping those bits, sliding, flipping and we just keep sliding and flipping those bits until ultimately we eventually get to the point where we slide over.

And now Exodus 16 lines up with the exit 16 place we've slid essentially as far over as as we can.

So we kind of we've gotten all the way to the end.

And then we do that final flip and this polynomial.

Now that we end up with the bottom there, that's RC RC.

So is messy.

And as complicated as his math might seem, it's actually a fairly simple algorithm to get from our message down to RC RC of just lining this up here and then sliding over and flipping and sliding and flipping.

And we just keep doing that will ultimately end up with RC RC.

Now let me show you that same mechanics of sliding and flipping represented a little bit differently.

So here we have our message in binary, and then this is the generator polynomial and another way we can think of it with that same sliding and flipping sort of idea is we can slide our message along like this until the X to the 16 place lines up with a one.

And so we sort of keep sliding and sliding and sliding.

And so here we have zero, and now it lines up with one.

It's like, OK, now that that lines up with the one.

What we could do is we can flip each of those four bit positions.

So what I'll do is we'll use a little white out here to flip each of those.

So that becomes a zero.

This becomes a one.

This becomes a zero and this becomes a one.

And now that we do that, we can keep sliding.

So now we just keep sliding this until the Exodus 16 position lines up with one, and there goes it lines up with another one.

It's now what we'll do is we'll flip those same four bits again, and now that we flip, those four bits will slide again.

And now this exit 16 lines up with another one.

So we'll flip those four bits again, and then we keep going.

So slide over that's still a zero slide over and still a zero slide over.

And now we got a one here.

So we'll flip those four bits again.

And hopefully you see, this is a pretty straightforward pattern, so we can just continue to do this.

Slide over until the X to the 16 place, lines up with one and then flip those four bits and keep sliding and flipping and sliding and flipping until we finally get to the end and then we'll slide again.

Now this lines up, and at this point, we're now at the end, so we'll do one last flip another.

We're we're at the end.

We've done that last flip.

You'll notice that all of the positions from Exodus 16 to the left have all been zeroed out.

So that's one sort of property of this operation.

And then the last 16 bits should be our RC RC.

So let's compare that to our long division here, and hopefully if I did this right?

Yes, it looks like it.

It's looks like it's the same, doesn't it?

Right?

So that's our CRC and were able to calculate it just by this sliding and conditionally flipping these four bits.

And so those air fairly mechanical things that we ought to be able to do in hardware.

And when I think about that idea of sliding bits along, what comes to mind for me is something like a shift register.

And so this is a 16 bit shift registered.

It's just made with a bunch of D flip flops, all chained together.

And basically the way this would work is that we've got our data and clock over here.

We can imagine our data coming in like this, and if we have a date a bit, let's say we have a zero here.

When the clock pulses that zero will be read into that first D flip flop.

Then the next time the clock pulse is if we have a one here at the data input than that, one will get read into that D flip flop.

But also the zero that was in the first D flip flop gets read in to the next D flip flop.

Because all these clocks are chained together, are connected together.

And so if each pulse of the clock each new data bit will get read into the first D flip flop here, but then each subsequent data bit just shifts along down this shift register.

And so this gives us something very much like that sliding that we were seeing as part of our Searcy algorithm.

So it seems like this would be a good place to start us with a 16 bit shift register like this that we can read all of our data into.

And then once we get this working, we can start to think about Okay, how would we flip certain of these bits under certain conditions?

So we've got our transmitter here, and if we reset this, we can see we've already got the clock and data signals.

I'll set up here for transmitter.

And so those are those are going to the inputs to our shift registers.

We've already got that.

We've got a clock that's pulsing every time there's a bit and we've got a bit that's either on or off, indicating whether it's a zero or one.

So we're gonna have no problem.

As far as getting the inputs to our shift register.

We just need to build the actual shit register, and to do that, we can use the 74 HD to 73 which has eight of these D flip flops in here.

So we're gonna need 16 of them.

So we need two of these chips.

But but each of these little blocks in here is one of these blocks in our shift register, and we could just hook them up like I've got here.

And actually, I've already got one of those 74 h c 2 73 is here that we used because we did use one d flip flop for our parody circuit so we can actually re use that.

Let me actually get rid of some of the parts here for a parody, and we can reuse the same chip for RC RC.

And so the first thing I'm gonna do is actually hook up a bunch of led so we can see the contents of each of the D flip flops.

So basically, what I'm gonna do is I'm gonna connect the outputs of each of these d flip flops up to an led.

So the Q p in here just so we can see because each of these D flip flops is gonna hold A is gonna store a bit a zero or one, and so, by hooking led up to each one will be able to see whether it's storing a zero or one.

Then I'm gonna connect the other side of each of these ladies to ground through a current limiting resister.

Think this is just a 270 ohm resistors, something like that.

And as I'm hooking this up, it looks like some of these bits are on.

But I guess I would expect this sort of random data in the D flip club.

And so now I have connected the outputs for each of these eight D flip flops that air in this in this chip.

But, you know, we're doing a 16 bit CRC, so we actually want another another eight bits here.

So what I'm gonna do is add a 2nd 74 80 to 73 Chip, um, over here and add another eight l E D's.

I could use a jumper here to connect my clear pin to ground momentarily, and that clears it.

Okay, so we've got our 16 d flip flops here, Um, and they're hooked up to led so we can see what's in them, and we've even got our clock hooked up.

That's this white wire that's hooked around here.

And so now what we need to do is hook our data into one of them.

I guess we'll do the one on the right here just so everything kind of makes sense and then hook the outputs of each one into the inputs of the next one.

So that's what I'll do next is just hook up all those outputs and inputs.

Actually, before we do that, there is one thing we contest, which is, uh, just hooking the data into the first flip flop and just verifying that that works.

So I'll just disconnect the data signal here.

That was we were using for parody.

And then I come to connect a jumper from the data pin or the data out of the Arduino into the input for the first full plop over here.