ON FAST DECODING ALGORITHMS FOR LOW-ERROR-CORRECTING-CAPABILITY REED-SOLOMON CODES

Abstract

This thesis studies efficient decoding algorithms for low error correcting capability RS (Reed-Solomon) codes. By studying the properties of DBEC-TBED (Double-Byte-Error-Correction & Triple-Byte-Error-Detection) RS codes, we derive a very simple algorithm for finding the error locator polynomial of such codes. By testing the weight of the syndrome vector, this algorithm is more suitable for parallel processing. In general, it has computational advantage over the Lee-Deng-Koh and Berlekamp-Massey algorithms. By extending the idea for decoding of DBEC-TBED RS codes, efficient decoding algorithms for TBEC (Triple-Byte-Error-Correction) RS codes and TBEC-QBED (Triple-Byte-Error-Correction & Quad-Byte-Error-Detection) RS codes can be obtained. The method for finding the error locations or the roots of the error locator polynomial is another important topic in this thesis. We show that any general quadratic, cubic and quartic equations can always be reduced to normalized forms. The roots of quadratic equation and cubic equation can be found easily based on the normalized forms. A novel technique for solving quartic equations is then proposed. Based on the relationship between roots of the normalized quartic equation, we derive a formula to calculate a particular root, using which all roots can be found. These methods can speed up the decoding of RS codes. The techniques are implemented using MATLAB. Their computational advantages are shown compared with other existing algorithms.