Electrical – C++ – Help Interpreting the instructions of a CRC error-checking programming assignment

A Hamming code is a particular kind of error-correcting code (ECC) that allows single-bit errors in code words to be corrected. Such codes are used in data transmission or data storage systems in which it is not feasible to use retry mechanisms to recover the data when errors are detected. This type of error recovery is also known as forward error correction (FEC).

Constructing a Hamming code to protect, say, a 4-bit data word

Hamming codes are relatively easy to construct because they're based on parity logic. Each check bit is a parity bit for a particular subset of the data bits, and they're arranged so that the pattern of parity errors directly indicates the position of the bit error.

It takes three check bits to protect four data bits (the reason for this will become apparent shortly), giving a total of 7 bits in the encoded word. If you number the bit positions of an 8-bit word in binary, you see that there is one position that has no "1"s in its column, three positions that have a single "1" each, and four positions that have two or more "1"s.

If the four data bits are called A, B, C and D, and our three check bits are X, Y and Z, we place them in the columns such that the check bits are in the columns with one "1" and the data bits are in the columns with more than one "1". The bit in position 0 is not used.

Bit position:  7  6  5  4  3  2  1  0
   in binary:  1  1  1  1  0  0  0  0
               1  1  0  0  1  1  0  0
               1  0  1  0  1  0  1  0
         Bit:  A  B  C  X  D  Y  Z  -

The check bit X is set or cleared so that all of the bits with a "1" in the top row — A, B C and X — have even parity. Similarly, the check bit Y is the parity bit for all of the bits with a "1" in the second row (A, B and D), and the check bit Z is the parity bit for all of the bits with a "1" in the third row (A, C and D).

Now all seven bits — the codeword — are transmitted (or stored), usually reordered so that the data bits appear in their original sequence: A B C D X Y Z. When they're received (or retrieved) later, the data bits are put through the same encoding process as before, producing three new check bits X', Y' and Z'. If the new check bits are XOR'd with the received check bits, an interesting thing occurs. If there's no error in the received bits, the result of the XOR is all zeros. But if there's a single bit error in any of the seven received bits, the result of the XOR is a nonzero three-bit number called the "syndrome" that directly indicates the position of the bit error as defined in the table above. If the bit in this position is flipped, then the original 7-bit codeword is perfectly reconstructed.

A couple of examples will illustrate this. Let's assume that the data bits are all zero, which also means that all of the check bits are zero as well. If bit "B" is set in the received word, then the recomputed check bits X'Y'Z' (and the syndrome) will be 110, which is the bit position for B. If bit "Y" is set in the received word, then the recomputed check bits will be "000", and the syndrome will be "010", which is the bit position for Y.

Hamming codes get more efficient with larger codewords. Basically, you need enough check bits to enumerate all of the data bits plus the check bits plus one. Therefore, four check bits can protect up to 11 data bits, five check bits can protect up to 26 data bits, and so on. Eventually you get to the point where if you have 8 bytes of data (64 bits) with a parity bit on each byte, you have enough parity bits to do ECC on the 64 bits of data instead.

Different (but equivalent) Hamming codes

Given a specific number N of check bits, there are 2^N equivalent Hamming codes that can be constructed by arbitrarily choosing each check bit to have either "even" or "odd" parity within its group of data bits. As long as the encoder and the decoder use the same definitions for the check bits, all of the properties of the Hamming code are preserved.

Sometimes it's useful to define the check bits so that an encoded word of all-zeros or all-ones is always detected as an error.

What happens when multiple bits get flipped in a Hamming codeword

Multible bit errors in a Hamming code cause trouble. Two bit errors will always be detected as an error, but the wrong bit will get flipped by the correction logic, resulting in gibberish. If there are more than two bits in error, the received codeword may appear to be a valid one (but different from the original), which means that the error may or may not be detected.

In any case, the error-correcting logic can't tell the difference between single bit errors and multiple bit errors, and so the corrected output can't be relied on.

Extending a Hamming code to detect double-bit errors

Any single-error correcting Hamming code can be extended to reliably detect double bit errors by adding one more parity bit over the entire encoded word. This type of code is called a SECDED (single-error correcting, double-error detecting) code. It can always distinguish a double bit error from a single bit error, and it detects more types of multiple bit errors than a bare Hamming code does.

It works like this: All valid code words are (a minimum of) Hamming distance 3 apart. The "Hamming distance" between two words is defined as the number of bits in corresponding positions that are different. Any single-bit error is distance one from a valid word, and the correction algorithm converts the received word to the nearest valid one.

If a double error occurs, the parity of the word is not affected, but the correction algorithm still corrects the received word, which is distance two from the original valid word, but distance one from some other valid (but wrong) word. It does this by flipping one bit, which may or may not be one of the erroneous bits. Now the word has either one or three bits flipped, and the original double error is now detected by the parity checker.

Note that this works even when the parity bit itself is involved in a single-bit or double-bit error. It isn't hard to work out all the combinations.

If your bit-error rate is measurable but not so high that no level of error-correction logic would help, you should either slow down your communications rate by 1% or so, or use the "best" 16 bits of your bus and not bother with the others.

Error correction logic is only useful in cases where the probability of an errors is relatively low and the probability of two errors occurring is far below the probability of one, the probability of three errors occurring is far below that, etc. For a connection between a CPU and an FPGA, either you'll be meeting timing constraints, in which the most probable causes of errors will be things like power-supply glitches (which should be best addressed by power-supply improvements), you'll significantly miss timing constraints (in which case at least some bits of the bus will routinely yield incorrect data), or you'll be right on the edge of meeting timing constraints (in which case increasing timing margins even a little may help enormously).

If you were worried about guarding a parallel-data cable that went between boards, then the primary data to be guarded against would probably be that of a disrupted communication (e.g. one that was happening while a connector was unplugged) being perceived as legitimate. Unless very-short-turnaround transactions are required (as might be the case here), such things are best guarded against by performing a CRC or other validation code on all the words of a longer transmission. Appending a two-word (32-bit) CRC to a 64-word transmission would less overhead than adding a parity bit to each word, but would be far more likely to detect transmission errors.