Fault-Tolerant FFT Networks

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.