Parity, Hamming code, Hamming distance, checksums and CRC
Type the data bits and the parity bits are worked out. Then click any bit of the word to flip it as if it were a transmission error, and see what the receiver does: the syndrome gives the position of the wrong bit. Try one and two errors, with and without the overall parity bit.
parity · data · overall parity · flipped bit.
Type the frame as hexadecimal bytes (with or without spaces) or as text. The “in the frame” column gives the bytes in the order they are sent.
No channel is perfect: an RS-485 frame running past a drive, a memory bit hit by a particle or a scratch on a disc can turn a 0 into a 1. To notice it, the sender adds some redundancy bits to the data, worked out from them, and the receiver repeats the calculation. If it does not match, there are two strategies:
The Hamming distance between two words of the same size is the number of bits in which they differ: between 1011101 and 1001001 it is 2. The minimum distance \(d\) of a code is the smallest between any two valid words, and it sets what the code can do:
| Code | Minimum distance | Detects | Corrects |
|---|---|---|---|
| Data without redundancy | 1 | nothing | nothing |
| Parity bit, 2-out-of-5 | 2 | 1 error | nothing |
| Hamming | 3 | 2 errors | 1 error |
| Hamming with overall parity (SECDED) | 4 | 3 errors | 1 error and detects 2 |
| Repeating each bit 3 times | 3 | 2 errors | 1 error (by majority) |
The idea is geometric: if valid words are at least distance 3 apart, a word with one error is still closer to the original than to any other.
It is the simplest code: one bit is added so that the total number of ones is even (even parity) or odd (odd parity). It detects any odd number of errors, but not two bits flipped at once. It is the parity of serial ports (8E1 means 8 data bits, even parity and 1 stop bit; Modbus RTU uses even parity by default) and of some old memories. In a circuit it is worked out with a chain of XOR gates.
With two-dimensional parity, the data are arranged in a table and the parity of each row and each column is added. One error changes the parity of one row and one column, and where they cross is the bit to correct.
Richard Hamming devised it in 1950, fed up with relay-machine faults ruining his weekend calculations. The positions of the word are numbered from 1; those that are powers of 2 (1, 2, 4, 8…) hold parity bits and the rest hold data. Each parity bit \(p_k\) covers the positions whose binary number has the bit of weight \(k\) set: \(p_1\) covers 1, 3, 5, 7…; \(p_2\) covers 2, 3, 6, 7…; \(p_4\) covers 4–7, 12–15… With \(r\) parity bits, \(m\) data bits are protected if:
The data go in positions 3, 5, 6 and 7. \(p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0\), \(p_2 = d_1 \oplus d_3 \oplus d_4 = 1\) and \(p_4 = d_2 \oplus d_3 \oplus d_4 = 0\). The word sent is \(0110011\). If \(0110111\) arrives (position 5 has failed), the receiver recalculates the three parities on what it received: \(s_1 = 1\), \(s_2 = 0\), \(s_4 = 1\). The syndrome \(s_4 s_2 s_1 = 101_2 = 5\) is exactly the position of the error, and that bit just has to be flipped.
| Code | Data bits | Parity bits | Efficiency |
|---|---|---|---|
| Hamming (7, 4) | 4 | 3 | 57 % |
| Hamming (15, 11) | 11 | 4 | 73 % |
| Hamming (31, 26) | 26 | 5 | 84 % |
| Hamming (63, 57) | 57 | 6 | 90 % |
| SECDED (72, 64), ECC memory | 64 | 8 | 89 % |
With two errors, plain Hamming gives a non-zero syndrome and “corrects” a bit that was right, making the word worse. To avoid it, an overall parity bit P is added over the whole word (single error correction, double error detection):
It is the scheme used by server ECC memory and by many automotive and safety microcontrollers: 8 check bits for every 64 data bits.
They are fast and easy to program, but they detect much worse than a CRC of the same size.
The CRC treats the message as a polynomial with coefficients 0 and 1 (\(1011 = x^3 + x + 1\)) and divides it by a generator polynomial of degree \(r\). In this arithmetic (modulo 2), adding and subtracting are the same as the exclusive OR and there are no carries. The sender appends \(r\) zeros to the message, divides and sends the remainder in their place; the receiver divides the whole frame and, if there are no errors, the remainder is 0.
Three zeros are appended and the generator is subtracted (XOR) under each 1 left on the left. The remainder is 100, so 11010011101100100 is sent. It is the example loaded in the calculator above.
With a good polynomial of degree \(r\), the CRC detects:
Besides the polynomial, each CRC defines the initial value of the register, whether the bits of each byte go in reflected (least significant first, as they come out of a UART), whether the result is reflected and which value is used for the final exclusive OR. That is why CRC-16/MODBUS, CRC-16/ARC and CRC-16/CCITT give different results with the same data. To find out which one a device uses, work out the CRC of the text string 123456789 and compare it with the check value: 4B37 for Modbus, 29B1 for CCITT-FALSE, CBF43926 for CRC-32.
Related: binary and hexadecimal converter, 2-out-of-5 code and logic gate simulator (the XOR).