Hamming code parity bits calculation

Question

I need to calculate the number of parity bits required for a given word (set of bits).

I know a way, but is not always working, below my current approach:

• word length: 8
• so 2^3
• then parity bits = 3 + 1

I am doing this to any given word (2^n bits), but it is not working for 2^1 or 2^2

Any idea?

Thank you!!!

Answer 1

Hamming code is simply 2 or more parity bits over different groupings of data bits such that if you draw a venn diagram of each grouping you will find each data bit belongs to a unique group of parity bits. In this way you can identify any 1 bit in error. Therefore any 1 bit error is correctable.

By definition of the Hamming code, the parity bit positions are in locations 2 to the zero through Nth power. So the parity bits occupy the 1st, 2nd, 4th, 8th... positions.

Example:

position:  1  2  3  4  5  6  7  8...
bit type: P1 P2 D1 P3 D2 D3 D4 P4...

The 1st data bit occupies the 3rd position. So, if we follow the definition, 1 data bit needs 2 parity bits. Not really worth it. We can place the next data bit into the 5th position. So 2 data bits needs 3 parity bits. Still not really worth it. (In both these cases we can simply send 1 parity bit with every data bit giving the receiver the ability to detect and correct errors.) We can place the next data bit into the 6th position. So 3 data bits needs only 3 parity bits. We are at the break even point with respect to sending out 1 parity bit for each data bit. We can place the next data bit into the 7th position. So 4 data bits needs only 3 parity bits. Not until we get to 4 data bits do we see an advantage to using the Hamming code.

So, as you build the Hamming code sequence (given the left to right sequence in the above example), you need all the parity bits to the left of the required number of data bits.

I'll leave it up to you to come up with an equation to calculate the number of necessary parity bits.

Answer 2

You need to have enough parity bits to cover the entire codeword — data bits PLUS parity bits.

Therefore, for 8 bits, you need at least 3 bits, 8 + 3 bits = 11 bits. 11 bits requires 4 parity bits, and so does 8 + 4 bits, so you're done at 4 parity bits.

Sometimes you need to iterate this more than once to arrive at a final answer.

Answer 3

The below sudo code will generate the total number of parity bits for a given word of a size (2^n bits):

Integer parityBits = 0;

while (powerOf(2, parityBits) < parityBits + wordLength + 1) {
   parityBits++;
}

Note: I have not tested this solution against words with a length different than (2^n bits)