Error analysis of fast fourier transform

The error of the decimate in time (DIT) radix-2 fast Fourier transform (FFT) is analyzed, where the data format is two's complement. The error analysis model of butterfly operation is given explicitly. Utilizing the characteristics of signal flow graph, for the three quantization methods of truncation, rounding and convergent rounding, the exact upper bound and lower bound of mean square error are obtained for the two FFT algorithms of fixed point and block floating point. Finally, the power ratio of noise and signal is given and the simulated results are plotted. The results show that the block floating point algorithm is better than with the fixed point algorithm. The rounding and convergent rounding quantization method is better than the method of truncation.