基于三阶对称的一种快速傅立叶变换算法

A new algorithm for fast Fourier transform based on 3 levels of symmetry of Fourier kernel

在分析傅立叶变换特性的基础上,利用傅立叶变换核的三阶对称性,给出了一种快速傅立叶变换算法。该算法原理简单,编程容易,该算法N可为任意正整数,并给出了计算机软件实现的方法和步骤。作为比较,用该算法和DFT算法对函数exp(-t)作了傅立叶变换,二者相比,提高时效4倍多。

After analysing the character of Fourier transform, using 3 level symmetry of Fourier Kernel as a new algorithm for fast Fourier transform was proposed.The principle of the algorithm is simple and it only needs to calculate 1/8 proportion of number of Fourier Kernel.It is also easy for computer program.The number of N might be any whole number in the algorithm.The method of computer program is also given.Using the algorithm and DFT algorithm the result is given for x(n)=e-t.It shows that the speed for Fourier transform incereases more than 4 times.