DocumentCode :
2918398
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
fYear :
1990
fDate :
3-6 Apr 1990
Firstpage :
1993
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Acoustics, Speech, and Signal Processing, 1990. ICASSP-90., 1990 International Conference on
Conference_Location :
Albuquerque, NM
ISSN :
1520-6149
Type :
conf
DOI :
10.1109/ICASSP.1990.115906
Filename :
115906
Link To Document :
بازگشت