Cyclic Redundancy Check Simulation

Using Serial Communication

Najib Ghatte #1, Vinit Pereira #2, Madur Dattaprasad #3, Tushar Surwadkar #4
Fr. Conceicao Rodrigues College of Engineering
Fr. Agnel Ashram,
Bandstand, Bandra (W), Mumbai: 400 050, India
1
[email protected]
2
[email protected]
3
[email protected]
4
[email protected]

Abstract—CRC refers to cyclic redundancy check bits used for [Wells99]. A CRC can be thought of as a (non-secure) digest
error detection purpose. Normally the frame format consists of function for a data word that can be used to detect data
data bits combined with CRC bits which results in packet corruption. Mathematically, a CRC can be described as
transmission from source to destination. Teracopy is one of the treating a binary data word as a polynomial over GF (2) (i.e.,
important applications where CRC calculation is done. Due to
with each polynomial coefficient being zero or one) and
some reasons it may happen that data transmitted from the
source to destination gets corrupted and arrives with error at the performing polynomial division by a generator polynomial
receiving end. Now, the CRC bits play very important role for G(x). The generator polynomial will be called a CRC
finding out the error in the received packet. For n length of the polynomial for short. (CRC polynomials are also known as
data if n errors occur then all the errors can be detected. CRC feedback polynomials, in reference to the feedback taps of
calculation is based on the division method which is very simple hardware-based shift register implementations.) The
for detection of multiple errors. It even gives the position of bit remainder of that division operation provides an error
or bits which are toggled at the receiver with respect to the detection value that is sent as a Frame Check Sequence (FCS)
transmitter. Standard polynomials used for CRC calculation are within a network message or stored as a data integrity check.
applicable for 1 to n bits of data.
Whether implemented in hardware or software, the CRC
computation takes the form of a bitwise convolution of a data
Keywords— CRC polynomials, Division method word against a binary version of the CRC polynomial. Error
I. INTRODUCTION detection is performed by comparing an FCS computed on a
piece of retrieved or received data against the FCS value
A cyclic redundancy check (CRC) is an error-detecting originally computed and either sent or stored with the original
code commonly used in digital networks and storage devices data. An error is declared to have occurred if the stored FCS
to detect accidental changes to raw data. Blocks of data and computed FCS values are not equal. However, as with all
entering these systems get a short check value attached, based digital signature schemes, there is a small, but finite,
on the remainder of a polynomial division of their contents; on probability that a data corruption that inverts a sufficient
retrieval the calculation is repeated, and corrective action can number of bits in just the right pattern will occur and lead to
be taken against presumed data corruption if the check values an undetectable error. The minimum number of bit inversions
do not match. CRCs are so called because the check (data required to achieve such undetected errors (i.e., the HD value)
verification) value is a redundancy (it adds no information to is a central issue in the design of CRC polynomials. The
the message) and the algorithm is based on cyclic codes. essence of implementing a good CRC-based error detection
CRCs are popular because they are simple to implement in scheme is picking the right polynomial. The prime
binary hardware, easy to analyse mathematically, and factorization of the generator polynomial brings with it certain
particularly good at detecting common errors caused by noise potential characteristics, and in particular gives a trade-off
in transmission channels. Because the check value has a fixed between maximum numbers of possible detected errors vs.
length, the function that generates it is occasionally used as a data word length for which the polynomial is effective. Many
hash function. The CRC was invented by W. Wesley Peterson polynomials are good for short words but poor at long words,
in 1961; the 32-bit polynomial used in the CRC function of and the converse. There are relatively few polynomials that
Ethernet and many other standards is the work of several are excellent for medium-length data words while still being
researchers and was published during 1975. [1] good for relatively long data words. [2]
Cyclic redundancy codes (also known sometimes as cyclic
redundancy checks) have a long history of use for error II. DESIGN
detection in computing. [Peterson72] and [Lin83] are among The Cyclic Redundancy Check (CRC) is an efficient
the commonly cited standard reference works for CRCs. A technique for detecting errors during digital data transmissions
treatment more accessible to non-specialists can be found in between a source and a destination. The destination device
calculates the CRC of the received data. If the CRC calculated TABLE I
STANDARD CRC POLYNOMIALS
by the destination device does not match the one calculated by
the source device, then the received data contains an error. Name Polynomial Application
This technique is used in a wide variety of applications from CRC-8 x8 + x2 + x + 1 ATM header
Ethernet transmission to daily file transfers. It provides quick CRC-10 x10 + x9 + x5 + x4 + x2 +1 ATM AAL
and easy insurance of data integrity within digital CRC-16 x16 + x12+ x5 + 1 HDLC
communication systems The CRC is based on polynomial CRC-32 x32 + x26 + x23 + x22 + x16 LANs
manipulations which treat each received message as a binary + x12 + x11 + x10 + x8 + x7
number. The received message is then divided by a fixed + x5 + x4 + x2 + x + 1
value, also known as the generator polynomial, using modulo-
2 arithmetic. The characteristic of the CRC implementation is
III. IMPLEMENTATION
determined by the generator polynomial selection. The
generator polynomials are selected to maximize the error The design is simulated via Proteus ISIS v7.6 sp4 provided
detection capability without using too many resources. by Labcenter Electronics. The design is created using
Generator polynomials that have been incorporated into Schematic Capture and same is simulated.
standards such as CRC-8, CRC-16 and CRC-CCIT are A. Keyboard
commonly known and are well tested. This reference design
describes the use of Lattice programmable devices to US layout keyboard is used to feed the data into controller
implement the CRC generator and checker. The design allows onto the user input, The data input from the keyboard is
users to implement the CRC using different generator manipulated as per the code and results are transmitted via
polynomials. [3] Serial Communication using SCI protocol.
A way of viewing the CRC process is to express all B. Serial Communication
values as polynomials in a dummy variable X, with binary
Data is transmitted serially i.e. bit by bit using Serial
coefficients. The coefficients correspond to the bits in the
Communication Interface (SCI). The transmission is done by
binary number. Thus, for M = 110011, , 𝑀(𝑋) = 𝑥 5 + 𝑥 4 +
means of UART: 1 start bit, 8 bit data, 1 stop bit; thus forming
𝑥 + 1, and, for P = 11001, 𝑃(𝑋) = 𝑥 4 + 𝑥 3 + 1. Arithmetic
a frame, which is transmitted at the desired baud rate.
operations are modulo 2. The CRC process can now be
The data transmitted is displayed on the Virtual Terminal
described as
𝑋 𝑛 𝑀(𝑋) 𝑅(𝑋)
Screen provided on the simulation platform. Fig. 1 shows the
= 𝑄(𝑋) − (2.1) Virtual Terminal Screen used in Proteus to display the data
𝑃(𝑋) 𝑃(𝑋)
𝑛
𝑇(𝑋) = 𝑋 𝑀(𝑋) + 𝑅(𝑋) (2.2) being transmitted.
An error E(X) will only be undetectable if it is divisible by
P(X). It can be shown [PETE611 that all of the following
errors are not divisible by a suitably chosen P(X) and, hence,
are detectable:
• If G contains two or more terms, all single-bit errors are
detected.
• If G is not divisible by x (that is, if the last term is 1), and
e is the least positive integer such that G evenly divides
xe + 1then all double errors that are within a frame of Fig. 1 Virtual Terminal Screen in Proteus
e bits are detected. A particularly good polynomial in this The baud rate is so adjusted to match with the controller
respect is x15 + x14 + 1 for which e=32767 and virtual terminal transceiver. The controller is loaded with
• If x + 1 is a factor of G, all errors consisting of an odd the count and thus desired baud rate is obtained.
number of bits are detected.
• An r-bit CRC checksum detects all burst errors of C. Microcontroller AT89C55
length ≤ r (A burst error of length r is a string of r bits in The AT89C55WD is a low-power; high-performance
which the first and last are in error, intermediate r - 2 bits CMOS 8-bit microcontroller with 20K bytes of Flash
may or may not be in error.) programmable read only memory and 256 bytes of RAM. The
In addition, it can be shown that if all error patterns are device is manufactured using Atmel’s high-density non-
considered equally likely, then for a burst error of length r + 1, volatile memory technology and is compatible with the
𝑟−1
the probability that E(X) is divisible by P(X) is 1�2 , and
industry standard 80C51 and 80C52 instruction set and pinout.
𝑟 The on-chip Flash allows the program memory to be user
for a longer burst, the probability is 1�2 , where r is the programmed by a conventional non-volatile memory
length of the FCS[4]. programmer. By combining a versatile 8-bit CPU with Flash
Four versions of P(X) shown in Table I are widely used: on a monolithic chip, the Atmel AT89C55WD is a powerful
microcomputer which provides a highly flexible and cost V. ALGORITHM
effective solution to many embedded control applications. Cyclic redundancy check is a way of providing error
The microcontroller is programmed with Embedded C control coding in order to protect data by introducing some
language using Keil cross-compiler and Intel-hex file is redundancy in the data in a controlled fashion. It is a
generated and embed into the controller to simulate the results. commonly used and very effective way of detecting
Microcontroller is embedded with the generated hex file and transmission errors.
design is simulated to get optimum results.

IV. WORKING PRINCIPLE

In networking systems a significant role of the Data
Link layer is to convert the potentially unreliable physical link
between two machines into an apparently very reliable link. Fig. 2 Principle of error detection using the CRC algorithm
This is achieved by including redundant information in each
The CRC encoding procedure is described by equation 5.1
transmitted frame. Depending on the nature of the link and the
𝑉(𝑋) = 𝑆(𝑋) + 𝑋 𝑛−𝑘 𝑈(𝑋) (5.1)
data, one can include just enough redundancy to make it
Where V(x) is the n bit long data word transmitted and it
possible to detect errors and then arrange for the
consists of the original data and U(x) followed by a code word
retransmission of damaged frames. The cyclic redundancy
S(x) called the CRC-sum. S(x) represents the extra bits added
check or CRC is a widely used parity bit based error detection
to a message in order to provide redundancy so that errors
scheme in serial data transmission applications. This code is
during transmission can be detected. The length of S(x) is
based on polynomial arithmetic.
denoted by the constraint length. S(x) is computed according
The bits of data to be transmitted are the coefficients of
to equation 5.3.
the polynomial. As an example, the bit stream 1101011011
has 10-bits, representing a 10-term polynomial: 𝑋 𝑛−𝑘 𝑈(𝑋) = 𝑎(𝑋)𝑔(𝑋) + 𝑆(𝑋) (5.2)
𝑀(𝑋) = 𝑥 9 + 𝑥 8 + 𝑥 6 + 𝑥 4 + 𝑥 3 + 𝑥 1 + 1 (4.1) 𝑋 𝑛−𝑘 𝑈(𝑋)⁄𝑔(𝑋) = 𝑎(𝑋) + 𝑆(𝑋)⁄𝑔(𝑋) (5.3)
To compute the CRC of a message, another polynomial S(x) is in other word means the remainder resulting from a
called the generator polynomial G(x) is chosen. G(x) should division of the data stream and a generator polynomial g(x).
have a degree greater than zero and less than that of the Since all code words are divisible by g(x) the remainder of the
polynomial M(x). Another requirement for G(x) is a non-zero left hand side of equation has to be zero for a real code-word.
coefficient in the x0 term. This results in several possible The actual coding procedure is the same at both the receiving
options for the generator polynomial, and hence the need for and transmitting end of the line.
standardization. CRC-16 is one such standard that uses the
generating polynomial:
𝐺(𝑋) = 𝑥 16 + 𝑥 15 + 𝑥 2 + 1 (4.2)
CRC-16 detects all single and double errors, all errors with
an odd number of bits, all burst errors of length 16 or less, and
most errors for longer bursts. CRC-32 uses the generating
polynomial:
𝐺(𝑋) = 𝑥 32 + 𝑥 26 + 𝑥 23 + 𝑥 22 + 𝑥 16 + 𝑥 12 + 𝑥 11 + 𝑥 10 +
𝑥 8 + 𝑥 7 + 𝑥 5 + 𝑥 4 + +𝑥 2 + 𝑥 + 1 (4.3) Fig. 3 Parallel Logic Implementation
In general, an n-bit CRC is calculated by representing The CRC encoding/decoding principle is illustrated in
the data stream as a polynomial M(x), multiplying M(x) by xn Fig. 2 and the parallel logic implementation is shown in Fig. 3,
(where n is the degree of the polynomial G(x)), and dividing the receiver performs a CRC-check on the incoming message
the result by a generator polynomial G(x). The resulting and if the result (S(x)) is zero, then the transmission is error
remainder is appended to the polynomial M(x) and transmitted. free. One more practical way of solving this is to compute the
The complete transmitted polynomial is then divided by the CRC only for the first part of the message U(x), and then
same generator polynomial at the receiver end. If the result of perform a bitwise 2’s-complement addition with the computed
this division has no remainder, there are no transmission checksum S(x) on the transmission side. If the result is non-
errors. Mathematically, this can be represented as: zero the receiver will order a retransmission from the sender. [5]
𝑥𝑛
CRC = Remainder of �𝑀(𝑋) � (4.4)
𝐺(𝑋) VI. RESULTS
CRC computation involves manipulating M(x) and G(x)
using modulo 2 arithmetic. Modulo arithmetic yields the same The proposed design is simulated on the simulation
result for addition and subtraction. Therefore it is necessary platform. The virtual terminal screen displayed the message
only to consider three operations involving polynomials bits being transmitted and CRC-generator polynomial used to
namely, addition, multiplication, and division. [6] compute the Source CRC. The data appended with CRC is
transmitted over the channel and tested for its veraciousness.
 Fig. 4 shows the Virtual Terminal Screenshot used for
computation in CRC.
VII. CONCLUSIONS
Cyclic Redundancy Check used to detect errors in the
transmission of the data over the channel. The CRC generated
by means of the CRC generator suffixed with the message bits
is transmitted over the channel. The received code word is
again validated by means of the same CRC generator
polynomial. If remainder is zero, then is validity is proved else
the erroneous frame is retransmitted.

REFERENCES
[1] (2012) Cyclic Redundancy Check [Online]. Available:
http://en.wikipedia.org/wiki/Cyclic_redundancy_check
[2] Philip Koopman, “32-Bit Cyclic Redundancy Codes for Internet
Applications,” ECE Department & ICES Carnegie Mellon University
Pittsburgh, PA, USA, Apr. 2002
[3] (2012) Cyclic Redundancy Check [Online]. Available:
http://www.latticesemi.com/products/intellectualproperty/referencedesi
gns/cyclicredundancycheck.cfm
Fig. 4 Simulated Results Screenshot [4] William Stallings, Data and Computer Communications,
5th ed., Pearson Prentice Hall, 2009
[5] S.R. Ruckmani1, P. Anbalagan2, High Speed cyclic Redundancy
Check for USB, DSP Journal, Volume 6, Issue 1, September, 2006
[6] IEEE 802.3 Cyclic Redundancy Check, Chris Borelli. Avalable:
http://www.xilinx.com/support/documentation/application.../xapp209.p
df