The problem: I am jointly developing a low-speed automation bus for low-cost hardware and I need some error verification for your messages. Using a CRC for that seems to make sense, but which one?
I found an article by Koopman + Chakravarty but it doesn't say how they calculated Hamming's distances from the polynomials used.
An additional complication is that our bus design offers three possible values that you could use to calculate a CRC:
- the real binary message
- the state of the $ n $ bus cables in each time slot
- as above, but XOR to the previous slot: it cannot be zero
Algorithm to encode a message: given $ n $ wires there $ s = 2 n-1 possible states (one is excluded because it is identical to the previous one). Therefore, treat the message as a bit stream, divide it into 11-bit or 14-bit boxes, treat each box as an unsigned number, convert it to base $ s $, add one to each digit, XOR the binary value of each digit in the state of the wires, wait a couple of µsec, repeat. The receiver simply reverses this process.
I would like to discover how to achieve a maximum distance from Hamming to $ le 100 $Bit messages, with the least amount of overhead (that is, a CRC-8 if possible), and I freely admit that I have more questions than answers at this time.
For example, the state of the XOR & # 39; d bus has the interesting property that, by definition, there are no single-bit errors and there are no long series of zeros: does that affect the importance of CRC? how? Koopman + C. provides maximum Hamming distances for several "good" polynomials and block lengths, but a 1-bit error in the hardware state changes from 1 to ~ 10 bits in the resulting message: this obviously affects the end behavior At the end of the CRC, but is it possible to select a polynomial so that it cannot result in a Hamming distance of 2?
NB: 11-bit and 14-bit frames are used because they are at most 16 bits long (important for a fast 8-bit CPU implementation) and have a low overhead, i.e. $ 7 ^ 5 $ is reasonably close to $ 2 14 If the bus has three wires. Similarly, 11-bit blocks are used for 2 and 4 wire buses.
A brute force approach would be to encode random messages, protect them with a selected CRC pair, bombard them with 1 … 5 random bit errors, do this on a large machine with several CPUs for a week and see where I find false positive …
If anyone has a more efficient idea, I would appreciate it.