Concurrent error detection in fast unitary transform algorithms

Discrete fast unitary transform algorithms, of which the fast Fourier transform (FFT) and fast discrete Cosine transform (DCT) are practical examples, are highly susceptible to temporary calculation failures because of their interconnected computational flows. Many error detection techniques for FFT algorithms have been reported, but fault tolerance issues for other important transforms have not been addressed as vigorously. A general design and analysis approach for all fast unitary transforms is presented. It relies on fundamental linear algebra methods coupled with associated dual space representations that are natural descriptions of real parity values. Basic output error patterns from single computational errors are used to define an equal-sized group of dual space basis vectors on which practical parity weighting functions may be evaluated. An iterative design approach leads to complete single error detection capabilities. FFT and fast DCT examples are given.