Automated Crc Engine Using Verilog Computer Science Essay

Published:

The CRC or cyclic redundancy check is a widely used technique for error checking in many protocols used in data transmission. The aim of this project is to design the CRC RTL generator or a tool that calculates the CRC equations for the given CRC polynomials and generates the Verilog RTL code .This block deals with the calculation of equations for standard polynomials like CRC-4, CRC-8, CRC-16, CRC-32 and CRC-48, CRC-64 and also user defined proprietary polynomial. To use PERL as the platform it also aims at having a simpler user interface. To generate the RTLs for any data width and for any standard polynomial or user defined polynomial, this design aims to be complete generic. The RTLs generated by this tool are verified by System Verilog constrained random testing to make it more robust and reliable.

Introduction

A CRC (Cyclic Redundancy Check) [1] is a popular error detecting code computed through binary polynomial division. To generate a CRC, the sender treats binary data as a binary polynomial and performs the modulo-2 division of the polynomial by a standard generator (e.g., CRC-32[2]). The remainder of this division becomes the CRC of the data, and it is attached to the original data and transmitted to the receiver. Receiving the data and CRC, the receiver also performs the modulo- 2 division with the received data and the same generator polynomial. Errors are detected by comparing the computed CRC with the received one. The CRC algorithm only adds a small number of bits (32 bits in the case of CRC-32) to the message regardless of the length of the original data, and shows good performance in detecting a single error as well as an error burst. Because the CRC algorithm is good at detecting errors and is simple to implement in hardware, CRCs are widely used today for detecting corruption in digital data which may have occurred during production, transmission, or storage. And CRCs have recently found a new application in universal mobile telecommunications system standard for message length detection of variable-length message communications [3].

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Traditionally, the LFSR (Linear Feedback Shift Register) circuit is implemented in VLSI (Very-Large-Scale Integration) to perform CRC calculation which can only process one bit per cycle [4]. In this project the method used for the generation of CRC polynomials is based on the LFSR CRC implementation, where the CRC is calculated by passing each data bit every cycle, feeding the most significant bit first. Depending upon the data of the MSB register in the LFSR, shifting and XOR operations occur. This serial LFSR implementation is converted into a one shot or single cycle operation that is realized into a combinational circuit. Based on this method the CRC polynomials are generated

Cyclic Redundancy Check A CRC is an error-detecting code. Its computation resembles a polynomial long division operation in which the quotient is discarded and the remainder becomes the result, with the important distinction that the polynomial coefficients are calculated according to the carry-less arithmetic of a finite field. The length of the remainder is always less than the length of the divisor (called the generator polynomial), which therefore determines how long the result can be. The definition of a particular CRC specifies the divisor to be used, among other things.

The CRC is based on polynomial arithmetic, in particular, on computing the remainder of dividing one polynomial in GF (2) (Galois field with two elements) by another. It is a little like treating the message as a very large binary number, and computing the remainder on dividing it by a fairly large prime such as 2^32-5.Intuitively, one would expect this to give a reliable checksum. A polynomial in GF (2) is a polynomial in a single variable x whose coefficients are 0 or 1. Addition and subtraction are done modulo 2 - that is, they are same as the exclusive or operator. For example, the sum of the polynomials:

x3 + x + 1 and

x4 + x3 + x2 + x

is x4 + x2 + 1, as is their difference. These polynomials are not usually written with minus signs, but they could be, because a coefficient of -1 is equivalent to a coefficient of 1.Multiplication of such polynomials is straightforward. The product of one coefficient by another is the same as their combination by the logical and operator, and the partial products are summed using

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

exclusive or. Multiplication is not needed to compute the CRC checksum. Division of polynomials over GF (2) can be done in much the same way as long division of polynomials over the integers. Below is an example [5].

The reader might like to verify that the quotient of x4 + x3 + 1 multiplied by the divisor of x3 + x + 1, plus the remainder of x2 + 1, equals the dividend.

The CRC method treats the message as a polynomial in GF(2). For example, the message 11001001, where the order of transmission is from left to right (110…) is treated as a representation of the polynomial x7 + x6 + x3 + 1.

Table 3: Generator polynomial of some CRC codes [5]

To develop a hardware circuit for computing the CRC checksum, we reduce the polynomial division process to its essentials.

Figure 3: CRC circuit for G=x3 + x + 1

The process employs a shift register, which we denote by CRC. This is of length r (the degree of G) bits, not as you might expect. When the subtractions (exclusive or's) are done, it is not necessary to represent the high-order bit, because the high-order bits of G and the quantity it is being subtracted from are both 1. The division process might be described informally as follows[5]:

IMPLEMENTATION OF CRC RTL GENERATOR

CRC Generator is a command line application that generates verilog code for CRC of any data width starts from 1 bit and no inherent upper limit and any standard polynomial or user defined polynomial. The code is written in Perl and is cross platform compatible. This tool provides CRC RTL generator which can be used at transmitter for CRC checksum generation and the receiver end for verification. The generated CRC module is synthesizable verilog RTL. The method used for the generation of CRC polynomials is based on the LFSR CRC implementation, where the CRC is calculated by passing each data bit every cycle, feeding the most significant bit first. Depending upon the data of the MSB register in the LFSR, shifting and XOR operations occur. This serial LFSR implementation is converted into a one shot or single cycle operation that is realized into a combinational circuit. Based on this method the CRC polynomials are generated. Once all the RTL's of different polynomials are generated then the user can use these RTL's to calculate the CRC of entire packet.

Figure 4: Block Diagram of CRC RTL Generator

CRC Parameters

Data width: Width of the data ranges from 1 bit and no inherent upper limit.

Poly: Standard or any user defined Polynomial.

Equations: The remainder equations, these are the functions of data input and initial state remainders.

Data in: Input data to the verilog code.

Crc_ini: Input initial remainder to the verilog code.

RTL Engine: RTL Engine that generates the CRC bits.

Inputs

Polynomial: Which is one among the above mentioned standard polynomials or a user defined proprietary polynomial.

Data Width: Starting from 1 bit and no inherent upper limit.

Outputs

Verilog RTL code which in turn has its inputs as partial remainder, data (with the same width mentioned in the computational block) and output as final remainder.

RTL Engine

The RTL Engine takes Data stream, Initial Remainder as input and generates the RTL code as output using the equations from the Program block directly.

Program Block

The program block is the main block of the design. It calculates the polynomial equations that help in building the XOR tree.

Platforms used:

PERL (Practical Extraction and Report Language): The major internal data structures in the Perl interpreter that represent Perl language elements. Our extractor interrogates the Perl internals just before the execution phase of the Perl script. At that moment the internal data structures are ready to be used for fact extraction. Perl is a compiling interpreter. Instead of interpreting line-by-line the script file, it reads the entire script file, converts it to an internal representation, and then executes the instructions [18].

PERL (Practical Extraction And Report Language) is used as platform for generating the RTL codes because of the constructs available .Perl had useful data structures like Hashes, Arrays, Array of Hashes, Hash of Arrays , which are very much useful in generating the polynomial equations.

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

The output of the Perl program is a Verilog RTL code. Verilog is the mostly used standard HDL in industry .The verification of the Verilog RTL's generated is done in System Verilog because of its Constrained Random Testing feature which helps to verify thoroughly.

RESULTS:

Figure 4: Simulation results for CRC4 of data width is 2

Figure 4: Simulation results for CRC5 of data width is 8

Figure 4: Simulation results for CRC8 of data width is 16

Conclusion

In this report the objectives that is to design a tool that generates a verilog RTL, that calculated the checksum for the given data polynomial and CRC polynomial on Perl and generating RTL for any data width and any polynomial.

To calculate the CRC equations for the given CRC polynomials designed a tool that generates the verilog code for any standard polynomials like CRC8, CRC16, CRC24, CRC32 and also any user defined polynomial and data width. The RTLs generated by this tool are verified by system verilog constrained random verification to make it more robust and reliable. Hence the CRC applications are successfully Designed and verified.