Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-02-04
2003-06-03
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06574772
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to communication systems employing polynomial-generated error-correction encoding, and more particularly relates to encoding and decoding techniques for reducing the number of logic gates used in such systems.
Polynomial-generated error-correction coding, such as Reed-Solomon coding, requires encoders and decoders with many gates. Most of the gates are allocated to Galois field multiplier structures. By using certain field polynomials for the Galois field multiplier structures, the number of gates can be reduced. However, the field polynomial which enables gate reduction is frequently incompatible with other parts of the encoder or decoder system which are made with commercially available parts. As a result, there is a need for a system of converting a code compatible with one field polynomial to a code compatible with another field of polynomial which enables a reduction in the number of gates used in the encoders or decoders. This invention addresses the problem and provides a solution.
BRIEF SUMMARY OF THE INVENTION
The preferred embodiment is useful on a communication system employing polynomial-generated error-correction coding using encoders and decoders which comprise logic gates. In such an environment, according to a first embodiment of the invention, code words of a first form compatible with a first field polynomial selected to reduce the number of the logic gates are generated, preferably by an encoder. Code words of a second form compatible with a second field polynomial are decoded, preferably by a decoder. The code words of the first form are converted to code words of the second form before the code words of the second form are decoded.
According to a second embodiment of the invention, code words of a first form compatible with a first field polynomial are generated, preferably by an encoder. Code words of a second form compatible with a second field polynomial selected to reduce the number of logic gates are decoded, preferably by a decoder. The codes words of the first form are converted to code words of the second form before the code words of the second form are decoded by the decoder.
Using the foregoing techniques, systems employing field polynomials selected to reduce the number of logic gates can be made compatible with systems also employing encoders or decoders that use other field polynomials. As result, polynomial-generated error-correction coding systems can be customized to increase efficiency and reduce overall costs.
REFERENCES:
patent: 4777635 (1988-10-01), Glover
patent: 5130990 (1992-07-01), Hsu et al.
patent: 5272661 (1993-12-01), Raghavan et al.
patent: 5291496 (1994-03-01), Andaleon et al.
patent: 5377207 (1994-12-01), Perlman
patent: 5396502 (1995-03-01), Owsley et al.
patent: 5787099 (1998-07-01), Lan et al.
patent: 6263471 (2001-07-01), Huang
patent: 6343305 (2002-01-01), Ko.cedilla. et al.
patent: 6378104 (2002-04-01), Okita
McGregor et al., “Implementing the Reed-Solomon Code: A Case Study”, IEE Colloquium on Signal Processing Applications of Finite Field Mathematics, Jun. 1989, pp. 7/1-7/8.*
Paar et al., “Comparison of Arithmetic Architectures for Reed-Solomon Decoders in Reconfigurable Hardware”, Proceedings 5th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Apr. 1997, pp. 219-225.*
Furness et al., “Generalised Triangular Basis Multipliers for the Design of Reed-Solomon Codecs”, 1997 IEEE Workshop on Signal Processing Systems, Nov. 1997, pp. 202-211.*
Furness et al., “GF(2 m) Multiplication over Triangular Basis for Design of Reed-Solomon Codes”, IEE Proceedings—Computers and Digital Technology, vol. 145, No. 6, Nov. 1998, pp. 437-443.*
Paar, Christof; Fleischmann, Peter; Roelse, Peter; “Efficient Multiplier Architectures for Galois Fields GF(24n)”, IEEE Transactions on Computers, vol. 47, No. 2, Feb. 1998.
Baker Stephen M.
McAndrews Held & Malloy Ltd.
Northrop Grumman Corporation
LandOfFree
Efficient galois field multiplier structures for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient galois field multiplier structures for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient galois field multiplier structures for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3141500