tags:

views:

350

answers:

3

I've seen 8-bit, 16-bit, and 32-bit CRCs.

At what point do I need to jump to a wider CRC?

My gut reaction is that it is based on the data length:

  1. 1-100 bytes: 8-bit CRC
  2. 101 - 1000 bytes: 16-bit CRC
  3. 1001 - ??? bytes: 32-bit CRC

EDIT: Looking at the Wikipedia page about CRC and Lott's answer, here' what we have:

<64 bytes: 8-bit CRC

<16K bytes: 16-bit CRC

<512M bytes: 32-bit CRC

A: 

I think the size of the CRC has more to do with how unique of a CRC you need instead of of the size of the input data. This is related to the particular usage and number of items on which you're calculating a CRC.

Sam
+3  A: 

It's not a research topic. It's really well understood: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

The math is pretty simple. An 8-bit CRC boils all messages down to one of 256 values. If your message is more than a few bytes long, the possibility of multiple messages having the same hash value goes up higher and higher.

A 16-bit CRC, similarly, gives you one of the 65,536 available hash values. What are the odds of any two messages having one of these values?

A 32-bit CRC gives you about 4 billion available hash values.

From the wikipedia article: "maximal total blocklength is equal to 2**r − 1". That's in bits. You don't need to do much research to see that 2**9 - 1 is 511 bits. Using CRC-8, multiple messages longer than 64 bytes will have the same CRC checksum value.

S.Lott
This is accurate and helpful if the CRC is being used to detect changes to a file. However, if it's being used as a digest to detect duplicates among files, then it's more complicated. In specific, the birthday paradox requires us to factor in how many distinct values we expect to have.
Steven Sudit
@Steven Sudit: Correct. Sadly the question is too vague to determine anything about the use of the CRC.
S.Lott
+1  A: 

The CRC should be chosen specifically for the length of the messages, it is not just a question of the size of the CRC: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

starblue