Fast algorithms for reduction a modulo polynomial and vandermonde transform using FFT

Author

Krot, Alexander M. ; Minervina, Helena B.

Author_Institution

Inst. of Eng. Cybern., Minsk, Belarus

fYear

1998

fDate

8-11 Sept. 1998

Firstpage

1

Lastpage

4

Abstract

This paper shows on how the real algorithms for the reduction a modulo arbitrary polynomial and fast Vandermonde transform (FVT) are realized on computer using fast Fourier transform (FFT). This real-valued FVT algorithm on the developed fast reduction polynomial algorithm is based. The realization of FVT algorithm on computer with real multiplicative complexity O(2Nlog₂²N) and real additive complexity O(6Nlog₂²N) is obtained. New FVT algorithm is applied in digital signal, filtering and interpolation problems.

Keywords

computational complexity; fast Fourier transforms; polynomials; signal processing; FFT; digital signal; fast Fourier transform; fast Vandermonde transform; fast reduction polynomial algorithm; filtering theory; interpolation problems; modulo arbitrary polynomial; real additive complexity; real multiplicative complexity; Algorithm design and analysis; Complexity theory; Computers; Fast Fourier transforms; Polynomials; Signal processing algorithms; Computational complexity; fast Fourier transform; fast Vandermonde transform; linear and cyclic convolutions; reduction a modulo;

fLanguage

English

Publisher

ieee

Conference_Titel

Signal Processing Conference (EUSIPCO 1998), 9th European

Conference_Location

Rhodes

Print_ISBN

978-960-7620-06-4

Type

conf

Filename

7089765