The Decoding Research Of Reed-Solomon Code

Reed-Solomon code is an important class of linear block codes in the field of error correction code with tight algebraic structure. Due to its superior capability of error correction (especially, the advantage of correcting burst errors), RS code is usually used in data storage and modern digital communication systems. Generally hard-decision decoding algorithm of RS code is employed in the practical application which has a performance loss of2-3dB compared with the performance of more complex soft decision decoding algorithm. This thesis mainly treats soft-decision decoding algorithm of RS code.Firstly, in this thesis the fundamental theory of RS code is introduced along with time-domain encoding and frequency-domain encoding. Widely used hard-decision decoding BM algorithm is then given. The analysis of complexity of BM algorithm shows that the complexity is mainly concentrated on the computation of the syndrome and finding the root of the error locator polynomial under the condition of redundancy p<n/4. The complexity is slightly larger than the linear growth of code length n for long code which is an important condition that RS code is widely adopted in a variety of applications.Then we turn to the main soft-decision decoding algorithm such as generalized minimum distance (GMD) algorithm, Chase algorithm, algebraic soft decoding (ASD) algorithm proposed by Koetter and Vardy, adaptive belief propagation (ABP) algorithm given by Jing Jiang and Narayanana. The performance and complexity of the last two powerful algorithms are explored in more detail. Simulation results manifest that both algebraic soft-decision decoding algorithm and adaptive belief propagation algorithm provide obvious coding gain over conventional hard-decision decoding.Finally, concatenated algorithm is investigated which combines ABP algorithm and KV algorithm proposed by Mostafa.E and Robert JM. The complexity of ABP-KV algorithm is dissatisfactory. In view of its complexity, a revised algorithm is present for the concatenated algorithm with lower complexity. The purpose of ABP algorithm is to enhance the reliability of the received codeword by iteratively updating the log-likehood ratios. The improvement of this thesis contains the following steps based on the accuracy of the enhanced soft information,(1) all symbols are ordered on the basis of reliability measure in KV algorithm,(2) the s least reliable symbols are removed,(3) correspondingly, after the processing of (1) and (2), only (n-s) symbols have to be sent to the expensive bivariate interpolation. This thesis is concluded with the simulation results that the proposed algorithm has acceptable coding gains while the computational complexity is significantly reduced.