Pipelined high speed reed-solomon error/erasure decoder

Details Pipelined high speed reed-solomon error/erasure decoder Pipelined high speed reed-solomon error/erasure decoder

1999-03-23

2002-02-12

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06347389

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to a system that decodes a class of multiple error correcting codes known as Reed-Solomon Codes, which are typically used within digital communication systems to detect corrupted data contained in the digital transmission and correct these corrupted data. As part of the Reed-Solomon error correcting process, redundancy is added to the transmitted data, such that upon receipt of a data transmission, the possibly corrupted data and redundancy are mathematically processed to correct the corrupted data in the data transmission.
Problem
It is a problem in high speed decoding of multiple error correcting codes, known as Reed-Solomon codes, with or without erasure pointers, to reduce the number of computational steps that are required at each stage of decoding. It is, likewise, a problem to reduce the number of combinatorial operations that are required to exchange data between any two hardware registers that are operational within the Reed-Solomon decoder.
Reed-Solomon Codes are used within digital communication systems, such as fiber optic transmission systems, optical and magnetic data storage systems, where the corruption of data being transferred between any two points affects system reliability. As part of the Reed-Solomon error correcting process, redundancy is added to the transmitted data, such that upon receipt of a data transmission the possibly corrupt data and redundancy are mathematically processed to correct errors in the data transmission. Prior art Reed-Solomon decoders use both Berlekamp/Massey and Chien Search processes to detect and correct the errors that are present in the data transmission. These prior art Reed-Solomon decoders are primarily concerned with the total number of computations required to perform the data transmission decoding process, and the amount of hardware required to perform the data transmission decoding process. The Berlekamp/Massey synthesis process includes an erasure pre-shifting burden which adds to the processing complexity. These prior art Reed-Solomon decoders typically lack explicit early indication of error locations and do not provide early erasure information from the Berlekamp/Massey and Chien Search processes.
Solution
The above described problems are solved and a technical advance achieved by the pipelined high speed Reed-Solomon error/erasure decoder of the present invention which processes multiple code words in a pipelined fashion. The piplelined high speed Reed-Solomon error/erasure decoder processes Reed-Solomon encoded data words to detect the presence of data words that have been corrupted in a digital system and processes corrupted data, that comprises both errors as well as erasures, through a simple iterative modified syndrome process. The iterative nature of this method provides for limited computational effort at each step of the pipeline. This allows the pipelined high speed Reed-Solomon error/erasure decoder to easily handle full or shortened Reed-Solomon codes, as well as parallel processing to achieve higher data rates. The iterative modified syndrome process is one of the pipelined steps. It relieves the erasure pre-shifting burden from the Berlekamp/Massey synthesis process, which reduces the number of cycles required at that stage of processing. The pipelined high speed Reed-Solomon error/erasure decoder then proceeds classically with a Chien Search for any remaining error locations. This approach allows the pipelined high speed Reed-Solomon error/erasure decoder to relay early information on all error locations. The final stage of the decoding process is a parallel, iterative solution to Forney's equation for the calculation of the error magnitudes.
This pipelined high speed Reed-Solomon error/erasure decoder emphasizes the number of iterations (or clock cycles) and the number of combinatorial operations between each hardware register, which is accomplished by combining iterative LFSR solutions for syndrome modification and error magnitude processing to the well known Berlekamp/Massey and Chien Search iterative hardware solutions. Additionally, in augmenting the known erasure locations with a classic Berlekamp/Massey—Chien Search for any remaining error locations, the pipelined high speed Reed-Solomon error/erasure decoder also provides explicit early indication of all error locations. This can be helpful in providing early erasure information for errors that no erasure location was provided.


REFERENCES:
patent: 5323402 (1994-06-01), Vaccaro et al.
patent: 5379305 (1995-01-01), Weng
patent: 5430739 (1995-07-01), Wei et al.
patent: 5541937 (1996-07-01), Iwamura
patent: 5942005 (1999-08-01), Hassner et al.
patent: 6119262 (2000-09-01), Chang et al.
patent: 6122766 (2000-09-01), Fukuoka et al.
patent: 6131178 (2000-10-01), Fujita et al.
Blaum M. et al., “New Array Codes For Multiple Phased Burst Correction”; IEEE Transactions on Information Theory, US, IEEE Inc. New York, vol. 39, No. 1, 1993, pp. 66-77.

Affiliated with

Also associated with

Rating

Pipelined high speed reed-solomon error/erasure 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 Pipelined high speed reed-solomon error/erasure decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined high speed reed-solomon error/erasure decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2949551