Sunday, January 1, 2012

CRC for Protecting A Single Value

Some critical applications need to protect a single byte or word of data in memory against corruption. (For example, if you want to be extra-sure about protecting EEPROM values against corruption.) A previous post gives good CRC polynomials for a wide range of circumstances, but it is always nice to know if you can do better for a special case. Below are optimal CRC polynomials for a few special cases involving small data words that might be stored in memory (RAM, EEPROM, or otherwise).

Protecting an 8-bit data word:
8-bit CRC:  HD=5;  0x9C = x^8 + x^5 + x^4 + x^3 + 1  
16-bit CRC: HD=8; 0xE92F = x^16 + x^15 + x^14 + x^12 + x^9 + x^6 + x^4 + x^3 + x^2 + x + 1
32-bit CRC: HD=16; 0xC563942F = x^32 +x^31 +x^27 +x^25 +x^23 +x^22 +x^18 +x^17 +x^16 +x^13 +x^11 +x^6 +x^4 +x^3 +x^2 +x +1

Protecting a 16-bit data word:
8-bit CRC:  HD=4;  0x93 = x^8 + x^5 + x^2 + x + 1  
16-bit CRC: HD=7; 0x978A = x^16 + x^13 + x^11 + x^10 + x^9 + x^8 + x^4 +  x^2 + 1
32-bit CRC: HD=14; 0xB396786D = x^32 +x^30 +x^29 +x^26 +x^25 +x^24 +x^21 +x^19 +x^18 +x^15 +x^14 +x^13 +x^12 +x^7 +x^6 +x^4 +x^3 +x +1

Protecting a 32-bit data word:
8-bit CRC:  HD=4;  0x92 = x^8 + x^5 + x^2 + 1  
16-bit CRC: HD=6; 0x8BFC = x^16 + x^12 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 +  x^4 + x^3 + 1
32-bit CRC: HD=12; 0xB527A43B = x^32 +x^30 +x^29 +x^27 +x^25 +x^22 +x^19 +x^18 +x^17 +x^16 +x^14 +x^11 +x^6 +x^5 +x^4 +x^2 +x +1

The hex number has an implicit +1. "HD" means Hamming Distance. Other information about this topic can be found at my previous post on good CRCs.

Note that for this sort of use it is a good idea to "seed" the CRC computation with a value of that is not zero. That avoids a data word value of zero giving a CRC computed value of zero -- which will result in an undetected error if memory is wiped to all zeros for some reason.

2 comments:

  1. Hi, I work on embedded systems, and I was looking in the internet for a good CRC for my purpose. Almost immediately I stumbled on your publications: thank you so much for sharing your knowledge! I went through your blog and some articles but not sure what 3,4,5-bit CRC I should implement to protect remaining bits of a 32-bit word. My target: I have a fixed 32-bit length record that I need to protect. I can dedicate some of the 32 bits to store CRC, let's say from 3 to 5 bits thus leaving from 29 to 27 bits for data. Can you direct me?

    Thanks!
    Fabrizio

    ReplyDelete
  2. Have a look at this posting for your answer:

    http://checksumcrc.blogspot.com/2011/12/what-is-best-crc-up-to-16-bits-in-size.html

    ReplyDelete

Why To Avoid Hash Algorithms If What You Really Need Is A Checksum

Sometimes we hear that someone plans to use a hash function for fault detection instead of a checksum. This is probably not the best idea, b...