Fast Fourier Transforms With Factored Residue Look-Up Tables

A. P. Goutzoulis

doi:10.1117/12.962202

5 February 1990 Fast Fourier Transforms With Factored Residue Look-Up Tables

A. P. Goutzoulis

Proceedings Volume 1151, Optical Information Processing Systems and Architectures; (1990) https://doi.org/10.1117/12.962202
Event: 33rd Annual Technical Symposium, 1989, San Diego, United States

Abstract

The implementation of fast Fourier transforms (FFT) via the use of residue factored look-up tables (FLUT) 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 gate-level 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.

Citation Download Citation

A. P. Goutzoulis "Fast Fourier Transforms With Factored Residue Look-Up Tables", Proc. SPIE 1151, Optical Information Processing Systems and Architectures, (5 February 1990); https://doi.org/10.1117/12.962202

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available