25 comments, 58 views, 21 likes, 0 dislikes. So I'm fairly early in the viewing. I'm so Damn impressed. I'm 70, a retired Electrical Engineer, and had glancing contact with CRC back in late 60's early 70's, and figured I'd get back to clarifying it to my satisfaction later on in my life, as time allowed. I long ago forgot that "promise to myself", and thru disuse, long ago lost the discipline of the required regimen to reconstruct the required elements, to then reassemble. I ramble. I AM SO PLEASED, to see with such clarity, as pure as the resonance of the ringing of a bell. It is as an epiphany. Thank You So Much, for the intense effort and discipline, you've achieved. I REALLY ENJOYED YOUR PRESENTATION, have seen some , and expect to witness many more of your videos. They are quite refreshing, and a reaffirmation of many of my previous studies. At my age, what a joy. Opening so many new refreshing avenues of research. Keep up the good work. Thanks.
My Dad has a similar background (and age). I've been thinking of sending him this playlist's link and some description (as I've been *adoring* it). Seeing your comment I decided to just do it now, and the description is mostly a copy-paste of what you've written.
24 year old electrical engineer fresh out of school here, what I like about Ben's videos is how accessible and engaging these lessons are. Exactly like you said sometimes I've found in school that I make "promises to myself" that I will learn this material better once I'm out of school and that right now I just need to memorize answers so I can pass. But I've been watching these videos for the last four years and they have really helped me stop and take the time to dive into the required elements like you say. It's made me feel much more secure about my skills in the embedded systems/comp arch world and the ability to dive deep like this was critical in getting through grad school. I'm glad his videos can do something for anyone no matter what their experience.
If you have already seen the video but you want to review just a part of it (say, you are building a project which uses a CRC): 00:00 - Detecting errors with modulo division 10:51 - Message data as a polynomial 16:41 - Finite fields 22:57 - Polynomial division 31:04 - Sending and verifying CRC 36:29 - Choosing a generator polynomial
Paolo Lucchesi Fuck me just when you see smart guys like Ben breaking things like a genius down so I understand, he mentions professors that sit around all day finding the best generator polynomials vs overheads vs message sizes. Incredible stuff!
I'm not an engineer, I have no plans to build low-level computer hardware any time soon, but I look forward to every one of your videos. You have the spectacular ability of making complex concepts less intimidating and more digestible.
Ben, this is a real good video on CRC, I used CRC-32 multiple times in software, and relyed on some 3th party implementation to construct or validate it, but I never understood why it worked. Thanks you very much and I cannot wait for the next video to see the ex-or in action. Jeroen.
I started my career as a communications technician in the late 70'sand became a communications programmer in the early 80's. I've worked with crc16 and crc32, but never knew the details at this level. I always relied on either the hardware or canned software to do the trick. Thanks for taking the time to explain this. I always wanted to understand the details. I remember trying to read a paper on the subject. It took me a while to realize that this paper was so verbose as to start off by taking 3/4 of a page to explain the mathematical concept of a bit! (He must have had a word quota). I got frustrated and gave up. Thanks for explaining this in a concise way I can understand. Now that I'm retiring and playing with Arduinos, I'd love to see how you do this in hardware. Thanks again!
Your three spaces between sentences is messing with my head... One is internet standard, and two is a common holdover from typewriters and stuff, but where on earth did you get three from?
@@kaitlyn__L double spaces between *words?* If you want more space between words wouldn't you just make the "how much the typewriter moves on the space key" space bigger? It seems excessive to have to press a button twice between every word, you are adding no new information with that extra press if you do it every time
I'm 62 years old telecom engineer in Helsinki, Finland . When I started my studies in U in 80's my major was mathematics. Because I was using computers at home to amuse myself and using communications over phonelines first to local numbers but trough them to more distant computers I started to focus my studies more on computers. So I changed my major to computer technology and quickly realised that what happens within computer is kinda boring, but what happens when they communicate with each other is fascinating. So I changed Us and majored in telecommunications. Through out my studies I tutored my fellow students in math. Modular arithmetics eg. finite fields was always the big question how they work. I always used the clock as an example. When the lecturer wrote those x-polynomials and calculated with them I always changed the x's to a, b, w or what not when I explained the things so that they'd understand that it is just an abstract that is used to make the calculation work.
Besides being great explanation, I really like how you used pen and paper instead of computer graphics and animations. It adds sentimental value to video.
Hi, my name is Neil Harrison and way back in the 1980s I was an engineer working for BT. I created the CRC4 frame/mult structure for the 2.048Mbit/s transmission system that became a CCITT standard in G.704/706. Did all the modelling work on a BBC Micro. Seems a long time ago now. Amazed how it lasted. Been retired as a engineer for about 9 years.
Just started a new job where we implement a lot of CRC checks, so was great to watch this video and fill in missing areas of my knowledge. Huge thanks!!
This video just lit up parts of my brain i have not used since graduating year of high school, then i got a headache. Thank you so much for this video and others in the series, I have always been confused on how checksums, CRC and ECC actually work, really only paying attention to what they provide to my work. I've been in the IT realm for 20 years now and have always been ashamed of my lack of understanding of how most of the low-level components operate and the sheer brilliance in the engineering of it. Your videos are a massive asset to help me get my head around these concepts. I just hope that the crowd touting the likes of "AI" and "machine learning" take the time to understand how the low level machine enables the garbage that they talk. Thank you! I will be blowing the dust of my Arduino kit and playing with some of these things again as time permits. Thank God for the likes of you and Mr. Carlson and so many other great content creators!
I truly wish I had this channel when I was younger. The concepts and seemingly esoteric knowledge that you just nail down with simple examples is almost annoying with how obvious it is, having been confused so much by it. Absolutely amazing teacher and I am so tempted to buy your kit and start making my own computer, because you make it feel entirely attainable.
You have the gift of deconstructing complexity into triviality. A great teacher! Wish I had classes like that back in mid school... Well we all can have them now. Thanks a lot.
Amazon video! However, I think many ppl who aren't in touch with abstract algebra can find this overly confusing because of the field we are using. The main reason it's confusing is because it looks that the field follows random rules. It is actuslly just a mod 2 field or a xor field which makes it much easier to think about. Anyway great work!
Wow, I’ve gotten so dumb in my old age. I’ve had delusions of retaking the three semesters of 200 level calculus, but no way. I’m gonna have to start all the way at the beginning with algebra. What a great presentation, Ben, this is great work. I had an epiphany when you coverted the binary message to real numbers to show how the math works to reconstruct a message at the received end. I always considered the binary math with hesitation and suspicion , but when you did the math using real numbers, my brain went “oh, yeah, of course THAT math works reliably at both sides!” Now that I see it’s not only possible, but that it HAS to work, I just need practice. Lots and lots of practice. One more bucket list item is to order your breadboard kits and follow along all your marvelous labs. Chuckle, maybe then I won’t still be intimidated by actually learning to program on my C64.
For my senior design project in CE, we had an app communicating with a microprocessor using a Bluetooth module and our information would at times be sent incorrectly. We had to use a CRC to check that our data was being transmitted correctly and use the Stop-and-Wait ARQ protocol to send acknowledgment checks so that our information was transmitted and received correctly. It took such a long time to understand how CRCs work because the math was very convoluted. I wished this video existed then!
In our Networks class we studied CRC. And in Network Security class we studied about finite field theory. This video was much more intuitive than two regular courses at college. Thanks for your effort in simplifying the mathematical rigour to an understandable level for the common populace.
I can't really improve on Junk Mail's comment. My experience has followed his, almost word for word. Maybe the fact that our ages are only 2 years apart is a factor here; though a was a chemical engineer with just an amature interest in electronics and programming. The other common factor is that we have both just finished watching a video by a truly gifted teacher. Thank you, Ben.
This is by far the best math class I've had in decades. You don't speak slowly but you explain it thoroughly. You really know what you're talking about, and all that preparation with the math on paper really helped. Thanks!!!!
Hi Another well presented and explained video, in the late 80's i had done some pascal code, one of the sites had 2400 modems to warehouse and dedicated lines ( gov department) I could not guarantee serial transmission, and ended up discussing with other in the telco industry and they recommend using of the shelf comms programs, but the contract terms of the project forbid it as they wanted fresh hand coded and the source code to be theirs So it was 80% complete and workable, in discussions about the next step eventually i said - i can re-price the job down and give you all the workings for stock transfer / accounting / interface is all done and it works stand alone and via serial port to the 2 local (on site but 600meter away ) remote warehouses the comms is working but no error checking for long distance / line loss I was allowed to buy some external pascal code to use as a module for the crc error checking, used that and problem solved, the purchase of the module was cheap enough ( say 3-5% of my overall charge ) The issue was basically the long distance charges for the dial up and in organizing efficient / optimal packet size for the crc to stop resending large packets again and increasing phone charges There is a science to speed and pack size
Just like any subject of DSP, the math is hugely involved, but the implementation is simpler. I had been using CRC function on different microcontorller for so many years, the math behind the CRC is aptly explained here. Thank you. BTW, I had also realized that the CRC polynomials are determined after lot of reseach and that is another subject all together. Fortunately, mundane creatures like me are happy with usage of CRC. Thanks for the video.
For anyone who is confused by how the addition rules of the finite field translate to the polynomial expression: You can think of the polynomial as a vector (with some additional properties), where the powers of the indeterminate represent the independent entries of the vector. The video on abstract vector spaces in the linear algebra series by 3blue1brown explains why this is the case, if you're not familiar with the matter. Then the polynomial addition (or subtraction) is nothing more than vector addition. But in this case it is addition according to the adding rules of the finite field. At least to me this view makes it clearer why each component can be added independently and there is no carrying over.
This one of the best lectures on CRC on the Web. It explores the fundamentals and slowly takes u through all the steps to the final phase which is the construction of the Generating Poly. Even though the lecture is on paper and not some fancy ppt presentation but the presented material is to the core and very valuable, I am impressed by the step by step, hand calculation, sequence of the presentation, topics covered, Q&A that come to mind. Looking forward to the bext lecture of HW implementation of shift/XOR operation to perform the divisin. Thank u 🙏
Excellent explanation. Wish our university math professor was that clear 30 years ago. But since he wasn't I had to figure out that all those polynomial operations are just shifts and XORs in disguise myself, which was probably a good thing. OTOH, I never understood why you would use something complicated like polynomials instead of something simple like bitstrings. I put that down to mathematicians just using what they are familiar with. But now I see that proving properties (like the maximum length of a burst error that can be detected) is easier using polynomials. So another insight after 30 years :-).
This isn't merely an excellent deep dive into one of the most important algorithms in modern computing, but such depth in a RUclips video they got so many views reminds me that there are still intelligent, curious people.
During the early part of my career I was a hardware tech so I attended a number of classes where the instructor would attempt to explain redundancy checks by tracing through logic diagrams. On something like the error correction logic for reading a disk track this was near impossible. This explanation clears up the questions I always had but never answered. Since I never saw the hardware in this area fail it wasn't a problem but now my curiosity has been satisfied.
I came here to watch some arduino systems transmit data and suddenly BAM! I'm back at the uni again. The only difference is (contrary to my professors) he makes it easier to understand. Well explained. Earned my sub. Keep it up! Peace out
Speaking as someone who has no proper credentials to be watching your video, I found it very understandable. And, as much as I would like to pat myself on the back for being so clever, I'm posting this note to congratulate you on an outstanding explanation! Nothing but net!
A rigorous definition for fields actually demands that all of the multiplication rules are not defined for 0. How 0 behaves in multiplication then only follows from the distributive law (i.e. 0•anything = 0). If you know about groups then you can think of fields as being made up of an additive group and a multiplicative group connected by the distributive law, where the mutliplicative group doesn't contain the neutral element from the additive group. Everything else from the definition in the video is correct.
Thank you for the well prepared walkthrough..! Trying to write a software implementation, I read many guides online, tested different calculators, heard of all the terms around CRC, and it only left me wanting to shoot all the guide authors... You instead started from the beginning, stopping at the problems that resulted in CRC's weird traits.. I also wondered why mathematicians would come up with this fringe thing, but you showed that it's actually pretty general and super powerful, so their involvement was justified.
Excellent. I have had a basic understanding of CRC for over 40 years (300 baud modem days), but under understood the black box details of how it works. Thanks
Definately one of the best and most easily understood explanations I've heard. Bravo. Understanding the detailed math isn't essential. The concept is, and explained very well here.
Although it's long, I could watch it without any skipping or altering the playback speed. Now I feel like I fully understood CRC and can even apply it to different situations. Helped me a ton studying for my course. Amazing work!
Yhup! - you know there's no hiding that there's chunky maths in it from the slide at 0:35 (generator, fields, modulo, polynomial) but if I hang in there for 45 minutes plus re-plays, I know there's already a circuit-board implementation to look forward to in the next video. I've been hearing these terms and feel I #ought to# be able to understand them at face value [with some discrete maths background] rather than with a hand-wave over, "you spin it round and do a checksum (of sorts)". I trust you, Ben: commence the brain-dump!
Holy shit, you did a really good job explaining this, starting with simplified and generalized concepts slowly building up to how it's actually done and do a real world example.
Dear Ben, Impressive, what an explanation. Thank you very much for this amazing video, I'm subscribed now and will check your videos as I can. I'm a network engineer trying to fill all the gaps I, as Mr. Junk Mail promised to ourselves would do. Most of these missing pieces are details, so it takes much more time to find the information about it and then fully comprehend it, making it really difficult due to my daily activies. I invested both my days off for searching, refreshing long forgotten math concepts as it was required, practicing on paper just to get a blurry approach of how CRC works, how are the generator polynomials selected, if they are sent to the receiver, if the receiver already has the polynomial beforehand, etc. I was so close to give up for the week, all ready to go work and forget about it slowly overtime. I can't thank you enough for this, but there is something I can do. You can count on me watching your videos and recommend them to my coworkers who also seek to strengthen their knowledge. Regards from México.
We'll that's something I never knew I wanted to know. Now I do thanks to someone spending a ton of their time making a 47-minute-long video. Awesome! Thanks!
This video was hands down the best explanation of finite field I've ever seen. Not to say that my university professors are not impressive or anything, but sometimes explaining things just weren't their forte...
I really liked this video. I too am an electrical engineer and i've used CRC some times but never took the effort to see why it works. Thanks Ben. I wish you were my professor
This video is a gift! CRC is one of those concepts we all use but never stop to ask how it works, and why. I'd absolutely love to see a video from you on Reed-Solomon codes as used in CDs.
This is a really good video. Everything is explained clearly and patiently and I only had to pause at the monstrous polynomial division. I'm really happy to see that you continue to do these videos
20:51 i don't know if mentioned but well at the top right thats equals to the truth table of an XOR-gate (That to the right as well). And that below equals to the truth table of an AND-Gate EDIT: okay well to be fair: you have to "forget" the multiplication, addition, etc. and you have to take each value as an input EDIT 2: well you said it at 28:50 but well im proud that i at least figured that one out by myself
I was looking for something like this a few weeks ago. The structure and clarity of your explanation is remarkable. I look forward for the HW implementation video.
Back in the UseNet days, a parity reprocess was pretty much needed for large binary posts. I always thought the QuickPar .PAR2 rebuild process was one of the most ingenious and advanced engineering inventions ever. The way it could take ANY location of a 2 GB file (example) that was corrupt in ANY random spot, ... all you needed was a set number of PAR2 blocks to rebuild it. The idea of being able to rebuild any number of corrupt sections in the fileset was mind boggling. You could also rebuild entire lost segments. To this day, I do not fully understand how the Reed-Solomon algorithm EC worked to repair usenet sets. As long as the author published a set of PAR2 repair blocks, you could fix anything. To be able to fix an error in a 2 GB file, with a small 5 MB parse block was ingenious, and it had to work similar to how CRC worked, but on a much broader scale.
Reed-Solomon relies mainly on having a large enough size of signal bits versus data bits, that instead of the maths you just have a lookup table of valid byte codes. Anything invalid is then assumed to have intended to be the closest valid one (massive over simplification but I assume that’s what the “repair blocks” contained, the valid codes). For instance CDs use 14 bits to encode a byte, with the valid code words arranged in a particular geometric way through the possibility-space to keep the distance between them consistent. So quite large errors can still be recovered (and CDs use further techniques on top, interleaving, duplication, etc so all in all you can lose about a fifth of all the signal but the data will still be recoverable).
Well explained and better than any lectures about information/coding-theory during my studies! Furthermore links the topics (algebra, fields, polynoms) with practical use.
Fantastic video! Even though my professor mentioned CRC in her class, I still feel the CRC she taught is not clear enough for me. Then I find this. Thanks.
I had a question, but got it afterwards. I'll explain it too in case it helps someone else: 30:53 Here it's said that the remainder is added to the original message - but shouldn't we actually be adding "the divisor minus the remainder"? So that the message then becomes a multiple of whatever divisor we had? A: See, by adding the remainder, since we're using that different field, this is the same as subtracting it. So essentially we're making the message a multiple of the divisor, by taking off the original message of its remainder.
I gaven't even finished an elementary course in Linear Algebra and I just spent half an hour watching a video that talks about higher level algebra and computer science. Love it.
Awesome! I love how clearly you are able to convey this while using simple pen and paper. No over-fancy graphics and a very well thought-through structure.
This is a great video to highlight the importance of prime numbers in computing and understanding the value of them from a computing aspect. Greatly appreciate seeing an underlying hint towards primes!
Congratulations Ben, You have single handedly explained the weird math and rational behind the complex operations that take place with such ease. Loved and learnt !!!
Ben, this is so well done - I could listen to you for hours. Thanks for this fantastic video that helped me brush up the math I needed for implementing some of the firmware/embedded tasks I've been doing at my job.
Ben, the best think about your videos is their detail. I appreciate you taking the time to share your knowledge. I have watched every one you have made multiple times.
I knew that mathematics was important in computing, but this video really highlights how important it is. Fantastic video, very complicated but very well explained. Thanks for your efforts, you aren't just sharing knowledge
I noticed a clue in there as to how error correction can work. Something about knowing the received content and the divisor enabling you to reconstruct the original message? I'd guess that an expansion of that is what allows a corrupted received message to be reconstructed, so long as not too much of the message has been damaged? Of course this is beyond what a CRC could do, but it appears to be an expansion on how the CRC works? Edit: Also, it seems that I'm now coming to understand what a polynomial is, in spite of never learning about them in school (left too early - thereby lies a sad story totally unrelated to the video).
30:23 Your magic X16, x12, x5, x1 is all bits zero except the MSB and the LSB which are 1. It then moves to MSB-4 and LSB+4 and makes them 1. But it quits there. It doesn't move to MSB-8 and LSB+8. At this point we get X9 and X8 (i.e. adjacent bits). I wonder why? I will probably have to remove this comment by the time I get to the end of your presentation. However, your explanation is better than I have ever seen in my formal education...or even read in the literature. Thanks (even though I'm regrettably coming to the party 2 years late).
![KSI - Dirty [Official Visualiser]](http://i.ytimg.com/vi/VoDh1h1dPUE/mqdefault.jpg)
25 comments, 58 views, 21 likes, 0 dislikes. So I'm fairly early in the viewing.
I'm so Damn impressed. I'm 70, a retired Electrical Engineer, and had glancing contact with CRC back in late 60's early 70's, and figured I'd get back to clarifying it to my satisfaction later on in my life, as time allowed. I long ago forgot that "promise to myself", and thru disuse, long ago lost the discipline of the required regimen to reconstruct the required elements, to then reassemble. I ramble. I AM SO PLEASED, to see with such clarity, as pure as the resonance of the ringing of a bell. It is as an epiphany. Thank You So Much, for the intense effort and discipline, you've achieved. I REALLY ENJOYED YOUR PRESENTATION, have seen some , and expect to witness many more of your videos. They are quite refreshing, and a reaffirmation of many of my previous studies. At my age, what a joy. Opening so many new refreshing avenues of research. Keep up the good work. Thanks.
Ditto.
@@donprefontaine3237 re-ditto
Similar to Junk Mail, I'm 60. E.E. (Not retired). This really is an exceptional piece of work.
My Dad has a similar background (and age). I've been thinking of sending him this playlist's link and some description (as I've been *adoring* it). Seeing your comment I decided to just do it now, and the description is mostly a copy-paste of what you've written.
24 year old electrical engineer fresh out of school here, what I like about Ben's videos is how accessible and engaging these lessons are. Exactly like you said sometimes I've found in school that I make "promises to myself" that I will learn this material better once I'm out of school and that right now I just need to memorize answers so I can pass. But I've been watching these videos for the last four years and they have really helped me stop and take the time to dive into the required elements like you say. It's made me feel much more secure about my skills in the embedded systems/comp arch world and the ability to dive deep like this was critical in getting through grad school. I'm glad his videos can do something for anyone no matter what their experience.
Ah yes, "what is x". A strangely profound question in modern algebra.
According to some of my teachers, it was the only question...
x = y - 90°
"a letter"
Because the coefficients of all the the Xs are either 0 or 1, why we do-not replace the X with the number 2?
@@adamlanghans lol
Probably the most comprehensive explanation for CRC on RUclips. Not only just how to do it, but also the reasoning behind it. Thank you.
If you have already seen the video but you want to review just a part of it (say, you are building a project which uses a CRC):
00:00 - Detecting errors with modulo division
10:51 - Message data as a polynomial
16:41 - Finite fields
22:57 - Polynomial division
31:04 - Sending and verifying CRC
36:29 - Choosing a generator polynomial
Paolo Lucchesi Fuck me just when you see smart guys like Ben breaking things like a genius down so I understand, he mentions professors that sit around all day finding the best generator polynomials vs overheads vs message sizes. Incredible stuff!
RUclips allows chapters now, maybe Ben could use them and make everyone's life easier.
I'm not an engineer, I have no plans to build low-level computer hardware any time soon, but I look forward to every one of your videos. You have the spectacular ability of making complex concepts less intimidating and more digestible.
Tobias Fried I’m no engineer but I can’t wait to build a low level computer to show my kids how it works!
Ben, this is a real good video on CRC, I used CRC-32 multiple times in software, and relyed on some 3th party implementation to construct or validate it, but I never understood why it worked. Thanks you very much and I cannot wait for the next video to see the ex-or in action. Jeroen.
XOR
I started my career as a communications technician in the late 70'sand became a communications programmer in the early 80's. I've worked with crc16 and crc32, but never knew the details at this level. I always relied on either the hardware or canned software to do the trick. Thanks for taking the time to explain this. I always wanted to understand the details. I remember trying to read a paper on the subject. It took me a while to realize that this paper was so verbose as to start off by taking 3/4 of a page to explain the mathematical concept of a bit! (He must have had a word quota). I got frustrated and gave up. Thanks for explaining this in a concise way I can understand. Now that I'm retiring and playing with Arduinos, I'd love to see how you do this in hardware. Thanks again!
Your three spaces between sentences is messing with my head... One is internet standard, and two is a common holdover from typewriters and stuff, but where on earth did you get three from?
@@leave-a-comment-at-the-door some people learned to triple space between sentences because they double spaced between words
@@kaitlyn__L double spaces between *words?* If you want more space between words wouldn't you just make the "how much the typewriter moves on the space key" space bigger? It seems excessive to have to press a button twice between every word, you are adding no new information with that extra press if you do it every time
I'm 62 years old telecom engineer in Helsinki, Finland . When I started my studies in U in 80's my major was mathematics. Because I was using computers at home to amuse myself and using communications over phonelines first to local numbers but trough them to more distant computers I started to focus my studies more on computers. So I changed my major to computer technology and quickly realised that what happens within computer is kinda boring, but what happens when they communicate with each other is fascinating. So I changed Us and majored in telecommunications. Through out my studies I tutored my fellow students in math. Modular arithmetics eg. finite fields was always the big question how they work. I always used the clock as an example. When the lecturer wrote those x-polynomials and calculated with them I always changed the x's to a, b, w or what not when I explained the things so that they'd understand that it is just an abstract that is used to make the calculation work.
Besides being great explanation, I really like how you used pen and paper instead of computer graphics and animations. It adds sentimental value to video.
he knows the truth. never trust computers. :]
Marko you might like "Diode gone wild" on RUclips also. He uses good ol' pen and paper too! 😁 Not a programming channel but great electronics stuff!
@@Bob3519 Looks great. Subbed.
As he said one needs to do it by hand to see the pattern :-)
Makes it more organic.
Hi, my name is Neil Harrison and way back in the 1980s I was an engineer working for BT. I created the CRC4 frame/mult structure for the 2.048Mbit/s transmission system that became a CCITT standard in G.704/706. Did all the modelling work on a BBC Micro. Seems a long time ago now. Amazed how it lasted. Been retired as a engineer for about 9 years.
Old retired software engineer here. Used CRC countless times but never really understood it till now. Great presentation! Thanks.
Finally! Another great video.. We really missed you a lot, Ben :)
Dammit, I've just watched a video about CRC?
And I understood it.
And I even liked it!
Damn, I am a geek indeed.
Neeeerrrrd...! I liked it too though! It's a nice feeling when you understand something new. :)
Hell yeah we are 😤🤓
Just started a new job where we implement a lot of CRC checks, so was great to watch this video and fill in missing areas of my knowledge. Huge thanks!!
This video just lit up parts of my brain i have not used since graduating year of high school, then i got a headache. Thank you so much for this video and others in the series, I have always been confused on how checksums, CRC and ECC actually work, really only paying attention to what they provide to my work. I've been in the IT realm for 20 years now and have always been ashamed of my lack of understanding of how most of the low-level components operate and the sheer brilliance in the engineering of it. Your videos are a massive asset to help me get my head around these concepts. I just hope that the crowd touting the likes of "AI" and "machine learning" take the time to understand how the low level machine enables the garbage that they talk. Thank you! I will be blowing the dust of my Arduino kit and playing with some of these things again as time permits. Thank God for the likes of you and Mr. Carlson and so many other great content creators!
I truly wish I had this channel when I was younger. The concepts and seemingly esoteric knowledge that you just nail down with simple examples is almost annoying with how obvious it is, having been confused so much by it.
Absolutely amazing teacher and I am so tempted to buy your kit and start making my own computer, because you make it feel entirely attainable.
You have the gift of deconstructing complexity into triviality. A great teacher! Wish I had classes like that back in mid school... Well we all can have them now. Thanks a lot.
Amazon video! However, I think many ppl who aren't in touch with abstract algebra can find this overly confusing because of the field we are using. The main reason it's confusing is because it looks that the field follows random rules. It is actuslly just a mod 2 field or a xor field which makes it much easier to think about. Anyway great work!
The quality of these videos!!!! Makes learning new things so fun! Love your videos ben❤️!
Wow, I’ve gotten so dumb in my old age. I’ve had delusions of retaking the three semesters of 200 level calculus, but no way. I’m gonna have to start all the way at the beginning with algebra.
What a great presentation, Ben, this is great work. I had an epiphany when you coverted the binary message to real numbers to show how the math works to reconstruct a message at the received end. I always considered the binary math with hesitation and suspicion , but when you did the math using real numbers, my brain went “oh, yeah, of course THAT math works reliably at both sides!” Now that I see it’s not only possible, but that it HAS to work, I just need practice. Lots and lots of practice.
One more bucket list item is to order your breadboard kits and follow along all your marvelous labs. Chuckle, maybe then I won’t still be intimidated by actually learning to program on my C64.
For my senior design project in CE, we had an app communicating with a microprocessor using a Bluetooth module and our information would at times be sent incorrectly. We had to use a CRC to check that our data was being transmitted correctly and use the Stop-and-Wait ARQ protocol to send acknowledgment checks so that our information was transmitted and received correctly. It took such a long time to understand how CRCs work because the math was very convoluted. I wished this video existed then!
In our Networks class we studied CRC. And in Network Security class we studied about finite field theory. This video was much more intuitive than two regular courses at college. Thanks for your effort in simplifying the mathematical rigour to an understandable level for the common populace.
As a CS student, this is an eye opener as to why we need those math courses that we often complain about. Excellent work!
I can't really improve on Junk Mail's comment. My experience has followed his, almost word for word. Maybe the fact that our ages are only 2 years apart is a factor here; though a was a chemical engineer with just an amature interest in electronics and programming. The other common factor is that we have both just finished watching a video by a truly gifted teacher. Thank you, Ben.
This is by far the best math class I've had in decades. You don't speak slowly but you explain it thoroughly. You really know what you're talking about, and all that preparation with the math on paper really helped. Thanks!!!!
Why must you continue to blow my mind, repeatedly? You are an excellent instructor. Wish I had you as an instructor when I was in VOTEC Electronics.
Hi
Another well presented and explained video, in the late 80's i had done some pascal code, one of the sites had 2400 modems to warehouse and dedicated lines ( gov department)
I could not guarantee serial transmission, and ended up discussing with other in the telco industry and they recommend using of the shelf comms programs, but the contract terms of the project forbid it as they wanted fresh hand coded and the source code to be theirs
So it was 80% complete and workable, in discussions about the next step eventually i said - i can re-price the job down and give you all the workings for stock transfer / accounting / interface is all done and it works stand alone and via serial port to the 2 local (on site but 600meter away ) remote warehouses the comms is working but no error checking for long distance / line loss
I was allowed to buy some external pascal code to use as a module for the crc error checking, used that and problem solved, the purchase of the module was cheap enough ( say 3-5% of my overall charge )
The issue was basically the long distance charges for the dial up and in organizing efficient / optimal packet size for the crc to stop resending large packets again and increasing phone charges
There is a science to speed and pack size
Just like any subject of DSP, the math is hugely involved, but the implementation is simpler. I had been using CRC function on different microcontorller for so many years, the math behind the CRC is aptly explained here. Thank you. BTW, I had also realized that the CRC polynomials are determined after lot of reseach and that is another subject all together. Fortunately, mundane creatures like me are happy with usage of CRC. Thanks for the video.
For anyone who is confused by how the addition rules of the finite field translate to the polynomial expression:
You can think of the polynomial as a vector (with some additional properties), where the powers of the indeterminate represent the independent entries of the vector. The video on abstract vector spaces in the linear algebra series by 3blue1brown explains why this is the case, if you're not familiar with the matter.
Then the polynomial addition (or subtraction) is nothing more than vector addition. But in this case it is addition according to the adding rules of the finite field. At least to me this view makes it clearer why each component can be added independently and there is no carrying over.
That is such a great addition (pun intended) to the video. Thank you!
This one of the best lectures on CRC on the Web. It explores the fundamentals and slowly takes u through all the steps to the final phase which is the construction of the Generating Poly.
Even though the lecture is on paper and not some fancy ppt presentation but the presented material is to the core and very valuable, I am impressed by the step by step, hand calculation, sequence of the presentation, topics covered, Q&A that come to mind.
Looking forward to the bext lecture of HW implementation of shift/XOR operation to perform the divisin.
Thank u 🙏
Excellent explanation. Wish our university math professor was that clear 30 years ago. But since he wasn't I had to figure out that all those polynomial operations are just shifts and XORs in disguise myself, which was probably a good thing. OTOH, I never understood why you would use something complicated like polynomials instead of something simple like bitstrings. I put that down to mathematicians just using what they are familiar with. But now I see that proving properties (like the maximum length of a burst error that can be detected) is easier using polynomials. So another insight after 30 years :-).
This isn't merely an excellent deep dive into one of the most important algorithms in modern computing, but such depth in a RUclips video they got so many views reminds me that there are still intelligent, curious people.
Ben, glad to see that you are back. You are so incredibly talented at explaining these things in a simple manner. Thank you :o)
During the early part of my career I was a hardware tech so I attended a number of classes where the instructor would attempt to explain redundancy checks by tracing through logic diagrams. On something like the error correction logic for reading a disk track this was near impossible. This explanation clears up the questions I always had but never answered. Since I never saw the hardware in this area fail it wasn't a problem but now my curiosity has been satisfied.
I came here to watch some arduino systems transmit data and suddenly BAM! I'm back at the uni again. The only difference is (contrary to my professors) he makes it easier to understand. Well explained. Earned my sub. Keep it up!
Peace out
Speaking as someone who has no proper credentials to be watching your video, I found it very understandable. And, as much as I would like to pat myself on the back for being so clever, I'm posting this note to congratulate you on an outstanding explanation! Nothing but net!
Is there an exception for 0 in the axiom of multiplicative inverse?
Yes; good catch! I guess I neglected to mention it, but there is indeed an explicit exception for 0. Division by zero is undefined.
A rigorous definition for fields actually demands that all of the multiplication rules are not defined for 0. How 0 behaves in multiplication then only follows from the distributive law (i.e. 0•anything = 0).
If you know about groups then you can think of fields as being made up of an additive group and a multiplicative group connected by the distributive law, where the mutliplicative group doesn't contain the neutral element from the additive group.
Everything else from the definition in the video is correct.
Halberd Rejoyceth there should also be an axiom that says that the field is closed with respect to its binary operations
@@Sporkabyte That follows from the group axioms.
Extraordinary quality. You explained CRC way better than my Profs when studying electrical engineering. Nearly forgot about this topic. Thank you!
The ultimate teaching about crc. I hope i find this when I studied undergrads.
This is the best CRC video on youtube !!! Thank you so much for the amazing knowledge
Thank you for the well prepared walkthrough..!
Trying to write a software implementation, I read many guides online, tested different calculators, heard of all the terms around CRC, and it only left me wanting to shoot all the guide authors...
You instead started from the beginning, stopping at the problems that resulted in CRC's weird traits.. I also wondered why mathematicians would come up with this fringe thing, but you showed that it's actually pretty general and super powerful, so their involvement was justified.
Excellent. I have had a basic understanding of CRC for over 40 years (300 baud modem days), but under understood the black box details of how it works. Thanks
Another great video! Really taking the magic out of computers, which is awesome.
Definately one of the best and most easily understood explanations I've heard. Bravo. Understanding the detailed math isn't essential. The concept is, and explained very well here.
Although it's long, I could watch it without any skipping or altering the playback speed. Now I feel like I fully understood CRC and can even apply it to different situations. Helped me a ton studying for my course. Amazing work!
I knew I should've paid more attention in linear algebra... also this is the best CRC explanation I've seen
Yhup! - you know there's no hiding that there's chunky maths in it from the slide at 0:35 (generator, fields, modulo, polynomial) but if I hang in there for 45 minutes plus re-plays, I know there's already a circuit-board implementation to look forward to in the next video. I've been hearing these terms and feel I #ought to# be able to understand them at face value [with some discrete maths background] rather than with a hand-wave over, "you spin it round and do a checksum (of sorts)". I trust you, Ben: commence the brain-dump!
Excellent video. Straight to the point. No need for fancy graphics. I say again: excellent.
I remember (a long time ago) learning all the error correction stuff, I will have to say, you explain it so well. You'd make a great lecturer.
Holy shit, you did a really good job explaining this, starting with simplified and generalized concepts slowly building up to how it's actually done and do a real world example.
Dear Ben,
Impressive, what an explanation. Thank you very much for this amazing video, I'm subscribed now and will check your videos as I can. I'm a network engineer trying to fill all the gaps I, as Mr. Junk Mail promised to ourselves would do. Most of these missing pieces are details, so it takes much more time to find the information about it and then fully comprehend it, making it really difficult due to my daily activies. I invested both my days off for searching, refreshing long forgotten math concepts as it was required, practicing on paper just to get a blurry approach of how CRC works, how are the generator polynomials selected, if they are sent to the receiver, if the receiver already has the polynomial beforehand, etc. I was so close to give up for the week, all ready to go work and forget about it slowly overtime. I can't thank you enough for this, but there is something I can do. You can count on me watching your videos and recommend them to my coworkers who also seek to strengthen their knowledge.
Regards from México.
I'm so glad I found this channel! Your explanation is outstanding...can't thank you enough!!
We'll that's something I never knew I wanted to know. Now I do thanks to someone spending a ton of their time making a 47-minute-long video.
Awesome! Thanks!
This is the best channel on RUclips about computer engineering. I really love your videos
This video was hands down the best explanation of finite field I've ever seen. Not to say that my university professors are not impressive or anything, but sometimes explaining things just weren't their forte...
I really liked this video. I too am an electrical engineer and i've used CRC some times but never took the effort to see why it works. Thanks Ben. I wish you were my professor
This video is a gift! CRC is one of those concepts we all use but never stop to ask how it works, and why.
I'd absolutely love to see a video from you on Reed-Solomon codes as used in CDs.
I have ever seen...such a explanation for CRC .
Thank you very much sir
Mind blown at the XOR part around minute 29.. excellent observation
This is a really good video. Everything is explained clearly and patiently and I only had to pause at the monstrous polynomial division. I'm really happy to see that you continue to do these videos
20:51 i don't know if mentioned but well at the top right thats equals to the truth table of an XOR-gate (That to the right as well). And that below equals to the truth table of an AND-Gate
EDIT: okay well to be fair: you have to "forget" the multiplication, addition, etc. and you have to take each value as an input
EDIT 2: well you said it at 28:50 but well im proud that i at least figured that one out by myself
The clarity and depth of content in your videos are unmatched. Simply outstanding!
I was looking for something like this a few weeks ago. The structure and clarity of your explanation is remarkable. I look forward for the HW implementation video.
Back in the UseNet days, a parity reprocess was pretty much needed for large binary posts. I always thought the QuickPar .PAR2 rebuild process was one of the most ingenious and advanced engineering inventions ever. The way it could take ANY location of a 2 GB file (example) that was corrupt in ANY random spot, ... all you needed was a set number of PAR2 blocks to rebuild it. The idea of being able to rebuild any number of corrupt sections in the fileset was mind boggling. You could also rebuild entire lost segments. To this day, I do not fully understand how the Reed-Solomon algorithm EC worked to repair usenet sets. As long as the author published a set of PAR2 repair blocks, you could fix anything. To be able to fix an error in a 2 GB file, with a small 5 MB parse block was ingenious, and it had to work similar to how CRC worked, but on a much broader scale.
Reed-Solomon relies mainly on having a large enough size of signal bits versus data bits, that instead of the maths you just have a lookup table of valid byte codes. Anything invalid is then assumed to have intended to be the closest valid one (massive over simplification but I assume that’s what the “repair blocks” contained, the valid codes).
For instance CDs use 14 bits to encode a byte, with the valid code words arranged in a particular geometric way through the possibility-space to keep the distance between them consistent. So quite large errors can still be recovered (and CDs use further techniques on top, interleaving, duplication, etc so all in all you can lose about a fifth of all the signal but the data will still be recoverable).
WOW, this is by far the most complicated thing I have understood from start to end. Fantastic explanation by Ben. Now onto the hardware build video
Well explained and better than any lectures about information/coding-theory during my studies! Furthermore links the topics (algebra, fields, polynoms) with practical use.
Super video! I applauded for $2.00 👏
So much better explained then in my master degree EE course XD thx for the exam prep video :DD
Best video about CRC on the internet.
Fantastic video! Even though my professor mentioned CRC in her class, I still feel the CRC she taught is not clear enough for me. Then I find this. Thanks.
Great video, Ben. I've used and coded CRC routines but have never understood the fundamentals of them. Can't wait for the next installment!
I had a question, but got it afterwards. I'll explain it too in case it helps someone else:
30:53 Here it's said that the remainder is added to the original message - but shouldn't we actually be adding "the divisor minus the remainder"? So that the message then becomes a multiple of whatever divisor we had?
A: See, by adding the remainder, since we're using that different field, this is the same as subtracting it. So essentially we're making the message a multiple of the divisor, by taking off the original message of its remainder.
I gaven't even finished an elementary course in Linear Algebra and I just spent half an hour watching a video that talks about higher level algebra and computer science. Love it.
I don't know why, but the "oh wait a minute, there's no such thing as six" made me laugh. Thanks as always for the incredible videos Ben!
Awesome! I love how clearly you are able to convey this while using simple pen and paper. No over-fancy graphics and a very well thought-through structure.
This is a great video to highlight the importance of prime numbers in computing and understanding the value of them from a computing aspect. Greatly appreciate seeing an underlying hint towards primes!
Thanks!
Absolutely superb videos, Ben. The effort you go to in producing these is phenomenal. Quite simply, thank you.
How can you pick such perfect examples, man. That's where the magic comes from. Doesn't take too much time to explain, yet answers all the "what if"s!
Congratulations Ben, You have single handedly explained the weird math and rational behind the complex operations that take place with such ease. Loved and learnt !!!
Yeah, I too hate when I want to say "Hi!", but say "Ho!" to a girl.
I have the opposite problem
"O hai!" No... wait... let me checksum that."
When is he finally gonna release to video on how to avoid errors in RL?
@@R3lay0 he is a computer engineer.. We don't have that "RL" thing you're talking about :(
I bet she didn't check your bits.
Studying for computer networks final. This really helps great explanation!
Ben, this is so well done - I could listen to you for hours. Thanks for this fantastic video that helped me brush up the math I needed for implementing some of the firmware/embedded tasks I've been doing at my job.
I finally got how P can be equal to NP. All thanks to your video, Ben. Thank you so much!
Glad I could help! :)
37:11 small problem in the editing. awesome video as always. thnx a lot. I've leatned so much from your videos. you're the best.
Wow! Unbelievably clear explanation. Thank you!
Very patient teacher. Thanks for bringing clarity to this subject
You explain math better than my math teacher.
The video which make me really understand the trick behind CRC. Didn't know that it also relies on finite or Galois field. Thanks!
Perfect timing! Just as we were talking about this at university. Great resource, love it :)
This guy deserves a lot more subscribers. I strongly recommend this Man🙄
Ben, the best think about your videos is their detail. I appreciate you taking the time to share your knowledge. I have watched every one you have made multiple times.
I did not expect finite fields. I'm so impressed. Do not regret my patreon.
absolutely phenomenal video... Ben you are divine in explaining things!
I knew that mathematics was important in computing, but this video really highlights how important it is.
Fantastic video, very complicated but very well explained.
Thanks for your efforts, you aren't just sharing knowledge
This is an unbelievably elegant and powerful idea. What an incredible invention!
Some one suggested your channel in the comments of another video. This is the first video I've seen by you. I'm in love.
Brilliant video, very well explained. Many thanks, Ben. Love your channel
Super video! I applauded for A$5.00 👏👏
I noticed a clue in there as to how error correction can work. Something about knowing the received content and the divisor enabling you to reconstruct the original message? I'd guess that an expansion of that is what allows a corrupted received message to be reconstructed, so long as not too much of the message has been damaged?
Of course this is beyond what a CRC could do, but it appears to be an expansion on how the CRC works?
Edit: Also, it seems that I'm now coming to understand what a polynomial is, in spite of never learning about them in school (left too early - thereby lies a sad story totally unrelated to the video).
I've had this math at my university - i hated it - you made me love it again. Thank you.
30:23 Your magic X16, x12, x5, x1 is all bits zero except the MSB and the LSB which are 1. It then moves to MSB-4 and LSB+4 and makes them 1. But it quits there. It doesn't move to MSB-8 and LSB+8. At this point we get X9 and X8 (i.e. adjacent bits). I wonder why? I will probably have to remove this comment by the time I get to the end of your presentation. However, your explanation is better than I have ever seen in my formal education...or even read in the literature. Thanks (even though I'm regrettably coming to the party 2 years late).