×

A new proposed algorithm of arbitrary radix for the computation of the 2D DFT. (English) Zbl 0943.65161

Let \(N= B^r\) with an integer \(B\geq 2\). The authors present a two-dimensional fast Fourier transform (FFT) of size \(N\times N\). This algorithm is based on the decimation-in-time algorithm and an appropriate index mapping. A comparison to the row-column method shows that the proposed FFT requires a lower number of multiplications, but the same number of additions.
Reviewer: M.Tasche (Rostock)

MSC:

65T50 Numerical methods for discrete and fast Fourier transforms
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cooley, Mathematics of Computation 19 pp 297– (1965)
[2] Sorensen, IEEE Transactions on Signal Processing 41 pp 1184– (1993)
[3] Hinshaw, Proceedings of the IEEE 71 pp 1– (1983)
[4] Gertner, IEEE Transactions on Computers C-36 pp 1265– (1987)
[5] Two-dimensional FFT algorithms on hypercube machines. Proceedings of Transputer Applications 91, Glasgow, 1991.
[6] Granata, IEEE SP Magazine pp 40– (1992)
[7] Zapata, IEEE Procceedings E-137 pp 257– (1990)
[8] Niemel, European Transactions on Telecommunication and Related Technology 5 pp 377– (1994)
[9] Falkawski, IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing 41 pp 380– (1994)
[10] Rius, IEEE Transactions on Signal Processing ISS 4 pp 991– (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.