Research Project Summary

Algebraic soft-decision decoding algorithms for Reed-Solomon codes

This is my senior design project at Southeast Univeristy, China. Most work was done in the coding group in National Mobile Communication Laboratory under supervision of Prof. Chunming Zhao. The work was presented in my Bachelor's thesis.

The algebraic soft-decision decoding algorithm proposed by Koetter and Vardy was fully studied and implemented in software. Two improvement algorithms (reencoding and BGMD) were also studied and simulated.

Here is the the abstract of my Bachelor's thesis.

Due to their rigorous algebraic structure and effectiveness for correcting random symbol errors, burst errors and symbol erasures, Reed-Solomon codes have been widely used in mobile communications, deep space communications and data storage. Koetter and Vardy proposed an algebraic soft decision decoding algorithm, which offers a promising perspective to find more effective soft decoding algorithms for RS codes, and therefore, attracts many researchers.

Beginning with algebraic fundamentals, we introduce two definitions of RS codes and Berlekamp-Massey hard decision algorithm as well as its simulation results. Then, we present KV algorithm (KVA). It first converts the soft information to algebraic constraints, under which a bivariable polynomial is constructed by interpolation in the second step. Afterwards, identify all the factors of the polynomial of type y-f(x) to generate a list of candidate codewords, from which ML decision selects the output codeword finally. We analyze the principle of KVA, KV's multiplicity assignment algorithm and its simplification, Koetter's interpolation and R-R's factorization algorithms as well as practical upper bounds of KVA. After the simulation under AWGN channel, we compare the performance of RS codes of various code lengths and rates. We also discuss the influence of different complexity factors. The results reveal that KVA has 0.28-1.23dB coding gain over BMA.

We then investigate the reencoding algorithm, which can reduce the complexity by 90% at most with little performance loss. We also discuss and simulate BGMD algorithm, the combination of KVA and GMD algorithm.

Keywords: Reed-Solomon codes, Berlekamp-Massey algorithm, Koetter-Vardy algorithm, soft decision decoding, interpolation, factorization, reencoding, BGMD algorithm.