A novel algorithm for computing the 2D split-vector-radix FFT

Abstract

This paper presents a novel two-dimensional split-vector-radix fast-Fourier-transform (2D svr-FFT) algorithm. The modularizing feature of the 2D svr-FFT structure enables us to explore its characteristics by identifying the local structural property. Each local module is designated as a DFT (non-DFT) block if its output corresponds to DFT (non-DFT) values. The block attribute (DFT or non-DFT) directs the algorithm to construct the local module. We will show that the distribution of DFT blocks can be illustrated by the Sierpinski triangle-a class of fractals generated by IFS (iterated function system). The finding of the Sierpinski-triangle structural property enables us to actually implement the 2D svr-FFT algorithm. To the best of our knowledge, the 2D svr-FFT has never been realized in software. The computational efficiency of the proposed algorithm is considerably improved in comparison with that provided by Matlab. (C) 2003 Elsevier B.V. All rights reserved.