Browse Prior Art Database

High-Speed Parallel Cyclic Redundancy Check Generator

IP.com Disclosure Number: IPCOM000101988D
Original Publication Date: 1990-Oct-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 6 page(s) / 174K

Publishing Venue

IBM

Related People

McClannahan, GP: AUTHOR [+3]

Abstract

A parallel method for computing CRCs (Cyclic Redundancy Checks) is disclosed. This method is best used for systems which transmit data in parallel or for systems which may require software to process data after a CRC has been calculated.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 41% of the total text.

High-Speed Parallel Cyclic Redundancy Check Generator

       A parallel method for computing CRCs (Cyclic Redundancy
Checks) is disclosed.  This method is best used for systems which
transmit data in parallel or for systems which may require software
to process data after a CRC has been calculated.

      The derivation of a parallel CRC implementation from a serial
CRC implementation is as follows:  The serial generator uses a shift
register initialized to 'FFFF' hex, and, as a bit is shifted in, the
content of the register is altered by the feedback equation.
Generally, the input frame size for the serial generator can be
variable.  For the parallel implementation, a frame size that is a
multiple of eight bits is assumed.  In the parallel implementation,
the CRC register is composed of 16 Polarity Hold-Shift Register
Latches that are set to 1 on a reset or after a read of the
register. The data for which a frame check sequence (FCS) is desired
is moved (via DMA or an efficient processor string move) to an
address range which indicates a FCS is to be calculated.  The data
bus enable signals gate the data bus so that if only half the data
bus (8 bits) is valid, the correct half of the bus is presented to
the 8-bit CRC logic. The bus enable signals also gate the output of
the logic so that the proper result is gated to the register.  After
all data has been run through the register, it may then be read by
microcode and appended to the data stream.  When the read is
complete, the register is reset to 'FFFF' hex.  The overall structure
is shown in Fig. 1.

      The Parallel FCS generator has two important advantages:  its
speed and the control of data it allows microcode.  Its main drawback
is that it requires approximately 2 and 1/2 times the amount of logic
that the serial implementation needs.  When processing data in
parallel, all of the CRC bits are updated in a single clock cycle for
each data word, therefore, the speed-up is equal to the word length.
In a serial environment, however, no speed-up is realized because,
although the CRC is calculated one bit at a time, each bit is
calculated at the time it is required for serial transmission.  The
more important advantage comes into play when the data must be
manipulated after the CRC is generated, such as for the Synchronous
Data Link Control protocol used over a character-oriented network.

      Where SDLC is implemented on a bit-orientated protocol, the
hardware can calculate the FCS and do bit insertion or deletion while
the data is being transmitted or received. If the implementation is
on a character-orientated protocol, or operations must be done on the
data stream before or after the CRC is calculated due to transparency
requirements, the serial method for calculating the FCS is not
feasible.  For the microcode to use the CRC generator, it takes the
frame it wants to send, writes it to a 4K buffer in memory, and
extracts the FCS out of the CRC register...