Error Detection & Correction Codes

We know that the bits 0 and 1 corresponding to two different range of analog voltages. So, during
transmission of binary data from one system to the other, the noise may also be added. Due to
this, there may be errors in the received data at other system.

That means a bit 0 may change to 1 or a bit 1 may change to 0. We can’t avoid the interference

of noise. But, we can get back the original data first by detecting whether any error s present

and then correcting those errors. For this purpose, we can use the following codes.

Error detection codes

Error correction codes

Error detection codes − are used to detect the error s present in the received data

bitstream . These codes contain some bit s , which are included appended to the

original bit stream. These codes detect the error, if it is occurred during transmission of the

original data bitstream .Example − Parity code, Hamming code.

Error correction codes − are used to correct the error s present in the received data

bitstream so that, we will get the original data. Error correction codes also use the similar
strategy of error detection codes.Example − Hamming code.

Therefore, to detect and correct the errors, additional bit s are appended to the data bits at the
time of transmission.

Parity Code
It is easy to include append one parity bit either to the left of MSB or to the right of LSB of

original bit stream. There are two types of parity codes, namely even parity code and odd parity
code based on the type of parity being chosen.

Even Parity Code

The value of even parity bit should be zero, if even number of ones present in the binary code.
Otherwise, it should be one. So that, even number of ones present in even parity code. Even
parity code contains the data bits and even parity bit.

The following table shows the even parity codes corresponding to each 3-bit binary code. Here,
the even parity bit is included to the right of LSB of binary code.
 Binary Code Even Parity bit Even Parity Code

000 0 0000

001 1 0011

010 1 0101

011 0 0110

100 1 1001

101 0 1010

110 0 1100

111 1 1111

Here, the number of bits present in the even parity codes is 4. So, the possible even number of
ones in these even parity codes are 0, 2 & 4.

If the other system receives one of these even parity codes, then there is no error in the
received data. The bits other than even parity bit are same as that of binary code.

If the other system receives other than even parity codes, then there will be an error s in
the received data. In this case, we can’t predict the original binary code because we don’t
know the bit position s of error.

Therefore, even parity bit is useful only for detection of error in the received parity code. But, it is
not sufficient to correct the error.

Odd Parity Code

The value of odd parity bit should be zero, if odd number of ones present in the binary code.
Otherwise, it should be one. So that, odd number of ones present in odd parity code. Odd parity
code contains the data bits and odd parity bit.

The following table shows the odd parity codes corresponding to each 3-bit binary code. Here,
the odd parity bit is included to the right of LSB of binary code.
 Binary Code Odd Parity bit Odd Parity Code

000 1 0001

001 0 0010

010 0 0100

011 1 0111

100 0 1000

101 1 1011

110 1 1101

111 0 1110

Here, the number of bits present in the odd parity codes is 4. So, the possible odd number of
ones in these odd parity codes are 1 & 3.

If the other system receives one of these odd parity codes, then there is no error in the
received data. The bits other than odd parity bit are same as that of binary code.

If the other system receives other than odd parity codes, then there is an error s in the
received data. In this case, we can’t predict the original binary code because we don’t know
the bit position s of error.

Therefore, odd parity bit is useful only for detection of error in the received parity code. But, it is
not sufficient to correct the error.

Hamming Code
Hamming code is useful for both detection and correction of error present in the received data.
This code uses multiple parity bits and we have to place these parity bits in the positions of
powers of 2.

The minimum value of 'k' for which the following relation is correct valid is nothing but the
required number of parity bits.

k
2 ≥ n + k + 1

Where,
‘n’ is the number of bits in the binary code inf ormation

‘k’ is the number of parity bits

Therefore, the number of bits in the Hamming code is equal to n + k.

Let the Hamming code is bn+k bn+k−1 . . . . . b3 b2 b1 & parity bits p k , p k−1 , . . . . p 1 . We can

place the ‘k’ parity bits in powers of 2 positions only. In remaining bit positions, we can place the
‘n’ bits of binary code.

Based on requirement, we can use either even parity or odd parity while forming a Hamming
code. But, the same parity technique should be used in order to find whether any error present in
the received data.

Follow this procedure for finding parity bits.

Find the value of p1, based on the number of ones present in bit positions b3, b5, b7 and so
on. All these bit positions suf f ixes in their equivalent binary have ‘1’ in the place value

of 20.

Find the value of p2, based on the number of ones present in bit positions b3, b6, b7 and so

on. All these bit positions suf f ixes in their equivalent binary have ‘1’ in the place value

of 21.
Find the value of p3, based on the number of ones present in bit positions b5, b6, b7 and so

on. All these bit positions suf f ixes in their equivalent binary have ‘1’ in the place value

of 22.

Similarly, find other values of parity bits.

Follow this procedure for finding check bits.

Find the value of c1, based on the number of ones present in bit positions b1, b3, b5, b7 and
so on. All these bit positions suf f ixes in their equivalent binary have ‘1’ in the place

value of 20.

Find the value of c2, based on the number of ones present in bit positions b2, b3, b6, b7 and

so on. All these bit positions suf f ixes in their equivalent binary have ‘1’ in the place

value of 21.
Find the value of c3, based on the number of ones present in bit positions b4, b5, b6, b7 and

so on. All these bit positions suf f ixes in their equivalent binary have ‘1’ in the place

value of 22.

Similarly, find other values of check bits.

The decimal equivalent of the check bits in the received data gives the value of bit position,
where the error is present. Just complement the value present in that bit position. Therefore, we
will get the original binary code after removing parity bits.

Example 1
Let us find the Hamming code for binary code, d4d3d2d1 = 1000. Consider even parity bits.

The number of bits in the given binary code is n=4.

We can find the required number of parity bits by using the following mathematical relation.

k
2 ≥ n + k + 1

Substitute, n=4 in the above mathematical relation.

k
⇒ 2 ≥ 4 + k + 1

k
⇒ 2 ≥ 5 + k

The minimum value of k that satisfied the above relation is 3. Hence, we require 3 parity bits p1,
p2, and p3. Therefore, the number of bits in Hamming code will be 7, since there are 4 bits in
binary code and 3 parity bits. We have to place the parity bits and bits of binary code in the
Hamming code as shown below.

The 7-bit Hamming code is b7 b6 b5 b4 b3 b2 b1 = d4 d3 d2 p 3 d1 p 2 bp 1

By substituting the bits of binary code, the Hamming code will be

b7 b6 b5 b4 b3 b2 b1 = 100p 3 Op 2 p 1 . Now, let us find the parity bits.

p 1 = b7 ⊕ b5 ⊕ b3 = 1 ⊕ 0 ⊕ 0 = 1

p 2 = b7 ⊕ b6 ⊕ b3 = 1 ⊕ 0 ⊕ 0 = 1
 p 3 = b7 ⊕ b6 ⊕ b5 = 1 ⊕ 0 ⊕ 0 = 1

By substituting these parity bits, the Hamming code will be b7 b6 b5 b4 b3 b2 b1 = 1001011 .

Example 2
In the above example, we got the Hamming code as b7 b6 b5 b4 b3 b2 b1 = 1001011 . Now, let us

find the error position when the code received is b7 b6 b5 b4 b3 b2 b1 = 1001111 .

Now, let us find the check bits.

c1 = b7 ⊕ b5 ⊕ b3 ⊕ b1 = 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1

c2 = b7 ⊕ b6 ⊕ b3 ⊕ b2 = 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1

c3 = b7 ⊕ b6 ⊕ b5 ⊕ b4 = 1 ⊕ 0 ⊕ 0 ⊕ 1 = 0

The decimal value of check bits gives the position of error in received Hamming code.

c3 c2 c1 = (011) = (3)
2 10

Therefore, the error present in third bit (b3) of Hamming code. Just complement the value
present in that bit and remove parity bits in order to get the original binary code.