December 19th, 2003, 06:35 PM
Error Detection Techniques(Parity Bit)
Q. Explain some of the error detection and correction techniques?
Sol. Parity Check -This is the simplest scheme of error detection. In this scheme a single parity bit is introduced. This parity bit is appended at the end of the block of data in such a way that the block of data contains either even (even parity) or odd(odd parity) number of ones. For example in case of even parity consider a block of data to be sent is 10100100 this is a seven bit data a new parity bit will be appended at the end so that the number of one’s in the data become even 101001001. Now this data is sent across the transmission channel and if suppose error occurs during the transmission and the third bit in the block becomes zero(100001001) now this will be received by the receiver and will detect an error. However if two or more bits are inverted in such a way that the number of one’s remain even (eg 11001001)then the error will remain undetected. Same is the case with odd parity in which a parity bit is introduced in such a way the resulting block of data contain odd numbers of ones. Typically, even parity is used for synchronous transmission and odd parity for asynchronous transmission. This method in not foolproof, noise impulses are often long and destroy more than one bit of data.
The parity bit is only an error detection code. The concept of parity bit has been later on developed and error detection and correction code has been developed using more than one parity bits. One such code is Hamming error correcting code.
Hamming Error-Correcting Code: This code was devised by Richard Hamming at Bell Laboratories. Lets understand this codes with the help of Venn diagrams, lets consider 4 bit data. Figure below shows the Venn diagrams with filled in data bits, which are filled in the intersecting inner compartments.
The next step is to fill in the parity bits for these four data bit The principle here is that we add the parity bits such that the total number of l's in each circle is even (even parity)
Please note that each of the circle have even number of l's.
After the data transfer, let us say, we encounter a situation where one of the data bit is changed from 1 to 0. Thus, an error has occurred. This condition is shown in Figure
How will this error be detected and rectified. ?. The parity bit of the two circles are indicating error of one bit, since two circles are indicating errors, therefore, the error lies at the intersection of these two circle. So, we have not only recognized the error but also its source. Thus, in this case by changing the bit in error, from 0 to 1 we can easily rectify the error.
Now let us discuss a scheme for error correction and detection of single bit errors in 8 bit words. The first question in this respect is: what should be the length of the code? Before answering this question we have to look into the comparison logic of error detection. The error detection is done by comparing the two i bit error detection and correction codes fed to the comparison logic bit by bit . Let us have a comparison logic which produce a 0 if the compared bits are same or else it produce a 1.
Therefore, if similar Position bits are same then we get 0 at that bit Position, but if they are different, that is this bit position may point to some error, then this Particular bit position will be marked as 1. This way a match word called syndrome word is constructed. This syndrome word is i bit long, therefore, can represent 2i values or combinations. For example, a 4 bit syndrome word can represent 24=16 values which range from 0 to 15 as:
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
The value 0000 or 0 represent no error while the other values i.e..2i-1 (for 4 bits 24-1=15 that is from 1 to15) represent an error condition. Each of these 2i-1(or 15 for 4 bits)can be used to represent an error of a particular bit. Since, the error can occur during the transmission of N bit data plus i bit error correction code, therefore we need to have at least N+i error values to represent them. Therefore, the number of error correction bits should be found from the following equation:
2i- 1 >N+i
If we are assuming 8 bit word then we need to have
say at i=3 LHS = 23-1 = 7; RHS = 8+3 = 11
i=4 2i-1 = 24-1 = 15; RHS = 8+4 = 12
Therefore, for 8 bit word we need to have at least 4 error correcting bits.
Similarly for 16 bit word we need to have i = 5
LHS=25-1 = 31 > RHS=16+i = 16+5 = 21
The next step in this connection will be to arrange the 8 bit word and its 4 bit error correction code in such a way that a particular value of the syndrome word specifies an error in a unique bit (which may be data or error detection code' ). The following arrangement of the (N+i) bits is suggested.
Bit positions 12 11 10 9 8 7 6 5 4 3 2 1
Data bits 8 7 6 5 4 3 2 1
Correction bits 8 4 2 1
Data bits and bit positions
The above arrangement is derived on the basis that:
Syndrome Word zero implies no error.
If syndrome word contains only one bit as 1 then it should be inferred that error has occurred only in the parity bits, therefore, no correction is needed in data. But how can we implement it? This can be implemented easily by assigning the check bits as 1st,2nd,4th, and 8th bit position
In case more than one bit in syndrome word are set as 1 then the numerical value of the syndrome word should determine the bit position which is in error.
The arrangement shown in figure above has an added advantage, that is each data bit position can be calculated as a function of correction bit positions. Please note, in case any one of the correction bit has changed during data transmission, that implies any one of the 1st or 2nd or 4th or 8th bit position data have altered, therefore, the syndrome bit will be 0001 if the data at first bit position has changed, 0010 if 2nd bit position has changed; or 0100 if data at 4th bit position has changed, or 1000 if data at 8th bit position has changed. Thus, the proposed bit arrangement scheme of figure above, satisfies the second assumption for the bit arrangement scheme. The next assumption in this regard is the value of syndrome word should indicate the bit position which is in error, that is, if there is error in bit position 3 it should change correction bits of bit position 1 and 2 and so on. Let us discuss how this can be achieved.
Let us make the table for the proposed scheme.
Bit position in error Effected bit position of syndrome word Comments
1 - - - 1 One bit position in error
2 - - 2 - One bit position in error
3 - - 2 1 1+2 =3
4 - 4 - - One bit position in error
5 - 4 - 1 4+1 =5
6 - 4 2 - 4+2 =6
7 - 4 2 1 4+2+1 =7
8 8 - - - One bit position in error
9 8 - - 1 8+1 =9
10 8 - 2 - 8+2 =10
11 8 - 2 1 8+2+1 =11
12 8- 4 - - 8+4 =12
We are assuming that only one bit can be in error. The table given above indicate that the first bit in syndrome word should be 1 if any one of the 1st, 3rd, 5th, 7th, 9th and 11th bit position is in error. the second bit of syndrome word should be 1 if any one of the 2nd, 3rd, 6th,7th, 10th, 11th bit positions is in error, the third bit of syndrome word should be 1 if any of the 4th, 5th, 6th,7th, or 12th bit positions is in error and the fourth bit of syndrome word should be 1 if any of the 9th, 10th, 11th , or 12th , bit positions is in error.
Since the 1st , 2nd, 4th , 8th bit positions are occupied by correction bits or check bits at the source, therefore, they should not be used for calculating check bits,
Based on the above facts, the check bits should be calculated as:
Check bit 1 = Even parity of (3rd , 5th , 7th , 9th & 11th bit position)
Check bit 2 =Even parity of(3rd ,6th ,7th ,10th ,11th bit position)
Check bit 3 = Even parity of (3rd , 6th, 7th, 12th bit position)
Check bit 4 =Even parity of(9th ,10th ,11th ,12th bit positions) or in other words (refer figure 11) :
Check bit 1 = Even parity of (Data bits 1,2,4.5, 7)
Check bit 2 = Even parity of (Data bits 1,3,4,6,7)
Check bit 3 = Even parity of (Data bits 2,3,4,8)
Check bit 4 = Even parity of (Data bits 5,6,7,8)
This is called a single error correcting (SEC) code. Let us see an example of error correction using this code.
Example: An 8 bit input word 01011011 on transmission is received as 01001011 (that is error in 5th data bit how the SEC code if used can rectify this error?
Solution: The SEC code for 8 bit word is of 4 bits
Check bit l =Even parity of(1,1,1,1,1)=1
Check bit 2 =Even parity of(1,0,1,0,1)=1
Check bit 3 =Even parity of(1,0,1,0)=0
Check bit 4 =Even parity of(1,0,1,0)=0
Therefore, the 12 bit word to be transmitted is
Bit Position 12 11 10 9 8 7 6 5 4 3 2 1
Data Bits 8 7 6 5 4 3 2 1
Check Bits 4 3 2 1
Data to be transmitted 0 1 0 1 0 1 0 1 0 1 1 1
Data Received 0 1 0 0 0 1 0 1 0 1 1 1
Error in the 5th data bit
Calculation of check bits of data received:
Check bit 1 = Even parity of(l,1,1,0,1,)=0
Check bit 2 = Even parity of(1,0,1,0,1,)=1
Check bit 3 = Even parity of(1,0,1,0)=0
Check bit 4 = Even parity of(0,0,1,0)=1
Syndrome word =compare the received check bits to calculated checks bits Of received data
= 0 0 1 1 Received check bits
1 0 1 0 calculated check bits
1 0 0 1
Please note for syndrome word calculation if two check bits are same then the respective bit in syndrome word will be 0 if the two check bits are same then the bit in syndrome word will be 1.
Thus, syndrome word = 1001, Which implies that 9th bit position in the received 12 bit information is in error. The 9th bit position corresponds to 5th data bit. Change this bit to 1 if it is 0 or 0 if it is 1. Since in the received data it is 0, therefore, change it to1.
Hence, the data was (excluding check bits) received as 01001011
The corrected data is 01011011
The corrected data is same as the transmitted data.