How do CRCs work?

2019-04-28

[public] 339K views, 18.0K likes, 94.0 dislikes audio only

CRC (cyclic redundancy check) is one of the most common methods of error detection. It uses some interesting mathematical tricks to guarantee that it can catch certain kinds of errors. How does it work?

Support these videos on Patreon: https://www.patreon.com/beneater or https://eater.net/support for other ways to support.

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

------------------

Social media:

Website: https://www.eater.net

Twitter: https://twitter.com/ben_eater

Patreon: https://patreon.com/beneater

Reddit: https://www.reddit.com/r/beneater

Special thanks to these supporters for making this video possible:

Ben Dyson

Ben Kamens

Ben Williams

Brandon Stranzl

Christopher Blackmon

Debilu Krastas

Eric Dynowski

Gonzalo Belascuen

Greg Stratton

Jay Binks

Jayne Gabriele

Johnathan Roatch

Jordan Scales

Manne Moquist

Michael

Nicholas Moresco

Nick Wrightsman

Randy True

Ric Allinson

Sachin Chitale

SonOfSofaman

Finite Fields
/youtube/video/izG7qT0EpBw?t=1003.459

The Additive Property of Equality
/youtube/video/izG7qT0EpBw?t=1039.52

Finite Field
/youtube/video/izG7qT0EpBw?t=1097.52

What Is the Field
/youtube/video/izG7qT0EpBw?t=1112.01

Field Axioms
/youtube/video/izG7qT0EpBw?t=1131.9

Additive Inverse
/youtube/video/izG7qT0EpBw?t=1286.21

The Additive Inverse of a Number
/youtube/video/izG7qT0EpBw?t=1299.1591

So It Looks like What We'Re Doing Is We'Re Just Adding that Remainder on to Our Message but Technically What We'Re Doing Is We'Re Subtracting the Remainder from the Message and Now It Looks the Same because Again We'Re Using this Finite Field Where It Turns Out that Addition and Subtraction Look like Identical Operations Which Is Admittedly a Little Bit Weird but Remember You Know As Long as We'Re Following these Field Axioms all of Our Algebra Is Going To Work and so that's Why I Say What We'Re Doing Here Is We'Re Subtracting the Remainder from Our Message To Get this Transmitted
/youtube/video/izG7qT0EpBw?t=1911.75

So Really What the Receiver Is Doing Is the Receiver Doesn't Know the Transmitted Message all It Knows Is the Transmitted Message plus Whatever Error Was Introduced so the Receiver Is Going To Take the Transmitted Message plus Error Divide that by this Generator Polynomial and Then Check if that's Equal to Zero and if It's Not Then It's Going To Detect an Error So Just To Look at another Example Real Quick Here's an Example Where Again the Message for Transmitting Is Still High but Well Received as the Message Ha in this Case Instead of Two Zero Bits Flipping Two Ones We Have a Bit That's Supposed To Be a One That Flips to a Zero
/youtube/video/izG7qT0EpBw?t=2077.98

We Can Try To Find a Polynomial That's GonNa Be Best at Detecting those Errors Now in Practice You Probably Won't Come Up with Your Own Polynomial There Are Lots of Different Ones That Have Become International Standards and You Can See a Bunch of Them Here on Wikipedia and I'Ve Been Using this One Called Crc 16 Ccitt this X Is 16 Plus X to the 12 plus X to the Fifth Plus 1 and You Can See It's Pretty Popular to Using a Whole Bunch of Different Things Bluetooth and You Know Many Other Things You May Have Heard of another Really Maybe Even More Popular One Is Crc 32 Which Is You Know as the Name Would Suggest a 32-Bit Polynomial
/youtube/video/izG7qT0EpBw?t=2410.0891

If We Go Back to Where this Video Series Started You Know We'Re Trying To Send Data from One Computer System to another and Evaluate whether We Receive that Correctly and So When We Looked at Parity You Know that Was Actually Quite Simple To Implement in Hardware like this if We Look at Crc this Is Way More Complex You Know How Are We GonNa Go about Implementing Something like this in Hardware or Even You Know in Software It Seems like It Might Be a Bit of Work To Get this Working Well It Turns Out and this Is One of the Coolest Things Is that in Addition to All the Mathematical Rigor That You Get with Crc
/youtube/video/izG7qT0EpBw?t=2761.0691

Patreon patreon.com
https://www.patreon.com/beneater

Hacking a weird TV censoring device 1,723,122 views
/youtube/video/a6EWIh2D1NQ