摘要： 传统位反算法在对快速傅里叶变换(FFT)的输出进行重排序时，只能以基-2形式输入数据。为此，提出一种新的基于映射迭代策略的算法，实现对任意基形式FFT输入的输出重排序，包括对映射迭代过程收敛性的证明。得出当FFT的输入点数N确定时，混合基形式下迭代次数为lbN的结论，为硬件架构的确定提供依据。
关键词:
混合基,
快速傅里叶变换,
重排序,
映射迭代,
收敛
Abstract: Considering the problem that the traditional bit-reversal algorithm is only fit for radix-2 Fast Fourier Transform(FFT) data reordering, a novel approach based on mapping recursion is proposed for radix-r FFT data reordering. The mapping recursion process is proved to be convergent, of which the recursion times is lbN, while the parameter N refers to the input number of FFT, thus affording the guideline for the implementation by hardware.
Key words:
mixed-radix,
Fast Fourier Transform(FFT),
reordering,
mapping recursion,
convergence
中图分类号:
黄佳森，陈帅，王小龙，叶凡，任俊彦. 基于映射迭代策略的FFT重排序算法设计[J]. 计算机工程.
HUANG Jia-sen, CHEN Shuai, WANG Xiao-long, YE Fan, REN Jun-yan. FFT Reordering Algorithm Design Based on Mapping Recursion Strategy[J]. Computer Engineering.