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. [email protected] 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].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. ) 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.
Why Work with Us
Top Quality and Well-Researched Papers
We always make sure that writers follow all your instructions precisely. You can choose your academic level: high school, college/university or professional, and we will assign a writer who has a respective degree.
Professional and Experienced Academic Writers
We have a team of professional writers with experience in academic and business writing. Many are native speakers and able to perform any task for which you need help.
Free Unlimited Revisions
If you think we missed something, send your order for a free revision. You have 10 days to submit the order for review after you have received the final document. You can do this yourself after logging into your personal account or by contacting our support.
Prompt Delivery and 100% Money-Back-Guarantee
All papers are always delivered on time. In case we need more time to master your paper, we may contact you regarding the deadline extension. In case you cannot provide us with more time, a 100% refund is guaranteed.
Original & Confidential
We use several writing tools checks to ensure that all documents you receive are free from plagiarism. Our editors carefully review all quotations in the text. We also promise maximum confidentiality in all of our services.
24/7 Customer Support
Our support agents are available 24 hours a day 7 days a week and committed to providing you with the best customer experience. Get in touch whenever you need any assistance.
Try it now!
How it works?
Follow these simple steps to get your paper done
Place your order
Fill in the order form and provide all details of your assignment.
Proceed with the payment
Choose the payment system that suits you most.
Receive the final file
Once your paper is ready, we will email it to you.
No need to work on your paper at night. Sleep tight, we will cover your back. We offer all kinds of writing services.
No matter what kind of academic paper you need and how urgent you need it, you are welcome to choose your academic level and the type of your paper at an affordable price. We take care of all your paper needs and give a 24/7 customer care support system.
Admission Essays & Business Writing Help
An admission essay is an essay or other written statement by a candidate, often a potential student enrolling in a college, university, or graduate school. You can be rest assurred that through our service we will write the best admission essay for you.
Our academic writers and editors make the necessary changes to your paper so that it is polished. We also format your document by correctly quoting the sources and creating reference lists in the formats APA, Harvard, MLA, Chicago / Turabian.
If you think your paper could be improved, you can request a review. In this case, your paper will be checked by the writer or assigned to an editor. You can use this option as many times as you see fit. This is free because we want you to be completely satisfied with the service offered.