数 理 第七章快速傅里叶变换 着考处 快速傅里叶变换(FFT)的出现推动了傅里叶分析 的发展和应用。事实上,FFT不是一种新的变换,而是 DFT的快速算法。线性卷和及离散傅里叶变换(DFT) 是信号处理涉及最多的运算,DFT在相关、滤波及谱估 计等方面已得到了广泛的应用。本章重点讨论FFT的基 2算法、分裂基算法和使频域细化的线性调频Z变换 (CZT)算法,同时,也讨论了卷和的快速算法
第七章 快速傅里叶变换 快速傅里叶变换（FFT)的出现推动了傅里叶分析 的发展和应用。事实上，FFT不是一种新的变换，而是 DFT的快速算法。线性卷和及离散傅里叶变换（DFT ） 是信号处理涉及最多的运算，DFT在相关、滤波及谱估 计等方面已得到了广泛的应用。本章重点讨论FFT的基 2算法、分裂基算法和使频域细化的线性调频 Z变换 (CZT)算法，同时，也讨论了卷和的快速算法
数 理 7.概述 着考处 虽然一个N点DFT的运算量非常大,但是,在一个N点DFT运算 中存在大量的重复运算,利用W因子的周期性,1958年 Goertzel提出 了一种DFT的快速算法。通过巧妙地利用W因子的周期性及对称性, 1965年 J W. Cooley和 J W.Tekey提出了一种高效的DFT快速算法,使N 点DFT的乘法计算量由N2次降为log2N次。因此,人们公认这 重要发现是数字信号处理发展史上的一个里程碑。加之超大规模集 成电路和计算机的飞速发展,使数字信号处理的理论在过去的50年 中得到飞速发展,并且广泛地应用于众多的技术领域,显示了这 学科的具大生命力
7.1 概述 2 2 1958 Goertzel 1965 J.W.Cooley J.W.Tekey log 2 nk N nk N N N W W N N N N DFT DFT DFT DFT DFT 虽然一个 点 的运算量非常大，但是，在一个 点 运算 中存在大量的重复运算，利用 因子的周期性， 年 提出 了一种 的快速算法。通过巧妙地利用 因子的周期性及对称性， 年 和 提出了一种高效的 快速算法，使 点 的乘法计算量由 次降为 次。因此，人们公认这一 重要发现是数字信号处理发展史上的一个里程 50 碑。加之超大规模集 成电路和计算机的飞速发展，使数字信号处理的理论在过去的 年 中得到飞速发展，并且广泛地应用于众多的技术领域，显示了这一 学科的具大生命力
数 理 着考处 自 Cooley和 Teke算法提出之后,新的算法不断涌现,概括起来, 快速傅里叶变换的发展有两个方向,一是针对N等于2的整数次幂的 算法,如基2算法、基4算法、实因子算法和分裂基算法等,二是针 对N不等于2的整数次幂的算法,它是以 Winograd为代表的一类算法 (如素因子算法、 Winograd算法)。 可以证明,在基4下,一个4点DFT可以不用乘法而只用加法来 实现,因此,基4算法比基2算法更有效。1984年提出的分裂基算法, 即同时使用基2和基4的算法,被认为是目前对N等于2的整数次幂的 各类算法中最为理想的一种算法
Cooley Tekey 2 2 4 2 Winograd Winograd 4 4 4 2 1984 N N DFT 自 和 算法提出之后，新的算法不断涌现，概括起来， 快速傅里叶变换的发展有两个方向，一是针对 等于 的整数次幂的 算法，如基 算法、基 算法、实因子算法和分裂基算法等，二是针 对 不等于 的整数次幂的算法，它是以 为代表的一类算法 （如素因子算法、 算法）。 可以证明，在基 下，一个 点 可以不用乘法而只用加法来 实现，因此，基 算法比基 算法更有效。 2 4 N 2 年提出的分裂基算法， 即同时使用基 和基 的算法，被认为是目前对 等于 的整数次幂的 各类算法中最为理想的一种算法
数 理 着考处 Winograd算法(WFTA)和上述算法在理论上有着根本的差别, 它是建立在下标映射和数论上的一套完全新颖的算法。在实际应用 上,所需的乘法次数比 Cooley- Teke算法有明显减少,因此,被认 为是对FFT算法的一大贡献。但是wFTA理论上比较复杂,编程也 比较困难,数据的长度受到较大的限制,在程序中,数据占有的内 存及数据的传递次数也比 Cooley- Teke算法增加很多。随着计算机 技术的发展,当执行一个乘法指令和执行一个加法指令所需的时间 相差不多,数据的传递时间相对于运算时间不能忽略不计时,WFTA 是否还具有突出的优点,已经受到人们的质疑。但是,对学习和研 究FFT的人员而言,了解WFTA及与之有关的一套理论仍然是一件 十分有意义的事
Winograd Cooley-Tekey Cooley-Tekey WFTA FFT WFTA 算法（ ）和上述算法在理论上有着根本的差别， 它是建立在下标映射和数论上的一套完全新颖的算法。在实际应用 上，所需的乘法次数比 算法有明显减少，因此，被认 为是对 算法的一大贡献。但是 理论上比较复杂，编程也 比较困难，数据的长度受到较大的限制，在程序中，数据占有的内 存及数据的传递次数也比 算法增加很多。随着计算机 技术的发展，当执 ,WFTA FFT WFTA 行一个乘法指令和执行一个加法指令所需的时间 相差不多，数据的传递时间相对于运算时间不能忽略不计时 是否还具有突出的优点，已经受到人们的质疑。但是，对学习和研 究 的人员而言，了解 及与之有关的一套理论仍然是一件 十分有意义的事
27.2直接计算DF存在的间题及改进的途径 数 虽然一个N点DFT的运算量非常大,但是可以利用W因子的 周期性、对称性及可约性,对DFT的运算加以改进 1、直接计算DFT存在的问题 由式(64.2)知道,一个N点序列x(n)=x(m)R(n)的DFT为 X(k)=∑x(mWx,k=0,2…,N (7.2.1) 由式(7.2.1)可知,DFT正是将时域的N点映射成频域的N点 的一种映射关系,即 X(0) wy W 0) X(1) wW X(N-1)|W0wN1…wx×x(N-1)
7.2直接计算DFT存在的问题及改进的途径 nk N W DFT N DFT 虽然一个 点 的运算量非常大，但是可以利用 因子的 周期性、对称性及可约性，对 的运算加以改进。 1 0 00 0 01 1 0 1 ( 1)( 1) 6.4.2 ( ) ( ) ( ) ( ) ( ) , 0,1,2, , 1 (7.2.1) 7.2.1 (0) (1) ( 1) N N nk N n N N N N NN N N N N NN N N xn xnR n X k x nW k N N N X WW W X WW W X N WW W − = − − − − = = =− ⎡ ⎤ ⎡ ⎢ ⎥ ⎢ ⎢ ⎥ ⎢ = ⎢ ⎥ ⎢ ⎢ ⎥ ⎢ ⎣ ⎦ − ⎣⎢ ∑ DFT DFT " " " # # #% # " 由式（ ）知道，一个 点序列 的 为 由式（ ）可知， 正是将时域的 点映射成频域的 点 的一种映射关系，即 (0) (1) (7.2.2) ( 1) x x x N ⎤⎡ ⎤ ⎥⎢ ⎥ ⎥⎢ ⎥ ⎥⎢ ⎥ ⎥⎢ ⎥ ⎥⎣ ⎦ − ⎦ # 1、直接计算DFT存在的问题
数 理 着考处 由式(64.3)知道,一个N点序列X(k)=X(k)R(k)的IDFT为 x(n n=0,1,2,…,N-1 (72.3) 由式(723)可知,IDFT正是将频域的N点映射成时域的N点 的一种映射关系,即 (0) X(0) X(1) (72.4) x(N-1) WW(N-D)..WN-1(N-D LX(N-1) 由式(722)可知,计算一个(k)值需要N次复数乘法及(N-1) 次复数加法,而一共有N个点,所以完成N个X(k)的运算,总共需要 N2次复数乘法及N(N-1)次复数加法
1 0 00 0 0 1 ( 1) 0 ( 1) ( 6.4.3 ( ) ( ) ( ) 1 ( ) ( ) , 0,1,2, , 1 (7.2.3) 7.2.3 (0) (1) 1 ( 1) N N nk N k N N N N NN N N N N N N N Xk XkR k xn X kW n N N N N x WW W x WW W N x N WW W − − = − −− −− − = = =− ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ − ∑ IDFT IDFT " " " # # #% # " 由式（ ）知道，一个 点序列 的 为 由式（ ）可知， 正是将频域的 点映射成时域的 点 的一种映射关系，即 1)( 1) 2 (0) (1) (7.2.4) ( 1) 7.2.2 ( ) ( 1) ( ) ( 1) N X X X N Xk N N N N X k N N N − − ⎡ ⎤⎡ ⎤ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎣ ⎦ − ⎣ ⎦ − − # 由式（ ）可知，计算一个 值需要 次复数乘法及 次复数加法，而一共有 个点，所以完成 个 的运算，总共需要 次复数乘法及 次复数加法
数 理 着考处 考虑到 (1)计算一次复数乘法,需要用四次实数乘法及二次实数加法 (2)计算一次复数加法,需要用二次实数加法。 (3)计算单个X(k)值,需要4N次实数乘法及2N+2(N-1)=2(2N-1) 实数加法。则完成N个Y(k)的运算,总共需要的实数乘法次数M和 实数加法次数M分别为 (1)M=4N2; (2)Mn=2N(2N-1) 因此,直接计算DFT,随着N的增加,其计算量是惊人的
2 1 2 3 ( ) 4 2 2( 1) 2(2 1) ( ) 1 4 2 2 (2 1) c a c a Xk N N N N N Xk M M M N M NN N + −= − = = − DFT 考虑到 （）计算一次复数乘法，需要用四次实数乘法及二次实数加法。 （ ）计算一次复数加法，需要用二次实数加法。 （ ）计算单个 值，需要 次实数乘法及 实数加法。则完成 个 的运算，总共需要的实数乘法次数 和 实数加法次数 分别为 （） ； （ ） 。 因此，直接计算 ，随着 的增加，其计算量是惊人的
F压数 理 22、改进的途径 着考处 利用DFT中W的下述性质,可以减小DFT的运算量 (1)W的对称性:(Ww)=W 2)W的周期性:Wm=W(+Nk=形mk+N) (3)W的可约性:W=Wm,W=WWm 显然有:WmN-8)=W(N-m)=W,WN2=-1,W(+N2)=-Wk 综上所述 (1)利用W的上述特性,可使DFT运算中的有些项可以合并; 2)利用W的对称性、周期性和可约性,可以将长序列的DFT 分解成短序列的DFT。 快速傅里叶变换(FFT)算法正是基于这样的基本思路发展 起来的。快速傅里叶变换的基本算法可以分为两类,即按时间 抽选(DT)法,按频率抽选(DIF)法
() () () () 2 ( 2) 1 ( ) 2 3 , 1 1 nk N nk nk nk N N N nk nk n N k n k N N N N N nk nk nmk nk nk m N N mN N N m n N k N n k nk N k N k N N NN N N nk N W W WW W WW W W WW WW W W WW W W W ∗ − + + − −− + = = = = = = = =− =− DFT DFT DFT 利用 中 的下述性质，可以减小 的运算量。 （） 的对称性： （ ） 的周期性： （ ） 的可约性： 显然有： ， ， 综上所述 （）利用 的上述特性，可使 运算中的有 2 ) nk WN DFT DFT FFT DIT DIF 些项可以合并； （ ）利用 的对称性、周期性和可约性，可以将长序列的 分解成短序列的 。 快速傅里叶变换（ 算法正是基于这样的基本思路发展 起来的。快速傅里叶变换的基本算法可以分为两类，即按时间 抽选（ ）法，按频率抽选（ ）法。 2、改进的途径
数 理 2473 Goertzel算法 着考处 利用W因子的周期性,1958年 Goertzel提出了一种 DFT的快速算法,我们称为 Goertz算法 1、将DFT运算化为线性卷和运算 考虑到x(n)=x(n)R(n)及W=(e12mN)M=e2 若定义 ys(n)=x(n)*WN u(n)=2x(m)R(mW(n-m u(n-m) ∑x(m)R、(mWx(m (73.1)
7.3 Goertzel算法 1958 nk WN Goertzel DFT Goertzel 利用 因子的周期性， 年 提出了一种 的快速算法，我们称为 算法。 2 2 ( ) ( ) () () () ( ) 1 () () () ( ) ( ) ( ) ( ) ( ) (7.3.1) Nk j N Nk j k N N nk n m k kN N N m n n mk N N m xn xnR n W e e y n x n W u n x m R mW u n m x m R mW − −− π π +∞ − − − =−∞ − − =−∞ = == = =∗ = − = ∑ ∑ 考虑到 及 若定义 1、将DFT运算化为线性卷和运算
数 理 着考处 由式(7.3.1)可得 y(N)=∑x(m)R(Om)Wm=∑x(m)R(mW n=-00 n=-0 ∑x(mWW=∑x(nx"=X(k) m=0 即X(k)=y(n)N 73.2) 由式(732)可知,Y(k)正是有限长序列x(m)=x(m)R(n)作用 于单位冲激响应为h(n)=W"u(m的线性位不变系统时,其系统零 状态响应y(n)在n=N位的输出值 考虑到h(n)=W"u(mn),则描述线性位不变系统的转移函数为 H(二) 1-Wx=,1<=|s (73.3) 因此,完成X(k的一阶复递推计算的信流图,如图7.3.所示
( ) 1 1 0 0 7.3.1 () () () () () ( ) () () ( ) ( ) (7.3.2) 7.3.2 ( ) N N N mk mk k N N N N m m N N mk nk N N m n k nN y N x m R mW x m R mW x mW x nW X k Xk y n X k − − =−∞ =−∞ − − = = = = = = == = ∑ ∑ ∑ ∑ 由式（ ）可得 即 由式（ ）可知， 正是有限长序列 1 () () () () () ( ) () () 1 ( ) , 1 (7.3.3) 1 ( ) 7.3.1 N nk N k nk N k N xn xnR n hn W un yn n N hn W un Hz z W z X k − − − − = = = = = < ≤∞ − 作用 于单位冲激响应为 的线性位不变系统时，其系统零 状态响应 在 位的输出值。 考虑到 ，则描述线性位不变系统的转移函数为 因此，完成 的一阶复递推计算的信流图，如图 所示