Cyclic Redundancy Check (CRC) Error Detection Technique

Abstract – This paper presents a way to guarantee the data transmitted over the network applying Cyclic Redundancy Check (CRC) error detection technique which work on the approach of binary division. A network must be able to transmit data from one end to other end with preciseness. Although transmission errors are the frequent fact of data communication. It is not compulsory that the data received at receiver end is same to the data transmitted by the sender. Several reasons are responsible for data corruption as thermal noise, impulse noise, etc. To have a dependable or steady communication, the system must be enhanced with error detection and error correction techniques. In that case, CRC have been positioned to achieve perfection in data communication.

1. INTRODUCTION

   For an efficient transmission of digital information (data in form of bits) over the channel, channel coding is a significant operation for signal processing. In channel coding the figure of symbols in the origin/beginning encoded message becomes larger in a managed way, in order to ease two basic objectives at the receiver, first is Error Detection and the second is Error correction. For they are both deployed in devices to accomplish good communication, by reducing the level of noise and interference form electronic mechanism. Once data is transmitted over the network, it does not assure error free or perfect reception and goes through unpredictable changes in the transmission media. The Data Link layer on the OSI Model is in charge of error control. Error control is defined as the composition of both error correction and error detection. Anytime data is transmitted over the network, the Data Link checks for the error between the routers and corrects them.

Two types of error:
 

1. Single bit error

  It occurs when one bit of data unit gets corrupted during transmission. Which means that only one bit of a given data unit is changed from 1 to 0 or 0 to 1 It can be easily detected and corrected.

Sent data — 1 1 1 0 1 1 0 1

(1      is changed to 0)

Received data —— 1 0 1 0 1 1 0 1
 

2. Burst Error

   It occurs when 2 or more bits in the data unit get corrupted during transmission, also known as multiple bit error. It means that the 2 or more bits have changed from 1 to 0 or 0 to 1.  It is difficult to be detected and corrected. It is likely to occur in a serial data transmission.

For example,
Multiple bit below are changed –

Sent Data ———-1 1 1 0 1 1 0 1
Received Data —-1 0 1 0 0 1 1 1       

3. Data: The information to be transmitted in the form of bits is recognized as data.
4. Message:  Message is the composition of data bits and the CRC bits generated using CRC generator algorithm. It is described as the data unit. To proof the correctness of data in CRC technique, the message operated under binary division using generating polynomial as the divisor, its remainder must be Zero.

[Message][CRC bits]

—————————-   = 0

Generating Function

2. ERROR CONTROL

   Error control is the process of detecting and correcting errors when data is transmitted over the network. It ensures reliability of data transmission from one end to the other end. Data can be corrupted during transmission, so in other to maintain reliable communication errors must be detected and corrected, from alteration or any type of changes. With this, data unit received can be identified if altered, or is in its actual form as sent from the sender. The man-in-the-middle is the usual type of attack in data communication whose existence results in data modification. Error control is implemented at the transport layer and data link layer of OSI model, but transport layer gives error control between router and host, while data link layer delivers error control between router and router. This study bothers about the error control at data link layer.

A. Error Detection: The procedure of detecting error by using the idea of redundancy is defined as error detection. Redundancy is appending some extra bits to the data unit for error detection known as redundant bits. One of the four different techniques of error detection is Cyclic redundancy check which I am focusing on in this paper.

B. Error Correction:  After detecting an error, the procedure for correcting the error is called error correction. This paper evaluates CRC error detection approach.

C. Redundancy: A group of bits is appended to data unit for error detection, instead of retransmitting the data bits to the receiver end. This procedure is known as the redundancy and the extra bits appended is recognized as the redundant bits. If the correct and precise data unit is received by the receiver the bits are discarded.

1. Generating function and Use:

 It generates redundant bits by analysing the data, while use checks the accuracy of transmitted data, with this one can accept or reject data.
 

3. CRC (CYCLIC REDUNDANCY CHECK)

        One of the most powerful redundancy checking procedure based on binary division. In this approach, a sequence of redundant bits is appended to the end of the data unit recognized as CRC with two significant standards.

1. It must be one less than the number of its divisor
2. Data units must be exactly divisible by the divisor after appending these bits.

There are two significant steps of CRC procedure, the CRC generator and the CRC Checker.

1.  CRC generator
   In this procedure, the CRC bits are calculated at the sender side using a

generating function in a way that the data unit and the generating function are conducted using bit-wise XOR. The generating function is n+1 bits and CRC are of n bits.

2.  CRC Checker

     In this procedure, CRC bits at the receiver side are calculated to check whether they are similar to 0 or not. It applies the bit-wise XOR on the data unit received from the sender and generating function. It is accepted when all the CRC bits are 0 else it is discarded.

3. Polynomial

    A polynomial should meet the following circumstance.

1. It should be not divisible by x
2. It should be divisible by x+1

     Number one condition assures detection of the burst errors of length equal to the highest degree of polynomial, while number two condition assures detection of all burst error affecting odd number of bits. The Generating polynomial is important in CRC error detection being a mathematical equation used to locate the generating function bits.

My explanation:
 

      When the highest degree of any equation is 4, the number of the generating function bits are 5. The generating bit stays same at both sender and receiver end and calculates precise results.  Error detection is not guaranteed for any data unit if the function changes and generates false result. It will be difficult to identify if the data unit is correct or corrupted.

If the Generating Polynomial is x^3+x+1 the generating function will be-

1011
1 – coefficient of degree 3

0 – coefficient of degree 2

1 – coefficient of degree 1

1 – coefficient of degree 0

   The leading degree of a given polynomial is 3, consequently the number of bits in the generating function is 4.

 Another example for seeking the generating polynomial where the prior term of equation is not known. If polynomial equation is-
x^5+x^3+x^+2+x   the generating function will be –

101110

1 – coefficient of degree 5

0 – coefficient of degree 4

1 – coefficient of degree 3

1 – coefficient of degree 2

1 – coefficient of degree 1

0 – coefficient of degree 0

     
       The topmost degree of polynomial equation is 5, hence number of bits in the generating function is 6.

4. ALGORITHM

   In this section two algorithm are presented for the CRC Error detection procedure, the first generates the CRC bit at the sender side and the second detects error in data unit transmitted from one end to another end at the receiver end. CRC bits calculated with CRC generated algorithm will be appended to the data unit to be transmitted from one end to the other end. CRC algorithm checked the obtained message’s correctness and if it so, CRC is discarded, and data is accepted, or else data is discarded. This paper introduces a clear algorithm for CRC. In the first instance, when there is only information then 0s are appended to the data bits, that performs as CRC bits to calculate the CRC. The calculated resulted is substituted by 0 bits append to the data bits. This is the genuine data unit known as the message and transmitted over the network to the other end. Same generating function is used and computed at the receiver end. The data received is correct when all are 0s or else it is corrupted and discarded.
The following algorithm are below.

1        Algorithm for CRC generator

2        Algorithm for CRC checker

A.      Algorithm for CRC generator

1. Enter the number of data bits and CRC bits
2. Input generating function bits, its value and data bits value
3. Carry out Adder operation on the variable inputted in step -1
4. Keep data bits, generating functions bits and data unit (data bits + CRC bits) to be conducted in separate arrays.
5. Rerun step-6 till each bit of data unit is actioned
6. Examine data unit to be actioned-

                If(1^st bit==0)

          XOR the data unit with 0 and keep the result in same array of data unit.
                  else
          XOR the data unit with generating function and store the result in the same            
          array of data unit.

7. Present CRC bits and data unit to be transmitted over the network to receiver side after appending CRC bits to data bits.
    

B. Algorithm for CRC checker

1. Insert the number of data unit bits (data bits + CRC bits) from the sender
2. Input generating function bits value and data unit.
3. Keep generating function bits and data unit from the sender in several arrays.
4. Run through stage 5, for each bit data unit to be processed
5. Review data unit from the sender-

                    If(1^st bit==0)

  XOR the data unit with 0 and keep the result in same array of data unit.
                    else
  XOR the data unit with generating function and store the result in the same   
  array of data unit.

6. Present CRC bits carry out adder exercise on them and keep the result in same array of data unit
7. Review the value of integer variable (var)-
                   if (var==0)

 Data unit is correct and accepted after discarding the CRC bits
         else

Data unit received is corrupted and discarded.

Fig 4.1 and fig 4.2 describes the flowchart for CRC checker and generator.
The user enters CRC generator, data bits, number of CRC bits, generating function bits, and its value.
Data and CRC bits are executed under binary division with generating function from generating polynomial. The binary division’s remainder is the actual CRC generated at the sender side. The CRC is appended to the data bits and transmitted on the network for the destination.

To ensure whether the data unit is correct or corrupt at the destination end, same generating function is used, the received message is operated under binary division.

The data unit is correct and accepted if the remainder of the binary division is all 0s, but if it is non-zero mean data is altered during transmission, then discarded by the receiver and of no use at the receiver end.

5. CONCLUSION

  
This writeup demonstrated CRC error detection approach based on the binary division applying elementary XOR bit-wise procedure and algorithm for its deployment.

It leverages the concept of redundancy that appends some extra bits known as redundant bits for error detection that was implemented at the Data Link Layer of OSI Model. Few techniques used for detecting at the data link layer including CRC delivers appealing efficiency Compared to other procedures CRC provides better secured and accurate performance compared to others.

6. CYCLIC PERFORMANCE

1. It detects burst error of length greater than degree of polynomial with high probability
2. It detects all burst error affecting odd number of bits
3. It detects all burst error length less than or equal to degree of polynomial

7. REFERENCES

1. Sukirty, J.A.I.N & Chouhan, S.S. 2014. Cyclic Redundancy Codes: Study and Implementation. International Journal of Emerging Technology and Advanced Engineering. 4(4), pp. 213 – 217.
2. Techopediacom. 2018. Techopediacom. [Online]. [18 November 2018]. Available from: https://www.techopedia.com/definition/6970/error-control-ec
3. Forouzan, B.A (2003). Data Communication and Networking. (3rd ed.). Singapore: Mc Graw Hill.
4. Peterson; et.al, “Cyclic Codes for Error Detection”, Proceedings of the IRE, Vol: 49 (1): January 1961.
5. Williams, Ross N. (24 September 1996), “A Painless Guide to CRC Error Detection Algorithms V3.00”, retrieved 5 June 2010.
6. Koopman; et.al, “Cyclic Redundancy Code (CRC) Polynomial Selection for Embedded Networks”, The International Conference on Dependable Systems and Networks: 145–154, retrieved 14 January 2011.
7. Castagnoli; et.al, “Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits”. IEEE, June 1993
8. Koopman, Philip, “32-Bit Cyclic Redundancy Codes for Internet Applications”. The International Conference on Dependable Systems and Networks Retrieved 14 January 2011.
9. Yanbin Zhang; Qi Yuan,” A multiple bits error correction method based on cyclic redundancy check code”, 9th International Conference on Signal Processing, ICSP 2008.
10. Jun Jin Kong;et.al,” Interleaved cyclic redundancy check (CRC) code”, Conference Record of the Thirty-Seventh Asilomar Conference on Signals, Systems and Computers, Vol:2,2004.
11. Vikas gupta; et.al,”Error detection and correction: An Introduction”,vol:2(2), ISSN, Nov 2012.