Algebraic decoding over finite and complex fields using reliability information

Abstract

In this dissertation, new algebraic decoding algorithms for Reed–Solomon codes are developed, all of which use reliability information. The two main scenarios are Reed–Solomon codes defined over finite fields and the complex field. For each scenario, we introduce two new algorithms: a syndrome-based and an interpolation-based decoder. For the first scenario, a syndrome-based method which depends on an intermediate decoding result obtained by the extended Euclidean algorithm is investigated. This method is suitable only for high-rate codes, where one or two additionally correctable errors are valuable. The second method in this scenario, utilizes the same intermediate result to perform an interpolation step similar to the Wu algorithm but with a reduced number of interpolation points. As a results, the complexity of the interpolation step is reduced considerably. The second scenario is the decoding of complex-valued Reed–Solomon codes, which recently gained attention in deterministic Compressed Sensing schemes. They allow the use of known algebraic decoding algorithms for sparse vector reconstruction. It is also possible to extract and exploit intrinsic reliability information. The first decoding method for this scenario performs a multi trial error/erasure decoding procedure to enhance the quality of the reliability information. While the other is a list decoder based on both the Guruswami–Sudan algorithm and generelized minimum distance decoding. The performance of all the aforementioned algorithms has been investigated and compared with similar state-of-the-art algorithms. Without exceptions, their performance surpasses that of their counterparts. The second part of this work has been supported by the German research council Deutsche Forschungsgemeinschaft (DFG) under Grant Bo 867/35-1.