CYCLIC REDUNDANCY CHECK (CRC)

CYCLIC REDUNDANCY CHECK (CRC)

In synchronous communications, CRC is used to verify the integrity of the entire packet or block of data. Integrity of the packet means whether the complete packet of data received in its correct form as it was sent from the sending end. In synchronous communications, parity checking is sufficient to ensure data integrity. In high-speed asynchronous communications, single bit corrections are not enough. As each packet is created, a CRC check is placed somewhere in the packet and is verified at the receiving end.

            CRC is a calculation method used to check the accuracy of a digital transmission over a communication link. The sending computer uses one of several formulas to calculate a value from the information contained in the data, and this value is appended to the message block before it is sent. The receiving computer performs the same calculation on the same data and should drive the same number. If the two CRCs  do not match, indicating that a transmission error has occurred, the receiving computer asks the sending computer to retransmit the data.

            This procedure is known as redundancy check because each transmission includes extra or redundant error-checking values as well as the data itself. A CRC is generated by dividing the total number of bits in the block of data being sent by a predetermined binary number. The reminder is then added to the packet and the packet is transmitted. On the receiving end, the reverse mathematical operation is performed to verify the packet contents. If the computation is successful, the packet is passed to the next step. If it fails, the issuing node is notified and the entire packet is re-transmitted.

            Common CRC patterns are 12-bit (CRC 12), 16-bit (CRC 16), and 32-bit (CRC 32).

One of the most common and widely used error detection methods for synchronous data transmission is Cyclic Redundancy Check (CRC), developed by IBM. IBM uses CRC-16 as the specific application of the CRC method. This process uses a constant "divisor" which is in binary form as ::

                          1000 1000 0001 0000 1

The steps are follows :

(a) Add 16 zeros (1 less bit than the number of bits in the "divisor") after the Least Significant Bit of the message to be sent. The message is then written down as it would be transmitted, with the extra bits sent first ( i.e. most significant bits).

(b) The divisor is exclusive ORed with the 16 most significant bits of the message are appended to the result of this to from another 16 bits of data headed by a 1.

(c) The exclusive ORing is repeated along with the rest of the process until all bits in the message are exhausted.

(d) The final exclusive OR result is the CRC characters. Enough leading zeros are appended to the CRC character to from a total of 16 bits.

           We shall try to understand the CRC character calculation using the following CRC-4 method with the modified divisor constant of 10011:

          Let the message be 1100 0110 1011 01 (The LSB is on the right)

          There is one less zero than the total number of bits in the divisor which is 10011. To use the shortened CRC-4 divisor, four zeros are

first appended to the message. The extended message becomes:

      

       110001101011010000

       Now we set up the problem:

       10011)110001101011010000

       

       Exclusive OR the first five bits with the "divisor" we have:

       10011)110001101011010000

             10011

             -----------

               1011

By bringing down the next bit from the message and repeating the process until all the bits in the appended message are used.

     We do this as shown below:

     10011)110001101011010000

           10011

           ----------

            10111

            10011

            ----------

             10010

             10011

             ----------

              11011

              10011

              ----------

               10000

               10011

               ----------

                 11100

                 10011

                 ----------

                  11110

                  10011

                  ----------

                   11010

                   10011

                   ----------

                     1001 = CRC

The original message followed by the CRC-16 bytes is sent to a receiving station. At the receiving station, the data are shifted in and a CRC is computed using the entire message plus the CRC bytes. If the same constant "divisor" is used, the result of the receiver's CRC computation is all zeros when there are no errors.

             To detect the correct communication errors, a sender must provide a receiver with information that enables the receiver to verify proper receipt of information or data. The sender could simply send an entire set of information twice and let the receiver compare the two sets of information for error detection, but because of the time and computer resources, it takes to perform this type of comparison. It is more popular to detect the error based on mathematical calculations that are hardware or software execute at high speed.

              The sender must use a mathematical technique to calculate error-checking data. The sender generates this redundancy data from the bit stream of information data from the bit stream of information data it sends and then appends the redundancy data to the end of the bit stream. The receiver must generate its own redundancy data from the information data it receives and compare the results with the redundancy data it receives from the sender. A favourable comparison indicates the absence of errors. An unfavourable comparison indicates the presence of errors.