Variable width parallel cyclical redundancy check

Details Variable width parallel cyclical redundancy check Variable width parallel cyclical redundancy check

2001-04-03

2004-05-04

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06732318

ABSTRACT:

TECHNICAL FIELD
The present invention relates to cyclical redundancy checking and, in particular, to an apparatus and method for producing a variable width parallel cyclical redundancy check for use where link width may or may not correspond to CRC calculation width.
BACKGROUND ART
A cyclic redundancy check (“CRC”) is a method of detecting changes and error in blocks of data that have been transferred or stored. Generally, a CRC is a mathematical algorithm that acts on a block of data. The CRC divides the block of data by a particular number which is referred to as the “CRC polynomial” or the “generator polynomial” and leaves a remainder, referred to herein as the cyclic redundancy check value. Usually, this CRC value is transferred with the data, and when the data is received or recovered from storage, another division is performed and the remainder from the second division is compared to the remainder sent or stored with the data. If the received data has been changed, the remainders will not be the same. Upon detecting this difference, the receiver may request that the data be resent.
Many different CRC polynomials are in use, and the length of the polynomial determines the length of the CRC value. For example, a 16-bit polynomial will produce a 16 bit CRC value. In fact, the most important distinction between polynomials may be their length. Long polynomials ensure greater data accuracy, are usable over larger amounts of data, and are more likely to detect errors in the data transmission than short polynomials.
A CRC uses modulo two arithmetic to produce its CRC value This is a digital form of division that is fast and easy to implement. A polynomial division modulo two is similar to binary division and is implemented through the use of a register having the same length as the CRC value produced by the division. The register is used to compute the CRC value and store it, at least temporarily, after computation. The register is usually cleared before the division is performed and then initialized to all ones to prevents errors caused by extraneous zeros that may or may not be detected by the CRC check.
SUMMARY OF THE INVENTION
An apparatus for generating a cyclical redundancy check value for a variable number of input data bits is provided. The apparatus includes at least a first device for calculating a cyclical redundancy check value on a full set of bits of input data and producing a first value and a second device for calculating a cyclical redundancy check value on a first subset of the full set of bits of input data and producing a second value. A multiplexer, coupled to the first and second devices, receives the first and second values and a selection input to the multiplexer selects one of the values for further transmission. The apparatus also includes a register having an input coupled to the output of the multiplexer. A second multiplexer can be coupled between the first multiplexer and the register for selecting the selected value from the first multiplexer or the output from the register for input to the register. The output from the register may be fed back to the first and second devices through a logic gate which selects an initialization input for the initial input bits and thereafter selects the output value from the register. By adding a checker to the apparatus, it becomes suitable for checking a cyclical redundancy check value. The checker compares a cyclical redundancy value from within the input data with the output value from the register or in accordance with an alternative embodiment compares the output value from the register with a constant.
A method receives a variable number of input data bits and generates a cyclical redundancy check value. A cyclical redundancy check value is calculated for a total number of bits to produce a first calculated value. A cyclical redundancy check value is calculated for a first subset of the total bits to produce a second calculated value. One of the calculated values is selected and transmitted to a register. For checking a received cyclical redundancy check value, the data except for the received cyclical redundancy check value can be used to generate a cyclical redundancy check value for comparison with the received cyclical redundancy check value. Alternatively, a cyclical redundancy check value is calculated for the input bits including their received cyclical redundancy check value and the result is compared with a constant.


REFERENCES:
patent: 0936537 (1999-08-01), None
InfiniBand™ Architecture Tutorial, Aug. 2000, pp. 1-144.
A Painless Guide to CRC Error Detection Algorithms Index V3.00, Sep. 24, 1996, pp.1-33.
InfiniBand™ Architecture Specification vol. 1, Release 0.9, Mar. 31, 2000, Published by InfiniBandSMTrade Association.
InfiniBand™ Architecture Specification vol. 2A, Release 0.9, Apr. 7, 2000, Published by InfiniBandSMTrade Association.

Affiliated with

Also associated with

Rating

Variable width parallel cyclical redundancy check does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Variable width parallel cyclical redundancy check, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable width parallel cyclical redundancy check will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3199650