Gaussian Elimination Decoding of src='/images/tex/695.gif' alt='t'> -Error Correcting Reed-Solomon Codes in src='/images/tex/695.gif' alt='t'> Steps and src='/images/tex/29312.gif' alt='O(t^2)'> Complexity

摘要

In this letter, a decoding algorithm based on Gaussian elimination is presented to decode a -error correcting Reed-Solomon (RS) code. This algorithm requires only steps, as opposed to the “classic” Berlekamp-Massey (BM) algorithm which requires steps. Both algorithms compute discrepancies which are used to iteratively update the error locator polynomial with roughly the same 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.