数 理 第七章快速傅里叶变换 着考处 快速傅里叶变换(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存在的问题