FFT/DFT旋转因子生成算法误差分析及修正

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

旋转因子生成是FFT/DFT算法中的重要步骤,直接影响系统实现时的计算速度和资源开销。一种改进的算法给出了一个原理简单、计算速度快、占用存储资源少的旋转因子生成方案。然而系统实现时,乘加单元定点操作会引入截位或舍入误差,且该误差会随着乘加次数的增加而逐级扩散,导致旋转因子精度值下降,无法满足系统性能要求。基于FFT/DFT矩阵分解实现方式,本文给出了旋转因子生成的具体硬件实现结构,以及详细的误差分析。同时采用重定标的误差修订方案以减小误差,并推导出了重定标次数与系统给定条件之间的关系式,便于设计者进行灵活的设计。文章同时引入流水技术提高了系统速率。性能分析表明,相对于以往的算法,本文提出的算法占用的存储资源大大减少;且相对于不进行重定标方案,7次重定标能保证旋转因子精度提高约16个dB。

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.