ERROR DETECTION METHODS , Parity checking , Checksum error detection , Cyclic Redundancy Check (CRC)

ERROR DETECTION METHODS
Before thinking of correcting the error introduced in the data bits, it is essential to first detect them. Some of the popular detection methods are as under :
(i)         Parity checking
(ii)        Checksum error detection
(iii)       Cyclic Redundancy Check (CRC)
For error detection and correction, it is essential to add some check bits to a block of data bits. These check bits are also known as redundant bits because they do not carry any useful information.
10.9.1. Parity Checking

1. Definition and Basic Concept

In the parity checking methods, an additional bit called as parity bit is added to each data word. This additional bit is so chosen that the resultant word will have either an even parity or odd parity. If even parity is to be used then a parity bit is added to make the total number of 1 bits even. Similarly, for odd parity the total number of 1 bits is made odd by adding the parity bit. The examples of even and odd parity are as shown in figure 10.9 (a) and figure 10.9 (b).

(a) Inclusion of a parity bit to obtain the even parity

(b) Inclusion of a parity bit to obtain the odd parity

2. Error Detection

The parity checking at the receiver can detect the presence of an error if the parity of the received signal is different from the expected parity. This means that if it is known that the parity of the transmitted signal is always going to be even and if the received signal has an odd parity then the receiver can conclude that the received signal is not correct. This has been shown in figure 10.10.
diagram
FIGURE 10.10 The receiver detects the presence of error if the number of errors is odd i.e. 1, 3, 5.

When a single error or an odd number of errors occur during transmission the parity of the code word changes. Parity of the received code word is checked at the receiver and change in parity indicates that error is present in the received word. This is shown in figure 10.10.

3. Failure of Parity Checking Method

If the number of errors introduced in the transmitted code is two or any even number, then the parity of the received code word will not change. It will still remain even as shown in figure 10.11 and the receiver will fail to detect the presence of errors.
diagram
FIGURE 10.11 The receiver cannot detect the presence of error if the number of errors is even i.e. 2, 4, 6.

4. Conclusions

(i)         Double or any even number of errors in the received word does not change the parity. Therefore even number of errors will be unnoticed.
(ii)        If one or odd number of errors occur then the parity of the received word will be different from the parity of transmitted signal. This error is noticed. However, this error cannot be corrected.

5. Limitations of parity checking

(i)         Thus, the simple parity checking method has its limitations. It is not suitable for detection of multiple errors (two, four, six etc.).
(ii)        The other limitation of parity checking method is that it cannot reveal the location of erroneous bit. It cannot correct the error either.
EXAMPLE 10.1. Write the ASCII code of word HOLE using even parity.
Solution : The following table shows the ASCII code of word HOLE using even parity.
Table 10.1.

 
It may be noted that the parity bits are selected in order to obtain an even parity for each row (i.e. for each letter).
Checksum Error Detection

1. Definition

The errors usually occur in burst. The parity check method is not useful in detecting the errors under such conditions. The checksum error detection method can be used successfully in detecting such errors. In this method, a checksum is transmitted along with every block of data bytes. In this method an eight bit accumulator to used to add 8 bit bytes of a block of data to find the checksum byte. The carries of the MSB are ignored while finding out the checksum byte.

2. Detection of Error using the Checksum Byte

            After transmitting a block of data bytes (say 8-data bytes) the checksum byte is also transmitted. The checksum byte is regenerated at the receiver separately by adding the received bytes. The regenerated checksum byte is then compared with the transmitted one. If both are identical then there is no error. If they are different then the errors are present in the block of received data bytes.
Sometimes the 2’s complement of the checksum is transmitted instead of the checksum itself. The receiver accumulates all the bytes including the 2’s complement of the checksum. If there is no error, the contents of the accumulator must he zero after accumulation of the 2’s complement of the checksum byte.

3. Advantage of the Checksum method

The advantage of this method over the simple parity checking method is that the data bits are mixed up due to the 8 bit addition. Therefore, checksum represents the overall data bock. In checksum, therefore, there is 255 to 1 chance of detecting random errors.
10.9.3. Error Detection using VRC and LRC

1. Basic Concept

The concept of parity checking has been discussed earlier. This concept can be extended for detection and correction of single errors. In order to do so, the data block is arranged in a rectangular matrix form as shown in figure 10.12, and we generate two sets of parity bits. They are as under:
(i)         Longitudinal Redundancy Check (LRC)
(ii)        Vertical Redundancy Check (VRC)
 

 
FIGURE 10.12 Vertical and longitudinal parity check bits.

2. The Vertical Redundancy Check (VRC) Bits

            As shown in figure 10.13, the VRC bits are parity bits associated with the ASCII code of each character. Each VRC bit makes the parity of its corresponding column an even parity. For example, we conside column 1 corresponding to character C. The ASCII code for the character C is,

FIGURE 10.13
Therefore, the eighth bit b₈ which is a VRC bit is made 1 to make the parity even.

3. The Longitudinal Redundancy Check (LRC) Bits

            The LRC bits are parity bits associated with the rows of the data block of figure 10.14. Each LRC bit makes the parity of the corresponding row, an even parity. For example, we consider row 1 of figure 10.14.

FIGURE 10.14

4. Signal Transmission

The ASCII of figure 10.15 are transmitted in the following sequence:
5          Identification of bits in Error
Even a signal error in any bit will result in a non-correct LRC in one of the rows and an incorrect VRC in one of the columns. The bit which is common to the row and column is the bit in error. However, there is still a limitation on the Block parity code, which is that, multiple errors in rows and columns can be only detected but they cannot be corrected. This is because, it is not possible to locate the bits which are in error. This will be clear by the following example.
EXAMPLE 10.2. The following bit stream is encoded using VRC, LRC and even parity. Locate and correct the error if it is present.
1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1             1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0
0 0 1 0 1 0 1 0             0 0 1 0 1 0 1 1             1 0 1 0 0 0 1 1             0 1 0 0 1 0 1 1
1 1 1 0 0 0 0 1
Solution :
diagram
FIGURE 10.16
Figure 10.16 shows the received data block alongwith the LRC and VRC’ bits. It may be noted that the parity bits corresponding to row 1 and column 5 indicate wrong parity. Therefore, the fifth bit in the first row (encircled bit) is incorrect. Thus, using VRC and LRC, it is possible to locate and correct the bits in error.