一种实现任意基FFT的快速整序算法

A Fast Digit-reversal Permutation Algorithm for Radix-B FFT

提出了一种数据整序快速算法，能对任意基ＦＦＴ变换的数据进行快速整序。该算法对数据进行循环嵌套分组，简化了数据交换的判断条件，并减少了求解数据序号位倒序值的运算量。计算结果表明，当数据规模越大，该算法的数据整序时间较其他算法越少，并使基２－ＦＦＴ的运算时间较用其他整序算法时减少１．３％～４％。较用直接整序方法时减少７％～１９％。

A fast digit-reversal permutation algorithm for the radix-B fast Fourier transforms ( FFT ) is presented in this paper , which decreases the computation of the ' digit-reversing' and speeds up the FFT by loop nesting dividing the datas into small groups . According to timing experiments , the fast permutation algorithm significantly hastens the digit-reversal permutation and saves the FFT running time by 1 . 3% ～ 4% ,which is 7%～ 19% shorter than that of other permutation algorithm.