ISSN:
1573-0824
Keywords:
multidimensional FFT
;
decimation-in-time algorithm
;
indexing process
;
new approach
;
radix
;
computational complexity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Electrical Engineering, Measurement and Control Technology
Notes:
Abstract In this paper, we propose a new approach for computing multidimensional Cooley-Tukey FFT's that is suitable for implementation on a variety of multiprocessor architectures. Our algorithm is derived in this paper from a Cooley decimation-in-time algorithm by using an appropriate indexing process and the tensor product properties. It is proved that the number of multiplications necessary to compute our proposed algorithm is significantly reduced while the number of additions remains almost identical to that of conventional Multidimensional FFT's (MFFT). Comparison results show the powerful performance of the proposed MFFT algorithm against the row-column FFT transform when data dimension M is large. Furthermore, this algorithm, presented in a simple matrix form, will be much easier to implement in practice. Connections of the proposed approach with well-known DFT algorithms are included in this paper and many variations of the proposed algorithm are also pointed out.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1008469008412
Permalink