Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Efficient 2D FFT implementation on mediaprocessors
Mermer C., Kim D., Kim Y. Parallel Computing29 (6):691-709,2003.Type:Article
Date Reviewed: Nov 18 2003

Mermer, Kim, and Kim address the problems of computation and data flow in the mapping of the 2D fast Fourier transform (FFT) onto a single programmable mediaprocessor. The MAP, which is a recently introduced commercial mediaprocessor, is a single-chip very long instruction word (VLIW) processor targeted mainly at computationally demanding multimedia applications. The implementation is based on the decomposition of the 2D FFT into a series of 1D FFTs via row-column decomposition. The authors develop a two-pass data flow method for performing the column-wise 1D FFTs by transferring and processing multiple image columns at a time.

The authors adopt the Cooley-Tukey FFT algorithm for implementing the 1D FFT. The radix-2 butterfly computation is the basic computational element of the FFT algorithm with one complex addition, one complex subtraction, and one complex multiplication. To balance the load on both types of functional units, the authors adopt a radix-4 butterfly as the basic computational element of the FFT algorithm, and implement two successive stages of radix-2 butterflies. In addition, the authors use MAP’s direct memory access (DMA) engine to perform the data transfer between the on-chip data cache and the external memory. Double buffering is employed within the data cache to allow concurrent handling of the data input/output (I/O) and the computation.

A significant reduction in discrete Fourier transform (DFT) computation time for large values of N is achieved. That is, the number of complex multiplications required by the N-point radix-2 FFT is (N/2)log N, and the number of complex additions is Nlog N, as opposed to N*N complex multiplications and N(N-1) complex additions with direct implementation of 1D FFT.

Reviewer:  Dr. Seyed Roosta Review #: CR128588 (0403-0313)
Bookmark and Share
 
Fast Fourier Transforms (FFT) (G.1.2 ... )
 
 
Computation Of Transforms (F.2.1 ... )
 
 
Multiprocessing/ Multiprogramming/ Multitasking (D.4.1 ... )
 
 
Process Management (D.4.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Fast Fourier Transforms (FFT)": Date
Fast computation of RBF coefficients using FFT
Abe Y., Iiguni Y. Signal Processing 86(11): 3264-3274, 2006. Type: Article
May 22 2007
 Digital Fourier analysis: advanced techniques
Kido K., Springer International Publishing, New York, NY, 2014.  178, Type: Book (978-1-493911-26-4)
Dec 8 2015
Parameter selection and numerical approximation properties of Fourier extensions from fixed data
Adcock B., Ruan J. Journal of Computational Physics 273453-471, 2014. Type: Article
Jan 13 2015
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy