Fast combined chase and GMD decoding of generalized Reed-Solomon codes

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 signal comprising a codeword y through a digital electronic communication channel, wherein y=x+e for at least one error vector e∈Fqn, where Fq is a finite field of q elements, wherein q is a prime power, and for transmitted codeword x∈C, wherein Cis a generalized Reed-Solomon code of length n<=q−1 and that is configured to be shortened and minimum Hamming distance d≥2;
• 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.