Contributions to folded reed-solomon codes for burst error correction

Abstract

Reed-Solomon (RS) codes are well-known maximal distance separable codes. They achieve the best compromise between the code rate and the minimum distance. Also the results of algebraic list decoding of RS codes shows they are also highly non-perfect codes. Due to these reasons, research on RS codes is interesting. In this thesis, the construction of folded RS codes is generalized to any RS, Generalized RS (GRS) codes and BCH codes with code length being a composite number. The cooperative list decoding of folded RS codes in burst error channels is studied. Also, a transform is derived to retrieve the message vector from the list decoding output when the RS code is not encoded in the polynomial evaluation fashion. Moreover, a possible way to decoding folded GRS codes is presented by making use of the synthesis of multisequences with unknown elements in the middle. In addition, since the row codes of folded RS codes are usually RS codes with short length and share the same error pattern, a search-based list decoding algorithm of RS codes is derived. Finally, a decoding algorithm based on Grobner bases and generalized Newton's Identity is proposed and its application to decode interleaved RS codes is studied.