Control Circuitry for High Speed VLSI (Very Large Scale Integration) Winograd Fourier Transform Processors

摘要

The calculation of the Discrete Fourier Transform has long been a significant bottleneck in many Digital Signal Processing applications. With the arrival of Very Large Scale Integration and new DFT algorithms, system architectures that significantly reduce the DFT bottleneck are possible. This thesis addresses the design, simulation, implementation, and testing of the control circuitry for a high speed, VLSI Winograd Fourier Transform (WFT) processor. Three WFT processors are combined into a pipelined architecture that is capable of computing a 4080-point DFT on complex input data approximately every 120 microseconds when operating with 70 MHz clock signals. The chip control architecture features a special Programmable Logic Array (PLA) to control the on-chip arithmetic circuitry, and a dense, 54K ROM to generate data addresses for the external RAM. The PLA controller was fabricated in 3 micron CMOS and functioned properly for clock rates of over 60 MHz. The address generator ROM was designed and submitted for fabrication in 3 micron CMOS, and SPICE simulations predict an access time of 60 nanoseconds. Software that automatically generates a ROM layout description from a data file was developed to ensure the correctness of the final design. The transistor minimization procedure is based on a graph partitioning heuristic, and the drain removal procedure is based on an algorithm that near-optimally solves the Traveling Salesman Problem.