Hamming decoding

Have you ever sent an important message, only to find out later that it contained errors? Perhaps some bits got scrambled during transmission, or maybe there was a mistake in the encoding process. Whatever the cause, errors in digital communication can be frustrating, and even disastrous in some cases. But fear not, because there is a solution: Hamming decoding!

You may recall from the previous topic that a Hamming code involves adding extra parity bits to a message in order to facilitate error detection and correction. Hamming decoding, on the other hand, is the process of using these parity bits to identify and fix errors that may have occurred during transmission. By detecting and correcting single-bit errors, Hamming decoding helps ensure the accuracy and reliability of data transmission in digital communication systems. Let's get on with the algorithm itself.

Detecting and correcting errors

We already know how to compute the Hamming code, however, we yet are unable to use it to correct errors. How is it done? The beauty of Hamming decoding lies in its simplicity: when the data arrives at the receiver end, it checks the received bits and compares them with the expected bits. Single-bit error detection can be done by following some simple steps:

1. Recalculate the expected parity bits for the received data. This can be done by resetting the values of parity bits equal to zero and repeating the procedure from encoding to recalculate these parity bits. How to find, where the parity bits are? Pretty simple, if you recall that parity bits are located in positions that are powers of two.
2. Compare the corresponding parity bits in the expected and received string. If they are equal, write $0$. Otherwise, write $1$.
3. Concatenate these ones and zeroes to form a binary number and reverse it.
4. Convert it to a decimal number. This is exactly the position of the incorrect bit. If the position is zero, it means no error has occurred.
5. Flip the value of this incorrect bit. This gives us the correct data.
6. Remove the parity bits in order to get the original binary string that was destined to be delivered.

It is worth noting if multiple-bit errors take place, the algorithm can detect that an error has occurred, but it cannot identify the exact positions of the errors. In such cases, the receiver will request the message to be retransmitted.

Example: 1100101

We already know the Hamming code of the string $1100101$ from the previous topic: it is equal to $c_1 = 00111000101$. Let's suppose that while transmitting it, an error occurred and the fifth character was flipped. In other words, the receiver got the string $c_2 = 00110000101$ instead.

How would we detect such an error? Let's use Hamming decoding for this:

1. First, we have to recalculate the parity bits for $c_2$ following the definition. Here, we get $p_1 = 1$, $p_2 = 0$, $p_3 = 0$, and $p_4 = 0$, as seen below.

   

2. Now we compare the expected values with the parity bits that are actually present in $c_2$, which are $q_1 = 0$, $q_2 = 0$, $q_3 = 1$, and $q_4 = 0$ (the green boxes in $c_2$). We see that: $p_1 \neq q_1, \quad p_2 = q_2,\quad p_3 \neq q_3,\quad p_4 = q_4$.

   

3. Hence, we get the binary string $1010$ that after reversing becomes $0101$. Converting it into decimal, we get $0\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0 = 5$, which means that the error occurred in the fifth bit.
4. We flip the value of this bit, ending up with the correct code word, $c_1$.
5. Finally, we remove the parity bits and receive the original string $1100101$. Hooray!

Time complexity and pseudocode

They say "many words is poverty". Let's take a look at the pseudocode of the algorithm:

function hamming_decode(code):
    parity_pos = [2^i, i = 0, 1, ...]          // Array of parity bit positions
    pv_exp = []                                // Array of expected parity bit values
    pv_code = [code[parity_pos]]               // Array of current parity bit values in code
    
    for pos in parity_pos:                     // Compute the parity values for each parity bit
        pv_exp.append(compute_parity_bit(code, pos))
    
    n = len(pv_code)
    error_pos = 0
    for i in range[1, n + 1]:                  // Indexing starts from 1
        if pv_code[i] != pv_exp[i] then
            error_pos += 2^{i - 1}             // Determine the position of any error in the code word
    
    if error_pos > 0 then
        code[error_pos] ^= 1                   // Correct the error, if one was detected
    
    // denote by non_parity_bits the positions for non parity bits
    m = code[non_parity_bits]                  // Extract the message bits from the code word
    
    return m

Similarly to the encoding process, here the longest process is recalculating the parity bits, which takes $O(n\log n)$. Indeed, the comparison, removal, and conversion to decimal are done in linear time in terms of $r$ (the number of parity bits), and flipping takes constant time.

Features and limitations

Like everything in this world, Hamming Code has its advantages and drawbacks.

Pros:

• Hamming code can be used to detect and correct single-bit errors in both data and control information.
• In computer memory systems or satellite communication, for example, single-bit errors are common due to factors such as cosmic radiation and electronic noise.
• It is a systematic code, which means that the original data bits are included in the code word, making it easier to decode.
• Hamming code is relatively simple to implement and can be used to improve the reliability in digital communication systems such as Ethernet, wireless communication, and fiber optic communication

Cons:

• Hamming code cannot handle multiple errors or errors that affect multiple bits.
• The use of additional parity bits increases the length of the code word, which can impact transmission efficiency and storage requirements.
• Hamming code is not suitable for applications where high levels of reliability are required, such as in mission-critical systems.

Conclusion

Here is a recap of the topic: Hamming decoding uses the Hamming code to detect possible errors that might have happened during data transmission. The steps of the process are relatively simple:

1. Calculate the expected parity bits of the received word.
2. Compare the parity bits and create a reversed binary word.
3. When converted to decimal, this shows the position of the error.
4. Flip the value of the incorrect bit and obtain the initial word.

Its time complexity is $O(n\log n)$, the same as the encoding process. It is worth noting that such an algorithm works well on single-bit errors, however, it is unable to correct multiple-bit errors.