New Look on q2r-Point Fast Fourier Transforms

In this paper, the method of splitting or parallelization 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 q2(r), where r > 1 and q > 1 is a positive odd number, is described. Two different partitions are considered and the corresponding effective algorithms of calculation of the q2(r)-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 q2(r)-point 1-D DFT are performed by the 1-D discrete 2- and q-paired 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.