Cyclic Redundancy Check in Computer Networks: Explained with Example

The brainchild of W. Wesley Peterson and D.T Brown, CRC, cyclic redundancy check was first introduced in 1961 as an innovative solution to the increasing data errors in communication networks. Over time, CRC has proven to be a valuable check system for protecting against errors in data transmission. It is instrumental in this era of the internet, where the transmission mediums have multiplied, and the load and complexity of data being exchanged have changed manifold.

Cyclic Redundancy Check (CRC): An Overview

During the transmission of the bits over the network, the data might get tampered with due to network glitches or unwarranted interventions. The result is that the bits are tampered with, leading to corrupt information, and these tampered bits are called errors.

Here, CRC or cyclic redundancy check in computer networks comes in, where the binary data packets are assigned a specific verification value or a checksum based on the remainder received after dividing their polynomial equivalents. Upon output, the polynomial calculation is repeated, and if the remainder of the check values does not match, it indicates data corruption and requires rectification.

Check out our free courses related to software development.

Terms and Features of CRC

To execute a cyclic redundancy check, CRC should be performed by both the sender and receiver. In other words, applying the cyclic redundancy check generator and the checker should be available for both the sender and the recipient.

The CRC algorithm is based on the pattern of the Checksum algorithm for error detection, especially the IPV4 TCP prototype that employs the Modulo algorithm. In this case, polynomial coefficients are converted to binary equivalents for computational purposes.

If we consider x2+x+1 a polynomial equation, we see the corresponding binary value at each position in converting it to the binary format. If a value is present in the nth position, the return is either 1 or 0. In this equation, 1 is the value at the 0th position. The value at the 1st position corresponds to x, and the value at the second position corresponds to x2. The resultant binary equivalent is 111.

The Executive PG Programme in Full Stack Development from IIITB is perfect for those seeking a short-term but holistic course. 

Understanding Cyclic Redundancy Check Through An Example

Using an example, let us see how cyclic redundancy check occurs with polynomial division.

Consider the dividend or the data stream to be x3+1 and the divisor or the CRC polynomial generator to be x3+x+1. Their corresponding binary formats will be 1001 for the dividend and 1011 for the divisor. Since the divisor is of 4 bits, a string of three zeroes will be appended to the dividend, which is one less than the divisor. The resultant dividend will be 1001000. 

After division, the remainder is a 3-bit string of 110. The receiver will get a data string of 1001110. They will further divide it with 1011. The remainder will be 000, indicating the sent data is accurate.

If you are particularly interested in cyber security and designing error correction algorithms, sign up for the Master of Science in Computer Science from LJMU. It will help propel your software development and coding career, especially full stack development. 

Controlling Error in Data Link Layer Through CRC (Cyclic Redundancy Check)

In data link layers, specific techniques for regulating errors ensure that the data bit streams are transmitted from the sender to the receiver with a certain veracity level. These include detection and correction.

Suppose a sender wants to transmit Q length of data and that S is the highest degree of the algebraic polynomial to generate the CRC binary units. The total number of bits the sender sends will then amount to Q+S bits.

As mentioned, the CRC bits are generated by dividing the input data stream, Q+S, with the generator polynomial. Then add S number of 0 bits to the data Q to create the dividend. Perform the XOR function at each division step during the entire division. 

The remainder of this first division gets replaced by an S number of 0 bits, thus changing the input data stream to Q+S again or the original input data stream + remainder. This resultant data gets sent to the receiver, verifying the received bits using the earlier division. Again, the XOR function is applied between bits at each division step. If the reminder is 0, then accurate data is received.

CRC Qualities

For a CRC generator to be valid, it must possess the following qualities:

•  The algebraic polynomial should not have x as one of its divisors. This ensures that any burst errors of the same length as the polynomial can be detected.
• The divisibility of the polynomial should include x+1 to identify all burst errors which impact an odd number of binary units.
• The bits of the CRC algorithm should possess a value equal to the highest degree of the algebraic polynomial.
• When the CRC generator is conjoined to the end of the data unit, the resultant data sequence should return no remainder when divided.
• The CRC generator should identify odd, single-bit, and any burst error of length equivalent to the polynomial degree.
• The CRC polynomial should have one bit less than the divisor. 

Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs or Masters Programs to fast-track your career.

CRC Generator and CRC Checker

CRC generator is a polynomial function represented in the algorithm as a bit sequence. To obtain a bit sequence from the CRC generator, programmers employ a mathematical rule— they determine the power of each term in the polynomial equation to locate the bit’s position and assess the coefficient to get the bit’s value, whether 0 or 1.

First, a sequence of n 0s or a certain number of redundant or null bits, also known as the CRC remainder, is added to the end of a data unit. The binary divisor divides the resultant data unit comprising parity alongside information bits. 

No remainder upon division proves the data’s accuracy and passes the check. The return of a remainder greater than zero indicates a discrepancy leading to data rejection. This exact function is replicated by the CRC checker, positioned at the transmitter’s end, and the CRC generator, provided by the receiver.

CRC Examples

CRC checks are conducted in multiple arenas, especially in various protocols and systems. A cyclic redundancy check example list is given below:

•  Ethernet: In ethernet network systems, programmers can use cyclic redundancy checks to identify discrepancies in the data load transferred over the system. The frame structure of Ethernet has a CRC field, which can help identify errors and ensure foolproof reception of data.
• USB devices: Appliances using USB technology, such as flash drives and storage devices, also benefit from monitoring data errors by applying a cyclic redundancy check on the data packet being read from the device.
• Disk storage: Disk storage equipment such as hard drives and optical disks use CRC to pinpoint errors in the information written to the disk. They store the CRC-generated checksum algorithm alongside the information and spot errors during data readback.
• Industrial regulation infrastructures: When data is transmitted between different parts of the industrial control systems, such as those used in factories and power plants, a cyclic redundancy check can help prevent any corrupted data from being sent.
• Digital audio and video: With the proliferation of higher video resolution and quality sounds, the quantity of data transmitted has also increased. The slightest error in the transmission of data can lead to an incorrect display of pixels or the production of poor-quality sound. Hence, a CRC checksum can minimise the chances of such glitches.

How Does the CRC Method Function?

To understand how the CRC method works, we need to understand it from the perspective of the sender and the receiver.

Sender Side

This part involves the CRC generator and Modulo Division. First, add a string of a certain number of zeroes to be appended to the input data stream. The mathematical operation k-1 obtains this number. Here k is the number of bits representing the polynomial equation in the CRC generator. Hence the number of bits to be added will be one less than the number of CRC bits.

The next step is to apply Modulo Binary Division to the resultant data stream. This is done by dividing the data string with the CRC generator with the XOR function at every step. The remainder is then called CRC. One has to add this CRC remainder to the end of the data unit by replacing the previous appended string of redundant bits. The final result (original data combined with CRC) is sent to the receiver.

Receiver Side

This part involves verifying if there are any errors in the received data. Once the sender receives the code, the Modulo Division is repeated with the CRC generator as the divisor. After division, if the remainder is zero, it can be assumed that the data was not corrupted during transmission and can be accepted. If the remainder is not zero, the receiver should assume that some transmission error occurred.

Conclusion

To get the maximum out of your cyclic redundancy check data protection, consider a few parameters, such as the number of bits for computation and the kind of errors you are mostly likely to encounter in your data network. 

To learn more about customising CRC computations to manage specific error situations, enrol at Full Stack Software Development Bootcamp from upGrad. This six-month long bootcamp offers holistic training on data check algorithms, among many other topics trending in the tech industry. Boost your employability 10 times with over 20 projects based on real-life industry projects.