Hamming(7, 4)

It's a pain to find any easy-to-understand explanations on how to do Hamming(7, 4), so here's the most useful information from my reference on how to do it.

NOTE: You can substitute addition (+) with XOR (^).

Encoding

Let's say you have four data bits: d1, d2, d3, d4. To create the parity bits, you use the following formulae:

1. p1 = d2 + d3 + d4
2. p2 = d1 + d3 + d4
3. p3 = d1 + d2 + d4

The bits sent across the wire are: d1, d2, d3, p1, d4, p2, p3

Decoding

Now that we have the bits sent across the wire (d1, d2, d3, p1, d4, p2, p3), we can detect appropriate errors.

Error Detection

First, we calculate:

1. p1^* = d2 + d3 + d4
2. p2^* = d1 + d3 + d4
3. p3^* = d1 + d2 + d4

If any of these parity bits don't match the parity bits sent over the wire, then there was an error.

Error Correction

Now this information was the most difficult to find.

With the bits sent across the wire (d1, d2, d3, p1, d4, p2, p3), we must first calculate:

1. c1 = d1 + d3 + d4 + p3
2. c2 = d1 + d2 + d4 + p2
3. c3 = d1 + d2 + d3 + p1

NOTE: You can detect errors by checking to see if any of c1, c2, or c3 are true (nonzero).

With these calculated, now we can find which bit we need to flip to correct the error:

1. bit = ((c3 ? 4 : 0) | (c2 ? 2 : 0) | (c1 ? 1 : 0)) - 1

1. If bit = 6, then flip d1.
2. If bit = 5, then flip d2.
3. If bit = 4, then flip d3.
4. If bit = 2, then flip d4.
5. In all other cases, there are more than one bit errors and we can't correct them.

Alternatively, it could be thought of this way: bit is the index of the flipped bit from the end of the string (where p3 is) with zero-indexing.