Title :
The new algorithms for 2-dimensional FFT with prime size
Author :
Liu, Hongyi ; Tolimieri, Richard ; An, Myoung
Author_Institution :
Center for Large Scale Comput., City Univ. of New York, NY, USA
Abstract :
Two algorithms for the 2D fast Fourier transform (FFT) are developed, where the prime size p≡3 mod 4 and p≡2 mod 3. The indexing set in each case forms a field, and the computation of the 2D FFT can be completely transferred into one dimension which is identical to the computational structure of the 1D FFT with prime size. Instead of the row-column algorithm which was designed based on the 1D FFT, an algorithm based on 1D cyclic convolution is designed. It is shown that this algorithm is efficient for some sample points and flexible for parallel or vector processing
Keywords :
fast Fourier transforms; signal processing; 1D FFT; 1D cyclic convolution; 2D fast Fourier transform; computational structure; indexing set; parallel processing; prime size; sample points; signal processing; vector processing; Algorithm design and analysis; Arithmetic; Convolution; Fourier transforms; Indexing; Large-scale systems; Monitoring; Polynomials; Tensile stress;
Conference_Titel :
Acoustics, Speech, and Signal Processing, 1991. ICASSP-91., 1991 International Conference on
Conference_Location :
Toronto, Ont.
Print_ISBN :
0-7803-0003-3
DOI :
10.1109/ICASSP.1991.151080
