FAST COMBINED CHASE AND GMD DECODING OF GENERALIZED REED-SOLOMON CODES

Abstract

A method for soft decoding of generalized Reed-Solomon (RS) error correction codes, includes receiving a codeword through a digital electronic communication channel; verifying that an HD error-and-erasures decoding has failed; finding a Groebner basis that accounts for a fixed set of erasures; constructing a Chase and GMD decoding tree on the set of Chase coordinates and the set of GMD coordinates; traversing the decoding tree using polynomials of the Groebner basis as a basis that represents updated coefficient polynomials on the Chase and GMD decoding tree; updating polynomials on the decoding tree using root and derivate steps that flip an edge, or a root step for an erasure edge; calculating error locations by polynomial evaluation of candidate polynomials from the decoding tree, and calculating error values by using Forney's formula; and correcting the received codeword according to the calculated error locations and calculated error values.

Claims

1. A method for soft decoding of generalized Reed-Solomon (RS) error correction codes, comprising: receiving a codeword y through a digital electronic communication channel, wherein y=x+e for at least one error vector eF.sub.q.sup.n, where F.sub.q is a finite field of q elements, wherein q is a prime power, and for transmitted codeword xC, wherein C is a generalized Reed-Solomon code having a length n<=q1 configured to be shortened and a minimum Hamming distance d2; performing hard decision (HD) error-and-erasures decoding on the codeword with a fixed set of erasures; verifying that the HD error-and-erasures decoding has failed; finding a Groebner basis to a solution module that accounts for a fixed set of erasures; determining a set of Chase coordinates and a set of generalized minimum distance (GMD) coordinates using channel reliability information; constructing a Chase and GMD decoding tree on the set of Chase coordinates and the set of GMD coordinates; traversing the decoding tree depth first using polynomials of the Groebner basis as a basis that represents updated coefficient polynomials on the Chase and GMD decoding tree; updating polynomials on the decoding tree using root and derivate steps that flip an edge, or a root step for an erasure edge; calculating error locations by polynomial evaluation of candidate polynomials from the decoding tree, and calculating error values; and correcting the received codeword according to the calculated error locations and calculated error values, and saving the corrected received codeword to a decoder output list.

2. The method of claim 1, wherein performing hard decision (HD) error-and-erasures decoding with a fixed set of erasures comprises: calculating an estimated error location polynomial (ELP) v(X) that excludes erasures by performing an errors and erasures Berlekamp-Massey algorithm, wherein X is an indeterminate variable; verifying that v(X) has deg(v(X)) inverses of roots on coordinates F*.sub.q\A.sub.1 that are not fixed erasures, wherein Fa:=F*.sub.q \{0} and A.sub.1 is a set of fixed erasures, and that deg(v)=Le.sub.0.sup.(1), wherein L is an estimated order, e.sub.0.sup.(1) is a number of fixed erasures and Le.sub.0.sup.(1) is a corrected order that excludes erasures; defining .sub.1:=v; calculating an errors and fixed erasures ELP .sub.E:=.sub.1.sub.0.sup.(1), wherein .sub.0.sup.(1) is an erasure locating polynomial, and an errors and fixed erasures error evaluation polynomial (EEP) .sub.E={tilde over (S)}.sub.1 mod (X.sup.d1), wherein {tilde over (S)} is a syndrome polynomial associated with y and the set of fixed erasures; finding error values for error locations outside A.sub.1, by using Forney's formula with roots of .sub.1; and error values for error locations in A.sub.1, by using Forney's formula with the inverses of elements of A.sub.1; correcting all errors in a decoded codeword using the found error values; and outputting a corrected decoded codeword.

3. The method of claim 2, wherein verifying that the HD error-and-erasures decoding has failed comprises verifying that v(X) does not have deg(v(X)) roots on inverses of non-erased coordinates, or that deg(v)Le.sub.0.sup.(1).

4. The method of claim 1, wherein constructing a decoding tree includes assigning memory for r.sub.max+1 Groebner bases, one for each depth, where r.sub.max is a maximum designed depth, and storing the Groebner basis {(1,0), (0,1)} for a module of coefficient polynomials $N_{0,e_0^{\left(1\right)},0}$ for a case of only fixed erasures in a memory of depth 0, wherein the decoding tree includes a root that is an all zero vector in F.sub.2.sup.n, vertices that at depth r, for all r{1, . . . , r.sub.max}, are vectors of length n and weight r in F.sub.2.sup.n, and edges that are pairs (, ), wherein is a number of Chase flipping coordinates plus a number of variable GMD erasure coordinates, wherein for each vertex =(.sub.1, . . . , .sub.)F.sub.2.sup.n at depth r with non-zero entries at coordinates i.sub.1, . . . , i.sub.r, a single vertex =(.sub.1, . . . , .sub.n) is selected at depth r1 that is equal to on all coordinates, except for one additional flipped or erased coordinate , {1, . . . , r} in an edge, for which =0.

5. The method of claim 1, wherein traversing the decoding tree depth first comprises updating a Groebner basis read from a memory of a previous depth when moving on an edge that corresponds to one additional variable erasure or one additional Chase flip, wherein the updated Groebner basis is stored in memory.

6. The method of claim 5, wherein updating the Groebner basis read from the memory of the previous depth comprises using Koetter's iteration that deletes an additional coordinate when moving on an edge that corresponds to one additional variable erasure or using a pair of Koetter's iterations when moving on an edge that corresponds to a Chase flip on an additional coordinate.

7. The method of claim 1, the method further comprising: verifying that, during an update of the Groebner basis, a stopping condition holds; outputting that the stopping condition was falsely positive, and returning to the depth-first search of the tree, when a number of roots of {circumflex over ()} whose inverses are not on a fixed or variable erasure is not deg({circumflex over ()})e.sub.0.sup.(2), wherein {circumflex over ()} is a set of estimated errors and variable erasures ELP, and e.sub.0.sup.(2) is a number of variable erasures.

8. The method of claim 1, the method further comprising: verifying that, during an update of the Groebner basis, a stopping condition holds; outputting that the stopping condition was falsely positive, and returning to the depth-first search on the tree, when at least one of error values found on coordinates with locators in the non-erased coordinates F*.sub.q\(A.sub.1 A.sub.2) equal 0, wherein F*.sub.q:=F.sub.q \{0}, A.sub.1 is a set of fixed erasures and A.sub.2 is a current hypothesis of variable erasures.

9. The method of claim 1, wherein calculating error locations by polynomial evaluation of candidate polynomials from the decoding tree, and calculating error values by using Forney's formula, comprises: verifying that a valid pair of an EEP and an ELP has been found by checking that a number of ELP roots equals its degree minus a number of variables erasures, and the inverses of all roots are outside a fixed erasure set, finding error values on non-erased coordinates using Forney's algorithm with the EEP and ELP, and checking that no estimated error value on a non-erased coordinate is zero; calculating an estimated errors and erasures ELP ={circumflex over ()}.Math..sub.0.sup.(1), wherein {circumflex over ()} is a set of estimated errors and variable erasures ELP and .sub.0.sup.(1) is a fixed erasures ELP, and finding error values only on coordinates with locators in F*.sub.q\(A.sub.1 A.sub.2) by using Forney's formula, wherein F=F.sub.q \{0}, A.sub.1 is a set of fixed erasures and A.sub.2 is a current hypothesis of variable erasures and calculating error values for all e.sub.0.sup.(1)+e.sub.0.sup.(2) erased coordinates by using Forney's formula, wherein e.sub.0.sup.(2) is a number of variable erasures.

10. The method of claim 9, wherein finding all the roots of {circumflex over ()} on inverses of elements from F*.sub.q\(A.sub.1A.sub.2) comprises: evaluating and storing values of h.sub.01(), h.sub.11(), h.sub.01(), and h.sub.11() for all coordinates F*.sub.q, wherein h.sub.01 and h.sub.11 are second polynomials from of the Groebner basis of the solution module for an errors and fixed erasures key equation; calculating {circumflex over ()} ()=f.sub.10().Math.h.sub.01()+f.sub.11().Math.h.sub.11() for a new set of estimated errors {circumflex over ()}, wherein f.sub.10 and f.sub.11 are individual polynomials from the current Groebner basis for the solution module of coefficient polynomials; and calculating a derivative of the ELP () by evaluating derivatives f.sub.10 (), f.sub.11(), and calculating () using 4 additional multiplications, using calculated and stored values and a following formula for an estimated value of (X): ${\stackrel{}{}}^{}\left(X\right)=f_{10}\left(X\right)h_{01}^{}\left(X\right)+f_{10}^{}\left(X\right)h_{01}\left(X\right)+f_{11}\left(X\right)h_{11}^{}\left(X\right)+f_{11}^{}\left(X\right)h_{11}\left(X\right).$

11. A digital electronic circuit, tangibly embodying a program of instructions executed by the digital electronic circuit to perform method steps for soft decoding of generalized Reed-Solomon (RS) error correction codes, the method steps comprising: receiving a codeword y through a digital electronic communication channel, wherein y=x+e for at least one error vector eF.sub.q.sup.n, where F.sub.q is a finite field of q elements, wherein q is a prime power, and for transmitted codeword xC, wherein C is a generalized Reed-Solomon code of length n<=q1 and that is configured to be shortened and minimum Hamming distance d2; performing hard decision (HD) error-and-erasures decoding on the codeword with a fixed set of erasures; verifying that the HD error-and-erasures decoding has failed; finding a Groebner basis to a solution module that accounts for the fixed set of erasures; determining a set of Chase coordinates and a set of generalized minimum distance (GMD) coordinates using channel reliability information; constructing a Chase and GMD decoding tree on a set of Chase coordinates and the set of GMD coordinates; traversing the decoding tree depth first using polynomials of the Groebner basis as a basis that represents updated coefficient polynomials on the Chase and GMD decoding tree; updating polynomials on the decoding tree using root and derivate steps that flip an edge, or a root step for an erasure edge; calculating error locations by polynomial evaluation of candidate polynomials from the decoding tree, and calculating error values; and correcting the received codeword according to the calculated error locations and calculated error values, and saving the corrected received codeword to a decoder output list.

12. The digital electronic circuit of claim 11, wherein performing hard decision (HD) error-and-erasures decoding with a fixed set of erasures comprises: calculating an estimated error location polynomial (ELP) v(X) that excludes erasures by performing an errors and erasures Berlekamp-Massey algorithm, wherein X is an indeterminate variable; verifying that v(X) has deg(v(X)) inverses of roots on coordinates F*.sub.q\A.sub.1 that are not fixed erasures, wherein F*.sub.q:=F.sub.q \{0} and A.sub.1 is a set of fixed erasures, and that deg(v)=Le.sub.0.sup.(1), wherein L is an estimated order, e.sub.0.sup.(1) is a number of fixed erasures and Le.sub.0.sup.(1) is a corrected order that excludes erasures; defining .sub.1:=0; calculating an errors and fixed erasures ELP .sub.F:=.sub.1.sub.0.sup.(1), wherein {circumflex over ()} (is an erasure locating polynomial, and an errors and fixed erasures error evaluation polynomial (EEP).sub.E={tilde over (S)}.sub.1 mod (X.sup.d1), wherein {tilde over (S)} is a syndrome polynomial associated with y and the set of fixed erasures; finding error values for error locations outside A.sub.1, by using Forney's formula with roots of .sub.1; and error values for error locations in A.sub.1, by using Forney's formula with the inverses of elements of A.sub.1; correcting all errors in a decoded codeword using the found error values; and outputting a corrected decoded codeword.

13. The digital electronic circuit of claim 12, wherein verifying that the HD error-and-erasures decoding has failed comprises verifying that v(X) does not have deg(v(X)) roots on inverses of non-erased coordinates, or that deg(v)Le.sub.0.sup.(1).

14. The digital electronic circuit of claim 11, wherein constructing a decoding tree includes assigning memory for r.sub.max+1 Groebner bases, one for each depth, where rmax is a maximum designed depth, and storing the Groebner basis {(1,0), (0,1)} for a module of coefficient polynomials $N_{0,e_0^{\left(1\right)},0}$ for a case of only fixed erasures in a memory of depth 0, wherein the decoding tree includes a root that is an all zero vector in F.sub.2.sup.n, vertices that at depth r, for all r{1, . . . , r.sub.max}, are vectors of length n and weight r in F.sub.2.sup.n, and edges that are pairs (, ), wherein n is a number of Chase flipping coordinates plus a number of variable GMD erasure coordinates, wherein for each vertex =(.sub.1, . . . , .sub.)F.sub.2.sup.n at depth r with non-zero entries at coordinates i.sub.1, . . . , i.sub.r, a single vertex =(.sub.1, . . . , B.sub.) is selected at depth r1 that is equal to on all coordinates, except for one additional flipped or erased coordinate , {1, . . . , r} in an edge, for which =0.

15. The digital electronic circuit of claim 11, wherein traversing the decoding tree depth first comprises updating a Groebner basis read from a memory of a previous depth when moving on an edge that corresponds to one additional variable erasure or one additional Chase flip, wherein the updated Groebner basis is stored in memory.

16. The digital electronic circuit of claim 15, wherein updating the Groebner basis read from the memory of the previous depth comprises using Koetter's iteration that deletes an additional coordinate when moving on an edge that corresponds to one additional variable erasure or using a pair of Koetter's iterations when moving on an edge that corresponds to a Chase flip on an additional coordinate.

17. The digital electronic circuit of claim 11, wherein the method steps further comprise: verifying that, during an update of the Groebner basis, a stopping condition holds; outputting that the stopping condition was falsely positive, and returning to the depth-first search of the tree, when a number of roots of {circumflex over ()} whose inverses are not on a fixed or variable erasure is not deg({circumflex over ()})e.sub.0.sup.(2), wherein {circumflex over ()} is a set of estimated errors and variable erasures ELP, and e.sub.0.sup.(2) is a number of variable erasures.

18. The digital electronic circuit of claim 11, wherein the method steps further comprise: verifying that, during an update of the Groebner basis, a stopping condition holds; outputting that the stopping condition was falsely positive, and returning to the depth-first search on the tree, when at least one of error values found on coordinates with locators in the non-erased coordinates F*.sub.q\(A.sub.1 A.sub.2) equal 0, wherein F*.sub.q:=F.sub.q \{0}, A.sub.1 is a set of fixed erasures and A.sub.2 is a current hypothesis of variable erasures.

19. The digital electronic circuit of claim 11, wherein calculating error locations by polynomial evaluation of candidate polynomials from the decoding tree, and calculating error values by using Forney's formula, comprises: verifying that a valid pair of EEP and ELP has been found by checking that a number of ELP roots equals its degree minus a number of variables erasures, and the inverses of all roots are outside a fixed erasure set, finding error values on non-erased coordinates using Forney's algorithm with the EEP and ELP, and checking that no estimated error value on a non-erased coordinate is zero; calculating an estimated errors and erasures ELP :={circumflex over ()}.Math..sub.0.sup.(1), wherein {circumflex over ()} is a set of estimated errors and variable erasures ELP and .sub.0.sup.(1) is a fixed erasures ELP, and finding error values only on coordinates with locators in F.sub.q\(A.sub.1 A.sub.2) by using Forney's formula wherein F*.sub.q:=F.sub.q \{0}, A.sub.1 is a set of fixed erasures and A.sub.2 is a current hypothesis of variable erasures, and calculating error values for all e.sub.0.sup.(1)+e.sub.0.sup.(2) erased coordinates by using Forney's formula, wherein e.sub.0.sup.(2) is a number of variable erasures.

20. The digital electronic circuit of claim 19, wherein finding all the roots of {circumflex over ()} on inverses of elements from F*.sub.q\(A.sub.1A.sub.2) comprises: evaluating and storing values of h.sub.01(), h.sub.11(), h.sub.01(), and h.sub.11() for all coordinates F*.sub.q, wherein h.sub.01 and h.sub.11 are second polynomials from of the Groebner basis of the solution module for an errors and fixed erasures key equation; calculating {circumflex over ()}()=f.sub.10().Math.h.sub.01()+f.sub.11().Math.h.sub.11() for a new set of estimated errors {circumflex over ()}, wherein f.sub.10 and f.sub.11 are individual polynomials from the current Groebner basis for the solution module of coefficient polynomials; and calculating a derivative of the ELP () by evaluating derivatives f.sub.10 (), f.sub.11(), and calculating () using 4 additional multiplications, using calculated and stored values and a following formula for an estimated value of (X): ${\stackrel{}{}}^{}\left(X\right)=f_{10}\left(X\right)h_{01}^{}\left(X\right)+f_{10}^{}\left(X\right)h_{01}\left(X\right)+f_{11}\left(X\right)h_{11}^{}\left(X\right)+f_{11}^{}\left(X\right)h_{11}\left(X\right).$

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0014] FIG. 1 is a flow chart of a decoding process with a new combined fast Chase/GMD algorithm according to an embodiment.

[0015] FIG. 2 is a block diagram of a system for performing a decoding process with a new combined fast Chase/GMD algorithm, according to an embodiment of the disclosure.

[0016] FIG. 3 shows an example of a variant of the decoding tree, according to an embodiment of the disclosure.

DETAILED DESCRIPTION

[0017] Embodiments of the disclosure are directed to a new method for fast combined Chase and GMD decoding of generalized RS (GRS) codes, including RS codes as a special case. The invention builds on, and extends, previous fast Chase decoding algorithms which did not consider combining fast GMD with the fast Chase decoding.

[0018] The main soft decoding algorithms for block codes were the generalized minimum distance (GMD) decoding, and the Chase decoding algorithms. GMD decoding includes repeated applications of errors-and-erasures decoding, while successively erasing an even number of the least reliable coordinates.

[0019] In Chase decoding, there is some pre-determined list of test error patterns on the n least reliable coordinates for some small , where typically, [d/2], and d is the minimum Hamming distance of the code. For example, this list may include all possible non-zero vectors, all vectors of a low enough weight, a pre-defined number of random vectors, etc. The decoder successively runs on error patterns from the list. Each such error pattern is subtracted from the received codeword, and the result is fed to a hard-decision (HD) decoder. If the HD decoder succeeds, then its output is saved into the output list of the decoder.

[0020] Note, however, that despite the exponential nature of Chase decoding, for high-rate codes of moderate length, it is known to have a better complexity/performance tradeoff than the algebraic soft decoding. For this reason, Chase decoding of RS codes is still of great interest.

[0021] When the finite-field size q grows, the complexity of 0(q.sup.n) for Chase decoding scanning over all test error patterns from F.sub.q.sup.n, where F.sub.q is the finite field of q elements underlying the RS code, for a prime power q, becomes infeasible. For this reason, to scan only on, say, the 2 most-likely noise symbols for each coordinate. Note that by the definition of the HD symbol as the most likely symbol, one of these 2 most-likely noise symbols is always 0. Note also that this is equivalent to scanning on the 2 most likely values of the codeword coordinate.

[0022] The exponential complexity of Chase decoding is much higher than the linear complexity of GMD. However, the decoding performance of Chase decoding is typically much better than that of GMD. It is possible to combine Chase and GMD decoding: for some unreliable coordinates, the decoder runs on test error patterns (Chase), while for other unreliable coordinates, only erasure attempts are carried out (GMD).

[0023] A possible criterion for selecting the coordinates on which GMD is performed and the coordinates on which Chase is performed in combined Chase and GMD decoding appears.

[0024] For example, the set I.sub.chase of .sub.chase coordinates on which Chase trials are performed can be defined by taking the .sub.chase coordinates i {0, . . . , n1} for which

[00002]${}_i^{\left(1\right)}:=\log \frac{p\left(r_i|s_i\left(1\right)\right)+{.Math.}_{j=M+1}^{q}p\left(r_i|s_i\left(j\right)\right)}{{.Math.}_{j=2}^{M}p\left(r_i|s_i\left(j\right)\right)}$

takes the .sub.chase lowest values, where (r.sub.0, . . . , r.sub.n1) is the channel output, s.sub.i(j) is the j-th most likely symbol for the i-th received coordinate, where i{0, . . . , n1} and j{1, . . . , q}, and M is the number of most likely symbols considered in a Chase coordinate, typically, M=2. In addition, the set I.sub.GMD of .sub.GMD coordinates on which GMD decoding is performed can also be defined by taking those coordinates i outside the above .sub.chase coordinates for which

[00003]${}_i^{\left(2\right)}:=\log \frac{p\left(r_i|s_i\left(1\right)\right)}{{.Math.}_{j=2}^{q}p\left(r_i|s_i\left(j\right)\right)}$

takes the .sub.GMD lowest values.

[0025] To get an intuitive idea on such criterions, recall that in a possible simplified Chase decoding, only the 2 most likely symbols out of q possible symbols are scanned. This method is reasonable if the posterior probabilities of the remaining q2 symbols are (loosely speaking) considerably smaller than those of the 2 most likely symbols.

[0026] If, for example, in some coordinate, all q1 symbols other than the HD symbol, which is the most likely symbol, have similar posterior probabilities, then there is no clear choice for the second most likely symbol in the coordinate. If such a coordinate is considered unreliable, it is better to try to erase it than to search over all q1 potential replacements.

[0027] In fast Chase decoding algorithms, the decoder shares computations between HD decodings of different test error patterns. For example, if two test error patterns differ on a single coordinate, it seems reasonable that there is no need to go through all steps of HD decoding twice. Similarly, in fast GMD algorithms, whenever additional erasures are added, instead of starting an entirely new errors-and-erasures decoding, the decoder uses the previous decoding output as a starting point.

[0028] Embodiments of the disclosure support two types of erasures: (1) Static erasures, present throughout all Chase and GMD trials, such as in the context of decoding GCC codes, static erasures correspond to detected errors in row codes, and (2) Dynamic erasures, added in the GMD decoding. The reason for supporting two types of erasures is for maximizing the efficiency of an algorithm according to an embodiment. Loosely speaking, static erasures are taken out of updated polynomials to avoid updating polynomials of high degree, especially when the number of static erasures is high, and then taken back into account at the end of the combined Chase/GMD process.

[0029] Embodiments of the disclosure make use of update rules: given an error locator polynomial (ELP) updated for GMD erasures and Chase-modified coordinates so far, embodiments of the disclosure provide a low-complexity method to update the ELP for the next GMD erasure/Chase-modified coordinate. The fast combined Chase and GMD decoding then arranges the scanned errors/erasures on a tree, described below, and uses the update rules on the edges of the tree.

GRS Codes and the Key Equation

[0030] Let q be a prime power, and let F.sub.q be the finite field of q elements. Consider a primitive generalized Reed-Solomon code (GRS) code, C, of length :=q1 and minimum Hamming distance d2. For example, let =(.sub.0, . . . , .sub.n1)(F*.sub.q).sup.n be a vector of non-zero elements (where F*.sub.q:=Fa \{0}). For a vector f=(f.sub.0, . . . , f.sub.n1)F.sub.q.sup.n, let f(X):=f.sub.0+f.sub.1X+ . . . +f.sub.n1X.sup.n1 F.sub.q[X]. Now C.Math.F.sub.q.sup.n is defined as the set of all vector fF.sub.q.sup.n for which (X)f(X) has roots 1, , . . . , .sup.d2 for some fixed primitive F.sub.q, where () stands for coefficient-wise multiplication of polynomials. Note that when .sub.0=.sub.1= . . . =.sub.n1, C is a Reed-Solomon (RS) code. Note also that there is no loss of generality in considering a primitive GRS code, as the more general case may be obtained by shortening a primitive GRS code. In the remainder of this document, will be referred to as the GRS scaling vector.

[0031] To recall the key equation, suppose that a codeword xC is transmitted, and the received codeword is y=x+e for at least one error vector eF.sub.q.sup.n. For j{0, . . . , d2}, let S.sub.j=s.sub.j.sup.(y):=((X)y(X))(.sup.j). The syndrome polynomial associated with y is S.sup.(y)(X):=S.sub.0+S.sub.1X+ . . . +S.sub.d2x.sup.d2. By the definition of the GRS code, the same syndrome polynomial is associated with e.

[0032] A full set of error locaters for e is a subset E.Math.F*q such that for all i{0, . . . , n1},

isupp(e).Math..sup.iE,

where supp(e):={i {0, . . . , n1}|e.sub.i0}. So, for E to be a full set of error locators, it must contain all field elements pointing to error locations, and it is also allowed to contain additional elements. For example, E=F*.sub.q is always a full set of error locators, but it is not a useful one, as will be clear below.

[0033] Let & be the total number of errors, i.e., the number of non-zero coordinates in e. Let E={a.sub.1, . . . , a.sub.}.Math.F.sub.q be a full set of error locators, where , and let the corresponding (possibly zero) error values be .sub.1, . . . , B.sub.F.sub.q. Define the error locator polynomial (ELP) associated with E, .sub.E (X)F.sub.q [X] by setting .sub.E(X):=.sub.i=1.sup.(1a.sub.iX), and the error evaluator polynomial (EEP) associated with E, .sub.E (X) E F.sub.q [X], by setting .sub.E (X)=.sub.i=1.sup..sub.ia.sub.i .sub.ji (1a.sub.jX), where a.sub.i:=.sub.i for the unique i{0, . . . , n1} with a.sub.i=.sup.i. Then the ELP, EEP, and syndome polynomial satisfy the following key equation:

[00004]${}_E{S}^{\left(y\right)}{}_E\mathrm{mod}\left(X^{d-1}\right)$ [0034] Another useful equation is Forney's formula, which relates the error locations and error values, and reads

[00005]${}_j=-\frac{{}_j{}_E\left({}_j^{-1}\right)}{a_j{}_E^{}\left({}_j^{-1}\right)}$

[0035] for all j{1, . . . , }.

Errors and Erasures Decoding

[0036] Before proceeding further, it will be useful to recall some facts regarding plain errors and erasures decoding of GRS codes.

[0037] Suppose that e.sub.0 coordinates of the received vector y are erased. Let {tilde over (y)}F.sub.q.sup.n be any vector that agrees with y on the non-erased coordinates. For example, {tilde over (y)} is obtained from y by filling arbitrary values on the erased coordinates, for example, these arbitrary values can be all zero, and write {tilde over (e)}:={tilde over (y)}x. The errors- and erasures decoder finds the locations and values of the non-zero entries of {tilde over (e)}, thus restoring x.

[0038] Let J.Math.{0, . . . , n1} be the set of non-erased coordinates, so that |J|=ne.sub.0. Let E.sub.1 be the set of locators of all errors on J, for example, let E.sub.1:={a.sup.j|jJ and x.sub.j{tilde over (y)}.sub.j}, and write e.sub.1:=|E.sub.1| for the number of errors on the non-erased part. Letting also E.sub.0:={a.sup.j|j.Math.J} be the set of erased coordinates, it holds that E:=E.sub.1 E.sub.0 is a full set of error locators for {tilde over (e)}. Define .sub.0 (X):=.sub.E.sub.0(1X) and .sub.1 (X):=.sub.E.sub.1(1X), so that .sub.E=.sub.0.sub.1. The key equation now reads S.sub.0.sub.1=.sub.E mod (X.sup.d1), where S:=S.sup.({tilde over (y)}) Defining {tilde over (S)}:=S.sub.0 mod X.sup.d1, we also have {tilde over (S)}.sub.1=.sub.E mod (X.sup.d1).

[0039] For g(X)F.sub.q [X] and rN, let M.sub.g,r .Math.F.sub.q [X]F.sub.q [X] for the solution module of a generic key equation: M.sub.g,r={(u, v)F.sub.q [X]F.sub.q [X]|u=gv mod (X.sup.r)}

[0040] For a pair (u, v)F.sub.q[X].sup.2, define the order ord(u, v) by ord(u, v):=max{deg(u)+1, deg(v)}. Also, for integer w, possibly zero or negative, define the (1, w)-weighted degree as wdeg.sub.1,w (u, v):=max {deg(u), deg(v)+w}. Note that when w=1, the order is the same as the weighted degree, up to an additive constant: ord(u, v)=wdeg.sub.1,1 (u, v)+1. The basis for practically all errors and erasures decoding algorithms is the following well-known proposition, for which the proof is omitted.

Proposition 1:

[0041] 1. gcd(.sub.E,.sub.1)=1.

[0042] 2. Suppose that 2e.sub.1+e.sub.0d1 and that S0. Then [0043] a. (.sub.E, .sub.1) has the minimum (1, e.sub.01)-weighted degree in M.sub.sd1 \{(0,0)}. Also, if some non-zero (u, v)M.sub.s,d1 has wdeg.sub.1,e.sub.0.sub.1 (u, v)=wdeg.sub.1,e.sub.0.sub.1 (.sub.E, .sub.1), then there exists some constant cF*.sub.q such that (u, v)=c. (.sub.E, .sub.1). [0044] b. Define N:={(u, v)M.sub.s,d1|.sub.0 divides v}. Then (.sub.E, .sub.E) has the minimum (1,1)-weighted degree in N \{(0,0)}. Also, if some non-zero (u, v)N has wdeg.sub.1,1 (u, v)=wdeg.sub.1,1 (.sub.E, .sub.E), then there exists some cF.sub.q such that (u, v)=C.Math.(.sub.E, .sub.F).

[0045] Proposition 1 shows that decoding can be performed by solving a minimization problem. For example, the Euclidean algorithm can be used to solve the minimization in part 2 (a) of the proposition, and a modified Berlekamp-Massey (BM) algorithm can be used to solve the minimization of part 2 (b).

Koetter's Iteration

[0046] This section uses the general form of Koetter's iteration, and K is an arbitrary field. In particular, for a field K and a monomial ordering on K, for some N*, write LM<(.Math.) for the leading monomial of a vector of polynomials with respect to . When the ordering is clear from the context, simply write LM(.Math.) for LM.sub.<(.Math.).

[0047] For a K [X]-submodule M.Math.K, for positive integer , of rank +1, let G={g.sub.0, . . . , } be a Groebner basis for M with respect to some monomial ordering on K. Assume without loss of generality that the leading monomial of g.sub.j contains the j-th unit vector, counting from 0.

[0048] Let D: K.fwdarw.K be a non-zero linear functions for which M.sup.+:=Mker(D) is a K[X]-module. Koetter's iteration converts the (+1)-element Groebner basis G of M to an (+1)-element Groebner basis G.sup.+={g.sub.0.sup.+, . . . , } of M.sup.+, while maintaining the property that LM(g.sub.j.sup.+contains the j-th unit vector. It is presented in the following pseudo code.

TABLE-US-00001 Koetter's iteration: Input: A Groebner basis G = {g.sub.0, . . . , } for M with LM(g.sub.j) containing the j-th unit vector for all j Output: A Groebner basis G.sup.+ = {g.sub.0.sup.+, . . . , } for M.sup.+ with LM(g.sub.j.sup.+) containing the j-th unit vector for all j Algorithm: For j = 0, . . . , , calculate .sub.j := D(g.sub.j) Set J = {j { {0, . . . , }|.sub.j 0} For j {0, . . . , } \ J Set g.sub.j.sup.+ := g.sub.j [00006]$\mathrm{Let}{j}^{*}J\mathrm{be}\mathrm{such}\mathrm{that}\mathrm{LM}\left(g_{j^{*}}\right)=\underset{jJ}{\min }\left\{LM\left(g_j\right)\right\}$ For j J [00007]$\mathrm{If}j{j}^{*},\mathrm{set}{g}_j^{+}:=g_j-\frac{{}_j}{{}_{j^{*}}}.Math.g_{j^{*}}$ [00008]$\mathrm{Else},\mathrm{set}{g}_{j^{*}}^{+}:=\left(X-\frac{D\left(X{g}_{j^{*}}\right)}{{}_{j^{*}}}\right)g_{j^{*}}$

The Decoding Tree

[0049] A possible embodiment of the decoding tree is described as follows. In an embodiment, there are .sub.chase coordinates for Chase flippings and .sub.GMD coordinates for variable GMD erasure attempts (on top of the e ( ) fixed erasures). Let I.sub.chase={.sub.1, . . . , .sub..sub.chase}.Math.F.sub.q be the set of coordinates on which Chase test vectors are scanned, and I.sub.GMD:={.sub..sub.chase.sub.+1, . . . >.sub..sub.chase.sub.+.sub.GMD} be the set of coordinates on which GMD erasures are attempted. The sets I.sub.chase and I.sub.GMD are determined from the channel reliability information, such as the p.sub.i.sup.(1) and p.sub.i.sup.(2) defined above.

[0050] Writing :=.sub.chase+.sub.GMD, each Chase test vector/GMD erasure pattern of an embodiment is determined by a binary vector of length . The first .sub.chase coordinates determine the Chase test error vector on I.sub.chase, where a 0 entry in coordinate i{1, . . . , .sub.chase} corresponds to a 0 on .sub.i, while a 1 entry in coordinate i corresponds to the second most likely error value in coordinate .sub.i. Note that the most likely error value is 0, by definition of the HD received vector.

[0051] Similarly, the following .sub.GMD coordinates determine a GMD erasure pattern, where a zero in coordinate i{.sub.chase+1, . . . , .sub.chase+.sub.GMD} corresponds to not erasing coordinate .sub.i, while a one in coordinate i corresponds to erasing coordinate .sub.i.

[0052] The binary vectors of length n and Hamming weight up to r.sub.max, for some pre-defined r.sub.max, are arranged on the vertices of a directed tree T which shall now be defined. The root is the all zero vector in F.sub.2.sup.n, and, for all r{1, . . . , r.sub.max}, the vertices at depth r are the vectors of weight r in F.sub.2.sup.n. To define the edges of T, for each r1 and for each vertex =(.sub.1, . . . , .sub.)F.sub.2.sup.n at depth r with non-zero entries at coordinates i.sub.1, . . . , i.sub.r, pick a single vertex =(.sub.1, . . . , .sub.b) at depth r-1 that is equal to on all coordinates, except for one if ({1, . . . , r}), for which =0. Note that there are r distinct ways to choose given , and one such choice can be fixed. Now the edges of T are exactly all pairs (, ).

[0053] The edge (, ) defined above corresponds to adjoining exactly one additional flipped or erased coordinate (i.e., ). Hence, the edge (, ) can be alternatively marked by (, ). Similarly, a path can be identified from the root to a vertex at depth r1, and hence the vertex itself, with a vector (.sub.i.sub.1, . . . , .sub.i.sub.r) with distinct 's.

[0054] Note that scanning the tree T corresponds to scanning all combinations of test error vectors and erasure patterns on I:=I.sub.chase I.sub.GMD for which the total number of non-zero test error values plus the total number of variable erasures is at most r.sub.max.

[0055] It should be kept in mind that the above is only one possible choice of the decoding tree. For example, in the above tree, when r=, all possible erasure patterns on I.sub.GMD are eventually scanned. In an alternative embodiment, many fewer erasure patterns are scanned. In this alternative embodiment, coordinates on I.sub.GMD are ordered in an ascending value of channel reliability, and for each test error pattern on I.sub.chase, the decoder first deletes the two least reliable coordinates on I.sub.GMD, then the next two coordinates, etc.

The Minimization Tasks

[0056] Let r, e.sub.0{0, . . . , n}, where n is the code length, let .sub.1, . . . , .sub.r, .sub.1, . . . , .sub.e.sub.0F*.sub.q be distinct, and let .sub.1, . . . , .sub.rF.sub.q (not necessarily distinct. The pairs (.sub.j, .sub.j) are the locators and value pairs of a hypothesized error pattern during the fast Chase/GMD decoding, while the .sub.j represent a hypothesized set of erased locators. Let A:={.sub.j} be the set of erased locators, and let .sub.0(X):=.sub.j=1.sup.e.sup.0 (1.sub.jX) be the erasure ELP.

[0057] Remark 1: Note that for convenience, this section uses a slightly different notation than that of the previous section. For example, the erasure locators are marked by A instead of E.sub.0, etc.

[0058] In practice, the erasure set A can be further divided into a large fixed subset of erasures that is present throughout the fast Chase/GMD decoding algorithm, and a small variable set of erasures, that is the current erasure hypothesis. Hence, let e.sub.0.sup.(1)e.sub.0 be the number of fixed erasures, e.sub.0.sup.(2):=e.sub.0e.sub.0.sup.(1) be the number of variable erasures,

[00009]$A_1^{}:=\left\{{}_1^{},.Math.,{}_{e_0^{\left(1\right)}}^{}\right\}$

be the set of fixed erasures,

[00010]$A_2^{}:=\left\{{}_{e_0^{\left(1\right)}+1}^{},.Math.,{}_{e_0}^{}\right\}$

be the current hypothesis of variable erasures. In addition, set .sub.0.sup.(1):=.sub.A.sub.1(1X) and .sub.0.sup.(2):=.sub.A.sub.2(1X), so that .sub.0=.sub.0.sup.(1).Math..sub.0.sup.(2)

[0059] Next are defined some useful F.sub.q[X]-modules. Let {tilde over (y)} be obtained from the received vector y, which includes erasures on the set A.sub.1 of fixed erasures, by filling in arbitrary values on the erased coordinates. Let

[00011]$\begin{array}{c}{M}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}=M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}\left(S^{\left(\tilde{y}\right)},{\left\{{}_j\right\}}_{j=1}^r,{\left\{{}_i\right\}}_{j=1}^r,{\left\{{}_j^{}\right\}}_{j=1}^{e_0}\right)\\ :=\left\{\begin{array}{c}\left(u,v\right){F_q\left[X\right]}^2|\\ \begin{array}{c}u\left(S^{\left(\tilde{y}\right)}{}_0^{\left(1\right)}\right)v\mathrm{mod}\left(X^{d-1}\right)\\ j\left\{1,.Math.,r\right\},\{\begin{array}{c}v\left({}_j^{-1}\right)=0\\ {}_j{a}_j{}_0^{\left(1\right)}\left({}_j^{-1}\right)v^{}\left({}_j^{-1}\right)=-{}_{j}u\left({}_j^{-1}\right)\end{array}\\ j\left\{e_0^{\left(1\right)}+1,.Math.,e_0\right\},v\left({}_j^{-1}\right)=0\end{array}\end{array}\right\}\end{array},$

with .sub.i:={tilde over ()}.sub.i for the unique i{0, . . . , n1} with .sub.i=.sup.i. Let also

[00012]$\begin{array}{c}{M}_{r,e_0}^{}=M_{r,e_0}^{}\left(S^{\left(\tilde{y}\right)},{\left\{{}_j\right\}}_{j=1}^r,{\left\{{}_j\right\}}_{j=1}^r,{\left\{{}_j^{}\right\}}_{j=1}^{e_0}\right)\\ :=\left\{\begin{array}{c}\left(u,v\right){F_q\left[X\right]}^2|\\ \begin{array}{c}u\left(S^{\left(\tilde{y}\right)}{}_0\right)v\mathrm{mod}\left(X^{d-1}\right)\\ j\left\{1,.Math.,r\right\},\{\begin{array}{c}v\left({}_j^{-1}\right)=0\\ {}_j{a}_j{}_0\left({}_j^{-1}\right)v^{}\left({}_j^{-1}\right)=-{}_{j}u\left({}_j^{-1}\right)\end{array}\end{array}\end{array}\right\}\end{array}.$

[0060] Also refer to the following module for fast Chase decoding without any erasures.

[00013]$\begin{array}{c}{M}_r=M_r\left(S^{\left(y\right)},{\left\{{}_j\right\}}_{j=1}^r,{\left\{{}_j\right\}}_{j=1}^r\right)\\ :=\left\{\left(u,v\right){F_q\left[X\right]}^2|\begin{array}{c}u{S}^{\left(y\right)}v\mathrm{mod}\left(X^{d-1}\right)\\ j\left\{1,.Math.,r\right\},\{\begin{array}{c}v\left({}_j^{-1}\right)=0\\ {}_j{a}_j{v}^{}\left({}_j^{-1}\right)=-{}_{j}u\left({}_j^{-1}\right)\end{array}\end{array}\right\}\end{array}.$

Remark 2. Note that:

[0061] 1. Both

[00014]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}$

and M.sub.r,e.sub.0 are defined as the set of all pairs of polynomial that satisfy a certain key-equation-type congruence, plus certain conditions that depend on the so-far hypothesized errors and erasures. As will be explained below, each additional condition can be taken into account by using update rules based on Koetter's iteration.

[0062] 2 Note that

[00015]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}$

and M.sub.r,e.sub.0 take erasures info account in two different ways. Clearly,

[00016]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}$

is more suitable for vehicle erasure patterns, as it does not include a modified syndrome depending on the variable part of the erasure pattern, and the Forney-like condition appearing in its definition does not require evaluating a varying erasure ELP. In fact, and M.sub.r,e.sub.0 is presented mainly as an auxiliary tool for the statement and proof of Theorem 3, below, while

[00017]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}$

is the module actually used to define the update rules of the fast combined Chase/GMD decoding.

[0063] 3. Observing the conditions that appear in the definition of

[00018]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{},$

it is apparent that it has a very similar form to that of M.sub.T, except for the following differences: [0064] a. It includes additional constraints of the form v(a.sub.j.sup.1)=0. Each such constraint has the same form as the first part of the constraint for Chase flipping. [0065] b. Each .sub.j, j {1, . . . , r}, is replaced by .sub.j:=.sub.0.sup.(1)(.sub.j.sup.1).sub.j, and S.sup.(y) is replaced by {tilde over (S)}:=S.sup.({tilde over (y)}).sub.0.sup.(1) mod(X.sup.d1). Once it is decided that HD decoding failed and that fast combined Chase/GMD should be initiated, .sub.0.sup.(1) can be calculated, and consequently also {tilde over (S)} and .sub.j for all the .sub.chase coordinates on which Chase flippings are planned.

[0066] Let A.Math.F*.sub.q\A be the set of all error locators outside A, and let E:=AA, so that E is a full set of error locators. Let .sub.E (X):=.sub.E (1X), .sub.1(X):=.sub.A (1X). In this section, it will sometimes be more convenient to index vectors by elements of F*.sub.q(instead of by integers in {0,1, . . . , n1}). Thus, for E, let () be the corresponding error value (possibly zero), and let () be the corresponding value of the GRS scaling vector {tilde over ()} (that is, if =.sup.i, then ():={tilde over ()}.sub.i). In this notation, we have .sub.E=.sub.E()().sub.E\{}(1X), and Forney's formula reads

[00019]$E,\left(\right)a\left(\right){}_E^{}\left({}^{-1}\right)=-{}_E\left({}^{-1}\right)$

[0067] In what follows, we will switch between indexing by integers and indexing by field elements (choosing the notation simplest in each context), and it should be clear from the context which notation is used.

[0068] The possibility of using Koetter's iteration for combined fast Chase/GMD decoding follows almost immediately from the following theorem. In the theorem, for a subset .Math.F*q and a vector z: F.sub.q.fwdarw.F.sub.q, we write z| for the punctured vector obtained by restricting z to . Also, we write .sup.c=F*.sub.q\ for the complementary set of in F*.sub.q.

Theorem 3.

[0069] 1. For all r, M.sub.T,

[00020]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{},$

M.sub.r,e.sub.0 are F.sub.q [x]-modules.

[0070] 2. The map :

[00021]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}.fwdarw.{F_q\left[X\right]}^2,$

(u, v)(u,v/.sub.0.sup.(2) is a monomorphism of F.sub.q [X]-modules whose image is exactly M.sub.r,e.sub.0 and therefore induces an isomuiplusin

[00022]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}.fwdarw.M_{r,e_0}^{}$

which shall be called .

[0071] 3. If 2d.sub.H (y|.sub.(A) c, x|.sub.(A) c)+e.sub.0d1+2r, .sub.1, . . . , .sub.r are error locators and .sub.1, . . . , .sub.r are the corresponding error values, then: [0072] C. (.sub.E, .sub.1)M.sub.r,e.sub.0, and for the (1, e.sub.01)-weighted lexicographic ordering with Y>X, it holds that LM(.sub.E, .sub.1)=min {LM(u, v)|(u, v)M.sub.r,e.sub.0 \{0}}. [0073] d.

[00023]$\left({}_E,{}_1{}_0^{\left(2\right)}\right)M_{r,e_0^{\left(1\right)}{e}_0^{\left(2\right)}}^{}$

and for the (1, e.sub.0.sup.(1)1)-weighted lexicographic ordering with Y>X,

[00024]$\mathrm{LM}\left({}_E,{}_1{}_0^{\left(2\right)}\right)=\min \left\{LM\left(u,v\right)|\left(u,v\right)M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}\backslash \left\{0\right\}\right\}$

[0074] The proof is omitted here.

Working with LowDegree Polynomials

[0075] Instead of working directly with the polynomials in

[00025]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{},$

it is positive to work with polynomials of a much lower degree. From this point on, write <.sub.w for the (1, w)-weighted lexicographic ordering with Y>X. Let {h.sub.0=(h.sub.00, h.sub.01), h.sub.1=(h.sub.10, h.sub.11)} be a Groebner basis for

[00026]$M_{0,e_0^{\left(1\right)},0}^{}$

with respect to the monomial ordering

[00027]${<}_{e_0^{\left(1\right)}-1},$

such that the leading monomial of h.sub.0 is on the left, i.e., in the first coordinate, while the leading monomial of h.sub.1 is on the right, i.e., in the second coordinate. Since {h.sub.0, h.sub.1} is also a free-module basis, every element

[00028]$\left(u,v\right)M_{0,e_0^{\left(1\right)},0}^{}$

can be written as (u, v)=f.sub.0(X) h.sub.0+f.sub.1 (X) h.sub.1 for a unique pair (f.sub.0(X), f.sub.1 (X)), and the map :

[00029]$M_{0,e_0^{\left(1\right)},0}^{}.fwdarw.{F_q\left[X\right]}^2,$

(u, v)(f.sub.0, f.sub.1) is an isomorphism of F.sub.q [X]-modules. :

[00030]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}.Math.M_{0,e_0^{\left(1\right)},0}^{}$

[0076] Note that for all r, e.sub.0.sup.(2), is a submodule, and let

[00031]$N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}=N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}\left(S^{\left(y\right)},{\left\{{}_j\right\}}_{j=1}^r,{\left\{{}_j\right\}}_{j=1}^r,{\left\{{}_j^{}\right\}}_{j=1}^{e_0}\right):=\left(M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{}\left(S^{\left(y\right)},{\left\{{}_j\right\}}_{j=1}^r,{\left\{{}_j\right\}}_{j=1}^r,{\left\{{}_j^{}\right\}}_{j=1}^{e_0}\right)\right)$

be the -image of

[00032]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}.}$

Refer to

[00033]$N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}$

as the module of coefficient polynomials of

[00034]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}.$

By writing a typical element

[00035]$\left(u,v\right)M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}$

as f.sub.0(x)h.sub.0+f.sub.1(x)h.sub.1 and substituting in the constraints in the definition of

[00036]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}},$

the following characterization of N.sub.T can be obtained with constraints that are suitable for applying Koetter's iteration. For the following proposition, recall from part 3 (b) of Remark 2 that for all j {1, . . . ,r}, .sub.j=.sub.0.sup.(1) (a.sub.j.sup.1) .sub.j. Proposition 4. It holds that

[00037]$N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}$

is the set of an pairs (f.sub.0,f.sub.1)F.sub.q[X].sup.2 that satisfy the following conditions:

[00038]$i\left\{1,.Math.,r\right\},$$1.b_{0i}{f}_0\left({}_i^{-1}\right)+b_{1i}{f}_1\left({}_i^{-1}\right)=0,$$\mathrm{and}$$2.b_{0i}{f}_0^{}\left({}_i^{-1}\right)+c_{0i}{f}_0\left({}_i^{-1}\right)+b_{1i}{f}_1^{}\left({}_i^{-1}\right)+c_{1i}{f}_1\left({}_i^{-1}\right)=0,$$\mathrm{where}$$b_{0i}=h_{01}\left({}_i^{-1}\right),$$b_{1i}=h_{11}\left({}_i^{-1}\right),$$c_{0i}=h_{01}^{}\left({}_i^{-1}\right)+\frac{{}_i}{{}_i{}_i^{}}{h}_{00}\left({}_i^{-1}\right),$$c_{1i}=h_{11}^{}\left({}_i^{-1}\right)+\frac{{}_i}{{}_i{}_i^{}}{h}_{10}\left({}_i^{-1}\right)$$i\left\{e_0^{\left(1\right)}+1,.Math.,e_0\right\},b_{0i}{f}_0\left({}_i^{-1}\right)+b_{1i}{f}_1\left({}_i^{-1}\right)=0$

[0077] To translate the minimality assertion of Theorem 3 to the language of coefficient polynomials, the following proposition can be used for the case where erasures are present. Proposition 5. Let w=deg(h.sub.11)deg (h.sub.00)+e.sub.0.sup.(1)1. Then for all

[00039]$\left(u_1,v_1\right),\left(u_2,v_2\right)M_{0,e_0^{\left(1\right)}{,}_0}^{},$

it holds that

[00040]${\mathrm{LM}}_{{<}_{e_0^{\left(1\right)}-1}}\left(u_1,v_1\right){<}_{e_0^{\left(1\right)}-1}{\mathrm{LM}}_{{<}_{e_0^{\left(1\right)}-1}}\left(u_2,v_2\right){\mathrm{LM}}_{<w}\left(\left(u_1,v_1\right)\right){<}_w{\mathrm{LM}}_{<w}\left(\left(u_2,v_2\right)\right)$

The proof is omitted.

[0078] Theorem 3 and Proposition 5 indicate that one should search for a vector of minimal leading monomial in

[00041]$N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}},$

with respect to <.sub.w, and for this it is sufficient to have a Groebner basis for

[00042]$N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}},$

with respect to <.sub.w. One may then take the unique vector of minimal leading monomial in this two-element Groebner basis. Alternatively, but typically less efficiently, search for a Groebner basis of

[00043]$M_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}^{},$

with respect to

[00044]${<}_{e_0^{\left(1\right)}-1}.$

The definition of

[00045]$N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}$

shows how a Groebner basis for

[00046]$N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}$

can be converted to a Groebner basis for

[00047]$N_{r+1,e_0^{\left(1\right)},e_0^{\left(2\right)}}$

by two applications of Koetter's iteration, or to a Groebner basis for

[00048]$N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}+1}$

with a single iterations of Koetter's iteration.

[0079] The exact update rules that corresponding to one or two Koetter iterations are detailed below. Note that such update rules are key to a fast Chase/GMD according to an embodiment: for an additional flip or erasure, do not start from scratch, but rather use all accumulated computations so far as a starting point, and apply only a low-complexity update rule.

[0080] Finally, note that by definition,

[00049]$N_{0,e_0^{\left(1\right)},0}=F_q^2,$

so that one can take {(1,0), (0,1)} as the <.sub.w-Groebner basis for this module. This Groebner basis will be used on the root of the decoding tree.

Algorithms

Initialization

[0081] The initialization of a fast combined Chase/GMD algorithm according to an embodiment is performed after bounded-distance HD decoding fails. To initialize an algorithm, one must find a Groebner basis for

[00050]$M_{0,e_0^{\left(1\right)},0}^{},$

Where the only constraint is u=(s.sup.(y) .sub.0.sup.(1)) v mod(x.sup.d1), with respect to

[00051]${<}_{e_0^{\left(1\right)}-1}.$

[0082] One algorithm for finding a Groebner basis for

[00052]$M_{0,e_0^{\left(1\right)},0}^{}$

is as follows:

TABLE-US-00002 Input: g(X) := S.sup.(y).sub.0.sup.(1) mod X.sup.d1 r := e.sub.0.sup.(1) 1 v := d 1 Output: [00053]$\left\{\left(a_0\left(X\right),b_0\left(X\right)\right),\left(a_1\left(X\right),a_2\left(X\right)\right)\right\}-a\mathrm{Groebner}\mathrm{basis}\mathrm{for}{M}_{0,e_0^{\left(1\right)},0}^{}$ Initialize: (a.sub.0, b.sub.0) := (1, 0); (a.sub.1, b.sub.1) := (0, 1); .sub.0 := 1; j := 1; k := 0 Iterations: If r 0, i := 0; d := 1 + r Else i := 1; d := r While k < Do .sub.j := Coefficient of X.sup.k in b.sub.j(X) .Math. g(X) k := k + 1 If .sub.i 0, [00054]$\left(a_{1-i}\left(X\right),b_{1-i}\left(X\right)\right):=\left(a_{1-i}\left(X\right),b_{1-i}\left(X\right)\right)-\frac{{}_{1-i}}{{}_i}\left(a_i\left(X\right),b_i\left(X\right)\right)$ (a.sub.i(X), b.sub.i(X)) := (Xa.sub.i(X), Xb.sub.i(X)) j := 1 i d := d 1 If d = 0, i := 1 i; d := 1 Else (a.sub.1i(X), b.sub.1i(X)) := (Xa.sub.1i(X), Xb.sub.1i(X)) j := i; d := d + 1

[0083] At the end of the algorithm, the leading monomials of (.sub.0(X), b.sub.0(X)), (.sub.1 (X), b.sub.1 (X)) with respect to

[00055]${<}_{e_0^{\left(1\right)}-1}$

are not in the same coordinate. For proceeding with combined Chase/GMD decoding, the first Groebner basis element is taken to be the (a.sub.i(X), b.sub.i(X)) (i=0,1) whose leading monomial is on the left, and the second Groebner basis element to be (.sub.1i(X), b.sub.1i(X)).

[0084] Alternatively, the two polynomials updates during the errors-and-erasures BM algorithm can be used to obtain the Groebner basis, as follows. One efficient version of the BM algorithm for errors and erasures is the following. The output is two pairs of polynomials.

TABLE-US-00003 Algorithm A: efficient errors and erasures BM algorithm Input: S.sup.(y)(X) e.sub.0.sup.(1) .sub.0.sup.(1) := .sub.A.sub.1(1 X) Output: v(X), if 2e.sub.1 + e.sub.0.sup.(1) d 1, otherwise v(X) = .sub.1(X) := .sub.A(1 X), where v(X) is an estimated ELP that excludes erasures; [00056]$v^{-}\left(X\right),\mathrm{which}\mathrm{is}\mathrm{required}\mathrm{for}\mathrm{finding}a\mathrm{Groebner}\mathrm{basis}\mathrm{for}{M}_{0,e_0^{\left(1\right)},0}^{};$ [00057]$,\mathrm{which}\mathrm{is}\mathrm{associated}\mathrm{with}\mathrm{finding}a\mathrm{Groebner}\mathrm{basis}\mathrm{for}{M}_{0,e_0^{\left(1\right)},0}^{};$ Initialization: Calculate {tilde over (S)}(X) := S.sup.({tilde over (y)})(X).sub.0.sup.(1)(X) mod X.sup.(d1) v(X) := 1 v.sup.(X) := 1 := 1 b := 1 L := e.sub.0.sup.(1) Iterations: For j = e.sub.0.sup.(1) to d 2 Set := Coeff.sub.X.sub.j({tilde over (S)}v) If = 0 Update + 1 If 0 and (j e.sub.0.sup.(1)) 2(L e.sub.0.sup.(1)) 1 Update v(X) v(X) .Math. b.sup.1X.sup.v.sup.(X) Update + 1 If 0 and (j e.sub.0.sup.(1)) 2(L e.sub.0.sup.(1)) Set TMP := v(X) Update v(X) v(X) .Math. b.sup.1X.sup.v.sup.(X) Update L j + 1 L + e.sub.0.sup.(1)// (L e.sub.0.sup.(1)) (j e.sub.0.sup.(1)) + 1 (L e.sub.0.sup.(1)) Set v.sup.(X) := TMP Set b := Set := 1

[0085] To obtain a Groebner basis from the outputs of the algorithm, in case plain errors and erasures decoding fails, it is possible to proceed in the following way:

[0086] 1. Calculate [0087] b.sub.0=({tilde over (S)}v mod X.sup.d1, v) [0088] b.sub.1=({tilde over (S)}X.sup.v-mod x.sup.d1, x.sup.v.sup.)

[0089] 2. If

[00058]${{\mathrm{LM}}_{<}}_{e_0^{{\left(1\right)}_{-1}}}\left(b_0\right)\mathrm{and}{{\mathrm{LM}}_{<}}_{e_0^{{\left(1\right)}_{-1}}}\left(b_1\right)$

contain different unit vectors (i.e., are located at different coordinates), then [0090] Let h.sub.0 be the vector from {b.sub.0, b.sub.1} with leading monomial in the first coordinate, and let h.sub.1 be the vector from {b.sub.0, b.sub.1} with leading monomial in the second coordinate [0091] Output {h.sub.0, h.sub.1} as the Groebner basis 3. If

[00059]${{\mathrm{LM}}_{<}}_{e_0^{{\left(1\right)}_{-1}}}\left(b_0\right)\mathrm{and}{{\mathrm{LM}}_{<}}_{e_0^{{\left(1\right)}_{-1}}}\left(b_1\right)$

contain the same unit vector (i.e., they are on the same side), then: [0092] If

[00060]${{\mathrm{LM}}_{<}}_{e_0^{{\left(1\right)}_{-1}}}\left(b_0\right){<}_{e_0^{{\left(1\right)}_{-1}}}L{M}_{{<}_{e_0^{\left(1\right)}-1}}\left(b_1\right),$

then for the unique cF*.sub.q and N* that assure leading monomial cancellation, update b.sub.1b.sub.1cb.sub.0 [0093] If

[00061]${{\mathrm{LM}}_{<}}_{e_0^{{\left(1\right)}_{-1}}}\left(b_0\right){}_{e_0^{{\left(1\right)}_{-1}}}L{M}_{{<}_{e_0^{\left(1\right)}-1}}\left(b_1\right),$

then for the unique cF*.sub.q and N that assure leading monomial cancellation, update b.sub.0b.sub.0cb.sub.1 [0094] Calculate and output {h.sub.0, h.sub.1} as in step 2. Note that by the definition of the monomial ordering <.sub.w (for any w), the comparison

[00062]${{\mathrm{LM}}_{<}}_{e_0^{{\left(1\right)}_{-1}}}\left(b_0\right){<}_{e_0^{{\left(1\right)}_{-1}}}L{M}_{<e_0^{\left(1\right)}-1}\left(b_1\right)$

in step 3 is equivilant to deg(b.sub.0j(x))<deg(b.sub.1j(x)), where j is the common coordinate of the leading monomial. Similarly,

[00063]${{\mathrm{LM}}_{<}}_{e_0^{{\left(1\right)}_{-1}}}\left(b_0\right){}_{e_0^{{\left(1\right)}_{-1}}}L{M}_{{<}_{e_0^{\left(1\right)}-1}}\left(b_1\right)$

is equivalent to deg(b.sub.0j (X))deg(b.sub.1j(X)).

[0095] Note that any algorithm for finding a Groebner basis for the module defined by the above constraint can also be used for HD errors-and-erasures decoding for the fixed e.sub.0.sup.(1) erasures. In a typical application, the Groebner basis for initialization is obtained from the same algorithm used for the initial errors-and-erasures HD decoding, in order to reduce complexity.

Update Rule for an Additional Flip

[0096] This rule corresponds to the case of moving from

[00064]$N_{r-1,e_0^{\left(1\right)},e_o^{\left(2\right)}}\mathrm{to}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}.$

TABLE-US-00004 [00065]$\mathrm{Algorithm}B:\mathrm{edge}\mathrm{update}\mathrm{rule}\mathrm{for}\mathrm{moving}\mathrm{from}{N}_{r-1,e_0^{\left(1\right)},e_0^{\left(2\right)}}\mathrm{to}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}.$ In the following, there are two types of iterations. In the root-type iteration, the algorithm imposes that some of the updated polynomials have an additional root. In the derivative iterations, the algorithm imposes that the updated polynomials satisfy Forney's formula, which involves the derivative of some polynomials. Input: w := deg(h.sub.11) deg(h.sub.00) + e.sub.0.sup.(1) 1 (this depends only on the initialization on the root of the decoding tree) [00066]$A\mathrm{Groebner}\mathrm{basis}G=\left\{f_0=\left(f_{00},f_{01}\right),f_1=\left(f_{10},f_{11}\right)\right\}\mathrm{for}{N}_{r-1,e_0^{\left(1\right)},e_0^{\left(2\right)}},\mathrm{with}{\mathrm{LM}}_w\left(f_j\right)$ containing the j-th unit vector for j {0, 1} The next hypothesized error location .sub.r and the corresponding hypothesized error value, .sub.r Output: [00067]$A\mathrm{Groebner}\mathrm{basis}{G}^{+}=\left\{f_0^{+}=\left(f_{00}^{+},f_{01}^{+}\right),f_1^{+}=\left(f_{10}^{+},f_{11}^{+}\right)\right\}\mathrm{for}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}},\mathrm{with}{\mathrm{LM}}_w\left(f_j\right)$ containing the j-th unit vector for j {0, 1} Algorithm: For type = root, der If type = der For j = 0, 1, set f.sub.j := f.sub.j.sup.+ // init: output of root iter. For j = 0, 1, calculate [00068]${}_j:=\{\begin{array}{cc}{b}_{0r}{f}_{j0}\left({}_r^{-1}\right)+b_{1r}{f}_{j1}\left({}_r^{-1}\right),& \mathrm{if}\mathrm{type}=\mathrm{root}\\ b_{0r}{f}_{j0}^{}\left({}_r^{-1}\right)+c_{0r}{f}_{j0}\left({}_r^{-1}\right)+b_{1r}{f}_{j1}^{}\left({}_r^{-1}\right)+c_{1r}{f}_{j1}\left({}_r^{-1}\right),& \mathrm{if}\mathrm{type}=\mathrm{der}\end{array}$ (where b.sub.0r, b.sub.1r, c.sub.0r, c.sub.1r are defined in Proposition 4) Set J := {j {0, 1}|.sub.j 0} For j {0, 1} \ J, set f.sub.j.sup.+ := f.sub.j [00069]$\mathrm{Let}{j}^{*}J\mathrm{be}\mathrm{such}\mathrm{that}{\mathrm{LM}}_w\left(f_{j^{*}}\right)=\underset{jJ}{\min }\left\{L{M}_w\left(f_w\right)\right\}$ For j J [00070]$\mathrm{If}j{j}^{*},\mathrm{set}{f}_j^{+}:=f_j-\frac{{}_j}{{}_{j^{*}}}{f}_{j^{*}}$ Else, set f.sub.j*.sup.+ := (X .sub.r.sup.1)f .sub.j*

Update Rule for an Additional Variable Erasure

[0097] This rule corresponds to the case of moving from

[00071]$N_{r,e_0^{\left(1\right)},e_0^{{\left(2\right)}_{-1}}}\mathrm{to}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}},$

which is one additional variable erasure. It is very similar to Algorithm B, and simpler than Algorithm B in the sense that instead of two iterations in Algorithm B (root, der), only a single iteration is configured.

TABLE-US-00005 [00072]$\mathrm{Algorithm}C:\mathrm{edge}\mathrm{update}\mathrm{rule}\mathrm{for}\mathrm{moving}\mathrm{from}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}-1}\mathrm{to}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}}.$ Input: w := deg(h.sub.11) deg(h.sub.00) + e.sub.0.sup.(1) 1 (this depends only on the initialization on the root of the decoding tree) [00073]$A\mathrm{Groebner}\mathrm{basis}G=\left\{f_0=\left(f_{00},f_{01}\right),f_1=\left(f_{10},f_{11}\right)\right\}\mathrm{for}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}-1},\mathrm{with}{\mathrm{LM}}_w\left(f_j\right)$ containing the j-th unit vector for j {0, 1} The next hypothesized erasure location and the corresponding hypothesized error value, .sub.r Output: [00074]$A\mathrm{Groebner}\mathrm{basis}{G}^{+}=\left\{f_0^{+}=\left(f_{00}^{+},f_{01}^{+}\right),f_1^{+}=\left(f_{10}^{+},f_{11}^{+}\right)\right\}\mathrm{for}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}},\mathrm{with}{\mathrm{LM}}_w\left(f_j\right)$ containing the j-th unit vector for j {0, 1} Algorithm: For j = 0, 1, calculate .sub.j := h.sub.01(.sup.1)f.sub.j0(.sup.1) + h.sub.11(.sup.1) + f.sub.j1(.sup.1) Set J := {j {0, 1}|.sub.j 0} For j {0, 1} \ J, set f.sub.j.sup.+ := f.sub.j [00075]$\mathrm{Let}{j}^{*}J\mathrm{be}\mathrm{such}\mathrm{that}L{M}_w\left(f_{j^{*}}\right)=\underset{jJ}{\min }\left\{L{M}_w\left(f_w\right)\right\}$ For j J [00076]$\mathrm{If}j{j}^{*},\mathrm{set}{f}_j^{+}:=f_j-\frac{{}_j}{{}_{j^{*}}}{f}_{j^{*}}$ Else, set f.sub.j*.sup.+ := (X .sub.r.sup.1)f.sub.j*

The Stopping Condition

[0098] Write {circumflex over ()}=f.sub.10(X) h.sub.01(X)+f.sub.11(X) h.sub.11 (X) for the so-far estimated ELP. Note that this polynomial may not be calculated explicitly. To definitely decide, at least up to undetected errors inherently possible for the GRS code, whether the so-far flippings and erasures result in a correct ELP, i.e., {circumflex over ()}=c.Math. for some non-zero c, one checks whether the number of roots of {circumflex over ()} in in F*.sub.q equals deg({circumflex over ()}), and this typically includes exhaustive substitution of all elements of F*.sub.q in {circumflex over ()}.

[0099] To avoid such exhaustive substitutions after each update on an edge of the decoding tree, a stopping condition is introduced, i.e., a condition on the so-far Groener basis that has the following properties: (1) It never misses the cases where {circumflex over ()}=c.Math. for some c; and (2) It might sometimes pass (with low probability) when {circumflex over ()}c.Math. for all non-zero c.

[0100] Case 2 is referred to as a false positive. The only cost of a false positive is in unnecessarily performing an exhaustive substitution in polynomials, i.e., in an increase in complexity. Since false positives are rare (see below for more on this), the resulting increment in complexity is typically negligible.

[0101] For the stopping condition to work, one additional error is needed in the unreliable coordinates on top of the minimum configured by part 3 of Theorem 3. This slightly reduces the correction capability of the combined fast Chase/GMD algorithm.

[0102] Let {circumflex over ()}:=f.sub.10(X) h.sub.00(X)+f.sub.11(X) h.sub.10 (X). The idea of the stopping condition is that when the condition of part 3 of Theorem 3 holds, ({circumflex over ()}, {circumflex over ()})=c.Math.(, ), and then, if an edge of the decoding tree corresponds to a correct flipping hypothesis, i.e., .sub.r is indeed an error locator with corresponding error value .sub.r, .sub.1=0 must be true in both iterations of Algorithm B. Similarly, in case the edge of the decoding tree corresponds to an erasure of a coordinate which contains error, then .sub.1=0 is true in the single iteration of Algorithm C.

[0103] So, the first criterion for stopping and performing an exhaustive substitution, is that the above discrepancies are zero. A second condition is for screening out cases which is also relevant to a method according to an embodiment, where variable erasures are allowed on top of variable flippings. This criterion will be described as follows, without getting into further details.

The Stopping Condition is Described as Follows:

[0104] 1. On an edge that corresponds to adding a flip, i.e., when moving from

[00077]$N_{r-1,e_0^{\left(1\right)},e_0^{\left(2\right)}}\mathrm{to}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}},$

check if .sub.1=0 for both the root and derivative iterations of Algorithm B. Alternatively, on an edge that corresponds to adding an erasure, i.e., when moving from

[00078]$N_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}-1}\mathrm{to}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}},$

check if .sub.1=0 for the single iteration of Algorithm C.

[0105] 2. If the check of part 1 passes, check that {circumflex over ()}(X), which corresponds to the parent node, either

[00079]$N_{r-1,e_0^{\left(1\right)},e_0^{\left(2\right)}}\mathrm{or}{N}_{r,e_0^{\left(1\right)},e_0^{\left(2\right)}-1},$

respectively to the case in part 1, and its formal derivative (X) do not have common roots in .sub.1, . . . , .sub.r1 in the first case (Algorithm ), or on .sub.1, . . . , .sub.r (Algorithm C).

Efficient Evaluation

[0106] Whenever the stopping criterion holds, {circumflex over ()}(X) is evaluated. In some cases, {circumflex over ()}(X) may also be evaluated. Recalling that {circumflex over ()}:=f.sub.10(X) h.sub.01(X)+f.sub.11(X) h.sub.11 (X), it holds that

[00080]${\stackrel{}{}}^{}\left(X\right)=f_{10}\left(X\right)h_{01}^{}\left(X\right)+f_{10}^{}\left(X\right)h_{01}\left(X\right)+f_{11}\left(X\right)h_{11}^{}\left(X\right)+f_{11}^{}\left(X\right)h_{11}\left(X\right)$

Noting that h.sub.01(X) and h.sub.11 (X) are known after calculating the Groebner basis for

[00081]$M_{0,e_0^{\left(1\right)},0}^{}$

as part of the initial errors and erasures decoding, {circumflex over ()} can be efficiently evaluated as follows:

[0107] 1. After calculating h.sub.0, h.sub.1 at the initialization step, evaluate and store the values of h.sub.01(), h.sub.11(), h.sub.01(), and h.sub.11() for all F*.sub.q.

[0108] 2. Whenever a new {circumflex over ()} is evaluated at some , evaluate only the low-degree polynomials f.sub.10(X), f.sub.11(X), and calculate {circumflex over ()} () with two additional multiplications, as {circumflex over ()} ()=f.sub.10(). h.sub.01()+f.sub.11().Math.h.sub.11(). Similarly, whenever is evaluated, calculate also the evaluations f.sub.10 (), f.sub.11(), and calculate () using 4 additional multiplications, using calculated and stored values and the following formula for the estimated value of (X):

[00082]${\stackrel{}{}}^{}\left(X\right)=f_{10}\left(X\right)h_{01}^{}\left(X\right)+f_{10}^{}\left(X\right)h_{01}\left(X\right)+f_{11}\left(X\right)h_{11}^{}\left(X\right)+f_{11}^{}\left(X\right)h_{11}\left(X\right).$

Embodiment of an Overall Decoding Algorithm on a Tree

[0109] This section presents one possible high-level embodiment of an entire decoding process with a new combined fast Chase/GMD algorithm. It should be kept in mind that different embodiments can also be used. For example, instead of using the BM algorithm at the first stage for errors-and-erasures decoding, one can use the algorithm for finding a Groebner basis for

[00083]$M_{0,e_0^{\left(1\right)},0}^{}$

outlined above, or other algorithms.

[0110] FIG. 1 is a flow chart of a decoding process with a new combined fast Chase/GMD algorithm according to an embodiment. Referring now to the figure, a decoding process starts at step 10 by receiving a codeword y through a digital electronic communication channel. The codeword y=x+e for at least one error vector eF.sub.q.sup.n, where F.sub.q is a finite field of q elements, wherein q is a prime power, and for transmitted codeword xC, wherein Cis a generalized Reed-Solomon code with possible shortening, of length n<=q1 and minimum Hamming distance d2. Hard decision (HD) error-and-erasures decoding is performed on the codeword with a fixed set of erasures, at step 11, and at step 12, it is determined whether the HD error-and-erasures decoding has failed. Upon failure of the HD error-and-erasures decoding, the decoding process further includes finding a Groebner basis to a solution module that accounts for the fixed set of erasures, at step 13, and determining a set of Chase coordinates and a set of generalized minimum distance (GMD) coordinates using channel reliability information, at step 14. At step 15, a Chase and GMD decoding tree is constructed on the set of Chase coordinates and the set of GMD coordinates, and the decoding tree is traversed depth first at step 16, using polynomials of the Groebner basis as a basis that represents updated coefficient polynomials on the Chase and GMD decoding tree. The polynomials on the decoding tree are updated at step 17 using root and derivate steps that flip an edge, or a root step for an erasure edge, and at step 18 error locations are calculated by polynomial evaluation of candidate polynomials from the decoding tree, and error values are calculated. The polynomial evaluation of candidate polynomials includes verifying that a valid pair of EEP and ELP has been found by checking that a number of ELP roots equals its degree minus a number of variables erasures, and the inverses of all roots are outside an erasure set, and calculating error values includes finding error values on non-erased coordinates using Forney's algorithm with the EEP and ELP, and checking that no estimated error value on a non-erased coordinate is zero. The received codeword is corrected at step 20 according to the calculated error locations and calculated error values, and the corrected received codeword is saved to a decoder output list.

[0111] An example of a decoding process with a new combined fast Chase/GMD algorithm according to an embodiment is as follows.

[0112] 1. Perform errors and erasures decoding with the e (fixed erasures, e.g., by taking the following steps: [0113] a. Perform algorithm A [0114] b. Check if v(X) has deg(v(X)) roots on the non-erased coordinates, i.e., on F*.sub.q\A.sub.1, and that deg(v)=Le.sub.0.sup.(1), where L is the estimated order and Le.sub.0.sup.(1) is a corrected order that does not account for erasures. [0115] c. If the condition in step b holds, then proceed to the following steps: [0116] i. Define .sub.1:=V [0117] ii. Calculate .sub.E:=.sub.1.sub.0.sup.(1), and .sub.E={tilde over (S)}.sub.1 mod (X.sup.d1). [0118] iii. Inverses of roots of 01 point to error locations outside A.sub.1. Use Forney's formula to find error values for all these error locations, as well as for the erased coordinates in A.sub.1. [0119] iv. Using the locations and values from the previous step, correct all errors. [0120] v. Output the decoded codeword and declare success.

[0121] 2. If the condition in step 1b fails, then start the fast combined Chase/GMD decoding: [0122] a. Find a Groebner basis {h.sub.0, h.sub.1} from

[00084]$M_{0,e_0^{\left(1\right)},0}^{}$

as described in the initiation step above. [0123] b. Construct the decoding tree T. Assign memory for r.sub.max+1 Groebner bases, one for each depth. Store the Groebner basis {(1,0), (0,1)} for

[00085]$N_{0,e_0^{\left(1\right)},0}$

in the memory of depth 0. [0124] c. Traverse the tree depth first [0125] i. When moving on an edge corresponding to moving from e.sub.0.sup.(2)1 to e.sub.0.sup.(2) such as an edge that corresponds to one additional variable erasure or one additional Chase flip, use Algorithm C for updating the Groebner basis read from the memory of the previous depth. Store the resulting Groebner basis in memory for the current depth, overriding previously stored values, if any. [0126] ii. When moving on an edge that corresponds to moving from r1 to r, use Algorithm B to update the Groebner basis read from memory of the previous depth. Store the resulting Groebner basis in memory for the current depth, overriding previously stored values, if any. [0127] iii. If during the update the stopping condition holds: [0128] 1. Writing {f.sub.0=(f.sub.00, f.sub.01), f.sub.1=(f.sub.10, f.sub.11)} for the original Groebner basis on the parent node, check if ({circumflex over ()})=c(.sub.E, .sub.1.sub.0.sup.(2)) holds for some c0, where =f.sub.10 (x) h.sub.00(x)+f.sub.11 (x)h.sub.10 (x) and {circumflex over ()}:=f.sub.10(X) h.sub.01(X)+f.sub.11(X) h.sub.11 (X), as follows: [0129] a. Find all the roots of {circumflex over ()} on inverses of elements from F*.sub.q\(A.sub.1 A.sub.2), using the fast evaluation methods defined above. Verify that the number of these roots is exactly deg({circumflex over ()})e.sub.0.sup.(2). If not, declare that the stopping condition was falsely positive, and return to the depth-first search on the tree. [0130] b. Calculate ={circumflex over ()}.Math..sub.0.sup.(1) and find error values only on non-erased coordinates, i.e., coordinates with locators in F*.sub.q\(A.sub.1 A.sub.2), by using Forney's formula for ({circumflex over ()}.sub.E, {circumflex over ()}.sub.E). If at least one of error value turns out to be 0, declare that the stopping condition was falsely positive, and return to the depth-first search on the tree.

[0131] 2. Calculate error values for all e.sub.0.sup.(1)+e.sub.0.sup.(2) erased coordinates using Forney's formula (these values may be either zero or non-zero).

[0132] 3. Correct the received codeword according to the calculated error locations and values, and save to the output list of the decoder.

[0133] Return to the tree search to find potential additional decoded codewords in the output list of the decoder. Note that in some embodiments, the maximum list size may be bounded by some integer parameter L1. In such embodiments, the search stops once the list reaches a size of L.

[0134] FIG. 3 shows an example of a variant of the decoding tree. Here, I.sub.Chase has 3 coordinates, and the left triple of each vertex in the figure represents do not flip/flip (0/1, respectively) for each coordinate in I.sub.Chase. In addition, I.sub.GMD has 2 coordinates, and the right pair of each vertex in the figure represents do not erase/erase (0/1, respectively) for each coordinate in I.sub.GMD. The thin black edges correspond to Chase flips, while thick gray edges correspond to GMD erasures. In this example, since there are only 2 GMD coordinates, constructing the decoding tree reduces to first constructing the only black edges tree, where there are only Chase flips without any erasures, and then, for each vertex, adding two successive GMD erasure edges, ending in a vertex with identical flipping values on I.sub.chase, but with the two GMD coordinates erased.

Final Remarks: Some Additional Embodiments

[0135] In an embodiment, it is not mandatory to restrict the Chase decoding to 2 error hypotheses per coordinate. In general, it is possible to choose any number of hypotheses between 2 and q per coordinate, and this gives a tradeoff between complexity and probability of decoding success.

[0136] In addition, in an embodiment, it is not mandatory to use two disjoint sets for variable erasures (GMD) and for Chase decoding. For example, it is possible to have coordinates on which it is attempted to both try both various error values and erasure. For example, in most of the text above, two error values were considered for a coordinate in Chase decoding, say, 0 and , where B is the second most likely error for the coordinate. However, it is also possible to add the value erased for this coordinate, i.e., the possibilities are now {0,, erased}. If on some edge of the decoding tree the value changes from 0, , use Algorithm B for the update, while if the value changes from 0 to erased, use Algorithm C for the update.

System Implementations

[0137] It is to be understood that embodiments of the present disclosure can be implemented in various forms of hardware, software, firmware, special purpose processes, or a combination thereof. In one embodiment, the present disclosure can be implemented in hardware as an application-specific integrated circuit (ASIC), or as a field programmable gate array (FPGA). In another embodiment, the present disclosure can be implemented in software as an application program tangible embodied on a computer readable program storage device. The application program can be uploaded to, and executed by, a machine comprising any suitable architecture.

[0138] FIG. 2 is a block diagram of a host storage system 20 that includes an error correction circuit that performs a fast combined chase and GMD decoding of generalized Reed-Solomon codes, according to an embodiment.

[0139] The host storage system 20 includes a host 100 and a storage device 200. Further, the storage device 200 includes a storage controller 210 and an NVM 220. According to an embodiment, the host 100 includes a host controller 110 and a host memory 120. The host memory 120 can serve as a buffer memory that temporarily stores data to be transmitted to the storage device 200 or data received from the storage device 200.

[0140] The storage device 200 includes storage media that stores data in response to requests from the host 100. For example, the storage device 200 includes at least one of an SSD, an embedded memory, and/or a removable external memory. When the storage device 200 is an SSD, the storage device 200 conforms to an NVMe standard. When the storage device 200 is an embedded memory or an external memory, the storage device 200 conforms to a UFS standard or an eMMC standard. Each of the host 100 and the storage device 200 generates a packet according to an adopted standard protocol and transmit the packet.

[0141] When the NVM 220 of the storage device 200 includes a flash memory, the flash memory may include a 2D NAND memory array or a 3D (or vertical) NAND (VNAND) memory array. For example, the storage device 200 can include various other kinds of NVMs. For example, the storage device 200 includes at least one of a magnetic RAM (MRAM), a spin-transfer torque MRAM, a conductive bridging RAM (CBRAM), a ferroelectric RAM (FRAM), a PRAM, an RRAM, or various other kinds of memories.

[0142] According to an embodiment, the host controller 110 and the host memory 120 are implemented as separate semiconductor chips. Alternatively, in some embodiments, the host controller 110 and the host memory 120 are integrated in the same semiconductor chip. For example, the host controller 110 is one of a plurality of modules included in an application processor (AP). The AP can be implemented as a System on Chip (SoC). Further, the host memory 120 may be an embedded memory included in the AP or an NVM or memory module located outside the AP.

[0143] The host controller 110 manages an operation of storing data, such as write data, of a buffer region of the host memory 120 in the NVM 220 or an operation of storing data, such as read data, of the NVM 220 in the buffer region.

[0144] The storage controller 210 includes a host interface 211, a memory interface 212, and a CPU 213. Further, the storage controllers 210 furthers include a flash translation layer (FTL) 214, a packet manager 215, a buffer memory 216, an error correction code (ECC) engine 217, and an advanced encryption standard (AES) engine 218. The storage controllers 210 further includes a working memory in which the FTL 214 is loaded. The CPU 213 executes the FTL 214 to control data write and read operations on the NVM 220.

[0145] The host interface 211 transmits and receives packets to and from the host 100. A packet transmitted from the host 100 to the host interface 211 includes a command or data to be written to the NVM 220. A packet transmitted from the host interface 211 to the host 100 includes a response to the command or data read from the NVM 220. The memory interface 212 transmits data to be written to the NVM 220 to the NVM 220 or receives data read from the NVM 220. The memory interface 212 complies with a standard protocol, such as Toggle or open NAND flash interface (ONFI).

[0146] The FTL 214 performs various functions, such as an address mapping operation, a wear-leveling operation, and a garbage collection operation. The address mapping operation converts a logical address received from the host 100 into a physical address used to actually store data in the NVM 220. The wear-leveling operation prevents excessive deterioration of a specific block by allowing blocks of the NVM 220 to be uniformly used. For example, the wear-leveling operation can be implemented using a firmware technique that balances erase counts of physical blocks. The garbage collection operation ensures usable capacity in the NVM 220 by erasing an existing block after copying valid data of the existing block to a new block.

[0147] The packet manager 215 generates a packet according to a protocol of an interface that consents to the host 100, or parses various types of information from the packet received from the host 100. In addition, the buffer memory 216 temporarily stores data to be written to the NVM 220 or data to be read from the NVM 220. Although the buffer memory 216 may be included in the storage controllers 210, the buffer memory 216 may be outside the storage controllers 210.

[0148] The ECC engine 217 performs error detection and correction operations on read data read from the NVM 220. More specifically, the ECC engine 217 generates parity bits for write data to be written to the NVM 220, and the generated parity bits are stored in the NVM 220 together with write data. During the reading of data from the NVM 220, the ECC engine 217 corrects an error in the read data by using the parity bits read from the NVM 220 along with the read data, and outputs error-corrected read data. The ECC engine 217 performs error correction using a fast combined chase and GMD decoding of generalized Reed-Solomon codes according to embodiments as described above, and may be implemented as an application specific integrated circuit.

[0149] The AES engine 218 performs at least one of an encryption operation and/or a decryption operation on data input to the storage controllers 210 by using a symmetric-key algorithm.

[0150] It is to be further understood that, because some of the constituent system components and method steps depicted in the accompanying figures can be implemented in software, the actual connections between the systems components (or the process steps) may differ depending upon the manner in which the present invention is programmed. Given the teachings of the present invention provided herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention.

[0151] While the present invention has been described in detail with reference to exemplary embodiments, those skilled in the art will appreciate that various modifications and substitutions can be made thereto without departing from the spirit and scope of the invention as set forth in the appended claims.