Hamming Code

Description

Hamming Code is an error-correcting code used for error detection and correction in data transmission. It adds extra bits to the original data bits to create a code word that can detect and correct single-bit errors. The positions of the extra bits are determined based on powers of two, providing redundancy to ensure data integrity.

C++ Code

#include <iostream>
#include <vector>
using namespace std;

vector<int> generateHammingCode(vector<int>& data) {
    int n = data.size();
    vector<int> hammingCode;
    int r = 0;

    while ((1 << r) < (n + r + 1)) {
        r++;
    }

    int j = 0;
    for (int i = 1; i <= n + r; i++) {
        if ((i & (i - 1)) == 0) {
            hammingCode.push_back(0);
        } else {
            hammingCode.push_back(data[j]);
            j++;
        }
    }

    for (int i = 0; i < r; i++) {
        int parityIndex = (1 << i) - 1;
        int parity = 0;
        for (int j = parityIndex; j < n + r; j += (1 << (i + 1))) {
            for (int k = 0; k < (1 << i) && j + k < n + r; k++) {
                parity ^= hammingCode[j + k];
            }
        }
        hammingCode[parityIndex] = parity;
    }

    return hammingCode;
}

int main() {
    vector<int> data = {1, 0, 1, 0};

    vector<int> hammingCode = generateHammingCode(data);

    cout << "Hamming code: ";
    for (int bit : hammingCode) {
        cout << bit << " ";
    }
    cout << endl;

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Hamming Code Generation	O(n)	O(n)

Where:

• n: Number of data bits.

← Back to Homepage