Hamming code given a generator matrix question

Question

Hello All

Can I just say from the outset that this isn't a homework question as I'm way to old for that. But is related to an open source radio decoder project I'm working on ..

http://github.com/IanWraith/DMRDecode

Part of the radio protocol I'm interested uses a Hamming (7,4,3) code to protect 4 bits in a particular part of a data packet. So for every 4 bits of data it adds 3 parity bits which is easy enough for me even 20 years after I studied this at technical college. The specification document just gives the Hamming generator matrix which is as follows

1000 101
0100 111
0010 110
0001 011

DDDD HHH
1234 210

Now my question is does this mean the following ..

H2 is the XORed product of D1 , D2 , D3

H1 is the XORed product of D2 , D3 , D4

H0 is the XORed product of D1 , D2 , D4

or have I got this horribly wrong ?

Thanks for your time.

Ian

Answer 1

This article, Hamming(7,4), will tell you more than you want to know about how to construct the parity bits and where they are encoded into the output.

Answer 2

For the generator matrix you give, your interpretation is correct. Your tables do mean:
H0 = D1 ^ D2 ^ D4
H1 = D2 ^ D3 ^ D4
H2 = D1 ^ D2 ^ D3

However, the normal Hamming(7,4) matrix, in the same notation would be

1000 011
0100 101
0010 110
0001 111

DDDD HHH
1234 210

Only H0 is the same among the two sets of matrices. The other two bits are
H1 = D1 ^ D3 ^ D4
H2 = D2 ^ D3 ^ D4
It would be handy to be sure that the specification actually matches what's done in practice.

Equally critical is the specification for the order of the bits in the transmitted word. For instance, for the typical Hamming(7,4) encoding, the order
H0, H1, D1, H2, D2, D3, D4
has the property that the XOR with the parity check matrix tells you either (1) that all bits seem to be correct (== {0,0,0}) or (2) one bit appears to be wrong and it is the one in the bit position given by the result of the parity check matrix. I.e., if the three bits returned from multiplying the received code by the parity check matrix are {1, 0, 1}, then the 5th bit (101 interpreted in base 2) has been flipped. In the above ordering, this means D2 has been flipped.