On the Design of VLSI Circuits for the Winograd Fourier Transform Algorithm
Abstract
A VLSI architecture for computing the discrete Fourier transform (DFT) using the Winograd Fourier transform algorithm (WFTA) is presented. This architecture is an addressless, routed, bit-serial scheme that directly maps an N-point algorithm onto silicon. The architecture appears to be far less costly than systolic schemes for implementing the WFTA, and faster than current FFT devices for similar transform sizes. The nesting method of Winograd is used for partitioning larger transformations into several circuits. The advantage of this partitioning technique is that it allows using circuits that are all of the same type. However, the number of input/output pins of each circuit is higher than with some other approaches like, for example, the prime factor algorithm. The design of a 20-point DFT circuit with logic diagrams of its major cells is presented. The gate array circuit has been sent for fabrication in a 0.7 micron CMOS technology. five circuits interconnected together will compute 60-point complex transforms at a rate of one transformation every 0.53 micron.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1991
- Accession Number
- ADA246317
Entities
People
- Pierre Lavoie
- Serge Martineau
Organizations
- Defence Research and Development Canada