Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-06-21
2002-12-10
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S785000
Reexamination Certificate
active
06493845
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 “R” ECC symbols includes R Galois Field multipliers. The Galois Field multipliers are associated, respectively, with the j roots 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 roots of g(x). The product produced by a first Galois Field multiplier updates the first 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. The remaining feedback adders add the products produced by the multipliers to the results of the encoding of the previous data symbol and supply 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 R 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 R 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 root 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 R registers contain the R 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 is depicted in FIG.
1
. The hardware includes R sets of associated registers
10
, Galois Field multipliers
12
, update adders
14
and feedback adders
16
. The R registers
10
hold updated sums produced by the R associated update adders
14
. Each Galois Field multiplier
12
multiplies the contents of the associated register
10
by a root of the generator polynomial and supplies the product to the associated feedback adder
16
. During encoding operations, an associated AND gate
18
passes to the adder
16
the sum produced by the previous feedback adder
16
. The adder
16
then adds the propagating sum to the product and passes the result both to the associated update adder
14
and through a next AND gate
18
to the next feedback adder
16
. The next feedback adder
16
adds the propagating sum to the product produced by the associated multiplier
12
, and the result is supplied to the associated update adder
14
and through the next AND gate
18
to a next feedback adder, and so forth. The feedback adders
16
and associated AND gates
18
thus form a feedback path in which the adders
16
operate as a chain. During syndrome generation operations, the AND gates
18
essentially break the chain of adders by blocking the propagation of a sum from one feedback adder
16
to the next, and the R sets of associated registers
10
, multipliers
12
and adders
14
operate separately to produce the R 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 R feedback adders as each symbol is encoded. If the chain of adders is long, it restricts the speed with which the data is encoded by setting a minimum time for a clock cycle, that is, a minimum time for the encoding of each symbol, since in each clock cycle the corresponding propagating sum must pass through the entire chain of R adders.
SUMMARY OF THE INVENTION
The invention is a parallel input/output combined encoding and syndrome generating system that encodes two symbols per clock cycle, and thereafter, produces two redundancy symbols per clock cycle. The system thus produces the R redundancy symbols and the R error syndromes in one-half the time of the conventional Fettweis-Hassner hardware.
More specifically, for an n-symbol code word with 2k information symbols c
n−1
, to c
n−2k
, the symbols c
n−1
, c
n−3
, c
n−5
. . . are supplied, in turn, to a first input line while the symbols c
n−2
, c
n−4
, c
n−6
, . . . are supplied, in turn, to a second input line. In a first clock cycle, the symbol c
n−1
is combined with the contents of the R registers and multiplied by the roots of the generator polynomial. The respective products then are combined with the paired symbol c
n−2
and the resulting sums are multiplied also by the roots of the generator polynomial. These products are then summed in the chain of R adders and the registers are appropriately updated with the results of the encoding of the pair of symbols. Accordingly, a sum is propagated along the chain of R adders once to encode the two symbols.
During the next clock cycle, the next pair of information symbols are encoded, with c
n−3
supplied to the first input line and c
n−4
supplied to the second input line, and so forth. During the k
th
clock cycle, when the last of the pairs of information symbols are being encoded, the system produces the first two redundancy symbols. More specifically, the first redundancy symbol is the k
th
update value for the last register r
R−1
, which is produced by the chain of R adders. The system then manipulates the update value, as discussed in more detail below, to produce the second redundancy symbol in the same clock cycle. During the k+1
st
clock cycle, the pair of redundancy symbols are fed back to the two input lines and encoded, as discussed above, to produce the next pair of redundancy symbols, and so forth. The system thu
Langer Diana L.
Shen Ba-Zhong
Weng Lih-Jyh
Cesari and McKenna LLP
De'cady Albert
Dooley Matt
Maxtor Corporation
LandOfFree
Parallel input output combined system for producing error... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel input output combined system for producing error..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel input output combined system for producing error... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2917157