BCH fast soft decoding beyond the (d-1)/2 bound

A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executed by the computer to perform method steps for a Bose-Chaudhuri-Hocquenghem (BCH) soft error decoding, comprising the steps of:

• receiving a codeword x through a digital electronic communication channel, wherein the received codeword x has τ=t+r errors for some r≥1, wherein t=(d−1)/2 and d is a minimal distance of a BCH code;
• performing error correction on the codeword to generate a corrected codeword;
• and
• outputting data included in the corrected codeword to the digital electronic communication channel,
• wherein performing the error correction comprises
• computing a minimal monotone basis {λi(x)}1≤i≤r+1⊆F[x] of an affine space V={λ(x)ϵF[x]:λ(x)·S(x)=λ′(x) (mod x2t), λ(0)=1, deg(λ(x)≤t+r}, wherein λ(x) is an error locator polynomial, S(x) is a syndrome, and F[x]=GF(q) wherein q=2m for m>1;
• computing a matrix A≡(λj(βi))iϵ[w], jϵ[r+1], wherein W={β1, . . . , βw} is a set of weak bits in x;
• constructing a submatrix of r+1 rows from sub matrices of r+1 rows of the subsets of A such that the last column is a linear combination of the other columns;
• forming a candidate error locating polynomial using coefficients of the minimal monotone basis that result from the constructed submatrix;
• performing a fast Chien search wherein the candidate error locating polynomial is verified;
• and
• flipping channel hard decision at error locations found in the candidate error locating polynomial and returning the decoded codeword x.

A computer memory-based product, comprising:

• a memory;
• and
• a digital circuit tangibly embodying a program of instructions executed by the computer to perform a method for a Bose-Chaudhuri-Hocquenghem (BCH) soft error decoding, wherein the method comprises the steps of:
• receiving a codeword x through a digital electronic communication channel, wherein the received codeword x has τ=t+r errors for some r≥1, wherein t=(d−1)/2 and d is a minimal distance of a BCH code;
• performing error correction on the codeword to generate a corrected codeword;
• and
• outputting data included in the corrected codeword to the digital electronic communication channel,
• wherein performing the error correction comprises
• computing a minimal monotone basis {λi(x)}1≤i≤r+1⊆F[x] of an affine space V={λ(x)ϵF[x]:λ(x)·S(x)=λ′(x) (mod x2t), λ(0)=1, deg(λ(x)≤t+r}, wherein λ(x) is an error locator polynomial, S(x) is a syndrome, and F[x] GF(q) wherein q=2m for m>1;
• computing a matrix A≡(λj(βi))iϵ[w], jϵ[r+1], wherein W={β1, . . . , βw} is a set of weak bits in x;
• processing for every subset W′⊆W by retrieving from memory a set W″=R(W′), computing BW′ by adding one row to BW″ and performing Gaussian elimination operations on BW′, wherein R(W′) is reliability probabilities of the bits in W′;
• wherein when a first r′ columns of BW′ are a transpose of a systematic matrix and deg(λ(x))=t+r′, wherein 1≤r′≤r, performing:
• computing u(x)=gcd(λ(x), λ′(x)), wherein λ′(x) is a derivative of λ(x);
• computing λ(Φ\W′) and deducting from it Zλ(x),Φwherein Zλ(x),Φ={βϵΦ:
• λ(β)=0}, when u(x) is a scalar in F*;
• adding a pair (λ(x), Zλ(x),Φ) to set a L of all (r′, λ(x), Zλ(x),Φ) such that 1≤r′≤r, λ(x)ϵV′r′, |Zλ(x),W|≥r′+1, and |Zλ(x),Φ|=t+r′, when |Zλ(x),Φ|=t+r′;
• and
• outputting the set L.