High speed generation and checking of cyclic redundancy...

Details High speed generation and checking of cyclic redundancy... High speed generation and checking of cyclic redundancy...

1999-05-27

2003-03-04

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C708S492000, C714S807000, C714S757000

Reexamination Certificate

active

06530057

ABSTRACT:

CROSS REFERENCE TO RELATED APPLICATIONS
Not Applicable
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
Cyclic Redundancy Check (CRC) is a well-known error detection and correction technique used in many transmission and storage systems. A number of redundant bits are added to a message or data block, so that errors occurring during transmission or storage can be detected and, possibly, corrected. The degree of error detection is a function of the size of the message or data block, and the particular CRC.
One common CRC used in Local Area Networks (LANs) is defined for the ANSI/IEEE Std. 802 family of LAN standards. In that standard, a 4-octet (32-bit) CRC value is loaded into the Frame Check Sequence (FCS) field of a data unit or packet when it is transmitted. The value is computed as a function of the contents of the data unit. The k bits of data covered by the FCS can be represented as a polynomial f(x) of degree k−1. For example:
f(x)=10100100=x
7
+x
5
+x
2
f(x)=000 . . . 010100100=x
7
+x
5
+x
2
f(x)=101001=x
5
+x
3
+1
The specific encoding of the CRC value for ANSI/IEEE 802 is defined by the following generating polynomial:
G(x)=x
32
+x
26
+x
23
+x
22
+x
16
+x
12
+x
11
+x
10
+x
8
+x
7
+x
5
+x
4
+x
2
+x+1
In existing ASNI/IEEE systems, the CRC value corresponding to a given data unit is formed by the following procedure:
(1) The first 32 bits of the data unit are complemented.
(2) The k bits of the data unit are then considered to be coefficients of a polynomial f*(x) of degree k=1.
(3) f*(x) is multiplied by x
32
and divided by G(x) using modula-2 arithmetic, producing a remainder R(x) of degree less than or equal to 31.
(4) The coefficients of R(x) are considered to be a 32-bit sequence.
(5) The bit sequence is complemented and the result is the CRC value placed in the FCS field.
Steps 1 and 5 allow detection of missing or added zero bits at the beginning of a message. The necessary polynomial division in (3) has a well-known recursive form that processes each bit of the message serially and can be implemented simply in hardware using a linear feedback shift register (LFSR) formed by exclusive-OR gates to perform divisions and registers to hold intermediate results. However, such a serial implementation becomes impractical as data rates increase because only one bit of the message is processed at a time. When the data rate becomes sufficiently high, the serial form cannot generate or check the CRC value of a message within the time it takes to transmit the message. Accordingly, CRC related processing becomes an unacceptable bottleneck on message throughput.
To address this problem, some existing systems have introduced a level of parallelism into CRC processing. These systems have extended the serial implementation to process several bits of the message in parallel, based on a modified recursive equation. The standard parallel CRC method is described in U.S. Pat. No. 4,593,393 of Mead et al., filed Feb. 6, 1984, and U.S. Pat. No. 5,103,451 of Fossey, filed Jan. 29, 1990. However, this standard parallel approach cannot process many bits in parallel because the number of terms in the logic equations it implements becomes excessively large. As a result, many exclusive-OR gates are required, causing the system to run too slow, and which further occupy too much area on a chip and consume too much power. In addition, the standard parallel approach suffers from limited performance due to a low degree of pipelining in its processing.
As the number of bits being processed in parallel increases, the number of message bits covered by the CRC may not always be exactly divisible by the number of bits being processed in parallel. Existing systems for CRC value generation have not addressed this problem, since such existing systems have typically processed 8 bits in parallel, and the messages covered by the CRC value are typically guaranteed to contain an integer number of octets or bytes (8 bit units).
Accordingly it would be desirable to have a system for generating and checking a CRC value that processes many bits in parallel without requiring excessive numbers of exclusive-OR gates. The system should be compatible with existing CRC generation and checking standards, and apply to systems for error detection and correction in communications and storage applications.
Further, a system is needed to provide additional pipelining in the processing of CRC values. In addition, a system is required that enables CRC checking to be performed on messages that are not equally divisible by the number of bits being processed in parallel.
BRIEF SUMMARY OF THE INVENTION
A parallel, recursive system for generating a CRC value for a unit of data is disclosed, in which the feedback and forward terms are separated, and the forward terms are reduced. The unit of data may be either a portion of a data unit that is to be transmitted onto a communications network, a portion of a unit of data that has been received from a communications network, or a data block that has been either read or is to be written to a storage device such as a magnetic disk.
A forward logic block, which implements the forward terms, is responsive to a number of bits received from the unit of data, and operates to perform logic operations based on the reduced forward logic terms on the bits received from the unit of data, in order to produce a first output. In an illustrative embodiment in which the number of bits being processed in parallel, also referred to as the size of the portion of the unit of data, is less than or equal to the size of the CRC value, then the forward logic block is a direct connection to a number of exclusive-OR logic gates.
A feedback logic block, responsive to an output of a remainder register, operates to perform logic operations based on the feedback terms on an output of the remainder register to produce a second output. The second output is also coupled to the exclusive-OR logic gates.
The exclusive-OR logic gates perform a bit-wise exclusive-OR logic operation on the first output and the second output to produce a third output. The third output is coupled to an input of the remainder register.
In an exemplary embodiment, a first pipeline register receives the first output, and the exclusive-OR logic performs the bit-wise exclusive-OR logic operation on the second output and an output of the first pipeline register, instead of on the first output and.the second output. A second pipeline register, having the bits from the data unit as an input, further has an output coupled to a first input of a multiplexer. The multiplexer has a second input coupled to the output of the remainder register. The multiplexer is controlled to select the output of the remainder register in the event that all bits of the data unit have been processed by the first logic block and the second logic block. Otherwise, the multiplexer is controlled to select the bits from the unit of data. This has the effect of appending the CRC or FCS to the message.
In another embodiment, an inverter coupled is coupled to the output of the remainder register, to allow for CRC values with CRC bits inverted.
In another embodiment, the forward logic block determines the first output to be the remainder of the division of a polynomial a(x), by a predetermined generating polynomial G(X), where a(x) corresponds to a subsequence of the unit of data, and wherein a(x) is a polynomial of size j−1, where j is equal to a number of bits of the data unit being processed in parallel. The coefficients of a(x) correspond to the bits of the data unit. The feedback logic block determines the second output to be the remainder of the division of a product polynomial by a predetermined generator polynomial G(X), wherein the product polynomial is the result of multiplying the polynomial r(x) by x
j
, which has the effect of shifting r(x) by j

Affiliated with

Also associated with

Rating

High speed generation and checking of cyclic redundancy... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High speed generation and checking of cyclic redundancy..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed generation and checking of cyclic redundancy... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3053628