A general purpose Reed-Solomon CODEC simulator and new periodicity algorithm

Ye, Ying (1995) A general purpose Reed-Solomon CODEC simulator and new periodicity algorithm. Masters thesis, Memorial University of Newfoundland.

[English] PDF (Migrated (PDF/A Conversion) from original format: (application/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 (10MB) [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. (Original Version)

Abstract

In most digital communication systems, if we can afford to send data below the modem transmission speed, then it is possible to achieve the system bit error rate as small as we desire by using error control codes. The Reed-Solomon codes are such error control codes, that are widely used for forward error correction due to their optimal characteristics in both Hamming distance and structure, but most of all, their capacity for correcting both random and burst errors. -- Finding a suitable code for a communication channel, or trying to explain how the Reed-Solomon codes work, or comparing various decoding methods is not an easy task, hence this thesis developed a general purpose Reed-Solomon (RS) coding and decoding (codec) simulator for teaching as well as research purposes. -- The RS codec simulator has two versions that can be run under Microsoft Windows and Unix operating system, respectively. A friendly and easy-to-use graphical user interface (GUI) is provided for PC. The user can define a code by selecting the symbol length m from 3 to 8 bits and the error correcting capability T of up to 20. -- In the encoder, the systematic code generation and the self-reciprocal generator polynomial are used. The noisy channel can be modeled by an error pattern. This error pattern can either be entered by the user with the arbitrary weight or generated by an external program, which generates all possible error positions. In the decoding process, both the Peterson and Berlekamp-Massey algorithms are available for finding the error locator polynomial. The simulation results show that the Peterson's direct method is better when T ≤ 6. However, the Berlekamp-Massey algorithm is much faster when T > 6. Chien search is used for locating the error position in the received word. Although the error values can be obtained by using either Gauss-Jordan elimination or Forney's algorithm, Gauss-Jordan elimination is preferred when T is small, i.e. T ≤ 10, but as T increased, i.e. T > 10, the Forney algorithm should be used in order to minimize decoding time. -- It is found that the periodicity algorithm conceived by S.Le-Ngoc and Z.Young [1] [2] is a special case of the LeNgoc-Ye Transformation Algorithm [3]. An improved periodicity algorithm is proposed which can eliminate the division operation required by the LeNgoc-Young algorithm. The analysis shows that the periodicity algorithm is valid for all values of m. Furthermore, a new periodicity algorithm is also developed by using direct solution method to eliminate the index table required in the proposed periodicity algorithm. It is shown that the new periodicity algorithm outperforms the look-up table, Chien search, binary decision (fast Chien search) and Okano-Imai algorithms in terms of optimization of both memory space and decoding time. The new periodicity algorithm has a simple structure and therefore it is well suited for VLSI implementation.

Actions (login required)

View Item