Galois field computation system and method

Details Galois field computation system and method Galois field computation system and method

1999-06-18

2002-06-25

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06412090

ABSTRACT:

TECHNICAL FIELD
The present invention is generally related to data communications and, more particularly, is related to Reed-Solomon (“RS”) decoding employed to minimize or eliminate errors in data communication.
BACKGROUND OF THE INVENTION
Communication of information in the form of digital data is quite commonplace in today's society. There are many different communications channels that may be employed to facilitate such data communication. Such channels may include existing telecommunications networks, optical fiber networks, cellular networks, the Internet, wide area networks, local area networks, or other like media. It is often the case that the communications channels chosen do not provide a perfect medium to transfer data information, and for various reasons such as noise, interference, or other phenomena, errors may be introduced into the data stream transmitted across a particular channel.
Many different approaches have been proposed to either reduce or eliminate errors in data communications. One such approach is to employ Reed-Solomon encoding/decoding. When employing Reed-Solomon encoding/decoding, data is transmitted in codewords which include a number of parity symbols along with the original data symbols. The parity symbols are generated using a Reed-Solomon encoder.
When using Reed-Solomon encoding, various numbers of parity symbols may be generated to allow a data system to correct up to a specific number of possible errors in the transmitted data. However, for each different number of total parity symbols generated, there is a unique Reed-Solomon generator polynomial with a specific number of coefficients employed. Thus, the typical Reed-Solomon encoder creates a specific number of parity symbols, which limits its usefulness if greater or fewer parity symbols are desired. Likewise, Reed-Solomon decoders are employed to correct errors in the transmission using the same specific number of parity symbols which limits its usefulness in the same manner.
SUMMARY OF THE INVENTION
The present invention provides a configurable Galois field computation system and method that addresses the above concerns. Broadly stated, the configurable Galois field computation system comprises a read bus and a write bus with a memory coupled therebetween. In addition, a logical circuit is coupled between the read and write busses, the logical circuit having a number of data calculation configurations that are established to generate an n symbol codeword from a number of symbols in a syndrome array. The logical circuit is placed in the various data calculation configurations in order to perform the various operations involved with Reed-Solomon decoding.
The present invention can also be viewed as providing a method performing a number of calculations in a Galois field computation unit to generate a symbol codeword from a number of symbols in a syndrome array. The present method comprises the steps of: storing a number of data symbols in a memory; establishing at least one data calculation configuration in a logical circuit having a number of data paths, the logical circuit being coupled to the memory; applying the data symbols to the data paths to perform a data calculation based upon the data calculation configuration established; and storing a result of the data calculation in the memory.
A significant advantage of the present invention is that it is highly configurable to implement Reed-Solomon decoding for different data communications applications, etc. Specifically, the Galois field computation unit of the present invention may be configured to decode Reed-Solomon codewords having various numbers of parity symbols and data symbols. The present invention is also economical in that it requires a minimum number of logical components to implement and is power efficient, while at the same time being highly configurable. Specifically, the Galois field computation unit can be configured to perform calculations inherent in a Berlekamp-Massey algorithm, a Chien search algorithm, and a Forney algorithm, etc., in an efficient manner during different decoding phases.
Other features and advantages of the present invention will become apparent to one with skill in the art upon examination of the following drawings and detailed description. It is intended that all such additional features and advantages be included herein within the scope of the present invention.


REFERENCES:
patent: 4162480 (1979-07-01), Berlekamp
patent: 4833678 (1989-05-01), Cohen
patent: 5414719 (1995-05-01), Iwaki et al.
patent: 5446743 (1995-08-01), Zook
patent: 5712861 (1998-01-01), Inoue et al.
patent: 5818854 (1998-10-01), Meyer
patent: 5944848 (1999-08-01), Huang
patent: 5983389 (1999-11-01), Shimizu
patent: 6052815 (2000-04-01), Zook
patent: 6209114 (2001-03-01), Wolf et al.
Richard E. Blahut, “Theory and Practice of Error Control Codes,” Addison-Wesley Publishing Co., Inc., 1983 pp. 174-191.
Lin, et al., “Error Control Coding Fundamentals and Applications,” Prentice-Hall, Inc. 1983, pp. 170-176.
Whitaker, et al.,. “Reed Solomon VLSI Codec for Advanced Television,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 1, No. 2, Jun. 1991, pp. 230-236.
Kuang Yung Liu, “Architecture for VLSi Design of Reed-Solomon Decoders, ” IEEE Transactions on Computers, vol. C-33, No. 2, Feb. 1984, pp. 178-189.
Shayan, et al., “A Versatile Time-Domain Reed-Solomon Decoder,” IEEE Journal on Selected Areas in Communications, vol. 8, No. 8, Oct. 1990, pp. 1535-1542.
Todoroki et al., “Design of a Reed-Solomon Decoder Using a Digital Signal Processor (DSP)”, ITS ′90, pp. 443-445.*
Drescher et al., “VLSI Architecture for Datapath Integration of Arithmetic over GF(2m) on Digital Signal Processors”, ICASSP-97, pp. 631-634.*
Song et al., “Low-Energy Heterogeous Digit-Serial Reed-Solomon Codecs”, ICASSP-98, pp. 3049-3052.

Affiliated with

Also associated with

Rating

Galois field computation system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Galois field computation system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Galois field computation system and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2904992