Hamming code check parity

Question

I am not sure if I am calculating the parity bit correctly for the the check Parity bit function I wrote. The codeWord is 11 chars long with 4 parity bits and 7 data bits. Does the implementation look good?

void parityCheck(char* codeWord) {
int parity[4] = {0}, i = 0, diffParity[4] = {0}, twoPower = 0, bitSum = 0;

// Stores # of 1's for each parity bit in array.
parity[0] = (codeWord[2] - 48) + (codeWord[4] - 48) + (codeWord[6] - 48) + (codeWord[8] - 48) + (codeWord[10] - 48);
parity[1] = (codeWord[2] - 48) + (codeWord[5] - 48) + (codeWord[6] - 48) + (codeWord[9] - 48) + (codeWord[10] - 48);
parity[2] = (codeWord[4] - 48) + (codeWord[5] - 48) + (codeWord[6] - 48);
parity[3] = (codeWord[8] - 48) + (codeWord[9] - 48) + (codeWord[10] - 48);

// Determines if sum of bits is even or odd, then tests for difference from actual parity bit.
for (i = 0; i < 4; i++) {
    twoPower = (int)pow((double)2, i);

    if (parity[i] % 2 == 0)
            parity[i] = 0;
        else
            parity[i] = 1;

        if ((codeWord[twoPower-1] - 48) != parity[i])
            diffParity[i] = 1;
}

// Calculates the location of the error bit.
for (i = 0; i < 4; i++) {
    twoPower = (int)pow((double)2, i);
    bitSum += diffParity[i]*twoPower;
}



// Inverts bit at location of error.
if (bitSum <= 11 && bitSum > 0) {
    if ((codeWord[bitSum-1] - 48)) 
        codeWord[bitSum-1] = '0';
    else
        codeWord[bitSum-1] = '1';
}

I'd replace twoPower = (int)pow((double)2, i) with twoPower = 1 << i. This is likely to give a big performance improvement. — John Zwinck
@randomname rather than do a codeWord[2] - 48) + (codeWord[4] - 48) + ..., consider codeWord[2] - 48) ^ (codeWord[4] - 48) ^ . Then if (parity[i] % 2 == 0) ... not needed. Further, - 48 s/b -'0'. — chux - Reinstate Monica
The 4 lines if-statement "if (parity[i] % 2.." can be replaced with the more efficient parity[i] &= 1;. — Jongware
I guess @meaning-matters meant “bit field” in the sense that you treat a single integer as a sequence of bits, using bit shift operations. This is quite portable, see my answer for an example. What is not portable are bit fields as structelements, i.e. using less than a whole adressable byte for a member of a structure. — MvG

MvG MvG · Accepted Answer · 2013-08-02T13:30:15

Does the implementation look good?

This very much depends on your measure for “good”. I can confirm that it does get the job done, so at least it is correct. Your code is very verbose, and thus hard to check for correctness. I'd do the following:

int parity_check(int codeWord) {
  int parity = 0, codeWordBit, bitPos;
  for (bitPos = 1; bitPos <= 11; ++bitPos) {
    codeWordBit = ((codeWord >> (bitPos - 1)) & 1);
    parity ^= bitPos*codeWordBit;
  }
  if (parity != 0) {
    if (parity > 11)
      return -1; // multi-bit error!
    codeWord ^= 1 << (parity - 1);
  }
  return codeWord;
}

Instead of a sequence of digit characters, I treat your whole code word as a single integer, which is a lot more efficient.

Looking at the table at Wikipedia, I see that the columns of that table form binary representations of the sequence 1 … 11. Each code word bit affects exactly those parity bits mentioned in that column, so I take the code word bit (which is zero or one), multiply it by the bit pattern of that column to obtain either that pattern or zero, then XOR this with the current parity bit pattern. The effect of this is that a zero code word bit won't change anything, whereas a non-zero code word bit flips all associated parity bits.

Some care has to be taken because the bit pattern is one-based, whereas the bit position using the right shift trick is zero-based. So I have to subtract one, then shift right by that amount, and then extract the least significant digit in order to obtain the codeWordBit.

Using my implementation for reference, I was able to verify (by complete enumeration) that your code works the same.

Hamming code check parity

3 Answers