To detect a number of n_errors
errors in a code of n_total
bits length, we must sacrifice a certain number n_check
of the bits for some sort of checksum.
My question is: What is the method, where I have to sacrifice the least number of bits n_check
to detect a given number of errors n_errors
in a code of n_total
bits length.
If there is no general answer to this question, I would greatly appreciate some hints concerning methods for the following conditions:
n_total=32
, n_errors>1
and
obviously n_check
should be as small as possible.
Thank you.
Link to CRC Zoo notes:
http://users.ece.cmu.edu/~koopman/crc/notes.html
If you look at the table for 3 bit crc:
http://users.ece.cmu.edu/~koopman/crc/crc3.html
You can see that the second entry, 0xb => x^3 + x + 1, has HD (Hamming Distance) 3 for 4 data bits, for a total size of 7 bits. This can detect all 2 bit error patterns (out of 7 bits), but some 3 bit patterns will fail, an obvious case where all bits should be zero would be
0 0 0 1 0 1 1 (when it should be 0 0 0 0 0 0)
This is a simple example where the number of 1 bits in the polynomial determined the maximum number of bit errors. To verify HD = 3 (2 bit errors detected) , all 21 cases of 7 bits total, 2 bits bad were checked.
If you check out 32 bit CRCs, you'll see that 0x04c11db7 (ethernet 802.3, has HD=6 (5 bit error detection) at 263 data bits => 263+32 = 295 total bits, while 0x1f4acfb13, has HD=6 at 32736 data bits => 32736+32 = 32768 total bits.
Here is a pdf article about a search for good CRCs:
https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf
Finding "good" CRCs for specific Hamming distances requires some knowledge about the process. For example, in the case of 0x1f4acfb13 with HD=6 (5 bad bit detection), there 314,728,365,660,920,250,368 possible combinations of 5 bits bad out of 32768 bits. However, 0x1f4acfb13 = 0x1f4acfb13 = 0xc85f*0x8011*0x3*0x3, and either of the 0x3 (x+1) terms will detect any odd number of error bits, which reduces the search to 4 bad bit cases. For the minimal size of a message that fails with this polynomial, the first and last bits will be bad. This reduces the searching down to just 2 of the 5 bits, which reduces the number of cases to about 536 million. Rather than calculating CRC for each bit combination, a table of CRCs can be created for each 1 bit in an otherwise all 0 bit message, and then the table entries corresponding to specific bits can be xor'ed to speed up the process. For a polynomial where it isn't the first and last bits, a table of CRC's could be generated for all 2 bit errors (assuming such a table fits in memory), then sorted, then checked for duplicate values (with sorted data, this only requires one sequential pass of the sorted table). Duplicate values would correspond to a 4 bit failure. Other situations will require different approaches, and in some cases, it's still time consuming.