  Document Type  :  Latin Dissertation  Language of Document  :  English  Record Number  :  53708  Doc. No  :  TL23662  Call number  :  3244733  Main Entry  :  Farzad Parvaresh  Title & Author  :  Algebraic list decoding of error correcting codesFarzad Parvaresh  College  :  University of California, San Diego  Date  :  2007  Degree  :  Ph.D.  student score  :  2007  Page No  :  154  Abstract  :  This dissertation is concerned with algebraic listdecoding of errorcorrecting 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 wellknown ReedSolomon (and other algebraic) codes can correct many more errorsin the listdecoding sensethan 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 GuruswamiSudan to multivariate interpolation decoding. To this end, we develop a new decoding algorithm for ReedSolomon 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 ReedSolomon code of length n and rate R. This is much higher than the GuruswamiSudan decoding radius of n (1  R1/2). Next, we consider the case of adversarial errors. We introduce a new family of codes that have a polynomialtime listdecoder correcting a fraction of 1  ε adversarial errors for a code of rate Ω(ε/log(1/ε)). The best previously known results required a rate of O(ε 2) for the same errorcorrection radius. In addition to the transition from bivariate to multivariate interpolation, we also modify the ReedSolomon codes in an essential way. ReedSolomon encoders view a message as a polynomial f(X), and produce the corresponding codeword by evaluating f(X) at n distinct elements of [special characters omitted]q. In Chapter 3, given f( X), we compute one or more related polynomials gi( X) and produce the corresponding codeword by evaluating all these polynomials. The a priori correlation between f(X) and gi( X) then enables us to recover the encoded message from the output of the interpolation process. Finally, we consider softdecision listdecoding. Koetter & Vardy have shown that algebraic softdecision 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 suboptimal solution based upon optimization of secondorder statistics. Specifically, we minimize the Chebyshev bound on the probability of failure of the softdecision decoder. This leads to coding gains of 0.25 dB to 0.75 dB, as compared to the KoetterVardy multiplicity assignment algorithm. It is widely recognized that bivariate (or multivariate) interpolation is the most computationally intensive step in algebraic listdecoding 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 dynamicprogramming algorithm to parse this matrixchain 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.  Subject  :  Applied sciences; Algebraic listdecoding; Errorcorrecting codes; Electrical engineering; 0544:Electrical engineering  Added Entry  :  A. Vardy  Added Entry  :  University of California, San Diego 
     
   
http://lib.clisel.com/site/catalogue/53708

 