Abstract:
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.

Description:
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. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates a schematic diagram of the configuration of an apparatus for decoding Reed-Solomon error correcting codes  10 . 
     FIG. 2 is a flowchart illustrating a decoding procedure of a decoding processing unit used in the apparatus of FIG.  1 . 
     FIG. 3 illustrates a flow diagram for determining a polynomial h(x, y). 
     FIG. 4 is a flow diagram for computing a matrix GεGF(q) m×r . 
     FIG. 5 is a flow diagram of a displacement method. 
     FIG. 6 is a schematic diagram of the configuration of an apparatus including parallel processing for decoding error correcting codes. 
     FIG. 7 is a flow chart illustrating a decoding procedure of a decoding processing unit in the apparatus of FIG.  6 . 
     FIG. 8 is a flow diagram of a displacement method for parallel processing. 
    
    
     DETAILED DESCRIPTION 
     Reference will now be made in greater detail to a preferred embodiment of the invention, an example of which is illustrated in the accompanying drawings. Wherever possible, the same reference numerals will be used throughout the drawings and the description to refer to the same or like parts. 
     FIG. 1 illustrates a schematic diagram of an apparatus for decoding error correction codes  10 . The error correction codes can be Reed-Solomon codes and subcodes thereof. Input unit  12  includes a reception device for receiving data from for example a satellite broadcast or a communication network, a reading circuit for reading data from a storage medium such as a CD (compact disc) and received words input corresponding to image data or voice data. Decoding processing unit  14  decodes the received words input to input unit  12 . Output unit  16  outputs decoded data and can include a display for displaying image data, a speaker for outputting decoded voice data, and the like. 
     A decoding procedure of a Reed Solomon (RS) code C can be used in decoding processing unit  14 . In this decoding procedure, the code word received at input unit  12  is represented by a k-dimensional Reed-Solomon code C corresponding to a set of points (x, . . . , x m ) in a Galois field GF(q) represented by the set of all vectors of the form (f(x 1 ), . . . , f(x m )) where f ranges over all polynomials of degree less than k with coefficients in GF(q). The decoding procedure is a list decoder of distance e for the RS code C which takes as input any m dimensional vector (y 1 , . . . , y m ) of a received word with coefficients in GF(q) and outputs all vectors in RS code C which differ in at most e positions from (y 1 , . . . , y m ). A list decoder can be designed given target list size l, and the vector (y 1 , . . . , y m ), from a polynomial h(x, y)=h 1 (x)+h 2 (x)y+ . . . +h l+1 (x)y l  such that h(x i , y i )=0 for all i=1, . . . , m, and deg(h i (x))&lt;b−(i−l)k where b is the smallest integer that is larger than          m     l   +   1       +       lk   2     .                            
     Accordingly, any Reed-Solomon vector (f(x 1 ), . . . , f(x m )) which differs from (y 1 , . . . , y m ) in at most        e   :=         m                 l       l   +   1       +     lk   2     -   1                            
     positions has the property that h(x, f(x))=0. 
     FIG. 2 illustrates a flow diagram of a decoding procedure of the k-dimensional Reed-Solomon code C. In step  21 , the polynomial          h        (     x   ,   y     )       =       ∑     i   =   1       l   =   1                h   i          (   x   )            y     i   -   1                                  
     is constructed from input of positive integers target list size l and k, vectors (x 1 , . . . , x m ) and (y 1 , . . . , y m ) with entries in GF(q) such that the x i  are pairwise distinct and nonzero by a displacement method described below and 1≦k≦m−l. 
     FIG. 3 illustrates a flow diagram of a method for implementation of step  21 . Step  31  applies input comprising points (x 1 , y 1 ), . . . , (x m , y m ) over GF(q) where the x i  are pairwise distinct and nonzero, and integers d 1 , d 2 , . . . , d r  such that            ∑     i   =   1     r          d   i       =     m   +   1                            
     Step  32  computes matrix G=(g ij )εGF(q) mxr  wherein r=l+1. FIG. 4 illustrates a flow diagram for the implementation of step  32 . In step  40 , the first element of row i is determined. In step  41 , x i   d     1     −1  is computed. In step  42  y i   i−2  is computed. In step  43 , x i   d     j     −1  is computed. In step  44 , g ij  is computed. In step  45 , y is updated. Steps  41 - 45  are repeated to m. Accordingly, the output is the matrix:              G   =       (     g   ij     )     =     (           1   /     x   1                 y   1     /     x   1       -     x   1       d   1     -   1             ⋯           y   1     r   -   2            (         y   1     /     x   1       -     x   1       d     r   -   1       -   1         )                 1   /     x   2                 y   2     /     x   2       -     x   2       d   1     -   1             ⋯           y   2     r   -   2            (         y   2     /     x   2       -     x   2       d     r   -   1       -   1         )               ⋮       ⋮       ⋰       ⋮             1   /     x   m                 y   m     /     x   m       -     x   m       d   1     -   1             ⋯           y   m     r   -   2            (         y   m     /     x   m       -     x   m       d     r   -   1       -   1         )             )               (   1   )                                
     Referring to FIG. 3, in step  33 , the matrix B=(b ij )εGF(q) r×m+1  is computed, where b ij =1 if j=d 1 + . . . +d i−1 +1, and b ij =0, otherwise as              B   =           (         1       0       0       ⋯       0           0       0       0       ⋯       0           0       0       0       ⋯       0           ⋮       ⋮       ⋮       ⋰       ⋮           0       0       0       ⋯       0           0       0       0       ⋯       0                  d   1                           0       0       0       ⋯       0           1       0       0       ⋯       0           0       0       0       ⋯       0           ⋮       ⋮       ⋮       ⋰       ⋮           0       0       0       ⋯       0           0       0       0       ⋯       0                       d   1                     ⋯                                0       0       0       ⋯       0           0       0       0       ⋯       0           0       0       0       ⋯       0           ⋮       ⋮       ⋮       ⋰       ⋮           1       0       0       ⋯       0           0       0       0       ⋯       0                       d     r   -   1                        0       0       0       ⋯       0           0       0       0       ⋯       0           0       0       0       ⋯       0           ⋮       ⋮       ⋮       ⋰       ⋮           0       0       0       ⋯       0           1       0       0       ⋯       0         )            d   r                   (   2   )                                
     In step  34 , a displacement method is applied for the input m, r, 1/x 1 , . . . , 1/x m , G, B to determine an output vector represented as v:=(v 1 , v 2 , . . . , v m+1 ) T . The objective is to compute a polynomial          h        (     x   ,   y     )       =       ∑     i   =   1     r              h   i          (   x   )            y     i   -   1                                  
     such that deg(h i (x))&lt;d i  and h(x i , y i )=0 for i=1, . . . , m. This problem can be phrased as that of computing an element in the kernel of a certain matrix. 
     In general, the task solved by the displacement method is the following: if V is a matrix over the field GF(q) having m rows and m+1 columns, given as the solution to the equation:                        (           x   1         0       ⋯       0           0         x   2         ⋯       0           ⋮       ⋮       ⋰       ⋮           0       0       ⋯         x   m           )            =   D         ·   V     -     V   ·       (         0       1       0       ⋯       0           0       0       1       ⋯       0           ⋮       ⋮       ⋮       ⋰       ⋮           0       0       0       ⋯       1           0       0       0       ⋯       0         )            =   Z             =     G   ·   B       ,           (   3   )                                
     where the x i  are pairwise different and nonzero elements of GF(q), then a nonzero vector v is determined such that V·v=0. It is assumed that the only nonzero entry in the first row of B is the (1,1)-entry. 
     The following space efficient variant can be as used in the displacement method: The matrix            V   _     :=     (         V           I         )       ,                          
     where I is the (m+1)×(m+1)-identity matrix, has the displacement structure                    (         D       0           0       A         )          V   _       -       V   _     ·   Z       =       (         G           C         )        B             (   4   )                                
     where              A   =         (         0       1       0       ⋯       0           0       0       1       ⋯       0           ⋮       ⋮       ⋮       ⋰       ⋮           0       0       0       ⋯       1           1       0       0       ⋯       0         )                   and                 C     =       (         0       0       0       ⋯       0           0       0       0       ⋯       0           ⋮       ⋮       ⋮       ⋰       ⋮           0       0       0       ⋯       0           1       0       0       ⋯       0         )     .               (   5   )                                
     Applying the displacement method to {overscore (V)} then recovers in an iterative fashion matrices D s , Z s , C s , G s , and B s , s=0, 1, . . . , such that                    (           D   s         0           0       A         )            V   _     s       -         V   _     s     ·     Z   s         =       (           G   s               C   s           )          B   s               (   6   )                                
     where {overscore (V)} s  is the Schur-complement of the matrix {overscore (V)} s−1  with respect to the (1,1)-entry. 
     FIG. 5 is a flow diagram illustrating a displacement method  50  which can be used to determine a nonzero element in the kernel of matrix V. In step  51 , input is applied as positive integers, m, r, pairwise distinct nonzero elements (x 1 , . . . , x m ) in GF(q), matrices G=(g ij )εGF(q) m×r  and B=(b ij )εGF(q) r×(m+1) , such that the only nonzero entry in the first row of B is the (1,1)-entry. 
     In step  52 , an integer index s is set to zero. In step  53 , a loop from k=1 to m is performed to determine vector τ k  representing a first column of the matrix. In step  54 , it is determined if the first m−s entries are equal zero. If the result of step  54  is affirmative, step  55  is performed and a nonzero vector vεGF(q) m+1  such that V·v=0 for the matrix V is outputted. The output vector v is given as (c m−s+1 , . . . , c m , 1, 0, . . . , 0) T , where c m−s+1 , . . . , c m  are entries m−s+1, . . . , m of the first column of {overscore (V)} s . Because of the special structure of the matrices involved, c m−s+1  is the (1,1)-entry of the matrix B s , and the remaining c&#39;s equal the τ&#39;s. If the result of step  54  is negative, such that the first m−s entries of the first column of {overscore (V)} s  are not all zero, pivoting is performed in step  56  to exchange the first entry with the first nonzero entry, among the first m−s entries of the first column, as represented as the k th  entry wherein 1≦k≦m−s. Specifically, x 1  and x k , τ 1  and τ k  and g lt  and g kt  are interchanged for t=1, . . . , r. This corresponds to a multiplication of {overscore (V)} s  with a permutation matrix, which results in exchanging the first and the k th  row of G s  and exchanging the first and k th  diagonal entries of D s . 
     Step  57  computes the first column of {overscore (V)} s . Step  58  computes the first row of {overscore (V)} s  for recovering the matrices G s−1  and B s−1 . Steps  59  and  60  then update the matrices G s+1  and B s+1  using the elimination step of the displacement approach. Step  61  updates D s+1  by deleting its (1,1)-entry and increases index s. Step  61  returns to step  53 . 
     Accordingly, if h i (x):=h i0 +h i1 x+ . . . +h i,d     i     −1 x d     i     −1 , V·v=0, where              V   :=     (           1         x   1         ⋯         x   1       d   1     -   1               1         x   2         ⋯         x   2       d   1     -   1               ⋮       ⋮       ⋰       ⋮           1         x   m         ⋯         x   m       d   1     -   1                          y   1             y   1          x   1           ⋯           y   1          x   1       d   2     -   1                   y   2             y   2          x   2           ⋯           y   2          x   2       d   2     -   1                 ⋮       ⋮       ⋰       ⋮             y   m             y   m          x   m           ⋯           y   m          x   m       d   2     -   1                          ⋯           ⋯           ⋰           ⋯                    y   1     r   -   1               y   1     r   -   1            x   1           ⋯           y   1     r   -   1            x   1       d   r     -   1                   y   2     r   -   1               y   2     r   -   1            x   2           ⋯           y   2     r   -   1            x   2       d   r     -   1                 ⋮       ⋮       ⋰       ⋮             y   m     r   -   1               y   m     r   -   1            x   m           ⋯           y   m     r   -   1            x   m       d   r     -   1                     )             (   7   )                                v :=( h   10   , h   11   , . . . h   1,d     i     −1   |h   20   , h   21   , . . . h   2,d     2     −1   | . . . |h   r0   , h   r1   , . . . h   r,d     r     −1 ) T   (8) 
     To find a nonzero element in the kernel of V, the following displacement structure for V can be determined:                      (           1   /     x   1           0       ⋯       0           0         1   /     x   2           ⋯       0           ⋮       ⋮       ⋰       ⋮           0       0       ⋯         1   /     x   m             )     ·   V     -     V   ·     (         0       1       0       ⋯       0           0       0       1       ⋯       0           ⋮       ⋮       ⋮       ⋰       ⋮           0       0       0       ⋯       1           0       0       0       ⋯       0         )         =     G   ·   B       ,           (   9   )                                
     where G and B are the matrices defined in steps  32  and  33 . 
     Referring to FIG. 3, in step  35 , vector v is transformed into polynomial h(x, y) where deg(h i (x))&lt;d i  and h(x i , y i )=0 for i=1, . . . , m by            ∑     i   =   1     r              h   i          (   x   )            y     i   -   1           ,                          
     where 
     
       
           h   2 ( x )= v   1   +v   2   x+ . . . +v   d     1     x   d     1     −1   
       
     
     
       
           h   2 ( x )= v   d     1     +1   +v   d     1     +2   x+ . . . +v   d     1     +d     2     x   d     2     −1   
       
     
     
       
         . 
       
     
     
       
         . 
       
     
     
       
         . 
       
     
     
       
           h   r ( x )= v   d     1     + . . . +d     r−1     +1   +v   d     1     + . . . +d     r−1     +2   x+ . . . +v   d     1     + . . . +d     r−1     + . . . +d     r     x   d     r     −1 .  (10) 
       
     
     Referring to FIG. 2 in step  22 , all polynomials f(x) of degree less than k with coefficients in GF(q) are computed such that h(x, f(x))=0 which can be determined, as described in S. Ar, R. Lipton, R. Rubinfeld, and M. Sudan, “Reconstructing Algebraic Functions from Mixed Data, In Proc. 33 rd  FOCS, pages 503-512, 1992. In step  23 , vectors (f(x 1 ), . . . , f(x m )) are output which differ from (y 1 , . . . , y m ) in a predetermined number of positions. The predetermined number of positions can be          m     l   -   1       +     lk   2     -   1.                          
     FIG. 6 represents a schematic diagram of an apparatus for error correction codes using parallel processors  70 . Decoding processing unit  74  includes a number P of processors  75  that can access the same memory locations. Decoding of RS code C as described in steps  21 - 23  is performed with accounting for parallel processing as described below. 
     FIG. 7 illustrates a method for implementation of step  21  with parallel processors. In step  81 , m different nonzero values (z 1 , . . . , z m ) are chosen in GF(q) such that z i ≠1/x j  for i≠j. In step  82 , if GF(q) does not contain these elements, GF(q) is extended to GF(q 2 ). 
     In step  83 , the matrix G=(g ij ) is computed in parallel assigning the computation of each row to a different processor as:              G   =       (     g   ij     )     =     (           1   /     x   1                 y   1     /     x   1       -     x   1       d   1     -   1             …           y   1     r   -   2                       (         y   1     /     x   1       -     x   1       d     r   -   1       -   1         )               -     y   1     r   -   1                         x   1     d     r   -   1                     1   /     x   2                 y   2     /     x   2       -     x   2       d   1     -   1             …           y   2     r   -   2                       (         y   2     /     x   2       -     x   2       d     r   -   1       -   1         )               -     y   2     r   -   1                         x   2     d     r   -   1                   ⋮       ⋮       ⋱       ⋮                         1   /     x   m                 y   m     /     x     m                    -     x   2       d   1     -   1             …           y   m     r   -   2                       (         y   m     /     x   m       -     x   m       d     r   -   1       -   1         )               -     y   m     r   -   1                         x   m     d     r   -   1                 )               (   11   )                                
     In step  84 , the matrix B is determined from input (x 1 , . . . , x m ) in GF(q), positive integers D 1 &lt;D 2 &lt; . . . &lt;D r−1 , with D 1 :=d 1 , D 2 :=d 1 +d 2 , . . . , D r−1 :=d 1 + . . . +d r−1 , and an integer m. 
     Matrix B is computed in parallel by assigning computation of each column to a different processor as              B   =     (         1       1       …       1       1             z   1     D   1             z   2     D   1           …         z   m     D   1           0           ⋮       ⋮       ⋱       ⋮       ⋮             z   1     D     r   -   1               z   1     D     r   -   2             …         z   m     D     r   -   1             0             z   1   m           z   2   m         …         z   m   m         0         )             (   12   )                                
     In step  85 , a displacement method is applied to input m, r, 1/x 1 , . . . , 1/x m     1   , z 1 , z 2 , . . . , z m , G, B to determine vector V as output. 
     In general, the task of the displacement method is the following: if V is a matrix over the field GF(q) having m rows and m+1 columns, given as the solution to the equation                        (           x   1         0       …       0           0         x   2         …       0           ⋮       ⋮       ⋱       ⋮           0       0       …         x   m           )            =   D         ·   V     -     V   ·       (           z   1         0       0       …       0       0           0         z   2         0       …       0       0           ⋮       ⋮       ⋮       ⋱       ⋮       ⋮           0       0       0       …         z   m         0           0       0       0       …       0       0         )            =   Z             =     G   ·   B       ,           (   13   )                                
     where the x i , z j  are pairwise different and nonzero elements of GF(q) and x i ≠z j , for i≠j, then a nonzero vector v is determined such that V·v=0. 
     The following space efficient variant can be used in the displacement matrix. The matrix            V   _     :=     (         V           I         )       ,                          
     where I is the (m+1)×(m+1)-identity matrix, has the displacement structure                    (         D       0           0       Z         )     ·     V   _       -       V   _     ·   Z       =       (         G           0         )                   B             (   14   )                                
     Applying the displacement method to {overscore (V)} then recovers in an iterative fashion matrices D s , Z s , C s , G s , and B s , s=0, 1, . . . , such that                    (           D   s         0           0       Z         )     ·       V   _     s       -         V   _     s     ·     Z   s         =       (         G           0         )                     B   s               (   15   )                                
     where {overscore (V)} s  is the Schur complement of the matrix {overscore (V)} s−1  with respect to the (1,1)-entry. If m s  denotes m−s, then D r εGF(q) m     s     ×m , Z s εG(q) (m     s     +1)×(m     s     +1) ,G s εGF(q) m     s     ×r , and B s εGF(q) r×(m     s     +1) . 
     FIG. 8 illustrates a flow diagram of displacement method  100  which can be used to determine a nonzero element in the kernel of matrix V. In step  101 , input m, r, 1/x 1 , . . . , 1/x m , z 1 , . . . , z m , G, B is applied. In step  102 , an integer index s is set to zero. In step  103 , a loop from k=1 to m is performed in parallel to determine vector τ k , representing a first column of the matrix. In step  104 , it is determined if the first m−s entries are equal to zero. If the result of step  104  is affirmative then step  105  is performed and a nonzero vector vεGF(q) m+1  such that V·v=0 for the matrix V is outputted. The output vector v is given as (c m−s+1 , . . . , c m , 1, 0, . . . , 0) T , where c m−s+1 , . . . , c m  are entries m−s+1, . . . , m of the first column of {overscore (V)} s . If the result of step  104  is negative, pivoting is performed in step  106  to exchange the first entry with the first nonzero entry, among the first m−s entries of the first column, as represented as the k th  entry whereon 1≦k≦m−s. This corresponds to a multiplication of {overscore (V)} s  with a permutation matrix, which results in exchanging the first and the k th  row of G s . 
     To retain the above described displacement structure, the same permutation matrix is multiplied from the right, which results in exchanging the first and the k th  column of B s , to recover the matrices G s+1  and B s+1 , the first row and the first column of {overscore (V)} s  is computed in parallel in steps  107 ,  108  and  109 . Steps  110  and  111  update the matrices G s+1  and B s+1  using the elimination step of the displacement approach. Step  112  updates D s+1  and Z s+1  by deleting their (1,1)-entry and returns to step  103 . 
     Referring to FIG. 7, in step  85  the displacement structure is determined for V·W T  since matrix V does not have the needed displacement for the displacement method where W is                W:=          (         1         z   1           z   1   2         …         z   1   m             1         z   2           z   2   2         …         z   2   m             1         z   3           z   3   2         …         z   3   m             ⋮       ⋮       ⋮       ⋱       ⋮           1         z   m           z   m   2         …         z   m   m             1       0       0       …       0         )             (   16   )                                
     Then a short calculation reveals the following displacement structure for V·W T :                    (           1   /     x   1           0       …       0           0         1   /     x   2           …       0           ⋮       ⋮       ⋱       ⋮           0       0       …         1   /     x   m             )     ·   V   ·     W   T       -     V   ·     W   T     ·     (           z   1         0       …       0       0           0         z   2         …       0       0           ⋮       ⋮       ⋱       ⋮       ⋮           0       0       …         z   m         0           0       0       …       0       0         )         =     G   ·   B             (   17   )                                
     Vector w=(w 1 , . . . , w m+1 )εGF(q) m+1  is determined from parallel matrix vector multiplication on m processors such that                (           w   1               w   2               w   3             ⋮             w   m               w     m   +   1             )     =       (         1       1       1       …       1       1             z   1           z   2           z   3         …         z   m         0             z   1   2           z   2   2           z   3   2         …         z   m   2         0           ⋮       ⋮       ⋮       ⋱       ⋮       ⋮             z   1   m           z   2   m           z   3   m         …         z   m   m         0         )     ·       (           v   1               v   2               v   3             ⋮             v   m               v     m   +   1             )     .   `               (   18   )                                
     Vector v is determined as W T ·w. 
     In step  86 , the vector v is transformed into the polynomial Σ f=1   r h i (x)y t−1  where 
     
       
           h   r ( x ):= v   1   x   d     r     −1   +v   2   x   d     r     −2   + . . . +v   d     r     −1   x+v   d     r     
       
     
     
       
           h   r−1 ( x ):= v   d     r     +1   x   d     r−1     −1   +v   d     r     +2   x   d     r−1     −2   + . . . +v   d     r     +d     r−1     −1   x+v   d     r     +d     r−1     
       
     
     
       
         . 
       
     
     
       
         . 
       
     
     
       
         . 
       
     
     
       
           h   1 ( x ):= v   d     r     +d     r−1+     . . . +d     2     +1   x   d     1     −1   +v   d     r     +d     r−1     + . . . +d     2     +2   x   d     1     −2   + . . . +v   m   x+v   m+1   (19) 
       
     
     In general, the present invention provides efficient list decoding of RS codes because the method runs in a time that is proportional to l·n 2  where n is the length of the code and l is the target list size. The method is efficient in the presence of high noise levels as indicated by the assumption of a very large number of errors in the codes which are decoded. 
     It is to be understood that the above-described embodiments are illustrative of only a few of the many possible specific embodiments which can represent applications of the principles of the invention. Numerous and varied other arrangements can be readily devised in accordance with these principles by those skilled in the art without departing from the spirit and scope of the invention.