Existence of a 2 ⁿ FFT algorithm with a number of multiplications lower than 2 ^{n
+1}

16 August 1984

journal article
Published by Institution of Engineering and Technology (IET) in Electronics Letters

Vol. 20 (17) , 690-692
https://doi.org/10.1049/el:19840474

Abstract

First we give a decomposition of an FFT of length 2ⁿ into a number of one-dimensional polynomial products. If these products are computed with minimum multiplication algorithms, we show that the 2n FFT can be computed with less than 2ⁿ⁺¹ nontrivial complex multiplications. A variation of this algorithm is also shown to give the same multiplication count as the ‘split-radix’ FFT.

Keywords

MINIMUM MULTIPLICATION ALGORITHMS
2N FFT ALGORITHM
MULTIPLICATION COUNT
DECOMPOSITION
NUMBER OF ONE-DIMENSIONAL POLYNOMIAL PRODUCTS
NONTRIVIAL COMPLEX MULTIPLICATIONS
MULTIPLICATIONS LESS THAN 2N+1 SPLIT RADIX FFT

This publication has 1 reference indexed in Scilit:

Fast Fourier Transform and Convolution Algorithms
Published by Springer Nature ,1981

Existence of a 2 n FFT algorithm with a number of multiplications lower than 2 n +1

Abstract

Keywords

Existence of a 2 ⁿ FFT algorithm with a number of multiplications lower than 2 ^{n
+1}