Memory-Based Self-Ordering FFT for Efficient I/O Scheduling
Abstract
A complex-valued self-ordering radix-2 memory-based Fast Fourier Transform (FFT) architecture suitable for low end Field Programmable Gate Arrays (FPGA) is presented. Employing a self-ordering algorithm within the data flow, both input and output data are kept in normal sequential order, not in digit-reversed-order. This way, with an appropriate scheduling, last stage of the FFT and I/O operations are performed in parallel with no wait states. Self-ordering FFT algorithms are generally designed for software implementations. We designed and implemented one on FPGA (hardware), showing that considerable number of clock cycle savings can be obtained compared to unordered FFT counterparts. The approach is implemented on various FPGAs. The results are compared with similar radix-2 architectures in terms of required clock cycles and resource usage, confirming the advantage of the approach.
Keywords
FFT, DFT, memory-based FFT, self-ordering, FPGA, radix-2
Ethical Statement
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
References
- [1] Chang YN, Parhi KK. An efficient pipelined FFT architecture, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 2003; 50-6: 322–325.
- [2] Chu E, George A. FFT algorithms and their adaptation to parallel processing, Linear Algebra and its Applications 1998; 284-1-3: 95–124.
- [3] Garrido M. A survey on pipelined FFT hardware architectures, Journal of Signal Processing Systems 2021; https://doi.org/10.1007/s11265-021-01655-1.
- [4] Garrido M, Grajal J, Sanchez MA. Gustafsson O, Pipelined radix-2k feedforward FFT architectures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 2013; 21: 23–32.
- [5] Garrido M, Moller K, Kumm M. World’s fastest FFT architectures: Breaking the barrier of 100 GS/s, IEEE Transactions on Circuits and Systems I: Regular Papers 2019; 66-4: 1507–1516.
- [6] Garrido M, Sanchez MA, Lopez-Vallejo ML, Grajal J. A 4096-point radix-4 memory-based FFT using DSP slices, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 2016; 25: 375–379.
- [7] Huang SJ, Chen SG. A high-throughput radix-16 FFT processor with parallel and normal input/output ordering for IEEE 802.15.3C Systems, IEEE Transactions on Circuits and Systems I: Regular Papers 2012; 59-8: 1752–1765.
- [8] Jo BG, Sunwoo MH. New continuous-flow mixed-radix (CFMR) FFT processor using novel in-place strategy, IEEE Transactions on Circuits and Systems I: Regular Papers 2005; 52-5: 911–919.
- [9] Johnson H, Burrus C. An in-order, in-place radix-2 FFT, ICASSP '84. IEEE International Conference on Acoustics, Speech, and Signal Processing 1984.
- [10] Kaya Z, Seke E, A novel addressing algorithm of radix-2 FFT using single-bank dual-port memory, Circuit World 2020; 48: 64–70.