FAST FAULT-TOLERANT DIGITAL CONVOLUTION USING A POLYNOMIAL RESIDUE NUMBER SYSTEM

We describe a fault-tolerant convolution algorithm which is an extension of residue number system fault-tolerance schemes applied to polynomial rings. The algorithm is suitable for implementation on multiprocessor systems and is able to concurrently mask processor failures. We develop a fast algorithm based on long division for detecting and correcting multiple processor failures. We then select moduli polynomials that yield an efficient and robust FFT-based algorithm. For this implementation, we study single fault detection and correction, and apply a generalized likelihood ratio test to optimally detect system failures in the presence of computational noise. The coding scheme which is presented is capable of protecting over 90% of the computation involved in convolution. Parts not covered by our scheme are assumed to be protected via triple modular redundancy. This hybrid approach is able to detect and correct any single system failure with as little as 70% overhead, compared with 200% needed for a system fully protected via modular redundancy.