# Hamming Error Correction - with Example

This article will focus on **Hamming** codes - mainly, this represents an attempt to explain a little bit better
how this method can help in **detecting** and **correcting**… **1 bit errors**.

This method is not really useful
at “higher level” - just because the data we work with is either 100% correct or has way more than 1 bit corrupted - and in this
case, the Hamming code *doesn’t work*. It seems to be used in low-level (data link layer) networking and in some DRAMs - to prevent interferences
from corrupting data.

As an example, we can consider this **byte** of data: `11010010`

## Hamming Encoding

The encoding implies taking the bits of the original message and computing a set of *parity/control bits* that will help us detect
possible errors - we’ll know which bit is flipped, so the correction consists in **negating** that one bit.
In the end, we insert the parity bits at positions equal to *powers of 2* (1,2,4,8,…).

The encoded message will look like this: P_{1}P_{2}D_{1}P_{4}D_{2}D_{3}D_{4}P_{8}D_{5}D_{6}D_{7}D_{8}
- where **D** is a data bit, from our original message, and **P** a parity bit => **12 bits**.

In order to determine the formulas for the parity bits it is important to understand the following part:

We say that a bit at position **n**, from our encoded data, is “controlled” by the **parity bits** whose positions, once summed, are equal to **n**.
This can be written as:

Position (n) | Bit | is controlled by parity bit(s) |
---|---|---|

1 | P_{1} | P_{1} |

2 | P_{2} | P_{2} |

3 | D_{1} | P_{1} + P_{2} |

4 | P_{4} | P_{4} |

5 | D_{2} | P_{1} + P_{4} |

6 | D_{3} | P_{2} + P_{4} |

7 | D_{4} | P_{1} + P_{2} + P_{4} |

8 | P_{8} | P_{8} |

9 | D_{5} | P_{1} + P_{8} |

10 | D_{6} | P_{2} + P_{8} |

11 | D_{7} | P_{1} + P_{2} + P_{8} |

12 | D_{8} | P_{4} + P_{8} |

* notice that the sum of the indexes is equal to the position, for each row.

From the table, we observe that:

- P
_{1}“controls” data bits: D_{1}, D_{2}, D_{4}, D_{5}, D_{7}. - P
_{2}“controls” data bits: D_{1}, D_{3}, D_{4}, D_{6}, D_{7}. - P
_{4}“controls” data bits: D_{2}, D_{3}, D_{4}, D_{8}. - P
_{8}“controls” data bit: D_{5}, D_{6}, D_{7}, D_{8}.

If we know this, we can write the **equations** for the **parity bits**:

P_{1} = D_{1} ^ D_{2} ^ D_{4} ^ D_{5} ^ D_{7}

P_{2} = D_{1} ^ D_{3} ^ D_{4} ^ D_{6} ^ D_{7}

P_{4} = D_{2} ^ D_{3} ^ D_{4} ^ D_{8}

P_{8} = D_{5} ^ D_{6} ^ D_{7} ^ D_{8}

* that’s **XOR** between them, ok?

If we apply this theory to our **example** `11010010`

, we get:

P_{1} = 1 ^ 1 ^ 1 ^ 0 ^ 1 = 0

P_{2} = 1 ^ 0 ^ 1 ^ 0 ^ 1 = 1

P_{4} = 1 ^ 0 ^ 1 ^ 0 = 0

P_{8} = 0 ^ 0 ^ 1 ^ 0 = 1

So the encoded data is: 011010110010.

## Hamming Decoding

This part verifies the original bits and flips one of them if it’s corrupted.
Keeping the same **example**, we use the value that we determined before, but to make it more interesting, we’ll **corrupt 1 bit**.

original: 011010110010

corrupted: 011010110110

* in this case I corrupted a **data bit** - if a **parity bit** gets **corrupted** there’s no need to correct anything, we only care about the data bits.

We have to recalculate the parity bits, but this time we’ll also include their values (taken from the encoded data):

P_{1} = P_{1} ^ D_{1} ^ D_{2} ^ D_{4} ^ D_{5} ^ D_{7}

P_{2} = P_{2} ^ D_{1} ^ D_{3} ^ D_{4} ^ D_{6} ^ D_{7}

P_{4} = P_{4} ^ D_{2} ^ D_{3} ^ D_{4} ^ D_{8}

P_{8} = P_{8} ^ D_{5} ^ D_{6} ^ D_{7} ^ D_{8}

If there were no bits corrupted, each new parity bit should be **0** (because we’re **XOR**-ing 2 identical bits).
Replacing the values with the ones in the **example**, we get:

P_{1} = 0 ^ 1 ^ 1 ^ 1 ^ 0 ^ 1 = 0

P_{2} = 1 ^ 1 ^ 0 ^ 1 ^ 1 ^ 1 = 1

P_{4} = 0 ^ 1 ^ 0 ^ 1 ^ 0 = 0

P_{8} = 1 ^ 0 ^ 1 ^ 1 ^ 0 = 1

This result is somehow obvious since I flipped/corrupted the **6th bit of data**, and from the formulas, only P_{2} and
P_{4} include that bit.

However, in a general case we won’t know which bit is corrupted…so here’s how these **parity bits** become useful. We use them to create the
**sindrome**, so we arrange these bits like this:

P_{8}P_{4}P_{2}P_{1}

and by replacing, we get this number in binary: `1010`

(10 in decimal) => the **10th** bit, in the encoded data, is corrupted and needs some flippin’.
Aand…finally, we get the original encoded message: `011010110010`

. From here, we extract the data bits => `11010010`

.

## The end

That’s all…probably not the most interesting article, but my teachers seem to love this subject (especially during the finals), so…just trying to help.