A FAULT-TOLERANT FFT PROCESSOR

A method is proposed for achieving fault tolerance by introducing a redundant stage for a special-purpose fast Fourier transform (FFT) processor. A concurrent error-detection technique, called recomputing by alternate path, is used to detect errors during normal operation. Once an error is detected, a faulty butterfly can be located with log (N plus 5) additional cycles. The method has 100% detection and location capability, regardless of the magnitude of the roundoff errors. A gracefully degraded reconfiguration using a redundant stage is introduced. This technique ensures a high improvement in reliability and availability. Hardware overhead is O(1/log N) with some additional comparators and switches. The method can be applied to other algorithms implementable on the butterfly structure.