On the testability of array structures for FFT computation

This article presents new approaches for testing VLSI array architectures used in the computation of the complexN-point Fast Fourier Transform. Initially, an unrestricted single cell-level fault model is considered. The first proposed approach is based on a process whose complexity is independent (or C- as constant) of the number of cells in the FFT architecture. This is accomplished by showing a topological equivalence between the FFT array and a linear (one-dimensional) array. The process of fault location is also analyzed. The second proposed method is based on a testing process whose complexity is linear with respect to the number of stages (columns) of the FFT array. A component-level fault model is also proposed and analyzed. The implications of this model on the C-testability process are fully described.This research is supported by grants from NSF and NSERC.