Share Email Print

Proceedings Paper

Flexible, runtime-efficient vector-radix algorithms for multidimensional fast Fourier transform
Author(s): Ferdinand Klaus; Ute Blewonska; Bernhard O. Bundschuh
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

Dynamic development in digital signal processing is inseparably bound to the disclosure of the fast Fourier transform (FFT). Implications from the application of these efficient algorithms for calculating the discrete (inverse) Fourier transform are significant in many ways. Applicability of FFT algorithms ranges far into almost every aspect of physics and performs a central role in analysis, design and implementation of DSP algorithms and digital systems. Consumed computer time almost ceases to be a problem when using FFT compared with straightforward discrete Fourier transform (DFT). The cutdown on consumed computer time by usage of FFT algorithms even holds greater promise for multidimensional applications with in general more complex tasks and heavier data loads to cope with. Without multidimensional FFT algorithms for high speed convolution or spectral analysis the successes for example in SAR, tomography, data compression or picture processing could not have been achieved. Since the introduction of the Cooley-Tukey-algorithm in 1965 methods to calculate the two- or N dimensional Fourier transform of a set of data are based essentially on the separability of the 2D FFT. With a 1D FFT algorithm the data set is `combed' row- and columnwise to form the 2D transform of the calculated 1D transforms. After some basics and recalling some different conventional approaches to 1D and 2D Fourier transform the paper concentrates on Vector-Radix-algorithms which decimate and transform a 2D data set simultaneous for both index directions and therefore seem suitable for parallelization. Vector-Radix-approaches are derived for general radices and for the 2D case also for nonquadratic data sets.

Paper Details

Date Published: 9 November 1994
PDF: 11 pages
Proc. SPIE 2247, Sensors and Control for Automation, (9 November 1994); doi: 10.1117/12.193943
Show Author Affiliations
Ferdinand Klaus, Univ. Siegen (Germany)
Ute Blewonska, Univ. Siegen (Germany)
Bernhard O. Bundschuh, Univ. Siegen (Germany)

Published in SPIE Proceedings Vol. 2247:
Sensors and Control for Automation
Markus Becker; R. W. Daniel; Otmar Loffeld, Editor(s)

© SPIE. Terms of Use
Back to Top