CIF: Small: List Decoding for Algebraic Geometry Codes: Theoretical Analysis, Efficient Algorithms, Practical Implementation

San Diego State University Foundation, San Diego CA

Investigators

Abstract

CIF:Small:Decoding of Algebraic Geometry Codes: Theoretical Analysis, Efficient Algorithms, Practical Implementation Error control coding ensures the reliability of data transmitted in a noisy environment and is therefore a critical component of communications systems. By adding a bit of redundancy to data, and using sophisticated mathematical algorithms to encode and decode, errors in the system can be reduced to an arbitrarily low threshold. This project concerns algebraic geometry (AG) codes, a large and powerful family of codes that includes Reed-Solomon (RS) codes, which are the standard code used in commercial products today. The standard decoding algorithm for Reed-Solomon codes is the Berlekamp-Massey algorithm, which decodes up to the sphere-packing bound. In the 1980's and 1990's, AG codes were discovered that yielded better error correction performance than RS codes, and efficient algorithms generalizing Berlekamp-Massey were developed. A method for efficiently decoding beyond the sphere-packing bound, called list decoding, was discovered in the 1990's by Sudan. This project advances the theoretical, algorithmic and applied understanding of list decoding for AG codes. There is strong evidence that Sudan's method, when used on high-rate AG codes, can perform much better than current analysis predicts, so a primary focus is improving the theoretical underpinnings of list decoding to discover its maxim capabilities for AG codes. The investigators also improve the efficiency of current algorithms and tailor them to hardware implementation by combining classical Berlekamp-Massey type methods and recent innovations due to several researchers. The investigators work with hardware and communication engineers in industry and in academia to identify applications where the special properties of AG codes will be particularly advantageous.