快速傅氏变换和离散小波变换.doc

《快速傅氏变换和离散小波变换.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.10快速傅氏变换和离散小波变换长期以来，快速傅氏变换(FastFourierTransform)和离散小波变换(DiscreteWaveletTransform)在数字信号处理、石油勘探、地震预报、医学断层诊断、编码理论、量子物理及概率论等领域中都得到了广泛的应用。各种快速傅氏变换(FFT)和离散小波变换(DWT)算法不断出现，成为数值代数方面最活跃的一个研究领域，而其意义远远超过了算法研究的范围，进而为诸多科技领域的研究打开了一个崭新的局面。本章分别对FFT和DWT的基本算法作了简单介绍，若需在此方面做进一步研究，可参考文献[2]。1.1快速傅里

2、叶变换FFT离散傅里叶变换是20世纪60年代是计算复杂性研究的主要里程碑之一，1965年Cooley和Tukey所研究的计算离散傅里叶变换(DiscreteFourierTest)的快速傅氏变换(FFT)将计算量从О(n2)下降至О(nlogn)，推进了FFT更深层、更广法的研究与应用。FFT算法有很多版本，但大体上可分为两类：迭代法和递归法，本节仅讨论迭代法，递归法可参见文献[1]、[2]。1.1.1串行FFT迭代算法假定a[0],a[1],…,a[n-1]为一个有限长的输入序列，b[0],b[1],…,b[n-1]为离散傅里叶变换的结果序列，则有：

3、，其中W，实际上，上式可写成矩阵W和向量a的乘积形式：一般的n阶矩阵和n维向量相乘，计算时间复杂度为n2，但由于W是一种特殊矩阵，故可以降低计算量。FFT的计算流图如图1.1所示，其串行算法如下：算法22.1单处理器上的FFT迭代算法输入：a=(a0,a1,…,an-1)输出：b=(b0,b1,…,bn-1)Begin(1)fork=0ton-1dock=akendfor(2)forh=logn-1downto0do(2.1)p=2h(2.2)q=n/p(2.3)z=wq/2(2.4)fork=0ton-1doif(kmodp=kmod2p)t

4、hen(i)ck=ck+ck+p(ii)ck+p=(ck-ck+p)zkmodp/*ck不用(i)计算的新值*/endifendforendfor(3)fork=1ton-1dobr(k)=ck/*r(k)为k的位反*/endforEnd图1.1n=4时的FFT蝶式变换图显然,FFT算法的计算复杂度为O(nlogn)。1.1.1并行FFT算法设P为处理器的个数，一种并行FFT实现时是将n维向量a划分成p个连续的m维子向量，这里，第i个子向量中下标为i×m,…,(i+1)×m-1，其元素被分配至第i号处理器（i=0,1,…,p-1）。由图1.1可以看到，

5、FFT算法由logn步构成，依次以2logn-1、2logn-2、…、2、1为下标跨度做蝶式计算，我们称下标跨度为2h的计算为第h步（h=logn-1,logn-2,…,1,0）。并行计算可分两阶段执行：第一阶段，第logn-1步至第logm步，由于下标跨度h≥m，各处理器之间需要通信；第二阶段，第logm-1步至第0步各处理器之间不需要通信。具体并行算法框架描述如下：算法22.2FFT并行算法输入：a=(a0,a1,…,an-1)输出：b=(b0,b1,…,bn-1)Begin对所有处理器my_rank(my_rank=0,…,p-1)同时执行如下的

6、算法:(1)forh=logp-1downto0do/*第一阶段，第logn-1步至第logm步各处理器之间需要通信*/(1.1)t=2i,,l=2(i+logm),q=n/l,z=wq/2,j=j+1,v=2j/*开始j=0*/(1.2)if((my_rankmodt)=(my_rankmod2t))then/*本处理器的数据作为变换的前项数据*/(i)tt=my_rank+p/v(ii)接收由tt号处理器发来的数据块，并将接收的数据块存于c[my_rank*m+n/v]到c[my_rank*m+n/v+m]之中(iii)fork=0tom-1

7、doc[k]=c[k]+c[k+n/v]c[k+n/v]=(c[k]-c[k+n/v])*z(my_rank*m+k)modlendfor(iv)将存于c[my_rank*m+n/v]到c[my_rank*m+n/v+m]之中的数据块发送到tt号处理器else/*本处理器的数据作为变换的后项数据*/(v)将存于之中的数据块发送到my_rank-p/v号处理器(vi)接收由my_rank-p/v号处理器发来的数据块存于c中endifendfor(2)fori=logm-1downto0do/*第二阶段，第logm-1步至第0步各处理器之间不需要通信*/(

8、2.1)l=2i,q=n/l,z=wq/2(2.2)fork=0tom-1doif((kmod