Hamming Codes:

The Hamming codes were originally designed with d_min = 3, which means that they can detect up to two errors or correct one single error. But there are some Hamming codes that can correct more than one error.

First let us find the relationship between n and k in a Hamming code. We need to choose an integer m >= 3. The values of n and k are then calculated from mas n = 2m – 1 and k= n-m. The number of check bits r =m.

For example, if m=3, then n= 7 and k= 4. This is a Hamming code C(7, 4) with d_min =3. The following Table shows the data words and code words for this code.

The following figure shows the structure of the encoder and decoder for this example.

A copy of a 4-bit data word is fed into the generator that creates three parity checks r0, r1 and r2 as shown below:

r0=a2+a1+a0   (modulo-2)
r1 =a3 + a2 + a1 (modulo-2)
r2=a1 +a0+a3 (modulo-2)

Each of the parity-check bits handles 3 out of the 4 bits of the data word. The total number of 1s in each 4-bit combination (3 data word bits and 1 parity bit) must be even. We are not saying that these three equations are unique; any three equations that involve 3 of the 4 bits in the data word and create independent equations (a combination of two cannot create the third) are valid.

The checker in the decoder creates a 3-bit syndrome (s2s1s0) in which each bit is the parity check for 4 out of the 7 bits in the received code word.

S0=b2+b1+b0+ q0   (modulo-2)
S1 =b3 +b2 + q1 (modulo-2)
S2=b1 +b0+q3 (modulo-2)

The equations used by the checker are the same as those used by the generator with the parity-check bits added to the right-hand side of the equation. The 3-bit syndrome creates eight different bit patterns (000 to 111) that can represent eight different conditions.

These conditions define a lack of error or an error in 1 of the 7 bits of the received code word, as shown in the following Table.

Note that the generator is not concerned with the four cases shaded in the above Table because there is either no error or an error in the parity bit. In the other four cases, 1 of the bits must be flipped (changed from 0 to 1 or 1 to 0) to find the correct data word.

The syndrome values in the above Table are based on the syndrome bit calculations. For example, if qo is in error, So is the only bit affected; the syndrome, therefore, is 001. If b2 is in error, So and S1 are the bits affected; the syndrome, therefore is 011. Similarly, if b1 is in error, all 3 syndrome bits are affected and the syndrome is 111.
There are two points we need to emphasize here. First, if two errors occur during transmission, the created data word might not be the right one. Second, if we want to use the above code for error detection, we need a different design.

For Example

Let us trace the path of three data words from the sender to the destination:

1. The data word 0100 becomes the code word 0100011. The code word 0100011 is received. The syndrome is 000, the final data word is 0100.

2. The data word 0111 becomes the code word 0111001. The syndrome is 011. After flipping b2 (changing the 1 to 0), the final data word is 0111.

3. The data word 1101 becomes the code word 1101000. The syndrome is 101. After flipping b0, we get 0000, the wrong data word. This shows that our code cannot correct two errors.