Fault-tolerance in FFT Arrays: Time Redundancy Approaches

Fault tolerance in VLSI/WSI FFT arrays acquires relevance when defects and run-time faults become significant, due to large dimensions of processors and arrays. Then, both restructuring to overcome end-of-production defects and reconfiguration to overcome run-time faults are required, to achieve the dual purposes of higher yield and higher reliability. Adopting as basic FFT network the two-dimensions array that directly corresponds to the FFT flow graph, the usual structure redundancy techniques tailored for two-dimensions arrays reconfiguration are not well applicable, since the limited locality of this network leads to relevant area increase due to the augmented interconnection structure. In this paper, time redundancy is suggested as a viable alternative for the two-dimensions FFT array; two different solutions are presented, one based on inter-stage reconfiguration, the other one adopting intra-state reconfiguration, both allowing for survival to multiple faults with limited increase of network complexity and very small hard-core sections. As usual in many time redundancy methods, both approaches result in a processing speed equal to half the processing speed granted by an ideal, fault-free device. Reliability and survival ratios to multiple faults are evaluated for the two cases, taking into account also the area increments necessary for fault tolerance. The reliability evaluations allow for a direct comparison of the two solutions.