A Rate-Distortion Perspective on Multiple Decoding Attempts for Reed-Solomon Codes

Reed-Solomon (RS) codes are one of the most widely used error correcting codes in digital communication and data storage systems. This is primarily due to the fact that RS codes are maximum distance separable (MDS) codes, can correct long bursts of errors, and have efficient hard-decision decoding (HDD) algorithms, such as the Berlekamp-Massey (BM) algorithm, which can correct up to half the minimum distance ($d_{min}$) of the code. An $(n,k)$ RS codes of length $n$ and dimension $k$ is known to have $d_{min}=n-k+1$ due to its MDS nature.

Since the arrival or RS codes, researchers have put a considerable effort into improving the decoding performance at the expense of complexity.

  • A breakthrough result of Guruswami and Sudan (GS) introduces a hard-decision list-decoding algorithm that can corrects beyond haf the minimum distance of the code. HDD algorithms, however, do not fully exploit the information provided by the channel output.
  • Koetter and Vardy later extended the GS decoder to an algebraic soft-decision (ASD) decoding algorithm by converting the probabilities observed at the channel output into algebraic interpolation conditions in terms of a multiplixity matrix.

Both of these algorithms however have significant computational complexity. Thus, multiple runs of error-and-erasure and error-only decoding with some low complexity algorithm, such as the BM algorithm, has renewed the interest of researchers.

(to be completed) - see our recent publication in the publications page

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License