Cheng-Wen Wu and Jiann-Yuan Choue
Department of Electrical Engineering
National Tsing Hua University
Hsinchu, Taiwan 30043, R.O.C.
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) techique 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.
Keywords: butterfly network, fast Fourier transform, interconnection network, iterative logic array, fault tolerance, three modular redundancy
Received November 17, 1992; revised February 1, 1993.
Communicated by Shing-Tsaan Huang.
*This work was supported in part by the National Science Council, R.O.C., under Contracts NSC81-0404-E007-596 and NSC82-0404-E007-186.