Fast Fourier transforms with factored residue look-up tables

The implementation of fast Fourier transforms (FFTs) via the use of residue factored look-up tables (FLUTs) is investigated. The principles of FLUTs are reviewed, and a gate-level pipelined adder architecture is presented. The basics of the quadratic residue system (QRNS) are then discussed, and FLUT-based gatelevel pipelined architectures are presented for binary-to-QRNS and QRNS-to-binary converters as well as for FFT butterflies. The Despain small integer approximations are used to represent the FFT complex rotations, each of which is expressed via a linear combination of common angles. The QRNS FLUT FFT performance is measured via a normalized mean square error (MSE) figure, which is estimated via computer simulations performed for 16- and 32-point QRNS FFTs in conjunction with various input signals and different approximation accuracy. Based on these results the largest FLUT FFT order, for which an MSE of <10(-8) can be supported, is estimated. The overall system gate complexity is then calculated and compared with that required by the equivalent conventional digital implementation.