NDLI: Fast parallel CRC algorithm and implementation on a configurable processor

Content Provider	IEEE Xplore Digital Library
Author	Ji, H.M. Killian, E.
Copyright Year	2002
Description	Author affiliation: Tensilica Inc., Santa Clara, CA, USA (Ji, H.M.; Killian, E.)
Abstract	We present a fast cyclic redundancy check (CRC) algorithm that performs CRC computation for any length of message in parallel. For a given message with any length, we first divide the message into blocks, each of which has a fixed size equal to the degree of the generator polynomial. Then we perform CRC computation among the blocks in parallel using Galois field multiplication and accumulation (GFMAC). Theoretically, our fast parallel CRC algorithm can achieve unlimited speedup over the bit-serial algorithm or byte-wise table lookup algorithm at the expense of adding enough GFMAC units. Our algorithm can perform CRC computation for any lengthy message with two to three clock cycles. In practice, we choose to use a configurable processor where a customized instruction is added to perform multiple pairs of GF multiplication and accumulation. For example, a 4-GFMAC implementation can compute a 32-bit CRC in two to three cycles for a 16-byte message. This level of performance is hundreds of times faster than a bit-serial CRC algorithm or tens of times faster than a byte-wise parallel CRC algorithm. The generator polynomial can be chosen to be software programmed or hard-coded. Our algorithm adds only a small number of logical gates to the processor core.
Starting Page	1813
Ending Page	1817
File Size	420075
Page Count	5
File Format	PDF
ISBN	0780374002
DOI	10.1109/ICC.2002.997161
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-04-28
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Cyclic redundancy check Table lookup Polynomials Hardware Concurrent computing Galois fields Clocks FDDI Asynchronous transfer mode Parallel processing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Table-Based Algorithm for Pipelined CRC Calculation

A Pipelined CRC Calculation Using Lookup Tables

Interleaved cyclic redundancy check (CRC) code

High-speed parallel CRC circuits

Fast CRC calculation

Implementation of fast CRC calculation

High-Speed Parallel CRC Implementation Based on Unfolding, Pipelining, and Retiming

Selective parallel CRC computation schemes for RapidIO

FPGA-based multi-channel CRC generator implementation

Fast parallel CRC algorithm and implementation on a configurable processor

Similar Documents

A Table-Based Algorithm for Pipelined CRC Calculation

A Pipelined CRC Calculation Using Lookup Tables

Interleaved cyclic redundancy check (CRC) code

High-speed parallel CRC circuits

Fast CRC calculation

Implementation of fast CRC calculation

High-Speed Parallel CRC Implementation Based on Unfolding, Pipelining, and Retiming

Selective parallel CRC computation schemes for RapidIO

FPGA-based multi-channel CRC generator implementation

Fast parallel CRC algorithm and implementation on a configurable processor