High-Performance Decoding of Algebraic Codes Beyond their Packing Radii

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Abstract This research will improve the decoding of error-control codes, in particular, Reed-Solomon codes, which are essential in most advanced modern communication and storage systems, ranging from deep space communication to optical and magnetic storage systems, such as the compact disk and CD-ROM. By developing decoders that operate at lower signal to noise ratios, this research will allow the recovery of data and records that currently are unreadable. This research will develop an efficient soft decoding algorithm that will significantly outperform GMD-based decoding algorithms. The algorithm is based on Sudan's list decoding technique that produces a list of tentative codewords and it shows a number of very interesting features. Among the most intriguing characteristics of the algorithm is a complexity and performance that can be traded freely within certain fundamental limits. Hence, the coding gain provided by the Reed-Solomon code can be traded on the fly for complexity in any application with the maximal list size changing accordingly.