Error Detection and Correction Codes

ERROR DETECTION AND CORRECTION CODES

The binary 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 be added. Due to this, there may be errors in the received data.

That means a bit 0 may changed to 1 (or) a bit 1 may changed to 0 we can't avoid the interference of noise. But we can get original data by detecting whether any error & present and then correcting those errors. For this reason, we use the error detection and correction codes.

Error detection codes are used to detect the error & present in the received data bit stream. 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

(i) Parity code

(ii) Hamming code

Error correction codes are used to correct the error ε present in the received data bitstream so that, we get the original data.

Example : Hamming code

Parity code

It is easy to include append one parity bit either to the left most bit (or) right mast bit of the original bit stream. There are two types of parity codes.

(i) Even parity

(ii) Odd parity

Even parity

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

The following table shows the even parity codes.

Here each 3 bit binary code added the even parity bit in the LSB of the binary code.

If the received system having even number one's then there is no error in the received data.

If the received system other than even number one's then there will be an 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.

The following table shows the odd parity codes

Here, the number of bits present to the odd parity codes is 4 bit. So, the possible odd number of ones in the odd parity codes.

If the received system having odd number one's then there is no error in the received data

If the received system other than odd number one's then there will be an 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

2^k ≥ n+k+1

where n is the number bits in the binary code information 'k' is the number of parity bit therefore, the number of bits in the Hamming codes is equal to n+k

Hamming code is b_n+k , b_n+k-1... b₃b₂b₁b₀ parity bits pk, p_k-1....p₁... k is the parity bits in power of 2 positions.

In remaining bit positions, we can place the 'n' bits of binary code. We van use either even parity (or) odd parity while forming a hamming code.

Procedure for finding parity bits.

(i) Find the value of p₁  based on the number of ones present in bit positions, b₃ b₅, b₇ and so on. All these bit positions suffixes in their equivalent binary have 'i' in two place value of 2°

(ii) Find the value of p₂ based on the number of ones present in bit positions b₃, b₆, b₇ and so on. All these bit positions suffixes in these equivalent binary have 'i' in the place value of 2¹

(iii) Find the value of p₃ based on the number of ones present in bit positions, b₅, b₆, b₇ and so on. All these bits suffixes in theri equivalent binary have 'i' in the place value of 2².

Similarly, find other values of parity bits.

Procedure for finding check bits.

(i) Find the value of c_l based on the number of one's present in bit positions b₁, b₃, b₅, b₇ and so on. All these bit positions suffixes in the their equivalent binary have 'i' in the place value of 2°

(ii) Find the value of c₂ based on the number of ones present in bit positions suffixes in their equivalent binary have 'i' in the place value of 2¹

(iii) Find the value of c₃ based on the number of one's present in bit positions b₄, b₅, b₆, b₇, and so on. All these bit positions suffixes in their equivalent binary have 'i' in the place value of 2².

Simillarly, find other values of check bits.

Example

Find the Hamming code for binary bit 1 0 0 0. Consider even parity bits

Solution

Number bit in the given binary code is n = 4

We can find the required numbers of parity bits by the formula

2^k ≥  n + k + 1

n = 4

⇒ 2^k ≥ 4 + k + 1

⇒ 2^k ≥ 5 + k

The minimum value of k that satisfied the above relation is 3. Hence we required 3 parity bits, P₁, P₂ and P₃.

Therefore, the number of bits in hamming code will be 7, since there are 4 bit in binary code and 3 parity bits.

7 bit hamming code is

d₄ d₃ d₂ P₂ d₁ P₂ P₁ ………(1)

Substituting the binary bits in equation (1)

Parity bits

Hamming with parity bits

1001011

Example 2

Hamming code as 1 0 0 1 0 1 1. Now let us find the error position when the code received is 1 0 0 1 111

Solution

Check bits

C₁ = 1

C₂ = 1

C₃ = 0

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

C₃ C₂ C₁ = (011)₂

= (03)₁₀.