Error detection of real-number input fast Fourier transform networks

Fast Fourier transform (FFT) is one of the techniques indispensable in signal processing. The recent development of hardware and parallel processing techniques makes it possible to use a specific chip circuit for signal processing such as FFT and in fact there exist systems that achieve high-speed computation of FFT. Such systems use many processors in a chip. Consequently, these are likely to have high error probability and require on-line fault detection. This paper treats the fault-detection methods of the FFT-CN (FFT calculation network) under the assumptions that the FFT-CN is made up of N/2 x log(2)N two-input butterfly modules, that its N inputs are all restricted to the real values, and that the detection of the fault is performed by the comparison of the outputs of the network. The assumed structure of the FFT-CN is symmetric so a simple fault-detection method would not be successful, But we will show here that the restriction of the inputs to real numbers makes it possible to find a fault in the FFT-CN.