Home > Published Issues > 2013 > Volume 8, No. 2, February 2013 >

High Performance Table-Based Algorithm for Pipelined CRC Calculation

Yan Sun and Min Sik Kim
School of Electrical Engineering and Computer Science, Washington State University

Abstract—In this paper, we present a fast cyclic redundancy check (CRC) algorithm that performs CRC computation for an arbitrary length of message in parallel. For a given message with any length, the algorithm first chunks the message into blocks, each of which has a fixed size equal to the degree of the generator polynomial. Then it computes CRC for the chunked blocks in parallel using lookup tables, and the results are combined together with XOR operations. In the traditional implementation, it is the feedback that makes pipelining problematic. In the proposed algorithm, we solve this problem by taking advantage of CRC’s properties and pipelining the feedback loop. The short pipeline latency of our algorithm enables a faster clock frequency than previous approaches, and it also allows easy scaling of the parallelism while only slightly affecting timing. We build a Verilog implementation our pipelined CRC. The simulation results show that our approach is faster and more spaceefficient than previous CRC implementations; with 256 bits input each clock cycle, our approach achieves about 36% throughput improvement with about 12% area reduction.

Index Terms—Keywords: CRC, lookup table, pipelining

Cite: Yan Sun, and Min Sik Kim, "High Performance Table-Based Algorithm for Pipelined CRC Calculation," Journal of Communications, vol. 8, no. 2, pp. 128-135, 2013. Doi: 10.12720/jcm.8.2.128-135