Efficient list decoding of Reed-Solomon codes for message recovery in the presence of high noise levels

摘要

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.