Flexible, runtime-efficient vector-radix algorithms for multidimensional fast Fourier transform

Ferdinand Klaus; Ute Blewonska; Bernhard O. Bundschuh

doi:10.1117/12.193943

9 November 1994 Flexible, runtime-efficient vector-radix algorithms for multidimensional fast Fourier transform

Ferdinand Klaus, Ute Blewonska, Bernhard O. Bundschuh

Proceedings Volume 2247, Sensors and Control for Automation; (1994) https://doi.org/10.1117/12.193943
Event: Optics for Productivity in Manufacturing, 1994, Frankfurt, Germany

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.

Citation Download Citation

Ferdinand Klaus, Ute Blewonska, and Bernhard O. Bundschuh "Flexible, runtime-efficient vector-radix algorithms for multidimensional fast Fourier transform", Proc. SPIE 2247, Sensors and Control for Automation, (9 November 1994); https://doi.org/10.1117/12.193943

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
11 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Fourier transforms

Sensors

Algorithm development

Digital signal processing

Computer programming

Image processing

Computing systems

Show All Keywords

Keywords/Phrases

Search In:

Publication Years