Decoding evaluation codes and their interleaving
FacultiesFakultät für Ingenieurwissenschaften und Informatik
Four classes of evaluation codes and their interleaving are considered in this dissertation: Reed-Solomon (RS) codes, Hermitian codes, Gabidulin codes, and Chinese remainder codes. The classical decoding approaches for these codes allow correcting up to half the minimum distance number of errors. The interleaving scheme allows for decoding beyond half the minimum distance. Our goal is to construct good decoding algorithms which are able to correct more errors with less complexity and less failure probability if any. For decoding interleaved RS codes, a version of a fast algorithm which is based on the extended Euclidean algorithm is proposed, reducing the complexity from quadratic to sub-quadratic in length. Furthermore, a joint decoding algorithm for interleaved extended RS codes is proposed, having quadratic in length complexity. We apply this algorithm to decode Hermitian codes resulting in correcting burst errors with sub-quadratic complexity. The low rate Hermitian codes can correct even more burst errors using ``power" decoding. To correct errors and erasures using Gabidulin codes and interleaved Gabidulin codes, efficient transform domain algorithms are proposed with quadratic number of operations in large field. The decoding radii and failure probability are analyzed. A syndrome-based decoder for error correction using Chinese remainder codes is proposed. Secondly, an algorithm is suggested to correct errors and erasures using generalized Chinese remainder codes which has almost linear complexity in length. In the end, we consider interleaved Chinese remainder codes correcting errors, and the corresponding decoding algorithm is analyzed from perspectives of complexity, decoding radius, and failure probability.
Subject HeadingsDecodierung [GND]
Hermeteische Form [GND]
Reed-Solomon codes [LCSH]