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 (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 (bit stream).Example − Parity code, Hamming code.

Error correction codes − are used to correct the error(s) present in the received data (bit stream) 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.

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.

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.

$$2^k\geq n+k+1$$

Where,

‘n’ is the number of bits in the binary code (information)

‘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 $b_{n+k}b_{n+k-1}.....b_{3}b_{2}b_{1}$ & 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 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 ‘1’ in the place value of 2⁰.

• 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 ‘1’ in the place value of 2¹.

• 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 ‘1’ in the place value of 2².

• Similarly, find other values of parity bits.

Follow this procedure for finding check bits.

• Find the value of c₁, based on the number of ones present in bit positions b₁, b₃, b₅, b₇ and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 2⁰.

• Find the value of c₂, based on the number of ones present in bit positions b₂, b₃, b₆, b₇ and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 2¹.

• Find the value of c₃, based on the number of ones present in bit positions b₄, b₅, b₆, b₇ and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 2².

• 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, d₄d₃d₂d₁ = 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.

$$2^k\geq n+k+1$$

Substitute, n=4 in the above mathematical relation.

$$\Rightarrow 2^k\geq 4+k+1$$

$$\Rightarrow 2^k\geq 5+k$$

The minimum value of k that satisfied the above relation is 3. Hence, we require 3 parity bits p₁, p₂, and p₃. 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 $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}=d_{4}d_{3}d_{2}p_{3}d_{1}p_{2}bp_{1}$

By substituting the bits of binary code, the Hamming code will be $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1} = 100p_{3}Op_{2}p_{1}$. Now, let us find the parity bits.

$$p_{1}=b_{7}\oplus b_{5}\oplus b_{3}=1 \oplus 0 \oplus 0=1$$

$$p_{2}=b_{7}\oplus b_{6}\oplus b_{3}=1 \oplus 0 \oplus 0=1$$

$$p_{3}=b_{7}\oplus b_{6}\oplus b_{5}=1 \oplus 0 \oplus 0=1$$

By substituting these parity bits, the Hamming code will be $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001011$.

Example 2

In the above example, we got the Hamming code as $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001011$. Now, let us find the error position when the code received is $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001111$.

Now, let us find the check bits.

$$c_{1}=b_{7}\oplus b_{5}\oplus b_{3}\oplus b_{1}=1 \oplus 0 \oplus 1 \oplus1 =1$$

$$c_{2}=b_{7}\oplus b_{6}\oplus b_{3}\oplus b_{2}=1 \oplus 0 \oplus 1 \oplus1 =1$$

$$c_{3}=b_{7}\oplus b_{6}\oplus b_{5}\oplus b_{4}=1 \oplus 0 \oplus 0 \oplus1 =0$$

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

$$c_{3}c_{2}c_{1} = \left ( 011 \right )_{2}=\left ( 3 \right )_{10}$$

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