Abstract
In the field of digital signal processing, the fast Fourier transform (FFT) is a fundamental algorithm, with its processors being implemented using either the pipelined architecture, well-known for high-throughput applications but weak in hardware utilization, or the memory-based architecture, designed for area-constrained scenarios but failing to meet stringent throughput requirements. Therefore, we propose an adaptive hybrid FFT, which leverages the strengths of both pipelined and memory-based architectures. In this paper, we propose an adaptive hybrid FFT processor that combines the advantages of both architectures, and it has the following features. First, a set of radix-$2^k$ multi-path delay commutators (MDC) units are developed to support high-performance large-size processing. Second, a conflict-free memory access scheme is formulated to ensure a continuous data flow without data contention. Third, We demonstrate the existence of a series of bit-dimension permutations for reordering input data, satisfying the generalized constraints of variable-length, high-radix, and any level of parallelism for wide adaptivity. Furthermore, the proposed FFT processor has been implemented on a field-programmable gate array (FPGA). As a result, the proposed work outperforms conventional memory-based FFT processors by requiring fewer computation cycles. It achieves higher hardware utilization than pipelined FFT architectures, making it suitable for highly demanding applications.
Introduction
Hardware designers for digital signal processing (DSP) traditionally face a trade-off between high-throughput pipelined architectures and area-efficient memory-based architectures. Pipelined designs offer speed but suffer from low hardware utilization when processing smaller tasks. Conversely, memory-based designs are compact but slow for large-scale processing. This paper introduces an "Adaptive Hybrid FFT" processor that reconfigures itself to balance these competing requirements, supporting FFT sizes up to 512K points with significantly improved efficiency.
Proposed Architecture
The core innovation lies in a hybrid structure that combines the strengths of both paradigms. The system utilizes a set of radix-$2^k$ multi-path delay commutator (MDC) units and a conflict-free memory access scheme to ensure continuous data flow.
Reconfigurable Radix-$2^5$ MDC
Unlike standard radix-2 units, this design employs a radix-$2^5$ (32-point) structure. It is designed for "backward compatibility," allowing it to bypass specific stages to perform radix-$2^4$, $2^3$, or $2^2$ operations. This flexibility is achieved by classifying twiddle factor rotations and identifying bypassable circuit components.
Adaptive Parallelism and Reordering
To handle varying FFT lengths and parallelism levels, the authors developed a generalized bit-dimension permutation scheme. This mathematical unification allows the hardware to adapt its addressing logic dynamically rather than relying on hard-coded shuffling logic.
Implementation and Results
The design was implemented on a Xilinx Virtex UltraScale+ FPGA using the Chisel hardware construction language. Benchmarking against state-of-the-art architectures revealed several key advantages:
- Throughput: A 70% reduction in execution time compared to traditional memory-based processors.
- Utilization: Average hardware utilization of 75-80%, even for smaller tasks where traditional pipelines drop to 15%.
- Performance: A maximum clock frequency of 196.8 MHz and the ability to handle 512K-point FFTs using 128Mb of UltraRAM.
Conclusion
The proposed adaptive hybrid FFT processor successfully bridges the gap between pipelined and memory-based architectures. By leveraging reconfigurable MDC units and a unified permutation scheme, it provides a scalable solution for high-resolution radar and long-range communications. Future work may involve extending the architecture to even higher radices or integration into automated SoC generation flows.
Reference: Zhao, F., et al. "Adaptive Hybrid FFT: A Novel Pipeline and Memory-Based Architecture for Radix-$2^k$ FFT in Large Size Processing." arXiv:2501.01259v1 [cs.AR].
Summary updated