Abstract
We consider fault-tolerant design techniques for butterfly networks which implement the fast Fourier transform algorithm. We developed fault tolerant FFT processors based on the novel fault tolerant linear cellular array multiplier. The fault tolerance of the multiplier is achieved by using the three modular redundancy (TMR) technique and a novel partitioning method. Reliabilities are analyzed. We show that the method can provide a highly reliable FFT butterfly network, which can tolerate multiple faulty cells (as many as 1/3 of the cells). Our approach can be applied to general digital signal processing applications using multipliers as the basic computation elements.