Radix-R FFT and IFFT Factorizations for Parallel Implementation

摘要

Two radix-R regular interconnection pattern families of factorizations for both theFFT. and the IFFT -also known as parallel or Pease factorizations- are reformulated and pre-sented. Number R is any power of 2 and N, the size of the transform, any power of R. The firstradix-2 parallel FFT algorithm -one of the two known radix-2 topologies- was proposed byPease. Other authors extended the Pease parallel algorithm to different radix and other particu-lar solutions were also reported. The presented families of factorizations for both the 141-T andthe IFFT are derived from the well-known Cooley-Tukey factorizations, first, for the radix-2case, and then, for the general radix-R case. Here we present the complete set of parallel algo-rithms, that is, algorithms with equal interconnection pattern stage-to-stage topology. In thispaper the parallel factorizations are derived by using a unified notation based on the use of theKronecker product and the even-odd permutation matrix to form the rest of permutation matri-ces. The radix-R generalization is done in a very simple way. It is shown that, both FFT andIFFT share interconnection pattern solutions. This view tries to contribute to the knowledge offast parallel algorithms for the case of FFT and IFFT but it can be easily applied to other dis-crete transforms.