The Wiert Corner – irregular stream of stuff

Jeroen W. Pluimers on .NET, C#, Delphi, databases, and personal interests

  • My badges

  • Twitter Updates

  • My Flickr Stream

  • Pages

  • All categories

  • Enter your email address to subscribe to this blog and receive notifications of new posts by email.

    Join 1,702 other followers

CRC: The C Stands for Confusion (quotes from the Dr Dobb’s article)

Posted by jpluimers on 2015/04/28

The CRC algorithm isn’t hard, but choosing the right polynomial and parameters can be tricky especially since there are so many permutations to choose from and lots of libraries have made their own (often incompatible) choices.

 A few quotes

Basics:      

… check out Wikipedia, which has a pretty good write up, or the classic “A Painless Guide to CRC Error Detection Algorithms.” Here’s the gist: Every CRC has a generator “polynomial.” The algorithm does an integer division of the data packet (treated as a polynomial) by the CRC polynomial. You don’t use the result, but the remainder from the division is the CRC. A reverse process can determine if the CRC matches the data. If it doesn’t, that implies that an error occurred.

Selecting the right CRC and polynomial:

… it stands to reason that longer CRCs can protect more data against more bit errors. However, it isn’t quite that simple. The selection of the polynomial makes a big difference as well.

Rather than go through the math, I’ll refer you the excellent paper “CRC Polynomial Selection for Embedded Networks.” … check out the table on page 6. It shows which CRCs can detect all errors of a certain size or less (related to the Hamming distance) for a certain number of bits. For example, a 10-bit CRC (with polynomial 0x327) can catch all 1- and 2-bit errors (HD=3) for up to 1,013 bits.

… The paper covers up to 16-bit CRCs, although the same author has another paper that covers 32-bit CRCs less exhaustively.

Parameters:

… you need to agree on the other implementation parameters:

  • The directions the bits are processed in (MSB first or LSB first)
  • The initial value
  • If the output is reversed before final processing
  • If the output is XORd with a constant at the end of the calculation

Testing:

A very competent tool to test CRC generation is jacksum. It is written in Java, … It implements several common CRC algorithms and even comments on the ambiguity in what CCITT CRC-16 means in its documentation.

–jeroen

via: CRC: The C Stands for Confusion | Dr Dobb’s.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

 
%d bloggers like this: