Error Analysis And Revision of Twiddle Factor Generation Method for FFT/DFT Algorithm

Twiddle factor generation is an important step for FFT/DFT algorithm, which straightforwardly influences the calculation speed and resource overhead in realization of system. An improved twiddle factor generation algorithm brings up a scheme characterized by simple principle, high calculation speed and few storage resource requirements. However, when system is carried out, fixed point operation of multiplication and addition will produce truncated error or roundoff error that will be spread along with increased times of multiplication and addition, which results in the precision of twiddle factor decline and can’t meet system requirement. Based on matrix decomposition realization method of FFT/DFT, our paper puts forward a detailed hardware realization of twiddle factor generation and error analysis. Our paper proposes to adopt relocated twiddle factor generation revision method to reduce error, at the same time, we deduce the equation between times of relocation and the given systemic condition in order to facilitate designer. Pipeline technology is also used to improve system rate. Performance analysis indicated that the revision of twiddle factor generation method needs much fewer storage resources compared with former methods; and relocate seven times can increase twiddle factor precision about 16 dB gains compared with the method which has no relocate.