What Is a Hamming Code?

Hamming code is a linear debugging code in the field of telecommunications, named after the inventor Richard Wesley Hamming. Hamming codes insert a verification code into the transmitted message stream. When a computer stores or moves data, data bit errors may be generated to detect and correct single bit errors. Because Hamming codes are simple, they are widely used in memory (RAM).

Hamming code is a linear debugging code in the field of telecommunications, named after the inventor Richard Wesley Hamming. Hamming code inserts a verification code into the transmitted message stream. When the computer stores or moves data, data bit errors may be generated to detect and correct single bit errors. Because Hamming codes are simple, they are widely used in memory (RAM).

Chinese name

Hamming code

Foreign name

Hamming Code

Hamming code history

People used a variety of encoding methods to check for errors before the Hamming code appeared, but none of them can get the same effect under the same space consumption as the Hamming code.

In 1940, Hamming worked at Bell Labs, using a Bell Model V computer, an electromechanical relay machine with a cycle time of a few seconds. The input end relies on a punched card, which inevitably causes some reading errors. On weekdays, special codes will detect the error and flash the lights, allowing the operator to correct the error. On weekends and during work, the machine simply moves to the next job without an operator. Hamming worked on the weekend, and he became increasingly frustrated when he had to restart the project after an error with an unreliable card reader. In the following years, he developed increasingly powerful debugging algorithms in order to solve debugging problems. In 1950, he published what is called the Hamming code today. Hamming codes are now widely used.

Hamming code check

Similar to other error check codes, the Hamming code also uses the concept of parity bits. By adding some bits after the data bits, the validity of the data can be verified. Using more than one check digit, Hamming codes can not only verify whether the data is valid, but also indicate the location of the error if the data is wrong.

Hamming code error correction

At the receiving end, the error correction function is realized by automatically correcting errors in transmission through error correction decoding, which is called forward error correction FEC. When there is a lot of noise in the data link, FEC can increase data throughput. Forward error correction can be achieved by adding redundant bits (also called error correction bits) to the transmission code sequence. However, this method is more expensive than a simple retransmission protocol. Hamming codes use the parity block mechanism to reduce the cost of forward error correction.

Hamming code checking method

If a piece of information contains more bits for error correction, and by properly arranging these error correction bits, different error bits produce different error results, then we can find the error bits. In a 7-bit message, there are 7 possibilities for a single bit error, so 3 error control bits are sufficient to determine whether an error occurred and which one went wrong.

The Hamming code SECDED (single error correction, double error detection) version also adds a detection bit, which can detect two or less simultaneous bit errors, and can correct a single bit error. Therefore, when the Hamming distance of the bit pattern of the transmitting end and the receiving end is less than or equal to 1 (only 1 bit error occurs), reliable communication can be achieved. In contrast, a simple parity check code can only detect an odd number of errors in addition to correcting the errors.

The following general algorithm can generate a Hamming code that can correct one bit for any digit:

1. Number the data bits (from left to right) from 1, starting with 1, 2, 3, 4, 5 ...

2. Convert the position numbers of these data bits to binary, 1, 10, 11, 100, 101, etc.

3. All the power-of-two bits in the position number of the data bit (numbers 1, 2, 4, 8, etc., that is, only one 1 in the binary representation of the data bit position number) are the check bits

4. The data bits in all other positions (at least 2 of the binary representation of the data bit position number are 1) are the data bits

5. Each bit of data is contained in a specific two or more check digits, these check digits depend on the binary representation of the position value of these data bits

(1) The parity bit 1 covers all the data in the binary representation of the data bit position number. The penultimate data is 1: 1 (the parity bit itself, here are all binary, the same below), 11, 101, 111, 1001, Wait

(2) Check digit 2 covers all data bits. The binary representation of the serial number is the data with the penultimate digit being 1: 10 (check digit itself), 11, 110, 111, 1010, 1011, etc.

(3) The parity bit 4 covers all the data in the binary position of the data bit position number. The third to last data is 1: 100 (the parity bit itself), 101, 110, 111, 1100, 1101, 1110, 1111, etc.

(4) The parity bit 8 covers all the data in the binary representation of the position number of the data. The penultimate data is 1: 1000 (the parity bit itself), 1001, 1010, 1011, 1100, 1101, 1110, 1111, etc.

(5) In short, all check digits cover numbers where the data position and the value of the binary AND of the check digit position are not zero.

Either odd or even parity is possible. Even parity is simpler from a mathematical point of view, but it makes no difference in practice. The general pattern of check digits can be expressed as follows:

Observe the above table to find a more intuitive rule: the i-th test bit is the 2 ^ (i-1) bit, starting from this bit, the 2 ^ (i-1) bit is tested, and the 2 ^ (i-1 is skipped ) Bits ... and so on. For example, the third check digit p4 in the table above starts from 23-1 = 4 digits, checks 4 digits of 5, 5, 6, 7 and then skips 4 digits of 8, 9, 10, 11 and then checks 12, A total of 4, 14, 15 ... ^[1]

Hamming code encoding principle

Parity check is a check method that adds a parity bit to indicate whether the previous data contains an odd number or an even number of ones. If an odd number of bits change during the transmission, this error will be detected (note that the parity bits themselves may also change). Generally, if the data contains an odd number of 1s, the parity bit is set to 1; otherwise, if the data contains an even number of 1s, the parity bit is set to 0. In other words, the new data consisting of the original data and the parity bits will contain an even number of 1. The parity check is not always valid. If the data has an even number of bits changed, the parity will still be correct. Therefore, errors cannot be detected. Also, even if parity detects an error, it cannot indicate which bit is wrong, making it difficult to correct. The data must be discarded as a whole and retransmitted. In a noisy medium, successful data transmission may take a long time or may not be completed. Although the effect of parity check is not good, because it only requires one extra bit of space overhead, this is the least expensive detection method. And, if the bit in which the error occurred is known, parity can also recover the data. If a piece of information contains more bits for error correction, and by properly arranging these error correction bits, different error bits produce different error results, then we can find the error bits. In a 7-bit message, there are 7 possibilities for a single data bit error, so 3 error control bits are sufficient to determine whether an error occurred and which one went wrong. ^[2]

In general, if the Hamming code length is n and the number of information bits is k, the number of supervision bits is r = nk. If you want to construct r supervising relations with r supervising bits to indicate n possible positions of a bit error code, you need

2 ^r -1n or 2 ^r k + r + 1 ^[3]

Take the data code 1101 as an example to explain the principle of Hamming code. At this time, D4 = 1, D3 = 1, D2 = 0, and D1 = 1. When P1 is encoded, first add the binary codes of D4, D3, and D1. The result is The odd number is 3, and the Hamming code encodes an odd number result as 1, and an even number result is 0 (odd number bits. If the odd number result is 0. Even number result is 1, it is called even number bits), so the value of P1 is 1, D4 + D2 + D1 = 2, even number, then P2 value is 0, D3 + D2 + D1 = 2, even number, P3 value is 0. In this way, referring to the position table above, the result of Hamming code processing is 1101001. In this 4-bit data code example, we can find that each Hamming code is encoded based on three data codes. Here is their correspondence table:

Hamming code	Data code for encoding
P1	D8, D4, D1
P2	D8, D2, D1
P3	D4, D2, D1

From the encoding form, we can find that the Hamming code is a very strict encoding method. In this example, the verification and correction of specific code bits are achieved through 3 combined detections of 3 data bits of 4 data bits (but only one bit error is allowed, and two errors cannot be detected. This is from This can be seen in the error correction example below). During the check, each Hamming code is added to its corresponding data bit value. If the result is even (error correction code is 0), it is correct. If it is odd (error correction code is 1), the current Hamming code There are errors in the corresponding three data bits. At this time, the specific operation of the other two Hamming codes is used to determine which bit is the problem.

Still the example of 1101 just now, the correct encoding should be 1101001, corresponding to D4 D3 D2 D1 P3 P2 P1. If the third data bit becomes 1 due to interference during transmission, it becomes 1111001, that is, D2 = 1. During detection, the result of P1 = D4 + D3 + D1 = 1 + 1 + 1 is an odd number 3, divided by 2 and the remainder 1, the original error correction code of the first bit is 1, correct. The result of P2 = D3 + D2 + D1 is an odd number 3, divided by 2 and the remainder 1, and the original error correction code of the second digit is 0, and there is an error. The result of P3 = D3 + D2 + D1 is an odd number 3, divided by 2 and the remainder 1, and the original error correction code of the third bit is 0, and there is an error. It can be inferred that there is an error in the second position. ^[4]

Hamming code ratio

So what is the ratio between the number of Hamming codes and the number of data bits? In the above example, the data bits are 4 bits, plus 3 bits of Hamming code is 7 bits, and the power of 2 to the power of 3 is 8. There is a rule here, that is 2 ^ PP + D + 1, where P represents the number of Hamming codes and D represents the number of data bits, such as 4 bits of data, plus 1 is 5, which can be greater than 5 The power of 2 is 3 (2 ^ 3 = 8, 2 ^ 2 = 4). In this way, we can calculate the number of Hamming codes required for any data bit: 7-bit data requires 4-digit Hamming code (16> 4 + 7 + 1), and 64-bit data requires 7-digit Hamming code (128> 64 + 7 + 1), everyone can calculate accordingly. At this time, their coding rules are also different from the 4-bit code.