Binary mapping of nonbinary codes and soft decision decoding algorithms of Reed-Solomon codes based on bit reliability.

摘要

This dissertation is intended to investigate soft decision decoding algorithms for Reed Solomon (RS) codes to achieve optimal or suboptimal performance with drastically reduced decoding complexity. Research contains three major parts.; The first part presents a method to form generator matrices of binary images of RS codes. In order to encode or decode codewords in an RS code with binary phase shift keying (BPSK) transmission, a binary generator of an RS code is required. The relation of binary generators of an RS code based on different mapping bases is explored. Furthermore, this method can be expanded into the other nonbinary codes, such as shorten RS codes, and maximum distance separable (MDS) codes.; In the second part, a computationally efficient hybrid decoding algorithm, including the re-encoding process and successive bit-and-symbol, erasure-and-error decoding algorithms (SBSEED), is devised. To eliminate the decoding complexity, the re-encoding process is first proposed to accept the information from the SDSEED algorithm. Two criteria in the re-encoding process serving the functions of examining error patterns and optimality testing have been invented. A less search complexity algorithm, implemented in a two-dimensional way, is investigated to form a list of error patterns. By simulations, this hybrid decoding algorithm can achieve a performance close to the MLD with a significant reduction in the decoding complexity.; The final part proposes a two-stage decoding algorithm for an RS codes. Based on a binary generator of an RS code, we develop a method to partition it into two generator submatrices. In each stage decoder, an MLD algorithm based on a corresponding generator submatrix is employed. With such a partition method, there are m different ways to partition a binary generator of RS codes over GF(2m). Consequently, a two-stage decoding scheme contains two-stage decoders connected in parallel, based on the m different matrix partitions. A proposed two-stage decoding algorithm is constituted by the two-stage decoding scheme and a final decision selector choosing the result codeword. This decoding algorithm is proved to be asymptotically optimal.