A Reed-Solomon code simulator and periodicity algorithm

Young, Zhenpen (1994) A Reed-Solomon code simulator and periodicity algorithm. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (31MB)

Abstract

Communication channels are usually affected by various kinds of noise. As a result, errors occur in data transmissions. Reed-Solomon (RS) codes, as other channel codings, are widely used to eliminate the errors due to its optimal characteristics in both Hamming distance and structure but most of all its capability of correcting both random and burst errors. -- The selection of the best RS code for a specific communication channel is always a major issue in system design. Hence, this thesis introduces and implements an RS code simulator to study a wide range of RS codes. The simulator first encodes the user's message into a codeword. The user can choose the symbol length m from 3 bits up to 8 bits or the block length N from 7 symbols up to 255 symbols, and the error correcting capability T of up to 16 random errored symbols. Then the user enters an error pattern of arbitrary weight which the simulator adds to the generated codeword. The resulting received word is then decoded. Either the direct (Peterson's) or iterative (Berlekamp's) method is used to construct the error locator polynomial. Only the Chien search is used as a root search technique for the error locator polynomial. This simulator does not handle erasures. -- Commonly, Chien search is used to find out all the possible roots of the error locator polynomial. It is found that for the double error correcting case (T = 2) these roots are not randomly distributed but they follow certain patterns. Based on these patterns, the periodicity algorithm is introduced and its validity is verified by exhaustive computer simulations. -- With fewer than 8 additions, 4 decision operations and only N symbols of memory space required, the periodicity algorithm outperforms Chien search and the binary decision fast Chien search techniques in terms of decoding time. Most of all it also outperforms the Okano's analytical solutions by a decision operation. Of course, the look-up table is the fastest in terms of the decoding time but its memory space required is N². This will limit its use when N is large. Therefore, it is concluded that the periodicity algorithm is the optimal solution for both decoding time and memory space. This algorithm is found to be very suitable for use in microprocessor based decoders.

Actions (login required)

View Item