Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-12-23
2001-07-10
Moise, Emmanuel L. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000, C714S785000, C708S492000
Reexamination Certificate
active
06260173
ABSTRACT:
FIELD OF INVENTION
The invention relates generally to error correction systems and, more particularly, to systems that use hardware that both encodes the data and produces associated error syndromes.
BACKGROUND OF THE INVENTION
Encoders for encoding data in accordance with a Reed-Solomon error correction code (“ECC”) to produce ECC symbols are well known. A conventional encoder that produces “j” ECC symbols includes j Galois Field multipliers. The Galois Field multipliers are associated, respectively, with the j coefficients of the code generator polynomial, g(x). The encoder also includes feedback adders that combine the products associated with a given data symbol with the results of the encoding of the previous data symbol, and j registers that hold the sums produced by the adders. At the end of the encoding, the j registers contain the ECC symbols.
When a data symbol is supplied to the encoder the symbol is combined with the contents of a last register and the result is supplied to the Galois Field multipliers, which simultaneously multiply the results by the coefficients of g(x). The product produced by a first Galois Field multiplier updates the firt register. The products produced by the remaining Galois Field multipliers are combined, respectively, with the contents of the remaining registers and the results are used to update these registers. The last register is thus updated with the sum of (i) the product produced by the last Galois Field multiplier and (ii) the contents of the preceding register.
The updated contents of the last register are then combined with the next data symbol and the result is fed back to the Galois Field multipliers, with the remaining feedback adders adding the products produced by the multipliers to the results of the encoding of the previous data symbol and supplying the sums to update the registers, and so forth. As soon as the last data symbol is encoded, the ECC symbols are read from or clocked out of the j registers and concatenated with the data symbols to produce a data codeword that is transmitted or stored, as appropriate.
With such an encoder the latency is the time associated with a single feedback adder, since the adders operate in parallel to produce the updated sums for the registers. Accordingly, the latency is essentially non-existent
As part of a decoding operation a decoding system manipulates the data symbols of a data code word to produce error syndromes that are then used to locate errors in the data. A conventional error syndrome generator includes j sets of associated update adders, Galois Field multipliers and registers, with each set operating simultaneously and essentially separately to produce the associated error syndrome.
Each update adder adds the product produced by the associated Galois Field multiplier to the next data symbol, and updates the associated register with the sum. Each Galois Field multiplier then multiplies the contents of the register by a coefficient of an error syndrome generator polynomial that is associated with the ECC and supplies the product to the associated update adder. The update adder adds the product to the next data symbol, and supplies the sum to the associated register, and so forth. After the last data symbol is supplied to the syndrome generator and added to the products produced by the respective Galois Field multipliers to update the registers, the j registers contain the j error syndromes.
The Galois Field multipliers that are included in the encoder and the syndrome generator are relatively complex components. An article by Gerhard Fettweis and Martin Hassner,
A Combined Reed
-
Solomon Encoder And Syndrome Generator With Small Hardware Complexity,
published by IEEE in 1992 describes hardware that uses the same Galois Field multipliers for both the encoding and the syndrome generation. The combined hardware thus uses one-half the number of multipliers that are required for separate encoder and syndrome generator hardware. The article is incorporated herein by reference.
The combined hardware described in the article includes j sets of associated registers, Galois Field multipliers, update adders and feedback adders. The j registers hold updated sums produced by the j associated update adders. Each Galois Field multiplier multiplies the contents of the associated register by a root of the generator polynomial and supplies the product to the associated feedback adder. During encoding operations, an associated AND gate passes to the adder the sum produced by the previous feedback adder. The adder then adds the propagating sum to the product and passes the result both to the associated update adder and through a next AND gate to the next feedback adder. The next feedback adder adds the propagating sum to the product produced by the associated multiplier, and the result is supplied to the associated update adder and through the next AND gate to a next feedback adder, and so forth. The feedback adders and the associated AND gates thus form a feedback path in which the adders operate as a chain.
During syndrome generation operations, the AND gates essentially break the chain of adders by blocking the propagation of a sum from one feedback adder to the next, and the j sets of associated registers, multipliers and adders operate separately to produce the j error syndromes.
With the combined hardware there is a latency in the encoding operations that corresponds to the time it takes the propagating sum to pass through the chain of j feedback adders. If the chain of adders is long, it restricts the speed with which the data can be encoded since the sum must propagate through the entire adder chain during a clock cycle. Accordingly, the system can not be clocked at a rate that exceeds the associated latency.
SUMMARY OF THE INVENTION
The invention is a combined encoding/syndrome generating circuit that is segmented into multiple-cell blocks that operate in parallel during encoding operations to produce interim sums. The interim sums are then combined to propagate a sum across the system, from the first cell to the last cell. The latency associated with propagating the sum across the system during encoding is thus reduced from the time associated with propagating a sum through a chain of j−1 adders to essentially the time associated with propagating a sum through log
2
j adders.
More specifically, each cell includes a Galois Field multiplier and an associated update adder and register. A block of two cells includes two sets of associated Galois Field multipliers, registers and update adders, and a block feedback adder that produces the associated interim sum by adding together the products produced in parallel by each of the cells. A block with more taan two cells includes additional feedback adders that operate in parallel to selectively combine the products produced by the plurality of cells, to produce, with minimal delay, an interim sum that includes a contribution from each of the cells in the block. The system then adds together the interim sums produced simultaneously by the various blocks, to propagate a sum across the system. Also, the interim sum from a given block is combined in parallel into the products produced by the respective cells of the next block, to include in the update signals that are fed back to the associated registers the contributions from each of the previous cells.
During syndrome generation operations, the cells essentially operate independently to produce the syndromes.
The current system includes more feedback adders than the conventional Fettweis-Hassner circuit, since the adders are required during encoding to (a) produce the interim sums, (b) combine the sums into the propagating sum, and (c) add the interim sums into the cells in an adjacent block. However, the delay through the current system is reduced from that of the conventional system, since many of the feedback adders in the current system operate in parallel.
REFERENCES:
patent: 5778009 (1998-07-01), Fredickson et al.
patent: 5887006 (1999-03-01), Sharma
patent: 5901158 (1998-07-01)
Chang Chung-Hsing
Mo Shih
Shen Ba-Zhong
Weng Lih-Jyh
Cesari & McKenna
Moise Emmanuel L.
LandOfFree
Combined system for producing error correction code symbols... 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 system for producing error correction code symbols..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combined system for producing error correction code symbols... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2560747