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.
Cyclic Redundancy Codes, Checksums, and related issues for computer system data integrity.
Subscribe to:
Post Comments (Atom)
32-bit CRCs might be insufficient for WiFi
A new paper suggests CRCs might not be enough for WiFi. Is It Time to Upgrade From CRC-32? / Mohit Balany; Craig Partridge (IEEE Xplore / ...
-
Checksums and CRCs involve a repeated computation over the length of a dataword that accumulates a result to form an FCS value. The accumul...
-
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...
-
Comparative speeds for different Checksum & CRC implementations. For more information see my new book: Understanding Checksums and Cy...
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?
ReplyDeleteThanks!
Fabrizio
Have a look at this posting for your answer:
ReplyDeletehttp://checksumcrc.blogspot.com/2011/12/what-is-best-crc-up-to-16-bits-in-size.html