Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
2000-05-01
2003-10-07
Bayard, Emmanuel (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C714S784000
Reexamination Certificate
active
06631172
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method for efficient list decoding of Reed Solomon codes and sub-codes thereof
BACKGROUND OF THE INVENTION
Algebraic geometric (AG) codes utilizing the algebraic curve theory have been developed. Reed Solomon (RS) codes are well known as a subclass of error correction AG codes for correcting errors produced in a communication channel or a storage medium at the reception side in a digital communication system and a digital storage system. The codes have been used for example in devices which deal with compact disc and satellite communication systems.
Reed-Solomon codes are defined in terms of Galois or finite field arithmetic. Both the information and the redundancy portions of such codes are viewed as consisting of elements taken from some particular Galois field. A Galois field is commonly identified by the number of elements which it contains. The elements of a Galois field may be represented as polynomials in a particular primitive field element, with coefficients in the prime subfield. The location of errors and the true value of the erroneous information elements are determined after constructing certain polynomials defined on the Galois field and finding the roots of these polynomials. Since the number of elements contained in a Galois field is always equal to a prime number, q, raised to a positive integer power, m, the notation, GF(q
m
) is commonly used to refer to the finite field containing q
m
elements. In such a field all operations between elements comprising the field, yield results which are each elements of the field.
Decoding methods for RS and AG codes have been described, for example, decoding methods have been described which decode RS codes and AG codes up to a designed error correction bound, such as the error-correction bound (d−1)/2 of the code in which d is the minimum distance of the code. See G. L. Feng and T. R. N. Rao, “Decoding Algebraic-geometric Codes up to the Designed Minimum Distance,” IEEE Trans. Inform. Theory, 39:37-45, 1993.
List decoding algorithms have been developed to provide decoding of RS codes beyond the error correction bound. Given a received encoded word and an integer l, this algorithm returns a list of a size at most l of codewords which have distance at most e from the received word, where e is a parameter depending on l and the code. See M. Sudan, “Decoding of Reed-Solomon Codes Beyond the Error-correction Bound,” J. Compl., 13:180-193, 1997. List decoding has been extended to AG codes using an interpolation scheme and factorization of polynomials over algebraic function fields in polynomial time. See M. A. Shokrollahi and H. Wasserman, “List Decoding of Algebraic-geometric Codes”, IEEE Trans. Inform. Theory, 45:432-437, 1999. The list decoding process for AG codes consists of a first step of computing a non-zero element in the kernel of a certain matrix and a second step of a root finding method. It is desirable to provide an improved method for efficient list decoding of RS codes and subcodes thereof.
SUMMARY OF THE INVENTION
The present invention relates to a method and apparatus for efficient list decoding of Reed-Solomon error correction codes. A polynomial for a predetermined target list size combining points of an error code applied to a message and points of a received word is determined for a k dimensional error correction code by a displacement method. The displacement method finds a nonzero element in the kernel of a structured matrix which determines the polynomial. From roots of the polynomial, it is determined if the number of errors in the code word is smaller than a predetermined number of positions for generating a list of candidate code words meeting the error condition. In one embodiment, parallel processing is used for executing the displacement method. The invention will be more fully described by reference to the following drawings.
REFERENCES:
patent: 4276646 (1981-06-01), Haggard et al.
patent: 4633470 (1986-12-01), Welch et al.
patent: 5535140 (1996-07-01), Iwamura
patent: 5600659 (1997-02-01), Chen
patent: 5642367 (1997-06-01), Kao
patent: 5818854 (1998-10-01), Meyer
patent: 5822336 (1998-10-01), Weng et al.
patent: 5944848 (1999-08-01), Huang
patent: 6199188 (2001-03-01), Shen et al.
patent: 6317858 (2001-11-01), Cameron
patent: 6345376 (2002-02-01), Cox et al.
patent: 6357030 (2002-03-01), Demura et al.
patent: 6449746 (2002-09-01), Truong et al.
Gui-Liang Feng and T.R.N. Rao “Decoding Algebraic-Geometric Codes up to the Designed Minimum Distance” IEEE Transactions on Information Theory, vol. 39, No. 1, Jan. 1993.
M. Amin Shokrollahi, et al., “List Decoding of Algebraic-Geometric Codes” Decoding AG-Codes.
Madhu Sudan, “Decoding of Reed Solomon codes beyond the error-correction bound”.
Olshevsky Vadim
Shokrollahi Mohammad Amin
Bayard Emmanuel
Lucent Technologies - Inc.
LandOfFree
Efficient list decoding of Reed-Solomon codes for message... 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 list decoding of Reed-Solomon codes for message..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient list decoding of Reed-Solomon codes for message... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3170262