错误检测：汉明码 | Baeldung中文网

1. Introduction

Error detection and correction are crucial to ensure reliable data transmission between devices. One of the most widely used error detection and correction methods is Hamming code. Richard Hamming developed it in 1950 at Bell Labs. In particular, it can detect and correct a single-bit error by adding redundant (or parity) bits to the original data.

A few use cases of Hamming code include:

- Computer memory systems: RAM and hard disk
- Communication networks: Bluetooth, ethernet, and wi-fi
- Digital signal processing: Satellite communications and digital audio broadcasting

In this tutorial, we’ll first study the basic terms of Hamming code, such as redundant bits, parity bits, and parity bit calculation. Next, we’ll provide an illustrative example of how to encode a data block using the Hamming code. Then, we’ll explore the various steps involved in error detection and correction. After that, we’ll discuss the advantages and limitations of the Hamming code. Finally, we’ll wrap up the tutorial with a brief summary of the topics covered.

2. Hamming Code Basics

In this section, we’ll discuss the fundamental terminologies of the Hamming code, including redundant bits, parity bits, and parity bit calculation.

2.1. Redundant Bits

The central idea of the Hamming code is based on redundancy. In general, the sender first divides the original data into fixed-sized blocks. It then adds some extra redundant bits to each data block before transmitting the block to the receiver. Upon reception, the receiver uses these bits to detect transmission error, locate the corrupted bit, and correct it. We can calculate the required number of redundant bits using the equation:

$[ 2^R \geq M + R + 1]$

In this equation, is the number of redundant bits, and is the number of data bits in a block.

2.2. Parity Bits

We add parity bits as redundant bits to an original data block for detecting and correcting errors during transmission. These bits ensure that each data block’s total count of is either even or odd. There are two types of parity bits:

Odd parity bit: We set a parity bit to when the count of in a bit sequence is even; otherwise, we configure it to .

Even parity bit: We fix a parity bit to if the count of in a given set of bits is odd; otherwise, we set it to .

2.3. Parity Bit Calculation

A Hamming code has number of bits, which is the sum of data bits and parity bits. We now discuss the step-by-step process to obtain the position and value of parity bits:

At first, we compute the number of parity bits using $2^R \geq M + R + 1$ and the total number of bits in the Hamming code using
Next, we convert the bit positions from to into binary numbers, i.e., $[0001,0010,0011,0100, 0101, 0110, 0111,1000,\cdots]$
Then, we label the bit positions corresponding to the power of as parity bits and the remaining positions as the data bits, e.g., $[P_1,P_2,D_1,P_3, D_2, D_3, D_4,P_4,\cdots]$
At last, we determine the value of each parity bit in the Hamming code iteratively. In each iteration, we determine the value of parity bit by counting the number of in the bit positions that have in the $i^{th}$ position from the least significant bit in their binary representations. Then, we set the parity bit to if the number of is odd, considering even parity; otherwise, we set it to

3. An Illustrative Example

Let’s break down the process of generating a Hamming code by looking at an example binary data block $\boldsymbol{10110110001}$ . This will help us understand how the Hamming code works and how it detects and corrects errors during data transmission. We’ll now apply each of the steps discussed in the previous section, one by one.

Step 1: The number of parity bits is R = 4 since M = 11 and $2^4 \geq 11 + 4 + 1$ . Therefore, the length of the Hamming code is N = 11 + 4 , that is, N = 15 .

Step 2: The binary conversion of the bit positions from to is [0001,0010,0011,0100, 0101, 0110, 0111,1000,1001,1010,1011,1100,1101,1110,1111] .

Step 3: The parity bits are placed at the positions [1,2,4,8] since they are power of . In contrast, the data bits are kept at the positions [3,5,6,7,9,10,11,12,13,14,15] . The image below shows the labeling of parity and data bits:

4. Error Detection and Correction

Let’s first discuss how to detect if there is an error in the received code. To do so, we recalculate the values of parity bits and perform parity checks. In particular, we record a for a parity check if the assigned and observed parity bits do not match. Otherwise, we record a . The recorded values are then written from right to left to form the checking number. The code is error-free if the checking number is zero. Otherwise, an error has occurred at the bit position corresponding to the checking number, given that there is only a single-bit error.

Let’s assume that the eleventh bit of the codeword generated in the previous section is changed from to during transmission. Then, the received code is:

hamming code received data

Now, we recalculate the parity bits and record their values based on the assigned and observed parity bits. The images below show the recorded values for parity bits P_1 , P_2 , P_3 , and P_4 , respectively:

hamming code p1 detect hamming code p2 detect hamming code p3 detect

hamming code p4 detect

Let’s obtain the checking number by writing the recorded values from right to left, i.e., P_4P_3P_2P_1 = 1011 , which is equal to decimal number eleven. This signifies that the received code has an error at the eleventh bit. In order to correct it, we just have to toggle the eleventh bit and the corrected code is:

hamming code received data correct

5. Advantages and Limitations

The key advantages and notable limitations of the Hamming code are:

Advantages

Limitations

1. Hamming code is easy to understand and implement.

1. Hamming code can detect and correct only single-bit errors.

2. It can efficiently detect and correct single-bit errors in data without the need for retransmission.

2. The addition of redundant bits increases the size of the data block and reduces the efficiency of transmission.

3. Hamming code is a cost-effective method as it does not require expensive hardware or software.

3. The fixed block size of the Hamming code may not be suitable for applications with variable data size.

4. It can be adapted to work with different block sizes, making it a versatile solution for error detection and correction.

4. It may not be flexible enough to handle different error patterns or positions within the codeword.

6. Conclusion

This tutorial first provides a brief overview of the Hamming code and its use cases. It then explains the basic concepts of the Hamming code, such as redundant bits, parity bits, and parity bit calculation.

Next, it presents an illustrative example of encoding a data block using parity bits. Later, it discusses and demonstrates the steps involved in error detection and correction. In the end, it highlights the key advantages and limitations of the Hamming code.

Persistence

REST

Security