基于函数映射的快速傅里叶变换算法

给出了一种新的快速傅里叶变换算法.算法利用了傅里叶变换因子C_N^kn、S_N^kn的对称特性,将函数序列x(n)个数压缩至四分之一.对其压缩后的函数序列,按其相邻函数值之差映射为函数p(n),同时对傅里叶变换因子C_N^kn、S_N^kn按累进求和映射为A_N^kn、B_N^kn.不同于FFT算法要求N为2的整数次幂,该算法中N可为任何偶数.对诸如方波、三角波、锯齿波及可分解为阶梯波的光学图象、特别是二值光学图象,能极大地减少计算量,某些情形低于FFT算法的计算量.

A NWE ALGORITHM FOR FAST FOURIER TANSFORM BASED ON FUNCTION MAPPING

A new algorithm for fast Fourier transform is proposed in the paper. Firstly, the number of function series x(n) is decreased from N to N/4 using the symmetry characteristics of Fourier transform factor C_N^kn S_N^kn. Secondly, the function x(n) is mapped to p(n) according to the difference of two neighbour value of x(n) while Fourier transform factor C_N^kn _N^kn are mapped to A_N^kn B_N^kn kn N with the summary of C_N^kn and S_N^kn respectively. The different from FFT algorithm, which need N=2^M (M must be a whole number), FMT algorithm N may be any even number. Comparing of the computational complexity with FFT algorithm for square wave,step wave,triangle wave, saw wave is also given, which shows that our algorithm significantly reduces the complexity and even better than FFT in some cases.