A new Reed-Solomon code decoding algorithm based on Newton's interpolation

摘要

A Reed-Solomon code decoding algorithm based on Newton's interpolation is presented. This algorithm has as main application fast generalized-minimum-distance decoding of Reed-Solomon codes. It uses a modified Berlekamp-Massey algorithm to perform all necessary generalized-minimum-distance decoding steps in only one run. With a time-domain form of the new decoder the overall asymptotic generalized-minimum-distance decoding complexity becomes O(dn), with n the length and d the distance of the code (including the calculation of all error locations and values). This asymptotic complexity is optimal. Other applications are the possibility of fast decoding of Reed-Solomon codes with adaptive redundancy and a general parallel decoding algorithm with zero delay.