Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.3, pp.445-461 (May 2001)

A Systematic Approach for Parallel CRC Computations


Ming-Der Shieh, Ming-Hwa Sheu, Chung-Ho Chen* and Hsin-Fu Lo

Department of Electronic Engineering
National Yunlin University of Science and Technology
Yunlin, Tiawan 640, R.O.C.
E-mail: shiehm@cad.el.yunteh.edu.tw
*Department of Electrical Engineering
National Cheng-Kung University
Tainan, Taiwan 701, R.O.C.

Cyclic redundancy codes (CRCs) form a powerful class of codes suited especially for the detection of burst errors in data storage and communication applications. In the traditional hardware implementation, a simple shift-register-based circuit performs the computation by handling the data one bit at a time. Parallel implementation can perform the necessary logic operations much faster than the serial implementation, therefore, it is very suitable to be applied in todays high-speed systems employing CRC checking. In this paper, we describe the ways toward accomplishing two types of circuit design for parallel CRC computations. Our approach is to systematically decompose the original input message into a set of subsequences based on the theory of Galois field. Parallel CRC computations can then be achieved by inputting those subsequences at the same time and employing the lookahead technique for those subsequences to speedup computation. The resulting hardware implementations are very flexible with the characteristics of modular design and scalable structure to fulfill different levels of parallelism in a single circuit for parallel CRC computation.

Keywords: parallel cyclic redundancy code (CRC) computation, Galois field, linear feedback shift register (LFSR), VLSI design, error control code

Full Text () Retrieve PDF document (200105_06.pdf)

Received July 26, 1999; revised October 25, 1999; accepted January 4, 2000.
Communicated by Yong-Long Lin