Hamming code

What is Hamming code?

Hamming code is an error correction system that can detect and correct errors when data is stored or transmitted. It requires adding additional parity bits with the data. It is commonly used in error correction code (ECC) RAM. It's named after its inventor, Richard W. Hamming.

Whenever data is transmitted or stored, it's possible that the data may become corrupted. This can take the form of bit flips, where a binary 1 becomes a 0 or vice versa. Error correcting codes seek to find when an error is introduced into some data. This is done by adding parity bits, or redundant information, to the data.

If enough parity data is added, it enables forward error correction (FEC), where errors can be automatically fixed when read back. FEC can increase the data transmission rate for noisy channels by reducing the amount of necessary retransmits.

Hamming code uses a block parity mechanism. The data is divided into blocks, and parity is added to the block. Hamming code can correct single-bit errors and detect the presence of two-bit errors in a data block.

The amount of parity data added to Hamming code is given by the formula 2^p ≥ d + p + 1, where p is the number of parity bits and d is the number of data bits. For example, if you wanted to transmit 7 data bits, the formula would be 2⁴ ≥ 7 + 4 + 1, so 4 parity bits are required.

The type of error correcting is given as the name of the algorithm, the total number of bits in the block and then the number of effective data bits. Therefore, Hamming encoding with 4 data bits and 3 parity bits for a total of 7 total bits is given as Hamming(7,4).

Standard Hamming code can only detect and correct a single-bit error. If two bits are in error, it is possible that the two errors will look like a single-bit error. To account for that, an additional overall parity bit can be added to reliably detect errors in two bits. This is known as single error correction/double error detection (SECDED).

Hamming code history

Before Hamming code, there were several error correction methods in use that were not as efficient or effective. The simplest method involves adding a single parity bit. This can detect a single error but not detect two-bit errors nor correct the error. Another method was repeating each bit three times. This could detect and correct a single bit error but not errors in two bits. Repeating the bits was also very inefficient.

Richard Hamming worked for Bell Labs in the 1940s and 1950s. During that time, computers used relays and read information from punched paper tape. These systems were often prone to errors relating to the paper tape being misread or relays getting stuck. If an operator was on hand when the error occurred, the program could be restarted; if the error occurred outside of working hours, the computer would skip the entire program, losing time and work.

Hamming reasoned that, if a computer can detect an error, it could also correct the error. So, he began working on an error correcting algorithm, and in 1950, he published the Hamming code.

Hamming code uses

Hamming code is used in situations where consistency is more important than efficiency of transmission. Its transmission efficiency goes up as the block size increases. In Hamming(7, 4), the effective data rate is only 0.571, while Hamming(255, 247) is 0.969.

Hamming code is relatively simple to use and can be implemented in hardware. This also means that it is fast to compute. These properties make it perfect for use in error correcting computer memory since it is possible for computer RAM to have an error or bit flip from radiation or cosmic rays striking the memory cell. ECC RAM uses Hamming code with SECDED to automatically correct single errors and raise an alarm on two errors.

To illustrate the value of ECC RAM, imagine a bank database server was recording a deposit of $100. As an 8-bit integer, that amount would be stored as the binary number 01100100. If a cosmic ray changed the first bit, it would change the deposit amount to $228, or 11100100. ECC memory would catch and correct this error automatically. In the rare case two bits became corrupted, the computer would assume that something was wrong with its hardware and cause a kernel panic or blue screen to protect the data integrity.

Hamming code is not used in modern data transmission. Wired data connections are generally not noisy enough to warrant the overhead of added parity data, and if an error is encountered, it may be faster to ask the sender to retransmit the faulty packet. Also, low-density parity-check (LDPC) codes are more efficient to transmit but require more computation than Hamming code. Since modern computers have more processing power available, LDPC is used for Wi-Fi 6 and 10GBASE-T Ethernet.

One area where Hamming code is used for data transmission is in satellite and space communication. Because of the great distances involved, long transmit times and the requirements for accurate data, it is preferred to use the slower but more precise Hamming code and sacrifice overall transmission rate.

Hamming code example and technical details

Generating and reading a Hamming code is simple and can be done on paper.

The general process to make a Hamming code is as follows. Note that all the following binary is given as big-endian numbers, where the most significant bit is on the left and least significant on the right:

• Find the total block length with both data bits and parity bits.
• Number each bit with its binary value.
• Each value with only a single binary 1 and the remaining digits 0s (powers of 2) become parity bits. All other bits are data bits.
• Each parity bit covers all data bits that have the parity bit's value set to 1. Put another way, where the data bit value is AND checked to the parity bit value it is greater than one:
  • For example, parity bit 1 (001) covers data bit 3 (011), bit 5 (101) and bit 7 (111).
  • Parity bit 2 (010) covers data bit 3 (011), bit 6 (110) and bit 7 (111).
  • Parity bit 4 (100) covers data bit 5 (101), bit 6 (110) and bit 7 (111).
• Set the parity bit equal to 1 if all the values of its data bits are odd; set it to 0 if the total number is even.

This can be expressed as a chart. Note that each data bit is covered by more than one parity bit.

As an example, let's encode the decimal value 12 (binary 1100) in Hamming code.

First, enter the binary values in the data positions.

Next, compute the parity values by checking if the sum of the protected bits is even or odd:

• Data 7, 5 and 3 added equals 01, an odd number. So, set parity 1 to 1.
• Data 7, 6 and 3 added equals 10, an even number. So, set parity 2 to 0.
• Data 7, 6 and 5 added equals 10, an even number. So, set parity 4 to 0.

The results are the following:

The parity bits are checked against the data bits on the receive side to validate that none of them have been changed.

Suppose that data bit 6 was flipped. In that case, parity 2 and 4 would not be correct. The decoder would see that means that data 6 was in error and correct it.

Suppose parity bit 2 was in error. Since none of the other parity bits would be wrong, it would know that only the parity was wrong and ignore it.

Hamming code can thereby detect and correct any single-bit error. If two data bits were flipped, it could detect it but not correct the error. Because the parity bits themselves do not have any parity data stored, if a data bit and a parity bit were flipped, it would be indistinguishable from a single-bit flip. Therefore, an additional overall parity bit is often added to reliably detect errors with 2 bits.

See also: forward error correction, modem error-correcting protocols, SPI NAND host-side error correction, encoding and decoding, most significant bit or byte, classical computing and Extended Binary Coded Decimal Interchange Code.