Fast Fourier transforms with factored residue look-up tables

Area of Science:

• Digital Signal Processing
• Computer Engineering
• Number Theory

Background:

• Fast Fourier Transforms (FFTs) are crucial in digital signal processing.
• Look-up tables (LUTs) can accelerate computations, but traditional LUTs face memory limitations.
• The Quadratic Residue Number System (QRNS) offers potential for efficient arithmetic operations.

Purpose of the Study:

• To investigate the implementation of FFTs using residue factored look-up tables (FLUTs) within the QRNS framework.
• To develop and evaluate gate-level pipelined architectures for QRNS-based FFT components.
• To assess the performance and complexity of FLUT-based QRNS FFTs compared to conventional methods.

Main Methods:

• Review of FLUT principles and QRNS basics.
• Design of gate-level pipelined architectures for binary-to-QRNS and QRNS-to-binary conversion.
• Implementation of FLUT-based FFT butterfly architectures using Despain approximations for complex rotations.
• Performance evaluation using normalized mean square error (MSE) via computer simulations for 16- and 32-point FFTs.
• Calculation and comparison of overall system gate complexity.

Main Results:

• FLUT-based gate-level pipelined architectures were successfully designed for QRNS FFT components.
• Computer simulations estimated the performance of 16- and 32-point QRNS FFTs using normalized MSE.
• The largest FLUT FFT order supporting an MSE below 10^-8 was estimated.
• Gate complexity of the FLUT QRNS FFT system was calculated and compared to conventional digital implementations.

Conclusions:

• FLUTs combined with QRNS provide a viable approach for implementing FFTs.
• The proposed architectures offer a potential trade-off between accuracy and hardware complexity.
• The study provides valuable data for optimizing digital implementations of FFTs in specific applications.