FFT architecture for WSI with concurrent error detection and fault location

The paper presents a new approach for concurrent error detection in homogeneous VLSI/WSI architectures for the computation of the complex N-point fast Fourier transform (FFT). The proposed approach is based on the relationship between the computations of cells at a given point distance. This relationship is analysed with respect to functional and physical faults. It is proved that a 100% probability of detection is possible. Overhead issues for hardware and timing are addressed. It is proved that hardware overhead is 50% compared to a fault intolerant complex 2-point implementation. Fault detection can be accommodated online and on a component basis (multiplier or adder/subtractor); full fault location is accomplished by a roving technique, which utilises a reconfiguration approach at no significant time overhead. The proposed technique can be accommodated efficiently in a homogeneous layout for WSI implementation. A two-phase reconfiguration policy for the proposed architecture is presented. It is proved that switching and routing overhead are modest, while achieving a significant reliability improvement over previous approaches.