Fault-Tolerant FFT Networks

Jing Yang Jou, Jacob A. Abraham

研究成果: 雜誌貢獻期刊論文同行評審

159 引文 斯高帕斯(Scopus)


The fast Fourier transform (FFT) has long been a major analytical tool in such diverse fields as system analysis, digital filtering, power spectrum analysis, and communication theory. With the advent of VLSI technology, large collections of processing elements, which cooperate with each other to achieve high-speed computation, have become economically feasible. Since any functional error in a high-performance system may seriously jeopardize the operation of the system and its data integrity, some level of fault tolerance must be incorporated in order to ensure that the results of long computations are valid. In this paper, two concurrent error detection (CED) schemes are proposed for N-point FFT networks which consists of log2N stages with (N/2) two-point butterfly modules for each stage. The method assumes that failures are confined to a single complex multiplier or adder or one input or output set of lines. Such a fault model covers a broad class of faults. It is shown that only a small overhead ratio—O(2/log2 N) of hardware—is required for the FFT networks to obtain fault-secure results in the first scheme. A new data retry technique is used to locate the faulty modules. Large roundoff errors can also be detected and treated in the same manner as functional errors. However, the data retry technique can also distinguish between the roundoff errors and functional errors which are caused by some physical failures. In the second scheme, a time redundancy method is used to achieve both error detection and location. It is shown that only negligible hardware overhead is required. However, the throughput is reduced to half compared to that of the original system, without both error detection and location due to the nature of time redundancy methods.

頁(從 - 到)548-561
期刊IEEE Transactions on Computers
出版狀態已出版 - 5月 1988


深入研究「Fault-Tolerant FFT Networks」主題。共同形成了獨特的指紋。