The structure of vector radix multidimensional fast Fourier transforms
HR Wu, FJ Paoloni · 1st IASTED International Symposium on Signal Processing and its Applications · 1987
The Discrete Fourier Transform (DFT) is of fundamental importance for digital signal processing in the frequency domain. Many efficient algorithms exist to implement the transform (Cooley and Tukey, 1965, Brigham, 1974, Burrus and Parks, 1985, Duhamel, 1986), each exploiting some properties of the DFT. Two dimensional (2D) DFT's are used in 2D signal processing such as image processing, implementation of FIR filters and 2D spectral analysis, etc, (Dudgeon and Mersereau, 1984). There are at least two approaches to performing 2D DFT's. One is the row-column method that sequentially applies one dimensional FFT's to the rows and columns of the data matrix. The other is the vector radix (VR) FFT method (Rivard, 1977 and Harris, et.al., 1977) that applies a two dimensional process to the data. Although less well known, the latter is more efficient in terms of the number of multiplications and additions than its ID counterpart.