Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2002-02-01
2004-12-28
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000
Reexamination Certificate
active
06836869
ABSTRACT:
TECHNICAL FIELD
The present invention relates to error detection and correction circuitry for reliable digital data storage or transmission. In particular, the invention relates to circuitry that employs finite (Galois) field polynomial arithmetic for generating error checking codes, such as Reed-Solomon (RS) codes and cyclic redundancy check (CRC) codes, or for decoding data containing such codes.
BACKGROUND ART
Error checking codes have been developed to assure digital data integrity in situations such as transmission of data over a communications channel or data storage onto and retrieval from a storage medium. The codes allow the existence of errors in the data stream to be identified and in most cases corrected. Two widely used error correction codes are Reed-Solomon (RS) and cyclic redundancy check (CRC) codes. They are often used together, with RS codes being used for every block of 255 bytes of an encoded word, and CRC codes being used cumulatively for every packet of 10 or 20 RS encoded blocks. Typically, distinct circuitry is used to generate the respective RS and CRC codes, although the respective circuitry can be largely operated in parallel.
In U.S. Pat. No. 5,383,204, Gibbs et al. describe an error correction system having distinct RS encoding and CRC encoding hardware units sharing the same codeword memory and processing the data largely in parallel. The CRC check bytes are calculated on a data packet, while the RS processing is done for each data block, or in the case of the final four blocks of a packet, for the data blocks plus CRC check bytes. Since the data that the two units encode is the same, only the RS encoding of the CRC check bytes appended to the final four blocks is not parallizable. Once the CRC check bytes have been calculated, the RS bytes can be calculated for those final blocks. The patent deals with how the codeword memory accesses are sequenced under the operation of the two encoding units.
In U.S. Pat. No. 5,671,237, Zook describes a two-stage CRC encoding/decoding system. The first stage takes the input data, encodes it, and puts both the input data and K
1
CRC bytes in memory. Then the second stage (with K
2
>K
1
streams) takes the input data plus K
1
CRC bytes from the memory, verifies that no errors were introduced by the memory, encodes it, and passes the data plus K
2
CRC bytes as output from the unit. Each CRC stage (a generator/checker) uses programmable 8-bit generator polynomials. Each stage has a segmenter, which splits a data input stream into a programmable number of substreams, and has a programmable variable number (m) of parallel CRC units, each operating on a separate data substream. The first byte goes to a first CRC unit, the second byte to a second CRC unit, the m
th
byte to an m
th
CRC unit, the (m+1)-st byte to the first CRC unit, etc., until the end of the input data. The error checking capability of the CRC system, usually limited to detecting errors lying entirely in one 8-bit block, is enhanced by multiple staging and by interleaving.
In U.S. Pat. No. 5,375,127, Leak et al. describe a system for processing high bandwidth data block transfers, having a plurality of dedicated, RS error correction code (ECC) generation circuits that operate in parallel in order to handle multiple input data words simultaneously. The block connections can be reconfigured depending on the width of the input data, including a configuration for serial operation when input data is presented one word at a time.
In U.S. Pat. No. 5,136,592, Weng describes a technique that increases the detectable and correctable burst error length by arranging the data bits in a two-dimensional array of d columns by x lines and applying RS encoding to every column and CRC encoding on every line.
It is an object of the invention to provide a single processing circuit that is capable of operating, responsive to program instructions, in both an RS mode (encode or decode) and a CRC mode.
DISCLOSURE OF THE INVENTION
The object is met by a circuit that shares both registers and a multi-stage processing engine capable of implementing finite (Galois) field arithmetic operations used in both RS and CRC encoding and decoding. In particular, this error checking circuit includes 4 input register, designated A, C, B and P for receiving and holding operands for finite-field arithmetic operations associated with RS and CRC codes, a result register, designated RSD, for holding and outputting a result of the particular finite field arithmetic operations, or intermediate results during the operation, and a combinatorial finite-field arithmetic circuit connected to the registers and selectively configurable in response to program instructions to operate in RS and CRC modes, as directed. Specifically, the arithmetic circuit is configured in RS mode to carry out an iterated bitwise multiply-accumulate operation and is configured in CRC mode to carry out, in an iterated manner, a polynomial modulo division operation.
Two of the input registers A and C are shift registers responsive to a clock counter for transferring individual bits to the arithmetic circuit. The result register RSD has feedback connections to the arithmetic circuit and provides parallel bit output to the feedback bus. The registers are preferably buffered, and thus have a buffer register and a working register. The registers may also have bit and byte swap multiplexers for use with certain CRC standards. For RS mode, the A and C registers have associated multiplexers responsive to respective RS encode and RS decode instructions which broadcast the least significant byte in the A or C register to all of the other byte locations of that register.
The arithmetic circuit is a multi-stage combinatorial circuit made up of pairs of stages, where each stage includes a set of AND gates and a set of XOR gates, the gates being associated with specific bit locations. The output of each AND gate is connected to one input of its associated XOR gate. The first stage XOR gate outputs are connected to the second stage via a configuration multiplexer unit, with different connections being selected in RS and CRC modes. Another configuration multiplexer unit selects connections between the result register feedback and the first stage according to the operating mode.
The two-stage implementation can be replicated two or four times to obtain 4-stage or 8-stage arithmetic circuits for faster CRC processing. The operation of the input shift register A is modified to supply appropriate bits to each of the stages. The RS processing continues to be performed by the first two stages in any of the implementations, and a multiplexed bus is provided so that the result register RSD is supplied with operational results after the final (fourth, or eighth) stage in the CRC mode, but after the second stage in RS mode.
REFERENCES:
patent: 3678469 (1972-07-01), Freeman et al.
patent: 5136592 (1992-08-01), Weng
patent: 5375127 (1994-12-01), Leak et al.
patent: 5383204 (1995-01-01), Gibbs et al.
patent: 5615221 (1997-03-01), Karp et al.
patent: 5671237 (1997-09-01), Zook
patent: 6370671 (2002-04-01), Pan et al.
patent: 6378104 (2002-04-01), Okita
patent: 6405339 (2002-06-01), Cox et al.
patent: 6467063 (2002-10-01), Fukuoka
patent: 6754870 (2004-06-01), Yoshida et al.
Baker Stephen M.
Cradle Technologies, Inc.
Protsik Mark
Schneck Thomas
Schneck & Schneck
LandOfFree
Combined cyclic redundancy check (CRC) and Reed-Solomon (RS)... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Combined cyclic redundancy check (CRC) and Reed-Solomon (RS)..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combined cyclic redundancy check (CRC) and Reed-Solomon (RS)... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3324270