Easily testable and fault-tolerant FFT butterfly networks

With the advent of deep submicron very large scale integration technology, the integration of a large fast-Fourier-transform (FFT) network into a sing le chip is becoming possible. However, a practical FFT chip is normally ver y big, so effective testing and fault-tolerance techniques usually are requ ired, In this paper, we first propose a C-testable FFT network design. Only 20 test patterns are required to cover all combinational single-cell fault s and interconnect stuck-at and break faults for the FFT network, regardles s of its size. A spare-row based fault-tolerant FFT network design is subse quently proposed. Compared with previous works, our approach shows higher r eliability and lower hardware overhead, and only three bit-level cell types are needed for repairing a faulty row in the multiply-subtract-add module. Also, special cell design is not required to implement the reconfiguration scheme. The hardware overhead for the testable design is low-about 4% for 16-bit numbers, regardless of the FFT network size.