This idea presents PLD code that can be used to generate arbitrary polynomial cyclic-redundancy-check (CRC) functions.
Communication systems often use CRCs to detect transmission errors. CRC functions are typically implemented as shift registers with a series of taps into which the last bit in the shift register is XOR'd.
Written in Altera's high-level design language (AHDL), the PLD code can be directly compiled into any of Altera's programmable logic devices (to download the listing, click here. Both CRC and residue-matching outputs are implemented.
The module automatically generates the required hardware from six compile-time parameters, including WIDTH, POLYNOMIAL, SEED, INVERT, RES-IDUE, and MATCH_PIPELINE. These parameters are used to define the CRC function as follows:
WIDTH sets the CRC length.
POLYNOMIAL sets the taps at which XOR gates are added.
SEED sets the value loaded into the shift register at the start.
INVERT determines whether the CRC output of the chain is inverted.
RESIDUE sets the value to which the result is compared at the end of the calculation.
MATCH_PIPELINE sets the number of clocks after which the residue-match output becomes valid.
As shown in the figure, a CRC-CCITT function of X16 + X12 + X5 + 1 can be generated by setting:
WIDTH = 16 POLYNOMIAL = H"1021" SEED = H"FFFF" INVERT = "YES" RESIDUE = "1D0F" MATCH_PIPELINE = 1
When the polynomial is being set, its most significant bit is omitted because no XOR gate is implemented at the end of the shift chain. Polynomials for CRC-16, CRC-32, and CRC-CCITT functions are included in the source code. The CRC-CCITT polynomial is the only one that has been tested in actual hardware. All of the others have been included for reference only.
Although the code is written specifically for Altera's devices, the program structure and flow are readily translatable into VHDL or Verilog. When implemented as part of a low-end EPF10K10-3 device, a CRC-CCITT function with EQZERO_PIPELINE = 1 takes 23 LCs and runs at 125 MHz.
While the math behind CRCs is fairly straightforward, bridging the gap between the math and hardware requires an understanding of modulo-two arithmetic, polynomials, and logic. A good detailed reference on the subject can be found in Data and Computer Communications, William Stallings, Prentice Hall, N.J., 1997.