Was working on some SEC-DED (Single Error Correction-Double Error Detection), and that led me to some research into parity bit, and eventually, the Hamming Code.
What Is Hamming Code
Well, this is what we got from wikipedia:-
In coding theory, Hamming(7,4) is a linear error-correcting code that encodes 4 bits of data into 7 bits by adding 3 parity bits. It is a member of a larger family of Hamming codes, but the term Hamming code often refers to this specific code that Richard W. Hamming introduced in 1950. At the time, Hamming worked at Bell Telephone Laboratories and was frustrated with the erroneous punched card reader, which is why he started working on error-correcting codes.[1]
The Hamming code adds three additional check bits to every four data bits of the message. Hamming’s (7,4) algorithm can correct any single-bit error, or detect all single-bit and two-bit errors. In other words, the Hamming distance between any two correct codewords is 3, and received words can be correctly decoded if they are at distance at most one from the codeword that was transmitted by the sender. This means that for transmission medium situations where burst errors do not occur, Hamming’s (7,4) code is effective (as the medium would have to be extremely noisy for 2 out of 7 bits to be flipped).
Well, honestly, I still can’t figure out how the whole damn thing works.
Lucky for me, I managed to bump into this page, and the explanation makes a lot more sense to people like me, that realy has a difficult time understanding all the mathemathical equations and stuff.
How The Algorithm Works
Here is how the algo works, quoted from this page:-
The key to the Hamming Code is the use of extra parity bits to allow the identification of a single error. Create the code word as follows:
1. Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.)
2. All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.)
3. Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips.
Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,…)
Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,…)
Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,…)
Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,…)
Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,…)
Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,…)
etc.
4. Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if the total number of ones in the positions it checks is even.
An Example
A byte of data: 10011010
Create the data word, leaving spaces for the parity bits: _ _ 1 _ 0 0 1 _ 1 0 1 0
Calculate the parity for each parity bit (a ? represents the bit position being set):* Position 1 checks bits 1,3,5,7,9,11:
? _ 1 _ 0 0 1 _ 1 0 1 0. Even parity so set position 1 to a 0: 0 _ 1 _ 0 0 1 _ 1 0 1 0
* Position 2 checks bits 2,3,6,7,10,11:
0 ? 1 _ 0 0 1 _ 1 0 1 0. Odd parity so set position 2 to a 1: 0 1 1 _ 0 0 1 _ 1 0 1 0
* Position 4 checks bits 4,5,6,7,12:
0 1 1 ? 0 0 1 _ 1 0 1 0. Odd parity so set position 4 to a 1: 0 1 1 1 0 0 1 _ 1 0 1 0
* Position 8 checks bits 8,9,10,11,12:
0 1 1 1 0 0 1 ? 1 0 1 0. Even parity so set position 8 to a 0: 0 1 1 1 0 0 1 0 1 0 1 0
* Code word: 011100101010.
Finding And Fixing A Bad Bit
So, now that we’ve got the code word (011100101010), and will be sending this word to the other side of the receiver, how is the receiver going to decode this and know which bit is having an error?
- Verify each and every parity bit.
- Sum up the location of all the pority bits which has error.
- The total is the location of the data bit which contains error!
Hamming.py
Here’s the simple (Really really simple) python library that I’ve written.
Usage is shown below:-
from Hamming import Hamming
x = Hamming()
#if you have only the data, and wanna get the code
x.data('1101')
x.code()
#>>> [1, 0, 1, 0, 1, 0, 1]
#if you have the code, and wanna get the Data/check for error
x.code('1010111')
x.data()
#>>> [1, 1, 1, 1]
x.check()
#>>> ERROR: bit 6
