[[abstract]]In the step-by-step Reed-Solomon decoding, in order to reduce the computation complexity, speed up the decoding process, and correct errors and erasures, new decoding algorithms and procedures are proposed and investigated in this thesis.First, we present a new step-by-step RS decoding algorithm for errors-only correcting to reduce the computation complexity of the conventional step-by-step RS decoding algorithm. The step-by-step RS decoding algorithm corrects the errors in terms of the differences between the original syndrome matrices and the temporarily changed syndrome matrices. This idea is based on the fact that the weight of error patterns can be distinguished from each other by using the syndrome matrices. If the weight of the error pattern is reduced, both the error location and the corresponding error value are found. However, the conventional step-by-step decoding algorithm must perform 2m - 1 iterations for each received symbol to detect whether or not every nonzero element of GF(2m) is the possible error value. For decoding each received symbol, we derive and simplify the computation of the determinants of the changed syndrome matrices. Then a new syndrome matrix is developed and defined. Several theorems for the new syndrome matrix are proposed. The new step-by-step decoding algorithm for errors-only correcting can directly determine whether the decoded symbol is an error location or not by detecting the new syndrome matrix. The corresponding error value then can be immediately obtained if the decoded symbol is an error location. Compared with the conventional step-by-step decoding algorithm, the computation complexity can be reduced by a factor of 2m — 1 for Reed-Solomon codes over GF(2m).Secondly, we propose a fast step-by-step decoding procedure to speed up the decoding process. The fast step-by-step decoding procedure decodes the received symbols in order from rn-1, rn-2, ..., till r0. For decoding each symbol rn-j, we derive several formulas to obtain fast the corresponding syndrome values and syndrome matrices of rn-j from those of rn-j+1. We find directly a probable and unique value of the corresponding error value which is designated as the quasi-error-value. Then the truth of the quasi-error-value is detected and the corresponding error value of rn-j is determined. Based on the fast step-by-step decoding procedure, a pipelined high-speed decoder architecture is presented, too. This pipelined decoder can be operated in a bit rate of several Gbits/sec and thus suitable for the very high speed data transmission systems.Finally, a step-by-step decoding algorithm for correcting errors and erasures is proposed and investigated. This decoding algorithm decodes the received symbols in the manner of symbol-by-symbol. For decoding each symbol, the corresponding error or erasure value can be directly found. A fast step-by-step decoding procedure for correcting errors and erasures is also proposed. Compared with the standard algebraic decoding, this step-by-step error/erasure decoding algorithm does not need to find the coefficients of the error-locator polynomial, to search the error locations, and to calculate the error evaluator and error/erasure polynomials for obtaining the error and erasure values.
展开▼
