Easily testable and fault-tolerant FFT butterfly networks

Jin Fu Li, Shyue Kung Lu, Shih Arn Hwang, Cheng Wen Wu

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


With the advent of deep submicron very large scale integration technology, the integration of a large fast-Fourier-transform (FFT) network into a single chip is becoming possible. However, a practical FFT chip is normally very big, so effective testing and fault-tolerance techniques usually are required. In this paper, we first propose a C-testable FFT network design. Only 20 test patterns are required to cover all combinational single-cell faults and interconnect stuck-at and break faults for the FFT network, regardless of its size. A spare-row based fault-tolerant FFT network design is subsequently proposed. Compared with previous works, our approach shows higher reliability 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.

Original languageEnglish
Pages (from-to)919-929
Number of pages11
JournalIEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing
Issue number9
StatePublished - Sep 2000


Dive into the research topics of 'Easily testable and fault-tolerant FFT butterfly networks'. Together they form a unique fingerprint.

Cite this