On The Decoding Algorithms For RS Codes And Their Implementations

Being a powerful class of nonbinary maximum distance separable codes, the family of Reed-Solomon (RS) codes has been widely used in modern digital communication systems and data storage devices. This dissertation is intended to investigate the optimal design of parallel finite field multiplier and the low-complexity soft-decision decoding algorithms for RS codes. The research includes five parts:1. Using the functional decomposition technique, we develop a method for automatically designing a high-speed parallel finite field multiplier, which is very suitable for implementation in the popular FPGA. The RS decoder's operation frequency is significantly improved by adopting this generated finite field multiplier.2. A key equation solver with comlexity of O (t 2) is developed for the fast GMD decoding of RS codes.3. Define a novel symbol-level reliability metric, which is calculated from the assigned multiplicities of all interpolation points contained in the corresponding point subset. And based on Koetter-Vardy algorithm, a soft GMD algorithm is presented. The proposed algorithm makes full use of the transitive interpolation polynomials, and improves the decoding performance of RS codes.4. Based on the symbol-by-symbol detection, this thesis presents a concept of decision-coordinate and the decision-coordinate-level reliability metric. Based on the reliability metric, a modified Chase algorithm is proposed, and an optimality condition suitable for nonbinary codes is derived. The optimality condition is used to reduce the decoding complexity.5. A dual reliability metric which combines the multiplitive interference and the additive noise is provided to measure the reliability of the received symbol over a fading channel. And a low-complexity erased Chase algorithm is developed.