University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Trellis decoding of Reed Solomon codes.

Shin, Sooyoung Kim. (1994) Trellis decoding of Reed Solomon codes. Doctoral thesis, University of Surrey (United Kingdom)..

Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (39MB) | Preview


Reed Solomon codes, a subset of multi-level cyclic block codes with, powerful error-correcting capabilities, are computationally very efficient when algebraic decoding is applied. They may, however, give weaker performance compared to convolutional codes, at least at moderate bit error rates (around 10-5 to 10-6) on the AWGN channel. This disadvantage mainly results from the lack of a generally applicable method for soft decision decoding. Because of easy acceptance of soft decision information, trellis decoders incorporating soft decisions can produce quite useful improvements in coding gain over hard decisions with little increase in complexity. Although trellis methods are commonly used for convolutional codes they can be applied to block codes[23]. In this project, therefore, it is intended to present results of an investigation of soft decision trellis decoding as applied to Reed Solomon codes, and the development of effective decoding algorithms. As a means of maximum likelihood decoding, Viterbi decoding for Reed Solomon codes was attempted. However, the complexity of such a decoder is often prohibitive. In order to reduce the complexity of the Viterbi decoder, an existing reduced search algorithm, which was developed for convolutional codes, was applied to Reed Solomon codes. Moreover, new reduced search methods were developed to enhance its computational efficiency. In contrast to convolutional codes, low rate codes require higher decoder complexity than high rate codes for Viterbi decoding of Reed Solomon codes. For low rate Reed Solomon codes, therefore, the Fano sequential decoding algorithm was investigated, since the complexity of a sequential decoder is independent of the number of encoder memory elements. A simulation model incorporating an AWGN channel has been used to establish the performance of the various suggested decoding algorithms. Importance sampling simulation techniques have been used to reduce simulation time. Simulation results of Viterbi decoding showed that soft decision decoding for the Reed Solomon codes could give at least 2dB coding gain over hard decision decoding on the AWGN channel and that the performance of reduced search, and sequential decoding could approximate that of the Viterbi method with much better computational efficiency. Theoretical decoding performance has been established by using the weight distributions of the codes. Based upon the theoretical results, the simulation results have been analysed. Moreover, the performance and the computational efficiency of each decoding method have been compared, and the advantages and disadvantages of each method indicated. It has been shown that, by using trellis methods, the potential disadvantages of Reed Solomon codes can be removed, and thus the performance of trellis decoded Reed Solomon codes is comparable with that of convolutional codes on the AWGN channel at moderate bit error rate. Therefore, Reed Solomon codes may be used in a wider range of applications, possibly with the decoding method adjusted to the channel conditions.

Item Type: Thesis (Doctoral)
Divisions : Theses
Authors :
Shin, Sooyoung Kim.
Date : 1994
Contributors :
Depositing User : EPrints Services
Date Deposited : 09 Nov 2017 12:14
Last Modified : 15 Mar 2018 20:45

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800