Share Email Print

Proceedings Paper

Fast Fourier Transform Algorithm For Two-Dimensional Array Of Processors
Author(s): K.Wojtek Przytula; J.Greg Nash; Siegfried Hansen
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 21 January 1988
PDF: 13 pages
Proc. SPIE 0826, Advanced Algorithms and Architectures for Signal Processing II, (21 January 1988); doi: 10.1117/12.942032
Show Author Affiliations
K.Wojtek Przytula, Hughes Research Laboratories (United States)
J.Greg Nash, Hughes Research Laboratories (United States)
Siegfried Hansen, Hughes Research Laboratories (United States)

Published in SPIE Proceedings Vol. 0826:
Advanced Algorithms and Architectures for Signal Processing II
Franklin T. Luk, Editor(s)

© SPIE. Terms of Use
Back to Top