Hardware build: CRC calculation 

Watching that complex math boil down to such simple logic operations was the most beautiful thing I ever saw

Dude. Do you realise how fucking amazing it is to see maths being used for something useful? Maths teachers can never tell you why you're doing what you're doing. It's just dull processes you memorise to pass a test. What a joy it is to see this!! Thanks

Just wanted to say that I'm glad you're making videos again! Love all of them!

Just amazing!!! I have never seen an complex topic been explained with such simplicity. I read about CRC during my college days but never understood it. Now after 15 years finally I am able to. Thanks a lot sir Ben.

This guy is awesome. How he divides all complicated systems to their simplest logic is marvellous

One thing I would add here is a "CRC" line. When it's held high, whatever system you have for reading the output would be disabled and the only thing that would read data would be the CRC logic. With that, you could also make a basic frame. On the falling edge of the CRC line, you know a frame has ended and a new frame will begin in some time.

Man, it's a real joy to see you uploading again... Thank you Ben!

Your channel is of very very high quality. I do project lead for living and the more i go thru life, the more i dream younger programmers be taught at least one-year course by you ) Logic and sense of it is what you do really well, and it is great ground to stand on for each programmer. Thank you for your videos and good luck, sir!

Always a delight when you upload!

What an awesome video, although I have to admint this complex math really hurts my brain. I REALLY appreciate this hardware version, seeing the LEDs themselves represent the values and corresponding to the computing/computed value in bits was simply AWESOME. It really did explain a lot.

I have been working on ethernet for 8 years. And written crc computation functions.. but this is truly amazing.

So... What you're talking about is pretty similar to how you do integer division on computers that don't have hardware divide/multiply functions. Division is harder to understand than multiplication, but it still comes down to repeated application of shifts and subtraction. The algorithm for a shift + subtraction version of division looks something like this: - Shift the 2nd number (divisor) to the left one bit at a time, until you reach a 1, which means you've shifted far enough. - Along the way, count how many shifts you did to get here. (depending on how your hardware handles loops, maybe add one more, maybe not) - now loop through as many times as you just counted. Each time you shift the left-hand bit out of the 2nd number (divisor). If it's a 1, you subtract the 1st number (Dividend) from the result, and count up by one (typically you need to store a working value for the result, and working values for both the 1st and 2nd number - unless you can safely use the input values directly for this), if it's a zero, you do nothing. - Then you shift the 1st number (Dividend) right by one position, and continue until you've gone through everything. - your result, since this is integer division consists of the integer portion, and the remainder. The integer portion is the count of how many subtractions were performed, the remained is your working value. I've probably made some kind of logical error here, but since I'm working from memory, I'll leave it alone. Hopefully you get the general idea.

This educational content is just out of this world !

Junk Mail says it all.... or rather he doesn't say it .... which is the appropriate response when one is in awe. Oh, I am 68. These videos on parity/CRC have left one seriously considering throwing away the PC and buying a crate load of 7400 chips to construct a circuit for each and every algorithm. Such a change from C++!

Great stuff there Ben, each second was captivating and kept me thinking with all this grade and money making race a lot of top tier institutes are failing to teach all this. Would love to see an FPGA implementation of this...keep it coming sir!

That's cool! I've done OR gates with diode logic but never known how and AND wold be done.... thanks for that.

Possibly add a little info to the description about who INVENTED the CRC (en.wikipedia.org/wiki/W._Wesley_Peterson). I mean, hats off to the guy who figured this out from first principles!

Me: That's a simple circuit, maybe I can try to make one Ben:(Math math math math math math) Me: Okay I give up

Hi Ben & viewers, Just a quick heads-up - the website you went to no longer returns the same CRC as it did in your video. The parameters for CRC-16/XMODEM are still the same, so I can only assume that at some point a bug was introduced. I spent a long time comparing my code to yours, only to find out they were exactly the same, and gave the same answer.

Your Arduino may have wanted to initialize the flip flops in the shift register to 16 0's on the transmitting and receiving end prior to sending or receiving the message and you wouldn't need to constantly manually reset the registers with a wire. This would have been a simple init loop identical to the one which was used to set the last 16 bits to zero when you began the video. Doing this would have made it easy to fill different patterns into the register and test CRC variants where only the shift register seed is non-zero. Zapping to zero manually as you have done precluded an easy demonstration of various seed alternatives.

I haven't seen XMODEM since the BBS days :)

This algorithm is genius! People who can imagine solutions this eloquent should be knighted.

I love your videos, and I'm glad you started making some again :) Thank you!

God, I think I actually understand this! Well done as always!

Very much inspiring! Thank you.

You could've used an or gate that ORs the output of the Arduino and the CRC checker, instead of using additional data lines. It would have the additional benefit of resetting the crc calculator. The AND gate to disable the calculator seems unavoidable though

RU-vid didn't tell me you had a new video.

Fantastic video

Thank you for your brilliant videos. Cheers!!

Sounds like somebody got a new keyboard!

This is so good! Thank you Ben!

I don't know, i much understand practice than theory, thank you

Love this video! Did you forget to list the diodes in the hardware list?

Thanks a lot for this video. How does this logic translate to the lookup table method calculation of crc? It is not clear how xoring the new data with the crc gives us the index for the lookup table with the new crc value.

So beautiful .

Where were you when I was doing my Electronics studies. I feel like I want to redo my BSc.

I would have taken a spare output to automatically clear the register at program start.

The "looks like we're doing a bunch of subtractions" at 3:05 confused me. As you also mention later, these are XORs, not subtractions. 010010000110100100 - 10001000000100001 would equal ----------------------------------- 00001000110000011 which is not the same as 010010000110100100 ^10001000000100001, which would equal ----------------------------------- 00011000110000101 So I'm not sure I really get it. Why is it you say subtractions? EDIT: Is that related to what you said at 20m50s in your earlier "How do CRCs work?" video? And to what you said there at 24m38s, etc.?

A little late to the game here, but was re-watching this and it occurred to me if you XOR'd every flip-flop and AND'd between the flip-flop 16 out and the XOR in, with the AND input 1 being Flip-Flop output and input 2 being controlled by code, you could have the hardware support any generator polynomial of the same CRC length. Is something similar to this built into chips with the firmware controlling (or exposing to code) the generator polynomial?

Sorry, but was there a reason to not use the fourth xor gate to toggle read mode of the crc circuit?

On paper, t(x) is supposed to be m(x) - (m(x)modg(x)), but your hardware seems to use t(x) = m(x) + (m(x)modg(x)). Why the discrepancy? And why does your circuit still work?

Hey man, why don't you just OR the output of the Arduino and the CRC and send that to the receiver? The Arduino output is low during the CRC transmission and the CRC output is low during the data transmission. That would simplify things.

Totally awesome

5:08 "So this x^35 got flipped off" can relate

I have to admit, after 42 years being a MSEE, your videos are truly works of inspiration. You are, most likely, one of the very best in the explanation in hardware and software of complex systems and how they work. Your simplification of concepts is just perfect. Thank you for all your videos. Please continue with these videos. I look forward to each and every one.

I'm 70. Refreshing AND Breath-Taking..... Oh wait, I still need that.... :-) Thank You So much I can't verbalize it. Keep it up!

"Hella, world!" ... could not have planned that

Absolutely awesome series Ben! This is the way electronics and engineering basics should be in college, breadboarding at its finest with detailed explanation all rolled into a practical example. What a world of difference this could make for the engineer to be that so rarely occurs when in school. I love it, and I haven't had digital classes since 1985! Tip for the kiddies: keep your breadboards on a 2D plane and try not to go full 3D …

20:18 This reveal was amazing, seeing the circuit and suddenly realising how elegantly it implements the algorithm. Nicely edited!

It would take a couple of days (if not weeks) of re-reading from whitepapers (or books) for me to grasp what CRC is. But in less than an hour, now I have a solid understanding of what it is, how it works, how it can be implemented. And I'm entertained all the way through. If only every college had at least one teacher like you, world would be a different place! :)

Hey! I was just playing around with the CRC generation and found a simpler and faster way that eliminates sending 16 zeroes into the crc generator. What you did was: 1. initialize with zero 2. feed message[i] into the right side 3. crc-flip based on crc[leftmost] 4. repeat until message over, then feed 16 zeros If you replace that algorithm with: 1. initialize with zero 2. feed 0 into the right side 3. crc-flip based on crc[leftmost] xor message[i] 4. repeat until message over, done. no 16 zeros needed. This works because you basically skip the 16 first steps of your algorithm, which only fill up the pipeline without any bit flipping. You could bypass that step. The message itself doesn't have to get fed through the pipeline. This has the advantage that there is no waiting time between the message and the crc sending, after sending the message you can directly send the crc. Love your videos, keep making them!

IMO it would take a few attempts at making public content for a person to appreciate the weeks of time and effort you've put into this. I don't care how long it takes you to upload something new. Your results are amazing, relevant, and timeless. The only thing that should change is how YT categorizes this channel's content. This is relevant to everyone interested in learning electronics, and it will never become dated. These fundamental core concepts will be just as important decades from now as they were decades ago. No one does a better job of breaking up these concepts to create intuitive and easy to follow lessons anyone can appreciate. I'm sorry that I feel like I need to watch these uploads with my full undivided attention. This usually means I watch an upload in parts over the course of a day or two. I doubt YT compensates for viewer metrics like this. I'm even worse about skipping around within a video while building some of these circuits myself. I imagine people like myself cause the channel viewer's statistics on the back end to look a bit screwy. I just wanted to say, those numbers are probably not a real indication of how some of us are watching :-) I hope you enjoy doing these and can keep them coming for as long as possible. You're a real inspiration, and a talented teacher. Many thanks. -Jake

*has an arduino* *calculates everything with logic gates*

The explanations are so good that sometimes we don't even realize that the video editing is also superb

Your notification is something rare that makes me happy everytime I see it. Keep uploading this content man, your videos are amazing!

I stopped watching a different video when I saw the notification pop up. :3

Incredible work :) you really explain things perfectly well

So amazing to see an algorithm I always use implemented in hardware! As a suggestion, you can hook up the FFs clear pins to the Arduino reset pin, that way when you press the reset button the pin will go to GND (that's what the button does on the PCB). You also benefit from the free pull-up that's on the Arduino board :)

This is inspiring me to build a CRC-16 generator in Minecraft this weekend. This is going to take a while. Edit: a shift register with some XOR gates isn't too difficult and took only like half an hour to lay out and test. Making a wireless communication system that generates a CRC-16, however, would take all weekend.

It is a bad idea to use Arduino Pin13 for input, because while bootloader is working Pin13 is OUTPUT and this conflict with XOR output. 1K series resistor after XOR is OK, but better avoid connect Pin13 to any push-pull outputs.

I work in an industry where I need to understand CRC, FEC, parity, etc. This is by far the coolest, most thoroughly and concise explanation of this material I have ever seen. It makes me want to grab a breadboard and start exploring this side of the coin. Thanks!

I really loved this series. Once I started, I was on the edge of my seat waiting to see how error detection would get better and better. Really amazing seeing the idea on paper and then transformed into an elegant circuit. Thanks so much for making these videos and explaining every step in such detail!

Always impressed with your skill at explaining things. That simple trick of covering half the XOR truth table was vastly better than my last attempt at explaining it.

Absolutely brilliant, its something that's confused me for a long time, made very simple! Have you any interest in doing forward error correction?

Woohoo! A ben video! I saw the bell and knew my homework was going to have to wait ;)

You are a good teacher. You do a great job of breaking the problem down into logical steps that are easy to understand.

I learned field algebra laws in my university on Software Engeneering cource. I might even see a XOR algebra as an example, but matrix algebra took more attention. This is the first time I see XOR algebra is applied to a real world problem. And this is such a pleasure to watch how theory you knew is getting common sense to exist. Your course about 8-bit PC was inspiring and helped me to fill the gap between adder (summer) from school and assembly from university. Now you remembered me how much I loved math while it was appliable, and I hope inspire to learn some high math again. Beautiful channel, thank you for your work!

Can't understand how you do to make people understand electronics that easily, myself I am not particulary focused on the video and still I understand everything you explain. Thanks, keep going (Hello from France by the way)

Excellent Video as always... But the read of the crc result into the Arduino feels a bit “meh” to me... You actually don’t need to read the crc output into the Arduino. Instead use an AND gate and crc output and crc read as inputs and then OR the result with tx data. And since you are not transmitting anything, when generating the crc, you could pulse the clock for the 16 zeros much quicker (as fast as the chips can handle, probably MHz...)

If I remember correct (I might be wrong), you don't have to shift in the 16 zeros at the end making a total of 40 shifts. You could get away with only 24 shifts if you modify the CRC circuit. Don't ask how. :-) I do indeed prefer Bens way as it explains the math perfect.

Thank you for your explanation of the columns in CRCCalc! I thought it was a bit off-topic for the video at first, but now I've successfully matched my CRC calculator to that website, now that I understand those columns. It's unfortunate that CRCCalc no longer shares their source code.. Also, I'm surprised that your hardware implementation didn't involve a table..! It's that same simple, infinite-length polynomial division.

I love your notification 🔔 😍😍

Gotta flip those bits

5:05 "This X^35 got flipped off" Yeah, I've done that many times while doing algebra as well

I don't get this black magic.... Edit: I kinda get it now.....

Pretty sure you could have gotten away without the diode toward the Arduino in your makeshift and, you could've set the Arduino pin away from output so it doesn't interfere.

I never really understood CRC until I watched your video. I can understand how early days you would calculate CRC in hardware and then send it along after the message. But after watching you having to add so many read/write pins for clocking CRC hardware separately, then reading CRC using a read-enable pin, I'm thankful I always got to do the CRC calculations in software (didn't understand them, just 'cookbooked' it) :)

200 years later... Finally! I love your videos, so clear, interesting and actually funny to see

Stop flipping things off... sorry,, had to make a joke. Couldn't a particular logic gate setup, just one design, do the check and also create it

Now we just need a video for how the receiving computer can fix that error. Great video!

I really enjoyed this video, and you gave some really great tips too! Thank you for your hard work, and keep up the great videos.

you could have also used some transistors to only send clk to the shift registers and only connect the crc output to the tx line that way there would be no gap in the transmission, although the transistors might distort the signal a bit

Wouldn't it have been easier to AND the data input for the CRC unit with a pin? Instead of having two clocks. You'd then set the pin to 1 when you want to input your data to the CRC unit and 0 when not

Would you explain your selection of HC family? I've got LS and HCT families but haven't considered HC family.

This video was the first one, that gave me a deep understanding of how CRC's work and how to compute them. I really appreciate that you put this amount of effort into explaining everything and building all up from scratch.

With regards to the conclusion of this video (which points out the similarity of CRCs with parity checks) -- Why is it called "Cyclic Redundancy" check instead of n-bit parity, or something similar? What is the "cyclic" thing? And what is "redundant" here?

33:19: Wait, did you just build an AND gate from scratch? Could you also build all the other fundamental logic gates from only passive components? Would it not belie the active/passive component distinction if you can press diodes into transistor service?

Could you simplify things a bit by clocking the CRC directly out of the CRC generator to the data line to the receiver? You'd still need the /READ signal and you'd have to be able to switch the data line from the Arduino to the CRC output, but that would eliminate the need for the Arduino to read CRC bits (and it would eliminate the "pause" that happens during that time).

Excellent work Ben, really wish these vids were available when I was learning computing.... keep up the great work...

Next video, receiver ack/nak?

could you do something on ECC, perhaps?

man your circuit wiring is so neat. i remember when i was using bread board none of my circuits were this neatly wired all of them were so jumbled that retracing my circuit was a nightmare for me. Whatever might be the case please keep up the good work.

Absolutely brilliant. As a Comp Sci graduate I have to say your stuff is like a blast from the (very distant in my case) past. The only thing I'd add about CRCs is that fundamentally although they confer a good degree of confidence in the correctness of a message, they still allow for a 1 in 65536 chance of passing of a mangled message . For a high message noisy environment, this could (and certainly can be) problematic.

It's so easy when you have a clock signal too. Clock recovery is half the fun.

Amazing error detection series, came here from your 8-bit breadboard computer videos and will continue with that now too!

This is an amazing set of videos. I wonder if you'd do a follow up introducing the elimination of the clock line. Perhaps using Manchester coding and cover the timing issues with the xor on the generation side and a suitable clock recovery technique?

Nice video, I really liked the bit fliping circuit, very clever! I have one doubt though. When I saw the chained D-flipflops, it was not clear to me why the entering signal was not propagating direcly through all of them on each clock pulse. I watched the D-latch video, and in fact I saw that when the enable is active the output follows the input, at this point I understand that if you chained several D-latches they all would've been set to the same state. Then I checked the D-flipflop video where the edge detectors are introduced, however I was still thinking that this propagation issue could happen. The explanation I'm thinking of is that there's a propagation delay so that the D-flipflop can be "storing" a new input while the output is still the old one, and that the clock pulse is shorter than that delay thus disabling the D-flipflop just before the signal propagates through. Am I somewhere close to the correct answer? I'd like to better understand the behavior of the circuit, thank you!

Up next Reed-Solomon on a breadboard?

Holy fuck seeing that really complicated division problem turn into just repeated Shift 1 flip 3 over and over again is super crazy Also just a bunch of flip flops? CRC in Minecraft wen eta?

Thank you! these CRC videos are amazing! Is there a way to find which bits are faulty according to the not-null CRC you receive? Then you would be able to change the "receive" side program to remove the last two bytes and display "transmission error on chars #x and #y" if the CRC is not null