# Parallel Computation of CRC-Code on an FPGA Platform for High Data Throughput
## 2 CRC Background  
A CRC-32 checksum algorithm is often used in data transmission and data storage systems to detect any alteration or corruption of the data [4]. Many digital sensor devices or wireless networks employ this technique in the form of a packet error check [5; 6; 7; 8; 9; 10; 11]. The packet error checking (PEC) is augmented with original data to check if there have been any modifications in the data packet. Both hardware and software CRC generation in serial format are currently well understood. However, with the significant increase of the amount of data being produced by sensor systems, serial CRC generation methods could create a throughput bottleneck that prevent such systems from achieving high performance results [12]. The first version of CRC based computational algorithm was proposed by [PERSON] and [PERSON] [9]. This algorithm only processes one-bit at a time by utilizing a simple shift register. For an \(n\)-bit message, the algorithm's time complexity is O(\(n\)), which significantly affects the throughput of a system. Since then, several techniques have been proposed with the focus on increasing the efficiency of the algorithm that are both software and hardware friendly for implementation. To obtain high throughput, [PERSON] et al. [13] proposed to use a table-based CRC algorithm which can process one byte at a time. This resulted in an 8x speedup than the original serial method by reducing the number of iterative steps it needed to compute the CRC code. The algorithm can be generalized to process multiple bytes at a time, but it always comes down to one thing: trade-off between memory and time complexity. For practical purposes, the table must be small enough to fit into a cache memory for quick access; otherwise, the algorithm will be slowed down significantly due to memory assessment penalty. For example, [PERSON]'s table-based algorithm to process 32 bits at a time will require a \(2^{32}=4\)G entries that is multiple times larger than the cache memory of the commercial system. To deal with this problem, [PERSON] and [PERSON] [14] proposed methods called Slicing-by-4 and Slicing-by-8 that use multiple small lookup tables to avoid a memory explosion problem. Moreover, it can be done in parallel via pipelined or concurrency processing. It is interesting to note that a CRC shift register can also be viewed as a linear system. From a linear system perspective, state-transformation can be computed using matrix multiplication. For example, a CRC code of a message \(M\) can be transformed to CRC code of message \(M\) appended by multiple zeros through the multiplication with a pre-computed matrix. [PERSON] et al. [15] proposed a parallelization method by taking advantage of this property of the CRC computation circuit. Most of the previous research [4; 5; 6; 7; 8; 9; 10] can be classified into two main categories: (1) lookup table (LUT) based and (2) matrix transformation (MT) based methods. Recently, parallel platforms such as FPGAs or multi-core CPUs have shown promising results in on-board processing capabilities. The traditional serial CRC generation method does not fully take advantage of the resources from such systems. Several researchers have implemented parallel CRC generation methods as both software algorithms and hardware circuitry [16; 17]. In this paper, we propose a hybrid algorithm called hybrid LUT-MT that takes benefits of both methods to speed-up the process while maintaining the memory requirements to a minimum. [PERSON] et al. [18] have a similar concept, but they focused mainly on a software implementation on a multi-core CPU system. In addition, their algorithm will not achieve the theoretical speed-up factor due to thread synchronization management overhead. In this paper, we will describe in detail how to develop the building blocks of the algorithm for an FPGA platform. The system is flexible, scalable, and adaptable which makes it easy to be integrated into a high-performance FPGA-based sensor system.