2

I'm a bit confused about computing Hamming code. In Wikipedia article it is written:

Parity bit 1 covers all bit positions which have the least significant bit set: bit 1 (the parity bit itself), 3, 5, 7, 9, etc.

How does that possible to get parity of bits that include that value?

Do I understand it right, that according to the article above the first parity bit should be calculated as:

parity_bit_1 = parity_bit_1 xor data_1 xor data_2 xor data_4 xor data_5 xor data_7 ...

However in some other sources (like joel.neely's answer to this question) it is said to be calculated like this:

parity_bit_1 = data_1 xor data_3 xor data_5 xor data_7 xor data_9 ...

So, how should that be done?

Community
  • 1
  • 1
Vladimir Keleshev
  • 13,753
  • 17
  • 64
  • 93

2 Answers2

2

What it means is: for each k, the following thing is zero: the exclusive-or of all bits whose index has bit k set. (Your bits have indices 1,2,...,2^n-1.)

The actual data goes in the bits whose indices have more than one bit set.

Then you can calculate the required values of the power-of-2-index bits using the parity constraints: each constraint includes exactly one bit whose index is a power of 2, and each bit whose index is a power of 2 appears in exactly one constraint.

So, for instance, consider the case n=3. You have 2^3-1 = 7 bits of code; 3 of them are parity bits, the ones with indices 1,2,4. The others, with indices 3,5,6,7, are the data you're interested in.

You choose what goes in bits 1,2,4 so as to ensure that bit1 XOR bit3 XOR bit5 XOR bit7 = 0 and bit2 XOR bit3 XOR bit6 XOR bit7 = 0 and bit4 XOR bit5 XOR bit6 XOR bit7 = 0.

So, e.g., if your message is 0110 then you'll send ?,?,0,?,1,1,0. The first ? has ?+0+1+0=0 and therefore must be 1. The second? has ?+0+1+0=0 and therefore must also be 1. The third ? has ?+1+1+0=0 and therefore must be 0. So what you send is 1100110.

Gareth McCaughan
  • 19,888
  • 1
  • 41
  • 62
2

I think Calculating the Hamming Code article will be helpful.

bancer
  • 7,475
  • 7
  • 39
  • 58