Title :
Algorithms and the multiplicative complexity of the reduction a modulo arbitrary polynomial, generalized KN-convolution and fast Vandermonde transform
Author :
Krot, Alexander M.
Author_Institution :
Inst. of Eng. Cybern., Acad. of Sci., Minsk, Byelorussia
Abstract :
This paper proves that the number of multiplications required for calculating the product of two polynomial modulo and arbitrary polynomial q(z) (or generalized KN-convolution), whose coefficients do not belong to the field of constants, is three times higher than the estimate for the case when the coefficients do belong to the field of constants. The existence of a fast Vandermonde transform (FVT) algorithm with the multiplicative complexity (O4NlogN) is shown. The new fast algorithms have applications in filtering and interpolation of digital signal and images
Keywords :
computational complexity; convolution; digital filters; filtering theory; interpolation; polynomials; signal processing; transforms; coefficients; digital filtering; digital images; digital signal; fast Vandermonde transform; fast algorithms; field of constants; generalized KN-convolution; interpolation; multiplications; multiplicative complexity; reduction a modulo arbitrary polynomial; Convolution; Digital filters; Digital signal processing; Discrete Fourier transforms; Filtering algorithms; Fourier transforms; Interpolation; Optimal control; Polynomials; Signal processing algorithms;
Conference_Titel :
Digital Signal Processing Proceedings, 1997. DSP 97., 1997 13th International Conference on
Conference_Location :
Santorini
Print_ISBN :
0-7803-4137-6
DOI :
10.1109/ICDSP.1997.628507
