Error checking and correction: Parity bits, Hamming code.
Data bits are repeated n times e.g. 1 is sent as 111 (3 times repetition).
A parity is reserved and set to 0 or 1 according to the number of 1s in a data word.
In even parity an even number of 1s will set the parity bit to 0 (so there is an even number of 1s) while an odd number of 1s will set the parity bit to 1 (so there is an even number of 1s).
In odd parity an even number of 1s will set the parity bit to 1 (to maintain the odd number of 1s) while an odd number of 1s will set the parity bit to 0 (to maintain the odd number of 1s).
The numeric value of data words is added before transmission and the checksum sent with the data. The same calculation is performed after transmission to see if the checksums match. If the checksums do not match an error occurred and the data are transmitted again.
The cyclic redundancy check considers a block of data as the coefficients to a polynomial and then divides by a fixed, predetermined polynomial. The coefficients of the result of the division is taken as the redundant data bits, the CRC.
A hash function is a mathematical function that turns data into an integer. Like a CRC this could be calculated before transmission, sent with the data and calculated again after transmission to check that the data arrived without error.
The Hamming code is named after Richard Hamming. It is a binary code that is capable of detecting and correcting errors (parity only detects errors, it cannot correct them). It works by embedding multiple parity bits in data and overlapping parity calculations. Its strength compared with simple parity is that the multiple parity bits allow the parity bits themselves to be checked.
Parity bits are located in bit positions whose values are powers of 2, so bits 1, 2, 4 and 8 are parity bits. The intervening bits are data bits, for example 3, 5, 6, 7, 9, 10, 11.
The bits checked by a given parity bit alternate in sequences equal to the value of the parity bit. The sequences of bits included in the check alternate with an equal number of bits that are excluded.
The parity bit in position 1 checks bits 1, 3, 5, 7... (count 1, skip 1, count 1, skip 1...)
The parity bit in position 2 checks bits 2, 3, 6, 7, 10, 11... (count 2, skip 2, count 2, skip 2...)
The parity bit in position 4 checks bits 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29...(count 4, skip 4, count 4, skip 4...)
A parity bit is set to 1 if the total number of ones it checks is odd; a parity bit is set to 0 if the total number of ones it checks is even (even parity).
When errors occur the parity bits will detect the change. e.g. if bit 4 (from the left, a parity bit) flips, the change will be detected and the error will be identified as occuring in bit 4 because that is the only bit that has changed.
If bit 3 changes (a data bit) it will be detected by parity bits 1 and 2, which both reference it. Now the magic: add the positions of the parity bits that detected the error: 1 + 2 = 3, which is the position of the error.
If bit 9 changes this will be detected by parity bits 1 and 8.
If bits 6 and 9 flip this will be detected by parity bits 2 and 4 and 8...
See spreadsheet for worked example.
The Hamming distance between two strings of equal length is the number of positions for which the corresponding symbols are different. It records the minimum number of substitutions required to change one into the other, or the number of errors that transformed one string into the other.
Programs consist of instructions which are stored as strings of binary digits.
| Wikipedia | Binary exercises | Binary addition |
| Truth tables | Presentation |