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

A NWE ALGORITHM FOR FAST FOURIER TANSFORM BASED ON FUNCTION MAPPING

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

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 kn N?S kn N. 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 kn N?S kn N are mapped toA kn N?B kn N with the summary of C kn N and S kn N 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.