Title :
A new parallel algorithm for the multidimensional Fourier transform processing
Author :
Shamash, M. ; Gertner, I.
Author_Institution :
Dept. of Electr. Eng., Technion Israel Inst. of Technol., Haifa, Israel
Abstract :
Tools are presented for the extension of the Cooley-Tukey (1965) and Pease (1968) fast Fourier transform algorithms to arbitrary dimensions in a compact Kroenecker product formulation. Several variations of the vector radix algorithm (VRA) are presented using this formulation, and an algorithm suitable for spatial concurrency is derived. The tools presented are the multidimensional stride and partitioning permutations together with the multidimensional lower-ordered transforms. The concepts of partitioning permutation and multidimensional perfect shuffle permutations are studied. The first enables one to apply a divide-and-conquer strategy used in Cooley-Tukey algorithms to multidimensions and the second defines algorithm data flow in a lattice
Keywords :
fast Fourier transforms; multiprocessor interconnection networks; parallel algorithms; signal processing; Cooley-Tukey algorithms; Kroenecker product formulation; divide-and-conquer strategy; fast Fourier transform algorithms; multidimensional Fourier transform processing; multidimensional lower-ordered transforms; multidimensional perfect shuffle permutations; parallel algorithm; partitioning permutation; signal processing; vector radix algorithm; Concurrent computing; Data flow computing; Fast Fourier transforms; Fourier transforms; Frequency; Lattices; Multidimensional systems; Parallel algorithms; Parallel processing; Partitioning algorithms; Polynomials; Sorting;
Conference_Titel :
Acoustics, Speech, and Signal Processing, 1990. ICASSP-90., 1990 International Conference on
Conference_Location :
Albuquerque, NM
DOI :
10.1109/ICASSP.1990.115906
