Title :
Complexity of implementation for evaluating polynomials over GF(2m)
Author_Institution :
Dept. of Electr. Eng., Linkoping Univ., Sweden
Abstract :
The evaluation of a polynomial over a finite field is widely used in discrete Fourier transforms, factorisation and solving equations. In addition, a decoder for Reed-Solomon codes and related codes can be constructed with two functional circuits: one for solving the key equations and one for evaluating polynomials. Two fundamental methods for evaluating polynomials are investigated. The time and space complexity of the implementations are estimated.
Keywords :
codes; decoding; encoding; information theory; polynomials; Chien method; Horner method; Reed-Solomon codes; decoder; discrete Fourier transforms; equation solving; factorisation; finite field; polynomials; space complexity; time complexity;
Journal_Title :
Electronics Letters
DOI :
10.1049/el:19911095
