# Fundamentals of Data Representation: Hamming code

< A-level Computing | AQA | Problem Solving, Programming, Data Representation and Practical Exercise | Fundamentals of Data Representation

Building on what you have learnt about parity bits we are now going to see a system that not only allows you to **detect** if the data you have been sent is incorrect, but it will allow you to **correct** the error. The way hamming code does this is to use multiple check digits in the same piece of sent data.

### Checking if correctEdit

- Number the column headings
- Highlight the column headings that are powers of 2 (1,2,4,8), these are the parity bits
- Insert your data and highlight the parity bits
- Work your way through the parity bits
- 2^0 = 1 : check 1, skip 1, check 1, skip 1 ... write down whether it's odd or even parity
- 2^1 = 2 : check 2, skip 2, check 2, skip 2 ... write down whether it's odd or even parity
- 2^2 = 4 : check 4, skip 4, check 4, skip 4 ... write down whether it's odd or even parity
- etc..

Example: Odd Parity Hamming Code Check
Let's take a look a an example of data sent with odd parity
Note that for the check 8 skip 8 we ran out of digits, not to worry, take it as far as the bits given allow. As we can see each line is odd parity, and the sent data was supposed to be odd parity, this number is correct. |

Exercise: Even Parity Hamming Code Question
Now try this example with even parity: 10101100011
All are even parity, the data should be even parity, therefore it has been sent and received correctly 11011110010 being sent with odd parity
All are odd parity, the data should be odd parity, therefore it has been sent and received correctly 00100011110 being sent with even parity
We have a mixture of odd and even parity, this means that there has been a mistake in sending this data. But where is the error? It has something to do with the lines that have odd parity! |

#### Detecting and correcting errorsEdit

- Number the column headings
- Highlight the column headings that are powers of 2 (1,2,4,8), these are the parity bits
- Insert your data and highlight the parity bits
- Work your way through the parity bits
- 2^0 = 1 : check 1, skip 1, check 1, skip 1 ... write down whether it's odd or even parity
- 2^1 = 2 : check 2, skip 2, check 2, skip 2 ... write down whether it's odd or even parity
- 2^2 = 4 : check 4, skip 4, check 4, skip 4 ... write down whether it's odd or even parity
- etc..

- If there is a disparity between rows, highlight all the error data and find where it overlaps

Example: Even Parity Hamming Code Check
Let's take a look a an example of data sent with even parity
Note that two of the lines, 2^1 and 2^2, show that an error has been detected. This means that somewhere that these lines cross over a bit has been corrupted, namely bit 6 or bit 7. If we know which one it is we can then switch it and correct the error. Look at the other checks that are in play, do any of them take part in this crossover? Looking at it, the 2^0 line also checks column 7 and it found it fine. So we are left with column 6 being the problematic one. As Hamming code is Another way of finding errors is to add the check digit values together, the error occurs where the check digit equals 4 and 2. Add 4 +2 = 6, the error is with the 6th digit!
The number is now even parity and correct: 10010110111 |

Exercise: Detect and Correct the error in the following Hammed Code
Now try this example with even parity: 01101001011
The error is in the lines crossing over, that is on lines 2^0 and 2^1, but which bit is it? You'll notice that the 2^2 and 2^3 lines are correct so we can discount any bits that are covered in those lines. This leaves us with the third column. Flipping this value gives us the corrected value of: 01101001 11111101000 sent with odd parity
The error is in the lines crossing over, that is on lines 2^1 and 2^3, but which bit is it? We can look at the place they cross over, bit ten, alternatively we can add the parity bit numbers together the row of parity bit 2 plus the row of parity bit: 2 + 8 = bit 10. Flipping this value gives us the corrected value of: 1 00111000101 sent with even parity
There is only one line with an error, the line of parity bit 4. This means that the error is in bit 4,5,6 or 7. Parity bit lines 1 and 2 imply that bits 5,6,7 are all fine, leaving us with the error in bit 4. Alternatively, as the error only occurs on parity bit line 4, then we know the error is with bit 4! Flipping this value gives us the corrected value of: 0011100 |

### Applying hamming codeEdit

- Number the column headings
- Highlight the column headings that are powers of 2 (1,2,4,8), these are the parity bits
- Insert your data into the bits that aren't parity bits
- Work your way through the parity bits
- looking at 2^0 : check 1, skip 1, check 1, skip 1 ... write the parity bit in column 1 to make the bits the desired parity
- looking at 2^1 : check 2, skip 2, check 2, skip 2 ... write the parity bit in column 2 to make the bits the desired parity
- looking at 2^2 : check 4, skip 4, check 4, skip 4 ... write the parity bit in column 4 to make the bits the desired parity
- ...

Example: Applying Hamming code to an ASCII character
We are going to take a look at sending the ASCII letter e: 1100101 with odd parity. This data would then be ready to send
We have now worked out the odd parity Hammed number ready for sending: 110 1011 |

Exercise: Applying Hamming code to an ASCII character
Apply even parity hamming code so we can transmit the ASCII character 'D' (1000100):
We have now worked out the even parity Hammed number ready for sending: 100 0101Apply even parity hamming code so we can transmit the ASCII character 'G':
ASCII 'G' = 1000111
We have now worked out the even parity Hammed number ready for sending: 100 1011Apply odd parity hamming code so we can transmit the denary value 9:
9 = 0001001
We have now worked out the even parity Hammed number ready for sending: 000 1011 |