Enhancing testability of VLSI arrays for fast Fourier transform

Fast-Fourier-transform (FFT) algorithms are used in various digital signal processing application, such as linear filtering, correlation analysis and spectrum analysis. With the advent of very large-scale-integration (VLSI) technology, a large collection of processing elements can be gathered to achieve high-speed computation economically. However, owing to the low pin-count/ component-count ratio, the controllability and observability of such circuits decrease significantly. As a result, testing of such highly complex and dense circuits becomes very difficult and expensive. M-testability conditions for butterfly-connected and shuffle-connected FFT arrays are proposed. Based on them, a novel design-for-testability approach is presented and applied to the module-level systolic FFT arrays. The M-testability conditions guarantee 100% single-module-fault testability with a minimum number of test patterns.