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.