Runtime programmable Reed-Solomon decoder

Details Runtime programmable Reed-Solomon decoder Runtime programmable Reed-Solomon decoder

2000-07-11

2004-03-09

Tu, Christopher T. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C708S492000

Reexamination Certificate

active

06704901

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to Reed-Solomon (RS) decoders. More particularly, the present invention relates a runtime programable RS decoder that can operate on multiple pieces of data during one clock cycle in order to generate, reduce, and evaluate polynomials involved in the decoding of an RS code, and which allows a user to choose the RS code after the circuit has been implemented.
BACKGROUND OF THE INVENTION
RS codes are used in many applications where data is transferred from one system to another. These applications include Digital Subscriber Lines (xDSL), digital television, asynchronous transfer mode (ATM) communications, tape drives, compact discs (CDs), digital versatile discs (DVDs), and so on. The decoding of RS error correcting codes requires the calculation of several polynomials with coefficients in a finite Galois Field (GF). These polynomials are generally known as the syndrome polynomial, the error evaluator polynomial (&OHgr;(x) polynomial) and the error locator polynomial (&Lgr;(x) polynomial). Conventional designs for computing these polynomials required circuitry that was generally limited to operating on one byte at a time for the computation of each of these polynomials, such as shown in U.S. Pat. No. 5,396,502 (hereinafter the '502 patent). The '502 patent describes an Error Correction Unit (ECU) that uses a single stack embodiment for the generation, reduction and evaluation of the polynomials involved in the decoding of an RS code. The circuit uses the same hardware to generate the syndromes, reduce the &OHgr;(x) and &Lgr;(x) polynomials and evaluate the &OHgr;(x) and &Lgr;(x) polynomials, but is limited to operating on one byte per clock cycle. The disclosure of the '502 patent is hereby incorporated herein in its entirety.
Additionally, RS decoders in the past were typically limited to being able to decode only a particular RS code. It was not possible with such RS decoders to choose the code after the circuit was implemented so as to enable use in multiple applications without predetermining the RS code. Such decoders did not allow a user the flexibility to change the RS code as desired without having to replace the RS decoder.
In view of the aforementioned shortcomings associated with conventional RS decoders, there is a strong need in the art for an RS decoder which is not limited to operating on one byte per clock cycle. Moreover, there is a strong need in the art for an RS decoder which is not limited in operation based on a set predefined RS code.
SUMMARY OF THE INVENTION
The RS decoder of the present invention provides improved operation compared to conventional RS decoders. According to the present invention, an RS decoder is provided which is able to operate on two or more words per clock cycle. Such a feature will reduce the decoding time to a point approaching the time it takes to generate the &Lgr; and &OHgr; polynomials. In addition, the RS decoder is runtime programmable, which allows a user to change the codefield after the circuit has been implemented (i.e. “on the fly.”)
More particularly, the present invention is a decoder circuit for decoding an input word stream which includes a plurality of Reed-Solomon encoded data segments. The decoder circuit includes at least one computation unit for receiving the input bit stream, resolving coefficients of a syndrome polynomial, generating an &OHgr;(x) polynomial, generating a &Lgr;(x) polynomial, and generating a &Lgr;′(x) polynomial, and for outputting an evaluated &OHgr;(x) polynomial and an evaluated &Lgr;(x) polynomial, each of these polynomials having a plurality of data words which the computation unit can resolve multiple words at a time. The decoder circuit has at least one register file for receiving data and storing the intermediate processed coefficients of the syndrome polynomial, the &OHgr;(x) polynomial, the &Lgr;(x) polynomial, and the &Lgr;′(x) polynomial. Additionally, the decoder circuit has at least one division unit for evaluating the &OHgr;(x) and &Lgr;(x) polynomials and for producing an output word stream of decoded data segments.
Additionally, the computation unit of
FIG. 1
has a general GF multiplier, which uses a primitive element of the field as an input. This allows the user to change the field “on the fly.” Traditional GF multipliers are polynomial specific, and if implemented in an ASIC or ASSP can only handle one field. The current invention allows the user to decode data encoded in any RS code of bit width less than a defined maximum, as long as the defining parameters of the code are known. Likewise, the GF multiplier can handle codes of lesser bit widths than the maximum defined by the size of the multipliers.


REFERENCES:
patent: 5297153 (1994-03-01), Baggen et al.
patent: 5396502 (1995-03-01), Owsley et al.
patent: 5905740 (1999-05-01), Williamson
patent: 6374383 (2002-04-01), Weng
patent: 6487691 (2002-11-01), Katayama et al.

Affiliated with

Also associated with

Rating

Runtime programmable Reed-Solomon decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Runtime programmable Reed-Solomon decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Runtime programmable Reed-Solomon decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3232790