Free Cyclic Redundancy Check (CRC) Technical Report. Report Example

Introduction:

Modern data transmission and network communication protocols utilize at least one error-detection algorithm to ensure reliability of communications between the source and destination. The most popular of these algorithms is the Cyclic Redundancy Check (CRC) algorithm (Wadhwani and Narkhede). CRC is used for error detection in digital data but does not necessarily make corrections to the errors detected. The algorithm is mainly used in data transmission and networking where a specified number of check bits known as a checksum are appended to a message during transmission. The recipient determines whether or not the checksum is in agreement with the received data, and to determine with a certain level of probability if any errors occurred during data transmission. If an error is detected, the recipient sends a negative acknowledgment (NAK) message back to the sender requesting him to retransmit the message (Warren).
CRC techniques are also applied in data transfer and storage technologies such as optical and hard disk drives. In the scenario, each data block on a disk would essentially have a checksum, and when an error is detected during data reads, the hardware might initiate and automatic clock reread, or if not possible, report the error to the software and/or user. The paper will discuss CRC from a networking perspective where there is a “source/sender” and a “destination/receiver” of a “transmission/message” but it should also be noted that the techniques apply to storage reading and writing as well (Warren).

CRC algorithm working theory:

The CRC algorithm uses polynomial arithmetic particularly in computing the remainder by dividing a GF (2) (Galois field with two elements) polynomial by another. Essentially, it involves treating the transmitted message as a very large binary number then dividing it by a very large prime such as 232-5 to obtain the remainder. Logically, a very reliable checksum is expected from the computation (Warren).
A GF (2) polynomial is a polynomial that has a single variable such as X and whose coefficients are either 0 or 1. The addition or subtraction of these polynomials is done in modulo 2 which means they are equivalent to the XOR (exclusive or) operator. A good example is the sum of polynomials x3+x+1 and x4+x3+x2+x which results to x4+x2+1 which is also their difference. These polynomials do not usually take up the negative signs (-) but it is possible to incorporate them since a coefficient of 1 is the same as the coefficient of -1 (Sheidaeian and Zolfaghari).
Multiplying GF (2) polynomials is easy since the product of coefficients is the equivalent of combining them using the logical operator AND, and summation of partial products is done using the XOR (exclusive or) operator. However, the details of multiplication are not of great importance in this context since CRC checksum computation does not need multiplication. Polynomial division over GF (2) is similar to long division of polynomials by integers (Warren).
CRC techniques treat the message as a GF (2) polynomial. For example, if the given message is 11001001 with a left to right transmission order then it is treated as a polynomial. The sender and recipient agree on a fixed generator polynomial such as the 16-bit CRC polynomial x16+x12+x5+1 chosen by the International Telecommunications Union – Telecommunications Standards Sector (ITU-TSS), and widely used to compute 16-bit checksums (Warren).
A degree r generator polynomial is required to compute an r-bit CRC checksum. A sender transmitting an m-bit message appends r 0-bits to the message then divides the resultant m+r-1 degree polynomial by the generator polynomial. The result of this division is a r-1 degree (or less) polynomial. There are r coefficients in the remainder polynomial after division and these form the checksum. The quotient polynomial is then disposed of and the code vector (data transmitted) is the original m-bit message with an r-bit checksum appended to it (Warren).

CRC Practical algorithms:

CRC is generally defined in polynomial or hexadecimal notation according to protocol specifications. The Table 1 below shows some generator polynomials used by common CRC standards and their corresponding hexadecimal equivalents with the most significant bit overlooked since it is always 1.
CRC standards vary in many other ways apart from their generating polynomials. Some CRC algorithms initialize through the assumption that a transmitted message has a number of non-zero bits preceding it while others do not initialize anything. Some CRC algorithms do transmit the bits within a byte with the most significant bit leading but in most algorithms; the least significant bit is the lead bit during transmission. In some algorithms, the least significant byte in the checksum is appended first while in others it the most significant byte that is appended first. In fact, some CRC algorithms complement the checksum to improve accuracy checks (Wadhwani and Narkhede).
CRC-12 is used when 6-bit character stream transmissions while the rest are used for 8-bit character and 8-bytes of arbitrary data transmission. CRC-16 is used in the BISYNCH communication standard developed by IBM while the CRC (ITU-SSS) is used in various communication protocols which include X.25, XMODEM, ISO’s HDLC, and IBM’s SDLC. CRC-32 also known as ITU-TSS and AUTODIN-II is used in ATM Adaptation Layer 5 (AAL5), Ethernet, PKZip, FDDI (Fiber Distributed Data Interface), and IEEE-802 LAN/MAN standards (Wadhwani and Narkhede).

CRC Hardware Implementation:

The hardware implementation example of CRC uses the CRC- 16 (ITU-TSS) where computation of CRC is done using XOR gates and shift registers. The Figure 1 below shows the CRC generator for the CRC- 16 (ITU-TSS) polynomial where each data bit is shifted into the CRC shift register designed using Flip Flops after being passed through XOR gates together with the most significant bit in the CRC.
Figure 1: CRC Hardware Implementation

Communication simulator implementing CRC error detection algorithm:

In order to explain how CRC actually works in a network, a simple communication application that uses a Pseudo Random Number Generator (PRNG) to generate 8-bit long messages d (x) is explained. The sender performs a CRC computation and encodes the message by appending a checksum to it. The now encode message is referred to as a code word c (x) (Mohtarim, Zaman, and Hoque).
The message transmission channel is unreliable and may corrupt the message being transmitted due signal attenuation, noise, and interference. The now possibly corrupted codeword c (x) is decoded at the destination using a CRC checking algorithm. It should be noted that the sender and recipient both agree on the common generator polynomial represented as G (x). The result of the CRC check, syndrome s (x) is then used to detect errors that may have occurred during transmission of the message as shown in the Figure 2 below.
Figure 2 Communication with CRC error detection (Wadhwani and Narkhede)

Error detection and verification:

Polynomials can be used to analyze the capability of cyclic codes. In this case, the representations used in the communication simulator are used. The representations are as follows: message d (x), generator polynomial G (x), code word c (x), syndrome s (x), and now introducing error e(x) in this section. During analysis, the chief intention is to find a suitable criteria that must applied to the polynomial generator G (x) so as to detect the type of error e (x) (Mohtarim, Zaman and Hoque).
In this case, the received codeword has not been determined to contain and error on not, and is thus considered as a summation of the initial code word c (x) and the error e (x) which is represented as:
Received code word = c (x) + e (x).
The recipient divides the received codeword by the generator polynomial G (x) to determine the syndrome s (x) as shown below.
Received CodewordGx=cxGx+exGx
According to the received code word definition above, the first term on the right side of the equation does not have a remainder thus the syndrome s (x) is definitely a remainder of the second term. If the second term does not have a remainder either, and the syndrome s (x) is equated to 0 i.e. (syndrome = 0) then the conclusion is that, e (x) = 0, or e (x) can divide G (x). In the first case where the error is 0 means that the message was successfully transmitted with no errors. The second case where e (x) is divisible by G (x) implies that errors may have been present and since they are divisible by G (x), they were not caught. In all cyclic codes, errors divisible by G (x) are not detected (Mohtarim, Zaman, and Hoque).

Summary and Conclusion:

It has been observed that CRC error detection algorithms are applicable in areas where data is transferred both to storage media such as disk drives and communication networks such as Ethernet LANs (local area networks). It has also been noted that there are many variations of CRC which are mostly defined by the protocol but all working to achieve the same goal. After going through the theoretical background of CRC and the mathematics behind it, it is evident that CRC algorithms are complex to design especially since computations involve modulo-2 operations. The paper has also presented practical examples of CRC algorithms and their implementation in communication as well as error detection and verification. Overall, the paper presents a basic idea of CRC operations but in reality, the math is more complex, and the processes are altered to correct for deficiencies where some errors might exist but still go undetected by the system.

Works Cited:

Mohtarim, Hasan Md., Ayesha Zaman, and Nowrin Hoque. 'An Approach for a Standard Polynomial for Cyclic Redundancy Check'. International Journal of Computer Applications (IJCA) 35.2 (2011): n. pag. Web. 10 Mar. 2015.
Sheidaeian, Hamed, and Behrouz Zolfaghari. 'Parallel Computation of CRC Using Special Generator Polynomials'. IJCNC 4.1 (2012): 39-47. Web. 10 Mar. 2015.
Wadhwani, Jyoti, and Nitin Narkhede. 'Implementation of Communication Using Cyclic Redundancy Check'. International Journal of Emerging Technology and Advanced Engineering 3.7 (2013): 228-232. Print.
Warren, Henry S. Hacker's Delight. Upper Saddle River, NJ: Addison-Wesley, 2013. Print.