Hamming code detects and corrects errors in binary transmissions by adding parity bits in a sequence. Hamming(7,4) is the most common code. Parity bits check nearby positions, and errors are corrected by adding the bits in the check sequence.
A Hamming code is a method of detecting and correcting errors in a binary transmission. It does this by including additional binary digits in the sequence used for checking, as well as an algorithm that provides the detection logic. Such code is capable of finding two errors in any sequence of bits and repairing one bit that may be incorrect. The most commonly referred to Hamming code is known as Hamming(7,4), where the four indicates the original number of leading bits and the seven represents the total number of bits in the sequence after the additional control bits have been included.
The technique is named after its creator, Richard Hamming, who published the method in 1950. The way Hamming’s code works is by taking a string of bits and inserting additional control bits, called parity bits, into the sequence. Check bits are always injected into a position that is a power of two, so any number of bits can be checked by including extra parity bits. This can continue until the last parity bit added to the sequence is in a position that is a power of two less than or equal to the final position in the sequence.
With all parity bits in place, the remaining positions are the actual data bits. Given the four-bit example, then, bit positions one, two, and four would be the parity bits, while positions three, five, six, and seven are the data. Once this sequence is established, the logic of the Hamming code comes into play.
In a Hamming code, each of the parity bits that have been added to the sequence is used to check for some of the bit positions they are near, including themselves. The parity bit in position one checks every other bit position, which is essentially every odd position in the sequence. The second parity bit, at position two, checks positions two and three, then skips two positions, checks two more positions, skips two more, and so on. If there is a parity bit in position four, it acts similarly in that it checks positions four through seven, then skips four positions, checks four more, and moves on. Each parity bit in the sequence continues in this way throughout the sequence.
The process by which a Hamming code detects and corrects an error is to add the bits in the check sequence for each parity check, each of which must exit an even number. Given the seven-bit example, bits one, three, five, and seven are added together for the first parity check. If the total is an even number, parity is checked, but if the total is odd, an error occurs. Since the parity checks overlap, you will see two of these errors. When the positions of two parity bits that fail to give even totals are added together, it will reveal the bit that needs to be fixed.
In the seven-bit Hamming code example, consider that the bit in position number five is incorrect. The sum of the bits in positions one, three, five, and seven will add up to odd, as will the sum of the bits in positions four through seven. This indicates that the parity checks for the control bits in positions one and four have failed. When one and four are added together, the total is five, which is the bad bit position in the transmission that needs to be fixed.
Protect your devices with Threat Protection by NordVPN
