Hamming (16,11) in C++ — interactive playground

Source (C++)

#include <iostream>
#include <vector>

using namespace std;

// Hamming (16, 11): indices 1..15, parity at powers of two (1, 2, 4, 8),
// master bit P0 at index 0.

vector<int> encode(const vector<int>& message) {
  vector<int> block(16, 0);
  int msgidx = 0;

  // Fill data slots only — skip parity positions 1, 2, 4, 8.
  // (idx & (idx - 1)) == 0 exactly when idx is a power of two.
  for (int idx = 1; idx < 16; idx++) {
    if ((idx & (idx - 1)) != 0) {
      block[idx] = message[msgidx++];
    }
  }

  // XOR indices of all 1-bits in positions 1..15.
  // The low four bits of that sum become P1, P2, P4, P8.
  int parity_sum = 0;
  for (int idx = 1; idx < 16; idx++) {
    if (block[idx] == 1) {
      parity_sum ^= idx;
    }
  }

  block[1] = parity_sum & 1;
  block[2] = (parity_sum >> 1) & 1;
  block[4] = (parity_sum >> 2) & 1;
  block[8] = (parity_sum >> 3) & 1;

  // P0: even parity over bits 1..15 (overall / master check).
  int p0 = 0;
  for (int idx = 1; idx < 16; idx++) {
    p0 ^= block[idx];
  }
  block[0] = p0;

  return block;
}

vector<int> decode(vector<int>& receivedBlock) {
  // Syndrome from P1..P8: zero means those checks pass.
  int syndrome = 0;
  for (int idx = 1; idx < 16; idx++) {
    if (receivedBlock[idx] == 1) {
      syndrome ^= idx;
    }
  }

  // Total parity over all 16 bits (uses P0 together with syndrome).
  int total_parity = 0;
  for (int idx = 0; idx < 16; idx++) {
    total_parity ^= receivedBlock[idx];
  }

  // Case 1: clean codeword
  if (syndrome == 0 && total_parity == 0) {
    cout << "No error detected" << endl;
  }
  // Case 2: only P0 flipped
  else if (syndrome == 0 && total_parity == 1) {
    cout << "Error in master bit" << endl;
    receivedBlock[0] ^= 1;
  }
  // Case 3: single-bit error at index == syndrome
  else if (syndrome != 0 && total_parity == 1) {
    cout << "single-bit error at position " << syndrome << endl;
    receivedBlock[syndrome] ^= 1;
    cout << "Corrected the error" << endl;
  }
  // Case 4: two-bit error (detect only)
  else {
    cout << "Two bit error detected" << endl;
    return {};
  }

  // Extract the 11 data bits from corrected positions.
  vector<int> message;
  for (int idx = 1; idx < 16; idx++) {
    if ((idx & (idx - 1)) != 0) {
      message.push_back(receivedBlock[idx]);
    }
  }
  return message;
}

void printmsg(const vector<int>& v) {
  for (int bit : v) {
    cout << bit;
  }
  cout << endl;
}

int main() {
  vector<int> message = {1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0};
  cout << "Original msg
";
  printmsg(message);

  auto encoded_data = encode(message);
  cout << "Encoded data is:
";
  printmsg(encoded_data);

  // Single-bit error example:
  // encoded_data[9] ^= 1;

  // Double-bit error (detected, not corrected):
  encoded_data[5] ^= 1;
  encoded_data[10] ^= 1;

  cout << "Received block:
";
  printmsg(encoded_data);
  auto decoded_data = decode(encoded_data);

  if (!decoded_data.empty()) {
    cout << "Received message:
";
    printmsg(decoded_data);
  }
  return 0;
}