Design of VLSI Circuits for the Winograd Fourier Transform Algorithm

摘要

A VLSI architecture for computing the discrete Fourier transform (DFT) using theWinograd 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 micrometer CMOS technology. five circuits interconnected together will compute 60-point complex transforms at a rate of one transformation every 0.53 micrometer.