Explanation of CRC Operation: Polynomial Division, Shift Register, and Comparison (video)

 Here is a video explaining the mechanics of Cyclic Redundancy Check computations, including:

  • An example of the polynomial division approach
  • An example of the XOR-feedback shift register approach
  • A step-by-step comparison of how the polynomial division and shift register approaches are actually doing exactly the same computation.
If you've ever wondered why it is that a shift register and polynomial division end up with the same result, this video explains it.

Video links (27 minutes):   YouTube | Archive.org

Comments

Post a Comment

Popular posts from this blog

Effect of Initial Seed Values on CRCs and Checksums

Checksums and CRCs involve a repeated computation over the length of a dataword that accumulates a result to form an FCS value. The accumulation value must be initialized to some known value for this process to produce a predictable result for any given codeword. When the initial value is unstated, it is typically assumed to be zero. In some cases, a non-zero value is used instead, such as 0xFFFF for a 16-bit checksum or CRC. This has the advantage of making an all zero codeword impossible. Perhaps more importantly for Fletcher checksum, ATN-32, and CRCs, this has the additional advantage of causing leading zeros of a message to affect the FCS value. To better understand, consider a CRC initialized with an all zero seed value. Any number of all zero dataword chunks can be fed into the CRC and it will stay at a zero value, throwing away information about how many zero chunks have been processed. However, if the CRC computation is initialized to any non-zero value, processing
Read more

CRC Information Quick Start

I'm not able to spend much if any time on this lately due to my work in self driving car safety. Here is a quick start for those looking for info. A tutorial on using CRCs and Checksums (how to apply them, pitfalls, system considerations; not a deep crawl through the math): https://betterembsw.blogspot.com/2013/11/crc-webinar.html A report written for the FAA on CRCs and Checksums (goes with the tutorial) https://betterembsw.blogspot.com/2015/04/faa-crc-and-checksum-report.html A web site of "best" CRCs, including: Description: https://betterembsw.blogspot.com/2010/05/whats-best-crc-polynomial-to-use.html Table of "best" CRCs for each size and length https://users.ece.cmu.edu/~koopman/crc/index.html A zoo that has performance of most published CRCs (there is a page for each polynomial size): https://users.ece.cmu.edu/~koopman/crc/crc32.html Software you can run yourself to confirm performance as a double-check on the tables (which were generated wi
Read more