Gaussian Elimination Decoding of -Error Correcting Reed-Solomon Codes in Steps and

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(t²) 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.