Title :
Partial column FFT pipelines
Author :
Gorman, Steve F. ; Wills, Jeffrey M.
Author_Institution :
Melphar Div., E-Systems, Falls Church, VA, USA
fDate :
6/1/1995 12:00:00 AM
Abstract :
This paper presents the development of two efficient FFT implementation algorithms which allow for more parallelization than the standard pipeline. M=2q radix r parallel computational elements are allocated per column of the FFT flowgraph, and the constant geometry FFT is used for uniform stages. The first method solves the interstage data shuffle problem by decomposing the perfect shuffle matrix into the product of four matrices, with a memory grouping resulting in a reduction of switching from M2 to 2M. The second method decomposes to the perfect shuffle into the product of two matrices, and the memory is partitioned such that multiport elements may be used. All required switching is accomplished via addressing of the multiport elements requiring no external switching elements. Finally implementations are presented which allow for a varied amount of parallization by using uniform modules and merely modifying interconnect wiring
Keywords :
data flow graphs; digital signal processing chips; fast Fourier transforms; hypercube networks; parallel algorithms; parallel architectures; pipeline processing; FFT flowgraph; constant geometry FFT; interconnect wiring; interstage data shuffle problem; memory grouping; multiport elements; parallel computational elements; parallelization; partial column FFT pipelines; perfect shuffle matrix; uniform stages; Application software; Computational geometry; Concurrent computing; Helium; Matrix decomposition; Pipelines; Signal processing algorithms; Standards development; Throughput; Wiring;
Journal_Title :
Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on