5.2 ERROR DETECTION

< Day Day Up >

---

5.2 ERROR DETECTION

The three widely used techniques for error detection are parity, checksum, and cyclic redundancy check (CRC). These techniques are discussed in the following sections.

5.2.1 Parity

Parity is used in serial communication protocols whereby we transmit one character at a time. For example, if the information bits are

1 0 1 1 0 1 0

then an additional bit is added, which is called a parity bit. The parity bit can be added in such a way that the total number of ones becomes even. In such a case, it is called even parity. In the above bit stream, already there are four ones, and hence a 0 is added as the parity bit. The bit stream transmitted is

1 0 1 1 0 1 0 0

In case of odd parity, the additional bit added will make the total number of ones odd. For odd parity, the additional bit added in the above case is 1 and the transmitted bit stream is

1 0 1 1 0 1 0 1

At the receiving end, from the first 7 bits, the receiver will calculate the expected parity bit. If the received parity and the calculated parity match, it is assumed that the character received is OK.

The various parities can be even, odd or none. In the case of none parity, the parity bit is not used and is ignored.

It is very easy to verify that parity can detect errors only if there is an odd number of errors; if the number of errors is 1, 3, or 5, the error can be detected. If the number of errors is even, parity bit cannot detect the error.

Parity bit is the additional bit added to a character for error checking. In even parity, the additional bit will make the total number of ones even. In case of odd parity, the additional bit will make the total number of ones odd. Parity bit is used in serial communication.

5.2.2 Block Codes

The procedure used in block coding is shown in Figure 5.2. The block coder takes a block of information bits (say 8000 bits) and generates additional bits (say, 16). The output of the block coder is the original data with the additional 16 bits. The additional bits are called checksum or cyclic redundancy check (CRC). Block codes can detect errors but cannot correct errors.

In block coders, a block of information bits is taken and additional bits are generated. These additional bits are called checksum or cyclic redundancy check (CRC). Checksum or CRC is used for error detection.

Figure 5.2: Block coder.

Checksum

Suppose you want to send two characters, C and U.

The 7-bit ASCII values for these characters are

C    1 0 0 0 0 1 1
U    1 0 1 0 1 0 1

In addition to transmitting these bit streams, the binary representation of the sum of these two characters is also sent. The value of C is 67 and the value of U is 85. The sum is 152. The binary representation of 152 is 1 0 0 1 1 0 0 0. This bit stream is also attached to the original binary stream, corresponding to C and U, while transmitting the data.

Checksum of information bits is calculated using simple binary arithmetic. Checksum is used extensively because its computation is very easy. However, checksum cannot detect all errors.

So, the transmitted bit stream is

1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0

At the receiving end, the checksum is again calculated. If the received checksum matches this calculated checksum, then the receiver assumes that the received data is OK. The checksum cannot detect all the errors. Also, if the characters are sent in a different order, i.e., if the sequence is changed, the checksum will be the same and hence the receiver assumes that the data is correct.

However, checksum is used mainly because its computation is very easy, and it provides a reasonably good error detection capability.

Note

Checksum is used for error detection in TCP/IP protocols to check whether packets are received correctly. Different algorithms are used for calculation of checksum.

Cyclic Redundancy Check

CRC is a very powerful technique for detecting errors. Hence, it is extensively used in all data communication systems. Additional bits added to the information bits are called the CRC bits. These bits can be 16 or 32. If the additional bits are 16, the CRC is represented as CRC-16. CRC-32 uses 32 additional bits. There are international standards for calculation of CRC-16 and CRC-32. Since CRC calculation is very important, the C programs to calculate the CRC are in Listings 5.1 and 5.2. When these programs are executed, the information bits and the CRC in hexadecimal notation will be displayed.

Error detection using CRC is very simple. At the transmitting side, CRC is appended to the information bits. At the receiving end, the receiver calculates CRC from the information bits and, if the calculated CRC matches the received CRC, then the receiver knows that the information bits are OK.

CRC-16 and CRC-32 are the two standard algorithms used for calculation of cyclic redundancy check. The additional CRC bits (16 and 32) are appended to the information bits at the transmitting side. At the receiving side, the received CRC is compared with the calculated CRC. If the two match, the information bits are considered as received correctly. If the two do not match, it indicates that there are errors in the information bits.

Program for calculation of CRC-16

Listing 5.1: Program for calculation of CRC-16.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long CRC = 0x0000;
long GenPolynomial = 0x8005; //Divisor for CRC-16 Polynomial

void bitBybit(int bit);

int main()
{
   unsigned int MsgLength;
   int i=0,j=0;
   char SampleMsg[] = "Hello World";
   char tempBuffer[100];

   MsgLength = sizeof(SampleMsg)-1;

   printf("\nActual Message: %s\n",SampleMsg);

   strcpy(tempBuffer, SampleMsg);
   tempBuffer[MsgLength] = 0x00;
   tempBuffer[MsgLength+1] = 0x00;
   tempBuffer[MsgLength+2] = '\0';

   printf("\nAfter padding 16 0-bits to the Message:");

   for(i=0;i<MsgLength+2;++i)
   {
      unsigned char ch = tempBuffer[i];
      unsigned char mask = 0x80;
      for(j=0;j<8;++j)
      {
         bitBybit(ch&mask);
         mask>>=1;
      }
      printf(" ");
   }
   printf("\n\nCalculated CRC:0x%x\n\n",CRC);
      return 0;
}

void bitBybit(int bit)
{
   long firstBit = (CRC & 0x8000);

   CRC = (CRC << 1);
   if(bit)
   {
      CRC = CRC ^ 1;
      printf("1");
   }
   else
   {
      CRC = CRC ^ 0;
      printf("0");
   }
   if(firstBit)
   {
      CRC = (CRC^GenPolynomial);
   }
}

In this listing, the actual message to be transmitted is "Hello World". The message is padded with sixteen 0 bits, and the message bit stream is

       01001000 01100101 01101100 01101100 01101111 00100000 01010111
01101111 01110010 01101100 01100100 00000000 00000000

The calculated CRC value in hexadecimal notation is 0x303f70c3.

Program for calculation of CRC-32

Listing 5.2: Program for calculation of CRC-32.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long CRC = 0x00000000L;
long GenPolynomial = 0x04c11db7L; //Divisor for CRC-32 Polynomial

void bitBybit(int bit);

int main()
{
   unsigned int MsgLength;
   int i=0,j=0;
   char SampleMsg[] = "Hello World";
   char tempBuffer[100];

   MsgLength = sizeof(SampleMsg)-1;

   printf("\nActual Message: %s\n",SampleMsg);
   strcpy(tempBuffer, SampleMsg);
   tempBuffer[MsgLength] = 0x00;
   tempBuffer[MsgLength+1] = 0x00;
   tempBuffer[MsgLength+2] = 0x00;
   tempBuffer[MsgLength+3] = 0x00;
   tempBuffer[MsgLength+4] = '\0';

   printf("\nAfter padding 32 0-bits to the Message:");

   for(i=0;i<MsgLength+4;++i)
   {
      unsigned char ch = tempBuffer[i];
      unsigned char mask = 0x80;
      for(j=0;j<8;++j)
      {
         bitBybit(ch&mask);
         mask>>=1;
      }
      printf(" ");
   }
   printf("\n\nCalculated CRC:0x%x\n\n",CRC);
      return 0;
}

void bitBybit(int bit)
{
    long firstBit = (CRC & 0x80000000L);

   CRC = (CRC << 1);
   if(bit)
   {
      CRC = CRC ^ 1;
      printf("1");
   }
   else
   {
      CRC = CRC ^ 0;
      printf("0");
   }
   if(firstBit)
   {
      CRC = (CRC^GenPolynomial);
   }
}

Listing 5.2 gives the C program to calculate CRC-32. In this program the message for which CRC has to be calculated is "Hello World". The message bit stream is

       01001000 01100101 01101100 01101100 01101111 00100000 01010111
01101111 01110010 01101100 01100100 00000000 00000000 00000000 00000000

The calculated CRC is 0x31d1680c.

Note

In CRC calculation, a standard polynomial is used. This polynomial is different for CRC- 16 and CRC-32. The bit stream is divided by this polynomial to calculate the CRC bits. Using error detection techniques, the receiver can detect the presence of errors. In a practical communication system, just detection of errors does not serve much purpose, so the receiver has to use another mechanism such as asking the transmitter to resend the data. Communication protocols carry out this task.