Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-06-02
2004-02-17
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06694476
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to systems and methods for performing Reed-Solomon encoding and decoding, and in particular to semi-parallel Reed-Solomon encoders and decoders.
The transmission of information is of great importance to computing networks, from a local area network to the Internet. In thriving computing networks, the demands for a faster, more reliable and cost-effective manner of transmitting information are constantly increasing. However, satisfying these demands is difficult and replete with obstacles. These obstacles include bandwidth limitations, total system component costs, reliability and quality of service.
Conventional fiber optic networks, generally conforming to standards such as synchronous optical network (SONET) and synchronous digital hierarchy (SDH), are widely prevalent and allow for increasingly greater transmission. Also, with the advent of time division multiplexing (TDM) components, the conventional fiber optic bandwidth is quadrupled. However, as new technologies and services develop in video, high resolution graphics and other types of applications requiring tremendous amounts of data, the bandwidth provided by TDM is being quickly exhausted.
Also, as the demand for faster service and the dependence of computing networks on the transmission of information grows, the reliability on the information becomes critical. Multiple types of transmission schemes have been developed to ensure data trustworthiness. One common and widely utilized transmission scheme, especially in the high-speed realm of fiber optics, is Reed-Solomon (RS) encoding and decoding. However, serial operation of RS encoding and decoding acts, to an extent, as a bottleneck in data transmission systems that use high data rates. On the other hand, fully parallel operation of RS encoding and decoding provides better time performance under high data rates, but is often costly and complex, and includes high VLSI gate counts and increased power usage requirements.
SUMMARY OF THE INVENTION
The present invention provides a semi-parallel Reed-Solomon encoder and decoder. In one embodiment, the present invention comprises a method of performing semi-parallel encoding and decoding using an (n,k) code. In one embodiment the method comprises sequentially providing sets of a plurality of information symbols to an encoder, the sets of the plurality of information symbols forming an information word. On each set of the information symbols Galois field multiplication is sequentially performed to form intermediate terms. Combining the intermediate terms results in, or forms, at least some of the symbols of the code word. The method further comprises sequentially generating n-k syndromes, and determining an error locator polynomial using the n-k syndromes. Further, in one embodiment, the method comprises evaluating a plurality of roots of the error locator polynomial using a plurality of polynomial evaluators, each polynomial evaluator evaluating a plurality of the roots of the error locator polynomial.
In another embodiment, a method of the present invention comprises encoding a data stream forming an information vector, the data stream comprising a plurality of information symbols, with a method comprising providing a first set of information symbols to a Galois field multiplier, the first set of information symbols being less than the plurality of information symbols. Further, the method comprises performing Galois field multiplication on the first set of information symbols to form a first set of code words, and providing a second set of information symbols to the Galois field multiplier and performing Galois field multiplication on the second set of information symbols.
REFERENCES:
patent: 3893078 (1975-07-01), Finet
patent: 4059825 (1977-11-01), Greene
patent: 4077028 (1978-02-01), Lui et al.
patent: 4099160 (1978-07-01), Flagg
patent: 4142174 (1979-02-01), Chen et al.
patent: 4162480 (1979-07-01), Berlekamp
patent: 4410989 (1983-10-01), Berlekamp
patent: 4413340 (1983-11-01), Odaka et al.
patent: 4494234 (1985-01-01), Patel
patent: 4504948 (1985-03-01), Patel
patent: 4587627 (1986-05-01), Omura et al.
patent: 4633470 (1986-12-01), Welch et al.
patent: 4633471 (1986-12-01), Perera et al.
patent: 4718067 (1988-01-01), Peters
patent: 4763330 (1988-08-01), Shimizu
patent: 4777635 (1988-10-01), Glover
patent: 4835775 (1989-05-01), Seroussi
patent: 4856004 (1989-08-01), Foster et al.
patent: 4873688 (1989-10-01), Maki et al.
patent: 4937829 (1990-06-01), Kadokawa
patent: 5068856 (1991-11-01), Nagasawa et al.
patent: 5140596 (1992-08-01), Weldon, Jr.
patent: 5170399 (1992-12-01), Cameron et al.
patent: 5226043 (1993-07-01), Pughe, Jr. et al.
patent: 5268908 (1993-12-01), Glover et al.
patent: 5272661 (1993-12-01), Raghavan et al.
patent: 5315600 (1994-05-01), Iwamura et al.
patent: 5323402 (1994-06-01), Vaccaro et al.
patent: 5375127 (1994-12-01), Leak et al.
patent: 5384786 (1995-01-01), Dudley et al.
patent: 5440570 (1995-08-01), Wei et al.
patent: 5446743 (1995-08-01), Zook
patent: 5512853 (1996-04-01), Ueno et al.
patent: 5666369 (1997-09-01), Nakamura
patent: 5689452 (1997-11-01), Cameron
patent: 5691997 (1997-11-01), Lackey, Jr.
patent: 5699368 (1997-12-01), Sakai et al.
patent: 5754563 (1998-05-01), White
patent: 5757826 (1998-05-01), Fredrickson
patent: 5805617 (1998-09-01), Im
patent: 5878058 (1999-03-01), Im
patent: 5974580 (1999-10-01), Zook et al.
patent: 6023782 (2000-02-01), Cox et al.
patent: 6031875 (2000-02-01), Im
patent: 6038694 (2000-03-01), Swallow
patent: 6192499 (2001-02-01), Yang
patent: 6209115 (2001-03-01), Truong et al.
patent: 6308295 (2001-10-01), Sridharan et al.
patent: 6374383 (2002-04-01), Weng
patent: 6493845 (2002-12-01), Shen et al.
patent: PCT/ISA/220 (2000-10-01), None
Stephen B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice-Hall, 1995, pp. 80-85 and 206-211.*
Stephen Wicker, Error Control Systems for Digital Communication and Storage, Prentice-hall, 1995, paes 116-121.*
Wang, et al., “VLSI Architectures for Computing Multiplications and Inverses in GF(2m),” IEEE Transaction on Computers, Vol C-34, No. 8, pp. 709-717, Aug. 1985.
Shao, et al., “A VLSI Design of a Pipeline Reed-Solomon Decoder,” IEEE Transaction on Computers,Vol C-34, No. 5, pp. 393-403, Aug. 1985.
Eastman, “Euclideanization of the Berlekamp-Massey Algorithm” from the Proceedings of the 1988 Tactical Communications Conference, Vol 1 (1988), pp. 295-303.
Choomchuay, Arambepola, “Reed-Solomon Decoding,” IEEE Proceedings-1, Vol 140, No. 3, Jun. 1993.
Manuscript: Neifeld, Hayes, “Optical and Electronic Error Correction Schemes for Highly Parallel Access Memories,” Proceedings of the SPIE—The International Society for Optical Engineering vol. 2026 (1993) p543-53.
Thesis: Sridharan, “VLSI Implementation of a Spectral Domain Parallel Error Decoder,” University of Arizona, 1995.
Neifeld, Hayesm, “Error-Correction Schemes for Volume Optical Memories,” Applied Optics, Vol 34, No. 35 pp. 8183-8191, Dec. 1995.
Internet Papers: Matache, “Berlekamp's Iterative Algorithm for Finding the Eror-Locator Polynomial,” http://drake.ee.washington.edu/~adina/rsc/slide
ode8.html.
Internet Papers: BAD, “Overview of Forward Error Correction,” http://ee.wpi.edu/courses/ee535/hwk97/hwk4cd97/bad/paper.html, pp. 1-14.
Conference Paper: “Practical Reed Solomon Design for PLD Architectures” Altera Corporation; http://www.altera.com/html/literature/lconf.html.
Jarchi Michael
Sridharan Satish
Christie Parker & Hale LLP
De'cady Albert
Torres Joseph D.
Vitesse Semiconductor Corporation
LandOfFree
Reed-solomon encoder and 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 Reed-solomon encoder and decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed-solomon encoder and decoder will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3319259