Improved Decoding Algorithms for Reed-Solomon Codes

In coding theory, Reed-Solomon codes are one of the most well-known and widely used classes of error-correcting codes. In this thesis we study and compare two major strategies known for their decoding procedure, the Peterson-Gorenstein-Zierler (PGZ) and the Berlekamp-Massey (BM) decoder, in order to improve existing decoding algorithms and propose faster new ones, based on a parallel implementation in integrated circuits. In particular we prove the correctness of a modified version of the PGZ decoder, which will be called the fast Peterson-Gorenstein-Zierler (fPGZ) decoding algorithm. This improvement is obtained by exploiting the Hankel structure of the matrices involved in the decoding and the resulting procedure can be seen as a particular case of the BM decoder. Indeed we prove that the intermediate outcomes obtained in the implementation of fPGZ are a subset of those of the BM decoding algorithm. In addition, thanks to the study done on the structure of the syndrome matrix and its leading principal minors, we improve the error value computation in both the decoding strategies studied (specifically we prove new error value formulas for the fPGZ and the BM decoding algorithm) and moreover we state a new iterative formulation of the PGZ decoder well suited to a parallel implementation on integrated microchips. Thus using techniques of linear algebra we obtain a parallel decoding algorithm for Reed-Solomon codes with an O(e) computational time complexity, where e is the number of errors which occurred, although a fairly large number of elementary circuit elements is needed. Finally the former decoding algorithm is compared with a parallel implementation of the BM decoder, which is less expensive and simpler from the point of view of the hardware required, but has an O(t) computational time complexity (t is the error correction capability and we always have e<=t)