Gaussian Elimination Decoding of $t$ -Error Correcting Reed-Solomon Codes in $t$ Steps and $O(t^2)$ Complexity
M.P.C. Fossorier · IEEE Communications Letters · 2015
In this letter, a decoding algorithm based on Gaussian elimination is presented to decode a t-error correcting Reed-Solomon (RS) code. This algorithm requires only t steps, as opposed to the “classic” Berlekamp-Massey (BM) algorithm which requires 2t steps. Both algorithms compute 2t discrepancies which are used to iteratively update the error locator polynomial with roughly the same O(t2) complexity, but the new algorithm is twice as fast as the conventional BM algorithm as two discrepancies can be computed in parallel at each step.