A Fast Crc Implementation on Fpga Using a Pipelined Architecture for the Polynomial Division

A Fast CRC Implementation on FPGA Using a Pipelined Architecture for the Polynomial Division Fabrice MONTEIRO, Abbas DANDACHE, Amine M’SIR,Bernard LEPLEY LICM, University of Metz, SUPELEC, Rue Edouard Belin, 57078 Metz Cedex phone: +33(0)3875473 11, fax: +33(0)387547301, email: fabrice. monteiro@ieee. org ABSTRACT The CRC error detection is a very common function on telecommunication applications. The evolution towards increasing data rates requires more and more sofisticated implementations. In this paper, we present a method to implement the CRC function based on a pipeline structure for the polynomial division.It improves very effectively the speed performance, allowing data rates from 1 Gbits/s to 4 Gbits/s on FPGA implementions, according to the parallelisation level (8 to 32 bits).

1 INTRODUCTION The CRC (Cyclic Redundancy Checking) codes are used in a lot of telecommunication applications. They are used in the internal layers of protocols such as Ethernet, X25, FDDI and ATM (AAL5). However, on modem networks, the need for increasing data rates (over 1 Gbit/s) is setting the constraints on performance very high. Indeed, the speed improvement (higher clock rates) due to the technological evolution is unable to fit the demand.Consequently, new architectures must be devised. Targetting the applications to an FPGA device is an issue for this paper, as it allows low-cost designs. The simple and evident serial implementation is a classical hardware implementation of the CRC algorithm.

Unfortunatly, on an FPGA implementation with maximal clock frequency of 250 MHz, maximal data rate is limited to 250 Mbits/s is the best case. Higher data rates can only be obtained through parallelisation. Some parallel architectures have been proposed in the past to address the need for high data throughput [ 1][2].The main problem is usually to limit the rapidly increasing area overhead while improving the speed performance. In this paper, we present a parallel approach for the polynomial division based on a pipeline structure. The parallelisation can be led to any level and is only lim- ited by the area constraint set on the design. The data throughput is almost directly linked to the parallelisation level, as the maximal clock rate is not very sensitive to it.

2 PRINCIPLE The polynomial division is the fundamental operation of the CRC applications.The serial implementation of the division is shown in figure 1 for the case where the polynomial divisor is G ( X ) = Go + G1. X1 + Gz. X2 + G3. X3 = 1 + X + X 3 . As indicated previously, the data throughput of this serial implementation is quite low. Very high data rates can only be achieved with high clock frequencies, which in turn can only be obtained using rather expensive technological solutions.

Parallelisation of data processing is the main solution to improve the speed performance of a circuit (or system) if the clock rate must remain low.Pipelining may be used as an effective parallelisation method when a repeatitive process must be applied on large volumes of ‘data. Previous works have addressed the parallelisation problem in large demanding computational applications, particularly in arithmetic (eg. [3][4]) and error control coding circuits (eg. [11[21[61). In the serial architecture (figure I), a new data bit is inject on each clock cycle. The previous cumulated remainder is simultaneously multiplied by X and divided by G(z) (where G(z) is the polynomial divisor).

On P Figure I : Serial polynomial division for G ( X ) = 1 -tX + X 3 -7803-7057-0/01/$10. 00 02001 IEEE. 1231 successive clock cycle , P bits are injected and P successive multiplication and divisions are performed. The next formula (related to the example of figure 1) describes the operation performed on one clock cycle. 0 T = [ o o 1 !]=[n Gz 0 1 o 1 1 Go GI 0 i ] 0 3 RESULTS This architecture have been implemented on FPGA devices of the FLEXlOKE ALTERA family. These devices have their maximal clock frequency limited to 250 MHz. The architecture was tested on the generating polynomials of table 1.

The results in table 2 were obtained on FPGA devices of the FLEXlOKE ALTERA family.The architecture tested in these examples implements a fully operational CRC checker. The synchronisation signals to write and read data respectively on input and ouput are fully implemented. The synthesis was done using Synplify 5. 3 and MaxPlus11 10. 0. The architecture was tested for 3 different levels of paralelism on 6 differents standard divisor polynomials.

It can be noticed that G17(z) is used on ethernet, FDDI and AALS-ATM, while G14(z) is the standard polynomial for the X2. 5 protocol. The clock rates must be compared to the highest frequency (250 MHz) that can be performed on FLEXlOKE devices.The “IC” indication means “logical cells” and is an indication of the area consumption. The results must be compared to those obtained in [SI. A data rate of 160 Mbits/s was obtained on an ALTERA FLEXIOK device (max. clock rate of 125 MHz), on a 32-bit parallel CRC runtime-configurable implementation of the decoder, based on the use of parallel combi- A pipeline structure can be devised by the implementation of P successive multiplications and divisions.

However, to keep the clock rate high, the P operations should not be done in a single combinatorial block. Thus, the stages of the P-multiplingldivising block must be separated by registers.This is the basic idea of the pipeline structure. Each of the P parallel bits of an input must be injected in their respective pipeline stage. consequently, they must be injected on different clock cycles. This may be done if the bits are delayed in a shift-register structure and (cf. the shift register path between [ d i n o ,.

.. , [douto, … ,doutp-l] in the figure 2, with P = 8 in this example and G ( X ) = 1 + X + X 3 . The operation performed when passing from the stage k + l to the stage k of the pipeline (k>O) is described in the next formula, where G ( X ) = 1 + X + X 3 as it is in figure 2.

ith Ri,J= 0 wheni + j > p – 1. The P bits of an input are processed in P clock cycles. At each clock cycle, the result of the processing of P bits is available at the output of the pipeline structure. This result (the remainder of the P bits divided by G(z) must be cumulated in the [ROO, ROZ] ROI, register using a recurrent approach, similar to the scheme of the serial architecture of figure 1. The cumulated remainder at time t must be multiplied by X p and then divided by G(x). Then, the new partial remainder coming out of the pipeline structure can be cumulated. This process is describet in the next formula.

Ro,o,ROJ,R0,Sltfl = [Ro,o,RO,l,R0,zIt * M +[Ri,o, Ri,i, Rl,z]t * T f [Do,P-l, 0,Olt natorial block for the polynomial division as presented in [ 11. The gain obtained on the 32-bit parallel architecture is within 16 and 30 times, that is, 8 to 1. 5 times using the same technology (cf. table 2). For any combination of the design parametres, the latency is alway equal to P clock cycles where P denotes the parallelisation level. It can be noticed that for given a maximal polynomial divisor degree, the area consumption (number of logic cells ) is almost proportional to the parallelisation level of the architecture.Furthermore, the results show that a large increase of the parallelisation level can be done with a reasonable decrease of maximal clock frequency.

The critical path is due to the M matrix. The complexity of this matrix depends on the choosen polynomial (number and position of the non-zero terms in the polynomial). It also depends on the parallelisation 1232 level, but not linearly. Actually, a higher parallelisation level can lead to a less complex matrix.

Calculate the price
Make an order in advance and get the best price
Pages (550 words)
*Price with a welcome 15% discount applied.
Pro tip: If you want to save more money and pay the lowest price, you need to set a more extended deadline.
We know how difficult it is to be a student these days. That's why our prices are one of the most affordable on the market, and there are no hidden fees.

Instead, we offer bonuses, discounts, and free services to make your experience outstanding.
How it works
Receive a 100% original paper that will pass Turnitin from a top essay writing service
step 1
Upload your instructions
Fill out the order form and provide paper details. You can even attach screenshots or add additional instructions later. If something is not clear or missing, the writer will contact you for clarification.
Pro service tips
How to get the most out of your experience with MyHomeworkGeeks
One writer throughout the entire course
If you like the writer, you can hire them again. Just copy & paste their ID on the order form ("Preferred Writer's ID" field). This way, your vocabulary will be uniform, and the writer will be aware of your needs.
The same paper from different writers
You can order essay or any other work from two different writers to choose the best one or give another version to a friend. This can be done through the add-on "Same paper from another writer."
Copy of sources used by the writer
Our college essay writers work with ScienceDirect and other databases. They can send you articles or materials used in PDF or through screenshots. Just tick the "Copy of sources" field on the order form.
See why 20k+ students have chosen us as their sole writing assistance provider
Check out the latest reviews and opinions submitted by real customers worldwide and make an informed decision.
Business and administrative studies
Excellent job
Customer 452773, March 17th, 2023
Criminal Justice
This has been the greatest help while I am recovering from an illness. Thank your team so much.
Customer 452671, May 2nd, 2021
Business and administrative studies
Thank you
Customer 452773, March 19th, 2023
English 101
great summery in terms of the time given. it lacks a bit of clarity but otherwise perfect.
Customer 452747, June 9th, 2021
Business Studies
Thank you very much for a good job done and a quick turn around time.
Customer 452615, March 31st, 2021
Business and administrative studies
Thank you for your hard work and help
Customer 452773, February 21st, 2023
Business and administrative studies
Customer 452773, March 3rd, 2023
Thank you for your hard work and help.
Customer 452773, February 13th, 2023
Great job
Customer 452773, February 13th, 2023
Business and administrative studies
Customer 452773, February 23rd, 2023
Business and administrative studies
excellent work
Customer 452773, March 9th, 2023
thank you so much
Customer 452749, June 10th, 2021
Customer reviews in total
Current satisfaction rate
3 pages
Average paper length
Customers referred by a friend
15% OFF your first order
Use a coupon FIRST15 and enjoy expert help with any task at the most affordable price.
Claim my 15% OFF Order in Chat

Sometimes it is hard to do all the work on your own

Let us help you get a good grade on your paper. Get professional help and free up your time for more important courses. Let us handle your;

  • Dissertations and Thesis
  • Essays
  • All Assignments

  • Research papers
  • Terms Papers
  • Online Classes