Design of Fault Tolerant Prime Factor Algorithm Array Elements

摘要

The calculation of the discrete Fourier transform (DFT) has long been a significant bottleneck in many Digital Signal Processing applications. This thesis contributes to the goal of implementing a very large-scale integrated (VLSI) circuit which uses the Winograd and Good-Thomas algorithms for computing DFTs with composite blocklengths. 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 a controller. The pipeline used the Good-Thomas Prime Factor Algorithm. Fault tolerance was enhanced by the use of watchdog processors to provide concurrent fault detection and error control coding to provide fault masking. A pipeline controller was designed as a Reduced Instruction Set Computer to control the pipeline and regulated the flow of data. Also, a dual ported, double buffered RAM memory was designed to provide intra-pipeline data storage.