Hamming code in C++

Practical Application

In practical scenarios, Hamming code is used in situations where an error-free transmission is critical. It's commonly seen in computer memory (RAM), wireless communication, and data storage devices. By implementing Hamming code, these systems can automatically detect and correct errors that occur due to various factors like electromagnetic interference or hardware malfunctions.

Implementing Hamming Code in C++

Now, let's look at how to implement Hamming code in C++. The process involves two main steps: encoding and decoding.

Encoding

This step includes generating the Hamming code from the original data. The C++ code will calculate the redundant bits and insert them into the correct positions to form the code word.

Decoding

This is where the magic of error correction happens. The code will check for errors in the received code word and correct them if necessary.

Here's a simple example to illustrate this:

#include <iostream>
#include <vector>
// Function to calculate redundant bits
int calcRedundantBits(int dataBits) {
    // Code to calculate number of redundant bits
    // ...
}

// Function to generate Hamming Code
std::vector<int> generateHammingCode(std::vector<int> data, int r) {
    std::vector<int> hammingCode;
    // Code to insert data & redundant bits into hammingCode
    // ...
    return hammingCode;
}
// Main function
int main() {
    std::vector<int> dataBits = {1, 0, 1, 1}; // Example data bits
    int r = calcRedundantBits(dataBits.size());
    std::vector<int> hammingCode = generateHammingCode(dataBits, r);
    // Code to display the Hamming Code
    // ..
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

In this code snippet, we start by including the necessary headers. The calcRedundantBits function calculates the number of redundant bits needed for a given number of data bits. The generateHammingCode function then takes these data bits and redundant bits and generates the final Hamming code.

This is just a basic structure. The actual implementation of calcRedundantBits and generateHammingCode functions would involve a bit more logic, which we'll delve into later.

Detailed Code Implementation

Calculating Redundant Bits

First, we need to determine the number of redundant bits required for a given set of data bits. The number of redundant bits, r, can be calculated using the formula 

2^r≥m+r+1, where m is the number of data bits. Here's how we can implement this in C++:

int calcRedundantBits(int dataBits) {
    int r = 0;
    while (pow(2, r) < dataBits + r + 1) {
        r++;
    }
    return r;
}

You can also try this code with Online C++ Compiler

Run Code

This function iteratively increases r until the condition 

2^r≥m+r+1 is met.

Generating the Hamming Code

Now, let's generate the Hamming code. The generateHammingCode function will place the redundant bits and data bits at their respective positions in the Hamming code:

std::vector<int> generateHammingCode(std::vector<int> data, int r) {
    int m = data.size();
    int totalBits = m + r;
    std::vector<int> hammingCode(totalBits, 0);
    // Placing the data bits
    for (int i = 0, j = 0; i < totalBits; i++) {
        // If the position is a power of 2, skip (for redundant bits)
        if (pow(2, j) == i + 1) {
            j++;
            continue;
        }
        hammingCode[i] = data[j++];
    }
    // Calculating redundant bits values
    for (int i = 0; i < r; i++) {
        int x = pow(2, i);
        for (int j = 0; j < totalBits; j++) {
            // If position has the i-th bit set in its binary representation
            if ((j + 1) & x) {
                hammingCode[x - 1] ^= hammingCode[j];
            }
        }
    }
    return hammingCode;
}

You can also try this code with Online C++ Compiler

Run Code

In this function, we first allocate space for the Hamming code with totalBits (data bits + redundant bits). We then iterate over the total bits, placing the data bits in positions that are not powers of 2. For the redundant bits, we calculate their values using XOR operations on the bits that have the corresponding bit position set in their binary representation.

Displaying the Hamming Code

Finally, we can display the generated Hamming code:

// Main function
int main() {
    std::vector<int> dataBits = {1, 0, 1, 1}; // Example data bits
    int r = calcRedundantBits(dataBits.size());
    std::vector<int> hammingCode = generateHammingCode(dataBits, r);

    std::cout << "The Hamming Code is: ";
    for (int i = 0; i < hammingCode.size(); i++) {
        std::cout << hammingCode[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Code

• C++

C++

#include <stdio.h>

#include <math.h>

#include <bits/stdc++.h>

int calcRedundantBits(int dataBits) {

    int r = 0;

    while (pow(2, r) < dataBits + r + 1) {

        r++;

    }

    return r;

}

std::vector<int> generateHammingCode(std::vector<int> data, int r) {

    int m = data.size();

    int totalBits = m + r;

    std::vector<int> hammingCode(totalBits, 0);

    // Placing the data bits

    for (int i = 0, j = 0; i < totalBits; i++) {

        // If the position is a power of 2, skip (for redundant bits)

        if (pow(2, j) == i + 1) {

            j++;

            continue;

        }

        hammingCode[i] = data[j++];

    }


    // Calculating redundant bits values

    for (int i = 0; i < r; i++) {

        int x = pow(2, i);

        for (int j = 0; j < totalBits; j++) {

            // If position has the i-th bit set in its binary representation

            if ((j + 1) & x) {

                hammingCode[x - 1] ^= hammingCode[j];

            }

        }

    }


    return hammingCode;

}


int main() {

    std::vector<int> dataBits = {1, 0, 1, 1}; // Example data bits

    int r = calcRedundantBits(dataBits.size());

    std::vector<int> hammingCode = generateHammingCode(dataBits, r);



    std::cout << "The Hamming Code is: ";

    for (int i = 0; i < hammingCode.size(); i++) {

        std::cout << hammingCode[i] << " ";

    }

    std::cout << std::endl;

    return 0;

}

You can also try this code with Online C++ Compiler

Run Code

  Output

When you run this program with the example data bits {1, 0, 1, 1}, it will display the corresponding Hamming code.

Frequently Asked Questions

How does Hamming Code detect and correct errors?

Hamming Code uses redundant bits to form patterns, detecting and pinpointing single-bit errors for correction by flipping the affected bit.

What makes Hamming Code efficient?

Its minimal redundant bits offer a compact solution for single-bit error correction, balancing data integrity with efficiency.

Can Hamming Code handle multiple-bit errors?

While great for single-bit errors, Hamming Code can only detect, but not correct, multiple-bit errors, requiring more advanced codes for such issues.

Conclusion

In this journey through Hamming Code in C++, we've covered its theoretical background, practical applications, and detailed code implementation. By now, you should have a strong grasp of how Hamming Code works and how to implement it in C++. This knowledge is not just a tool in your coding arsenal but also a stepping stone into the broader world of error detection and correction in digital communication.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. 

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.