Fast Fourier transforms with factored residue look-up tables

Akis P. Goutzoulis

doi:10.1364/AO.28.004167

Applied Optics
Vol. 28,
Issue 19,
pp. 4167-4175
(1989)
•https://doi.org/10.1364/AO.28.004167

Fast Fourier transforms with factored residue look-up tables

Akis P. Goutzoulis

Not Accessible

Your library or personal account may give you access

Get PDF
Email
Share
Get Citation
Copy Citation Text
Akis P. Goutzoulis, "Fast Fourier transforms with factored residue look-up tables," Appl. Opt. 28, 4167-4175 (1989)

Export Citation
- BibTex
- Endnote (RIS)
- HTML
- Plain Text
Citation alert
Save article

Abstract

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 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⁻⁸ can be supported, is estimated. The overall system gate complexity is then calculated and compared with that required by the equivalent conventional digital implementation.

Full Article | PDF Article

More Like This

Complexity of residue position-coded lookup table array processors

Anastasios P. Goutzoulis
Appl. Opt. 26(22) 4823-4831 (1987)

Implementation of a fast digital optical matrix–vector multiplier using a holographic look-up table and residue arithmetic

Sarry F. Habiby and Stuart A. Collins
Appl. Opt. 26(21) 4639-4652 (1987)

Optical processing with residue LED/LD lookup tables

A. P. Goutzoulis, E. C. Malarkey, D. K. Davies, J. C. Bradley, and P. R. Beaudet
Appl. Opt. 27(9) 1674-1681 (1988)

Previous Article Next Article

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Figures (6)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Tables (3)

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Equations (19)

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

MODULO m_i	GATE COMP. +−FLUT	GATE COMP. B/R	GATE COMP. B/QR	COST +−FLUT	COST B/QR
5	205	387	979	88	422
13	269	593	1455	73	393
29	517	967	2451	106	505
37	677	1141	2959	130	568
41	661	1225	3111	123	581
53	1069	1477	4023	187	702
61	560	1645	3850	94	649
73	989	1879	4747	160	767
89	1189	2183	5555	1848	858
157	1376	3417	8210	189	1126

D_I	A	DELTA	sq. pulse	SINEWAVE	WHITE N.	SINE+NOISE
12	12	9.9×10⁻⁶	8.8×10⁻⁶	9.8×10⁻⁶	6.8×10⁻⁶	9.8×10⁻⁶
14	12	9.9×10⁻⁶	8.8×10⁻⁶	9.8×10⁻⁶	5.6×10⁻⁶	9.8×10⁻⁶
16	12	9.9×10⁻⁶	8.8×10⁻⁶	9.8×10⁻⁶	6.6×10⁻⁶	9.8×10⁻⁶
12	16	2.9×10⁻¹⁰	2.7×10⁻¹⁰	2.9×10⁻¹⁰	6.9×10⁻⁹	3.5×10⁻¹⁰
14	16	2.9×10⁻¹⁰	2.7×10⁻¹⁰	2.9×10⁻¹⁰	9.7×10⁻⁹	3.7×10⁻¹⁰
16	16	2.9×10⁻¹⁰	2.7×10⁻¹⁰	2.9×10⁻¹⁰	7.5×10⁻⁹	3.5×10⁻¹⁰
12	19	1.8×10⁻¹²	6.5×10⁻¹¹	1.8×10⁻¹²	1.8×10⁻¹⁰	3.1×10⁻¹²
14	19	1.8×10⁻¹²	6.5×10⁻¹¹	1.8×10⁻¹²	2.5×10⁻¹⁰	3.6×10⁻¹²
16	19	1.8×10⁻¹²	6.5×10⁻¹¹	1.8×10⁻¹²	1.9×10⁻¹⁰	2.7×10⁻¹²

D_I	A	DELTA	SQ. PULSE	SINEWAVE	WHITE N.	SINE+NOISE
12	12	2.2×10⁻⁵	2.0×10⁻⁵	2.2×10⁻⁵	7.0×10⁻⁶	2.1×10⁻⁵
14	12	2.2×10⁻⁵	2.0×10⁻⁵	2.2×10⁻⁵	1.0×10⁻⁵	2.1×10⁻⁵
16	12	2.2×10⁻⁵	2.0×10⁻⁵	2.2×10⁻⁵	1.0×10⁻⁵	2.1×10⁻⁵
12	16	6.7×10⁻⁹	8.4×10⁻⁹	6.7×10⁻⁹	2.0×10⁻⁸	6.8×10⁻⁸
14	16	6.7×10⁻⁹	8.4×10⁻⁹	6.7×10⁻⁹	1.8×10⁻⁸	6.8×10⁻⁸
16	16	6.7×10⁻⁹	9.4×10⁻¹	9.3×10⁻¹	1.1×10⁻⁸	1.0
12	19	2.7×10⁻¹¹	6.0×10⁻¹¹	2.7×10⁻¹¹	2.9×10⁻¹⁰	2.8×10⁻¹¹
14	19	2.7×10⁻¹¹	6.2×10⁻¹	6.3×10⁻¹	2.3×10⁻¹⁰	7.8×10⁻¹
16	19	2.7×10⁻¹¹	1.0	1.0	1.0	1.0

MODULO m_i	GATE COMP. +−FLUT	GATE COMP. B/R	GATE COMP. B/QR	COST +−FLUT	COST B/QR
5	205	387	979	88	422
13	269	593	1455	73	393
29	517	967	2451	106	505
37	677	1141	2959	130	568
41	661	1225	3111	123	581
53	1069	1477	4023	187	702
61	560	1645	3850	94	649
73	989	1879	4747	160	767
89	1189	2183	5555	1848	858
157	1376	3417	8210	189	1126

D_I	A	DELTA	sq. pulse	SINEWAVE	WHITE N.	SINE+NOISE
12	12	9.9×10⁻⁶	8.8×10⁻⁶	9.8×10⁻⁶	6.8×10⁻⁶	9.8×10⁻⁶
14	12	9.9×10⁻⁶	8.8×10⁻⁶	9.8×10⁻⁶	5.6×10⁻⁶	9.8×10⁻⁶
16	12	9.9×10⁻⁶	8.8×10⁻⁶	9.8×10⁻⁶	6.6×10⁻⁶	9.8×10⁻⁶
12	16	2.9×10⁻¹⁰	2.7×10⁻¹⁰	2.9×10⁻¹⁰	6.9×10⁻⁹	3.5×10⁻¹⁰
14	16	2.9×10⁻¹⁰	2.7×10⁻¹⁰	2.9×10⁻¹⁰	9.7×10⁻⁹	3.7×10⁻¹⁰
16	16	2.9×10⁻¹⁰	2.7×10⁻¹⁰	2.9×10⁻¹⁰	7.5×10⁻⁹	3.5×10⁻¹⁰
12	19	1.8×10⁻¹²	6.5×10⁻¹¹	1.8×10⁻¹²	1.8×10⁻¹⁰	3.1×10⁻¹²
14	19	1.8×10⁻¹²	6.5×10⁻¹¹	1.8×10⁻¹²	2.5×10⁻¹⁰	3.6×10⁻¹²
16	19	1.8×10⁻¹²	6.5×10⁻¹¹	1.8×10⁻¹²	1.9×10⁻¹⁰	2.7×10⁻¹²

Abstract

Cited By

Figures (6)

Tables (3)

Equations (19)

Applied Optics