并行FFT实现
并行FFT算法的分析与实现 书目 1 FFT算法分析与实现2 1.1 FFT算法的分析2 1.1.1 FFT算法的意义2 1.2 DFT算法和FFT算法在计算量上的对比2 1.2.1 DFT正变换2 1.2.2 变换后以2为底的FFT算法2 2 基于二时分FFT算法的蝶式运算定理3 2.1 并行可行性分析3 2.2 难点分析4 2.3 FFT算法的实现4 2.3.1 计算旋转因子4 2.3.2 创建线程5 2.3.3 关闭线程5 3 蝶形变换5 4 试验结果分析6 4.1 FFT算法效率分析6 4.1.1 奇偶两部分的算法效率分析6 4.1.2 蝶形变换内部多线程效率分析8 5 原程序9 1 FFT算法分析与实现 1.1 FFT算法的分析 1.1.1 FFT算法的意义 在离散傅里叶变换中,若要处理的数据量很大,工作量也变得特别巨大。正是由于这个缘由,使得离散傅里叶变换的应用范围在过去很长的时间里受到了严格的限制。而快速傅里叶变换有效的解决了运算量的问题,使得它的理论与方法在数理方程、线性系统分析、信号处理与仿真等许多学科领域都有着广泛的应用。由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换。若把此算法应用到并行程序设计中,它的效率将会有进一步的提高,将能得到更广泛的应用。 FFT算法有多个不同的变形:基二时分FFT算法、基二频分FFT算法、基四时分FFT算法、基四频分FFT算法。其中基二时分FFT算法是最重要的一种,它是J.W.Cooley和J.W.Tukey在1965年发表的一篇论文中提出。 1.2 DFT算法和FFT算法在计算量上的对比 1.2.1 DFT正变换 (1-1) 公式(1-1)可以看出,对每个n,计算X(n)须作N次复数乘法和N-1次复数加法,要全部计算完成须要N2次复数乘法和N*(N-1)次加法运算,当N特别大时,计算量将特别大。例如N=1024,则要运算2*(1024*1023)次。 1.2.2 变换后以2为底的FFT算法 由式(1-2)可以看出,共有r重和式,每重和式N个方程,每个方程仅需一次乘法运算,因此FFT算法的总计算量为Nr乘法和Nr次加法。假如在考虑WNK=-WNk+N/2,乘法的运算量还可以削减一半。假如在多核环境下用多线程技术让算法很好的并行运行,那么并行部分运行的效率有可能再提升一倍。 (1-2) 由公式(1-1)和(1-2)可知:FFT的时间困难度为O(N2),DFT算法的时间困难度为O(Nlog2N),当N很大时,FFT算法的效率可以明显的显示出来。 2 基于二时分FFT算法的蝶式运算定理 设X(k)=DFT[x(n)](0<=N,K