Product code based forward error correction system

Details Product code based forward error correction system Product code based forward error correction system

2000-06-02

2004-05-18

Tu, Christine T. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S782000

Reexamination Certificate

active

06738942

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates generally to forward error correction systems, and in particular to a product code based forward error correction system.
Digital electronic systems store and transmit copious amounts of information. Storage or transmission of digital information sometimes results, however, in corruption of some of the data. Defects in a storage media, or errors in the reading and writing of data from a storage media, may result in data errors. Similarly, transmission of data through a transmission channel may result in errors, through noise in the transmission channel or the inability of the transmitting or receiving unit to properly transmit or read data. As data storage and data transmission may be viewed as transmitting data to a media using a transmitting unit, and thereafter reading the data using a receiving unit, the remaining discussion will be in terms generally of data transmission.
Forward error correction (FEC) is often used to increase data reliability. Generally speaking, FEC systems encode data using an encoder at a transmitter and decode data using a decoder at the receiver. During encoding redundant information is added to the data. The redundant information allows determination by receiving units as to whether data corruption has occurred, and if so, the data that has been corrupted. Thus, the redundant information allows the data to be corrected within limits. The decoder generally decodes the data, generates an error polynomial, and uses the error polynomial to determine corrections to the data.
The encoded data is generally grouped in terms of code words. A code word is comprised of n symbols, of which k symbols are information symbols. The codeword therefore contains n−k redundant symbols. The symbols are data words comprised of m bits. In a systematic encoding system, the n−k redundant symbols are appended to the information symbols, while in a non-systematic code the information symbols are also modified. For instance, for BCH codes, n=2
m
−1 and k=n−mt. To correct t bits within the code word, mt bits of overhead/redundancy is needed. Each of the k and n symbols is made of 1 bit. For Reed-Solomon (RS) codes, n=2
m
−1 and k=n−2t. For RS codes, to correct t symbols within the code word, 2t symbols of redundancy is needed. Each of the k and n symbols comprise m bits.
In order to increase data transmission reliability increased numbers of redundant symbols are required. The use of additional redundant symbols, however, decreases the effective bandwidth of a transmission system or reduces the total amount of storage space available in a storage system. Moreover, the use of additional redundant symbols increases the amount of processing performed by both the transmitting unit and the receiving unit to create or interpret the redundant symbols.
Moreover, different coding schemes have different abilities to correct different types of errors. For example, errors may be randomly distributed in a data set, or the errors may be grouped together, i.e. be burst errors. Generally speaking, increasing the number of bits within a symbol increases the ability of an FEC system to correct burst errors. However, as indicated above, increasing the number of bits per symbol also increases encoding and decoding circuit size and power requirements since the code word becomes longer.
SUMMARY OF THE INVENTION
The present invention provides a multi-dimensional forward error correction system. In one embodiment of the present invention comprises a method of performing a multi-dimensional forward error correction. The method includes encoding information symbols comprised of input data to form first code words and second code words, the first and second code words sharing at least some symbols. The method further comprises providing receipt symbols comprising potentially corrupted symbols of the first code words and second code words to a decoder. Potentially corrupted symbols are corrected by decoding the first received symbols, and further corrected by decoding the second received symbols, the second received symbols including symbols corrected during decoding of the first received symbols.
In a further embodiment, the received symbols are placed in a memory to form a multi-dimensional matrix, a first dimension of the multi-dimensional matrix being comprised of the first received symbols and the second dimension of the multi-dimensional matrix being comprised of the second received symbols. In a further embodiment the memory is comprised of virtual rows of symbols and virtual columns of symbols, and further includes placing corrected symbols in the memory in place of corrupted received symbols.
These and other aspects of the present invention are more readily understood when considered in conjunction with the accompanying drawings and the following detailed description.


REFERENCES:
patent: 4077028 (1978-02-01), Lui et al.
patent: 4099160 (1978-07-01), Flagg
patent: 4142174 (1979-02-01), Chen
patent: 4162480 (1979-07-01), Berlekamp
patent: 4410989 (1983-10-01), Berlekamp
patent: 4413340 (1983-11-01), Odaka
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: 4653051 (1987-03-01), Sugimura et al.
patent: 4718067 (1988-01-01), Peters
patent: 4777635 (1988-10-01), Glover
patent: 4835775 (1989-05-01), Seroussi
patent: 4873688 (1989-10-01), Maki et al.
patent: 4937829 (1990-06-01), Kadokawa
patent: 5140596 (1992-08-01), Weldon, Jr.
patent: 5170399 (1992-12-01), Cameron
patent: 5226043 (1993-07-01), Pughe, Jr. et al.
patent: 5247523 (1993-09-01), Arai et al.
patent: 5272661 (1993-12-01), Raghavan et al.
patent: 5323402 (1994-06-01), Vaccaro et al.
patent: 5375127 (1994-12-01), Leak et al.
patent: 5384786 (1995-01-01), Dudley
patent: 5392299 (1995-02-01), Rhines et al.
patent: 5512853 (1996-04-01), Ueno et al.
patent: 5563897 (1996-10-01), Pyndiah et al.
patent: 5666369 (1997-09-01), Nakamura
patent: 5689452 (1997-11-01), Cameron
patent: 5699368 (1997-12-01), Sakai et al.
patent: 5721745 (1998-02-01), Hladik et al.
patent: 5732208 (1998-03-01), Tamura et al.
patent: 5734962 (1998-03-01), Hladik et al.
patent: 5754563 (1998-05-01), White
patent: 5757826 (1998-05-01), Fredrickson
patent: 5878058 (1999-03-01), Im
patent: 5974580 (1999-10-01), Zook et al.
patent: 6023782 (2000-02-01), Cox et al.
patent: 6023783 (2000-02-01), Divsalar et al.
patent: 6282039 (2001-08-01), Bartlett
patent: PCT/ISA/220 (2000-10-01), None
Stephen B. Wicker, “Error Control Systems for Digital Communication and Storage”, Prentice-Hall, 1995.*
Conference Paper: “Practical Reed Solomon Design for PLD Architectures” Altera Corporation; http://www.altera.com/html/literature/lconf.html.
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, Hayes, “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 Error-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.
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 Berlek

Affiliated with

Also associated with

Rating

Product code based forward error correction system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Product code based forward error correction system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Product code based forward error correction system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3208792