Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Basics of Hamming Code
3.
Practical Application
4.
Implementing Hamming Code in C++
4.1.
Encoding
4.2.
Decoding
4.3.
Detailed Code Implementation
5.
Generating the Hamming Code
6.
Displaying the Hamming Code
6.1.
C++
7.
Frequently Asked Questions
7.1.
How does Hamming Code detect and correct errors?
7.2.
What makes Hamming Code efficient?
7.3.
Can Hamming Code handle multiple-bit errors?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Hamming code in C++

Author Ravi Khorwal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Hamming code, a fundamental concept in computer science, is a technique used for error detection and correction in digital communication systems. It's named after its inventor, Richard Hamming, and has become an essential tool in ensuring data integrity across various communication channels. As a coding student, grasping Hamming code is not just about learning an algorithm; it's about understanding the backbone of reliable data transmission. In this article, we'll dive deep into the nuts & bolts of implementing Hamming code in C++. 

Hamming code in C++

You'll learn how to code this error-checking method from scratch, understand its theoretical underpinnings, & see its practical applications. By the end, you'll have a solid understanding of Hamming code & be able to implement it in your projects.

Understanding the Basics of Hamming Code

Before diving into the code, it's crucial to understand the theory behind Hamming code. At its core, Hamming code is a set of error-correction codes that can detect up to two-bit errors or correct one-bit errors without needing any additional data. This makes it incredibly efficient for ensuring data integrity in digital communications. The key concept here is the use of redundant bits. These extra bits are added to the data bits to form a code word. The position of these redundant bits follows a specific pattern, typically placed at positions that are powers of 2 (like 1, 2, 4, 8, etc.).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}


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 

2r≥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;
}


This function iteratively increases r until the condition 

2r≥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;
}


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;
}


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;

}

  Output

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 DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. 

Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Previous article
C++ tolower() Function
Next article
strncpy() in C++
Live masterclass