10快速傅氏变换和离散小波变换 长期以来,快速傅氏变换( Fast fourier transform)和离散小波变换( Discrete Wavelet ansform)在数字信号处理、石油勘探、地震预报、医学断层诊断、编码理论、量子物理及 概率论等领域中都得到了广泛的应用。各种快速傅氏变换(FFT)和离散小波变换(DWT算法 不断出现,成为数值代数方面最活跃的一个研究领域,而其意义远远超过了算法研究的范围, 进而为诸多科技领域的研究打开了一个崭新的局面。本章分别对FFT和DWT的基本算法作 了简单介绍,若需在此方面做进一步研究,可参考文献(2]。 1.1快速傅里叶变换FFT 离散傅里叶变换是20世纪60年代是计算复杂性研究的主要里程碑之一,1965年 Cooley 和 Tukey所研究的计算高散傅里叶变换 Discrete Fourier Test))的快速傅氏变换(FF1将计算量 从O(m2)下降至O( nlogn,推进了FFT更深层、更广法的研究与应用。FT算法有很多版本, 但大体上可分为两类:迭代法和递归法,本节仅讨论迭代法,递归法可参见文献[1l、[2]。 1.1.1串行FFT选代算法 假定a[0]d1l…anl]为一个有限长的输入序列,b[0],b1l,…b{-1为离散傅里叶 变换的结果序列,则有:研]=∑k(k=012-,n-1),其中Wn=en,实际上,上式可 写成矩阵W和向量a的乘积形式: 10w1w2 =0w2w4 12(m-1) 0(n-)2(n-1)…w(n-Xn-)‖a 般的n阶矩阵和n维向量相乘,计算时间复杂度为n2,但由于W是一种特殊矩阵 故可以降低计算量。FFT的计算流图如图1.1所示,其串行算法如下: 算法221单处理器上的FFI迭代算法 输入:a=(aa,…,an1) 输 (I)for k=0 to n-l Ck-ak (2)for h=logn-I downtoN do (2.3)=nm21. 10 快速傅氏变换和离散小波变换 长期以来，快速傅氏变换(Fast Fourier Transform)和离散小波变换(Discrete Wavelet Transform)在数字信号处理、石油勘探、地震预报、医学断层诊断、编码理论、量子物理及 概率论等领域中都得到了广泛的应用。各种快速傅氏变换(FFT)和离散小波变换(DWT)算法 不断出现，成为数值代数方面最活跃的一个研究领域，而其意义远远超过了算法研究的范围， 进而为诸多科技领域的研究打开了一个崭新的局面。本章分别对 FFT 和 DWT 的基本算法作 了简单介绍，若需在此方面做进一步研究，可参考文献[2]。 1.1 快速傅里叶变换 FFT 离散傅里叶变换是 20 世纪 60 年代是计算复杂性研究的主要里程碑之一，1965 年 Cooley 和 Tukey 所研究的计算离散傅里叶变换(Discrete Fourier Test)的快速傅氏变换(FFT)将计算量 从 О(n 2 )下降至 О(nlogn)，推进了 FFT 更深层、更广法的研究与应用。FFT 算法有很多版本， 但大体上可分为两类：迭代法和递归法，本节仅讨论迭代法，递归法可参见文献[1]、[2]。 1.1.1 串行 FFT 迭代算法 假定 a[0],a[1], …,a[n-1] 为一个有限长的输入序列，b[0], b[1], …,b[n-1]为离散傅里叶 变换的结果序列，则有： [ ] [ ] ( 0,1,2,..., 1) 1 0 =  = − − = b k a k W k n n m km n ，其中 W n i n e 2 = ，实际上，上式可 写成矩阵 W 和向量 a 的乘积形式：                                 =                 − − − − − − − − 1 2 1 0 0 ( 1) 2( 1) ( 1)( 1) 0 2 4 2( 1) 0 1 2 1 0 0 0 0 1 2 1 0 n n n n n n n n a a a a w w w w w w w w w w w w w w w w b b b b            一般的 n 阶矩阵和 n 维向量相乘，计算时间复杂度为 n 2，但由于 W 是一种特殊矩阵， 故可以降低计算量。FFT 的计算流图如图 1.1 所示，其串行算法如下： 算法 22.1 单处理器上的 FFT 迭代算法 输入：a=(a0,a1, …,an-1) 输出：b=(b0,b1, …,bn-1) Begin (1)for k=0 to n-1 do ck=ak end for (2)for h=logn-1 downto 0 do (2.1) p=2h (2.2) q=n/p (2.3) z=w q/2