Architecture and Numerical Accuracy of High-Speed DFT (Discrete Fourier Transform) Processing Systems.

Abstract : This thesis examines a very large-scale integrated (VLSI) circuit implementation of the Winograd and Good-Thomas Algorithms for computing discrete Fourier transforms (DFTs) with composite blocklengths after developing the theoretical background for calculating DFTs, the algorithms of interest are presented. A VLSI architecture, which exploits the parallelism and pipelining inherent in the algorithms, is then discussed. Winograd processors use both the small and large Winograd algorithms to compute DFTs with blocklengths of 15, 16, and 17. Longer blocklength DFTs (240, 255, 272, and 4080) are computed using a pipeline of Winograd processors, dual-port memories, and an interface processor; the pipeline uses the Good-Thomas prime factor algorithm. Fault tolerant computing in the initial design of the VLSI architecture. Watchdog processors check both data and addresses of active Winograd processors, while parity checking circuits incorporated in the Winograd processors augment memory error-correction coding. A software simulation determined the numerical accuracy of the VLSI circuit. The signal-to-noise ratio was used as the accuracy metric. The signal was the output of a standard module, which used double-precision arithmetic, while the noise was the difference between the standard and the simulation module. The simulation module used integer arithmetic to exactly mimic operation of the VLSI circuit. Outputs of the standard module were compared with a direct evaluation of the DFT to verify the standard module did compute a DFT.