DocumentCode
3134293
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
Volume
2
fYear
1997
fDate
2-4 Jul 1997
Firstpage
893
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Digital Signal Processing Proceedings, 1997. DSP 97., 1997 13th International Conference on
Conference_Location
Santorini
Print_ISBN
0-7803-4137-6
Type
conf
DOI
10.1109/ICDSP.1997.628507
Filename
628507
Link To Document