Browse Definitions :
Definition

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 2p ≥ 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 24 ≥ 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).

memory modules
Hamming code is commonly used ECC RAM to detect and correct errors when data is stored or transmitted.

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.

Position DEC

7

6

5

4

3

2

1

Position BIN

111

110

101

100

011

010

001

Data/Parity

Data 7

Data 6

Data 5

Parity 4

Data 3

Parity 2

Parity 1

Parity Bit Coverage

P1

x

x

x

x

P2

x

x

x

x

P3

x

x

x

x

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

First, enter the binary values in the data positions.

Data/Parity

Data 7

Data 6

Data 5

Parity 4

Data 3

Parity 2

Parity 1

1

1

0

x

0

x

x

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:

Data/Parity

Data 7

Data 6

Data 5

Parity 4

Data 3

Parity 2

Parity 1

1

1

0

0

0

0

1

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.

This was last updated in July 2022

Continue Reading About Hamming code

SearchNetworking
  • network security

    Network security encompasses all the steps taken to protect the integrity of a computer network and the data within it.

  • cloud-native network function (CNF)

    A cloud-native network function (CNF) is a service that performs network duties in software, as opposed to purpose-built hardware.

  • Wi-Fi 6E

    Wi-Fi 6E is one variant of the 802.11ax standard.

SearchSecurity
  • incident response

    Incident response is an organized approach to addressing and managing the aftermath of a security breach or cyberattack, also ...

  • MICR (magnetic ink character recognition)

    MICR (magnetic ink character recognition) is a technology invented in the 1950s that's used to verify the legitimacy or ...

  • What is cybersecurity?

    Cybersecurity is the protection of internet-connected systems such as hardware, software and data from cyberthreats.

SearchCIO
  • privacy compliance

    Privacy compliance is a company's accordance with established personal information protection guidelines, specifications or ...

  • contingent workforce

    A contingent workforce is a labor pool whose members are hired by an organization on an on-demand basis.

  • product development (new product development -- NPD)

    Product development, also called new product management, is a series of steps that includes the conceptualization, design, ...

SearchHRSoftware
  • talent acquisition

    Talent acquisition is the strategic process employers use to analyze their long-term talent needs in the context of business ...

  • employee retention

    Employee retention is the organizational goal of keeping productive and talented workers and reducing turnover by fostering a ...

  • hybrid work model

    A hybrid work model is a workforce structure that includes employees who work remotely and those who work on site, in a company's...

SearchCustomerExperience
  • digital marketing

    Digital marketing is a general term for any effort by a company to connect with customers through electronic technology.

  • hockey stick growth

    Hockey stick growth is a growth pattern in a line chart that shows a sudden and extremely rapid growth after a long period of ...

  • Salesforce Trailhead

    Salesforce Trailhead is a series of online tutorials that coach beginner and intermediate developers who need to learn how to ...

Close