A fast algorithm for polynomial evaluation in Reed-Solomon codec

摘要

An efficient lookup table algorithm for computing the values of message polynomials during high throughput encoding of Reed-Solomon (RS) codes is presented in this paper. The algorithm can be applied to RS codes encoders, which are based on Vandermonde matrix and the polynomial computations. The lookup table derived from the algorithm can then be applied not only to an encoder of RS codes but also to syndromes evaluation in the decoding of RS codes. By comparison with Horner's rule, one of the advantages of utilizing this algorithm is that the table lookup operations for computing the values of the message polynomial are reduced by a factor of three. It would reduce the encoding time by fifty-percent using the linear feedback shift register to encode the (204, 188, t=8) RS code. The algorithm can also be used to evaluate the syndromes needed in part of the RS decoder, and thus the speed is much faster than Horner's rule. Ultimately, the proposed encoding and syndrome evaluation algorithm for RS codes can be made regular, simple and suitable for software implementations.