High-Performance Scalable Base-4 Fast Fourier Transform Mapping

摘要

This paper describes a novel, scalable, parallel Fast Fourier Transform (FFT) architecture mapping that supports transform lengths that are not powers of two or four, that provides low latency as well as high throughput, that can do both 1-D and 2-D Discreet Fourier Transforms (DFTs), that is ideally suited to today's complex FPGA architectures, that possesses all the regularity and design simplicity of systolic arrays, and that is naturally suited to a parameterized HDL form. Its algorithmic underpinnings are based on an observation that with suitable permutations, the DFT coefficient matrix can be partitioned into regular blocks of smaller 'base-4' matrices (equivalent to a decimation in time and frequency). From this new base-4 matrix DFT description the authors have derived a new latency and throughput optimal base- 4 FFT architecture. It combines the performance of traditional radix-4 'pipelined FFTs' with the design and implementation simplicity of systolic arrays, and yet is versatile. Twenty-six briefing charts summarize the presentation.