CODEWITHSUNDEEP
checksumcrcerror-detection
ysap
ysap

Reputation: 8115

Which one is the better CRC scheme?

Say I have to error-check a message of some 120-bits long.I have two alternative for checksum schemes:

  1. Split message to 5 24-bit strings and append each with a CRC8 field

  2. Append the whole message with a CRC32 field

Which scheme has a higher error detection probability, and why? Let's assume no prior knowledge about the error patterns distribution.

UPDATE:

What if the system has a natural mode of failure which is a received cleared bit instead of a set bit (i.e., "1" was Tx-ed but "0" was Rx-ed), and the opposite does not happen?

In this case, the probability of long bursts of error bits is much smaller, assuming that the valid data has a uniform distribution of "0"s and "1"s, so the longest burst will be bound by the longest string of "1"s in the message.

Upvotes: 0

Views: 1239

Answers (3)

DarkFranX
DarkFranX

Reputation: 561

A good paper by Philip Koopman goes through evaluation of several CRCs, mostly focusing on their Hamming Distance. Like Mark Adler pointed out, the error distribution plays an important role in CRC selection (e.g. burst errors detection is one of the variable properties of CRC), as is the length of the CRC'ed data.

The Hamming Distance of a CRC indicates the maximum number of errors in the data which are 100% detectable.

Ref: Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks: https://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

8-bit vs 32-bit CRC

For example, the 0x97 8-bit CRC polynomial has HD=4 up to 119 bits data words (which is more than your required 24-bit word), which means it detects 100% of 3 bits (or less) errors for data of length 119 bits or less.

On the 32-bit side, the 32-bit CRC 0x9d7f97d6 offer HD=9 up to 223 bits (greater than 5*24=120bits) data words. This means that it will detect 100% of the 8 bits (or less) errors for data composed of 223 bits or less.

Theoretically, 5x 8-bit CRCs would be able to 100% detect 3*5=15 evenly distributed bit flips across your 5 chunks (3 errors per 24-bit chunk). On the other end, the 32-bit CRC would only be able to 100% detect 8 bit flips per 120-bit chunk.

Error Distribution

Knowing all that, the only missing piece is the error distribution pattern. With it in hand, you'll be able to make an informed decision on the best CRC method to use. You seem to say that long burst of errors are not possible, but do not mention the exact maximum length. If that length does go up to 9 bits, you might be better off with the CRC32. If you expect occasional, <4-bit errors, both would do, though the 5x8-bit will consume more bandwidth (40 bits instead of 32 bits). If this is the case, a 32-bit CRC might even be overkill, a smaller CRC16 or even CRC9 could provide enough detection capabilities.

Beyond the hamming window, the CRC will not be able to catch every possible errors. The bigger the data length, the worse the CRC performances.

Upvotes: 1

Mark Adler
Mark Adler

Reputation: 112374

You have to make some assumption about the error patterns. If you have a uniform distribution over all possible errors, then five 8-bit CRCs will detect more of the errors than one 32-bit CRC, simply because the former has 40 bits of redundancy.

However, I can construct many 24-bit error patterns that fool an 8-bit CRC, and use any combination of five of those to get no errors over all of the 8-bit CRCs. Yet almost all of those will be caught by the 32-bit CRC.

Upvotes: 1

user207421
user207421

Reputation: 310913

The CRC32 of course. It will detect ordering errors as between the five segments, as well as giving you 224 as much error detection.

Upvotes: 0

Related Questions