New Look on $q2^r$ -Point Fast Fourier Transforms
Artyom M. Grigoryan, Sos С. Agaian · IEEE Transactions on Signal Processing · 2016
In this paper, the method of splitting orparallelization of calculation of the N-point discrete Fourier transform (DFT) by the DFTs of smaller orders is described. For that the concept of partitions revealing the one-dimensional (1-D) DFT of order q2r, where r > 1and q > 1 is a positive odd number, is described. Two different partitions are considered and the corresponding effective algorithms of calculation of the q2r-point 1-D DFT are described for the q = 3 case. The calculation of the transform is based on the paired representations, when the signal is represented as a set of 1-D signals which define the 1-D DFT in disjoint subsets of frequency-points which cover the set of all frequencies. The splittings of the q2r-point 1-D DFT are performed by the 1-D discrete 2and qpaired transforms which allow for calculating with a minimum number of operations. The examples of the paired transforms and computational complexity of the proposed algorithms for the N = 6 and 12 cases are given.