Fast Fourier Transform Algorithm For Two-Dimensional Array Of Processors

K.Wojtek Przytula; J.Greg Nash; Siegfried Hansen

doi:10.1117/12.942032

21 January 1988 Fast Fourier Transform Algorithm For Two-Dimensional Array Of Processors

K.Wojtek Przytula, J.Greg Nash, Siegfried Hansen

Proceedings Volume 0826, Advanced Algorithms and Architectures for Signal Processing II; (1988) https://doi.org/10.1117/12.942032
Event: 31st Annual Technical Symposium on Optical and Optoelectronic Applied Sciences and Engineering, 1987, San Diego, CA, United States

Abstract

The paper discusses mapping of a Fast Fourier Transform (FFT), Haar Transform and Hadamard Transform algorithms onto a small, two-dimensional, mesh-connected array of processors. The FFT algorithm is an in-place, decimation in frequency, Cooley-Tuckey algorithm in radix 2 and radix 4 versions applied to multidimensional, complex inputs. The data flow of the algorithms has been implemented on the array using an efficient, regular data transfer pattern, uniform for all the algorithms. The inputs and constants used in the algorithms are prestored in the local memories of the processors. The mapping makes it possible to reduce significantly the number of memory locations needed for the constants. A partitioning scheme has been developed for the algorithms which allows us to execute them with inputs of arbitrary size on a small processor array. Also an algorithm has been proposed for the processor array, which efficiently unscrambles the bit reversed output of the FFT algorithm. The processors of the array have East, West, North, South interconnections with their nearest neighbors. The local memory of the processors is small, on the order of hundreds of locations. The processors are controlled in Single Instruction Multiple Data Stream (SIMD) mode and can be selectively disabled using simple masks, consisting of combinations of rows or columns.

Citation Download Citation

K.Wojtek Przytula, J.Greg Nash, and Siegfried Hansen "Fast Fourier Transform Algorithm For Two-Dimensional Array Of Processors", Proc. SPIE 0826, Advanced Algorithms and Architectures for Signal Processing II, (21 January 1988); https://doi.org/10.1117/12.942032

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