UC San Diego

This dissertation is concerned with algebraic list- decoding of error-correcting codes. During the past decade, significant advances in this are were achieved. The breakthrough papers of Sudan, Guruswami & Sudan, and Koetter & Vardy showed that the well-known Reed-Solomon (and other algebraic) codes can correct many more errors - - in the list-decoding sense -- than previously thought possible. Herein, we extend the theory developed in these seminal papers, and improve upon the results reported therein. We first extend the bivariate polynomial interpolation method of Guruswami-Sudan to multivariate interpolation decoding. To this end, we develop a new decoding algorithm for Reed-Solomon codes, which decodes some M codewords together. We show that if the channel errors are synchronized then, with high probability, our multivariate interpolation decoding algorithm corrects up to $n(1 - RM/(M+1) errors in a Reed-Solomon code of length $n$ and rate $R$. This is much higher than the Guruswami- Sudan decoding radius of $n(1 - R¹⁻²). Next, we consider the case of adversarial errors. We introduce a new family of codes that have a polynomial-time list-decoder correcting a fraction of $1-\epsilon$ adversarial errors for a code of rate [Omega[varepsilon]/log(1[varepsilon]. The best previously known results required a rate of $O[varepsilon²) for the same error-correction radius. In addition to the transition from bivariate to multivariate interpolation, we also modify the Reed-Solomon codes in an essential way. Reed-Solomon encoders view a message as a polynomial f(X), and produce the corresponding codeword by evaluating f(X) at n distinct elements of F_q. In Chapter 3, given f(X), we compute one or more related polynomials g_i(X) and produce the corresponding codeword by evaluating all these polynomials. The a priori correlation between f(X) and g_i(X) then enables us to recover the encoded message from the output of the interpolation process. Finally, we consider soft-decision list-decoding. Koetter & Vardy have shown that algebraic soft-decision decoding can be achieved by converting symbol probabilities observed at the channel output into interpolation multiplicities. Such conversion is known as the multiplicity assignment problem. In Chapter 4, we first recast the multiplicity assignment problem into a geometric framework, and use this framework to establish certain properties of the optimal solution. We then devise a sub-optimal solution based upon optimization of second- order statistics. Specifically, we minimize the Chebyshev bound on the probability of failure of the soft-decision decoder. This leads to coding gains of 0.25 dB to 0.75 dB, as compared to the Koetter-Vardy multiplicity assignment algorithm. It is widely recognized that bivariate (or multivariate) interpolation is the most computationally intensive step in algebraic list-decoding algorithms. In Chapter 5, we show that bivariate polynomial interpolation is equivalent to computing a certain chain product of polynomial matrices. We then derive a dynamic-programming algorithm to parse this matrix-chain product in an optimal way. This leads to a reduction in the computational complexity of the interpolation process by a factor of at least two, as compared to the interpolation algorithm of Koetter