第2章离散傅里叶变换(DFT)及其快速算法(FFT)

1、成都理工大学工程技术学院成都理工大学工程技术学院 模拟域模拟域 FTFT、LTLT 数字域数字域 DTFTDTFT、ZTZT 时间域 t:连续 频率域、s:连续 时间域 n:离散 频率域、z：连续连续 离散傅立叶变换（离散傅立叶变换（DFTDFT）实现了信号在频域实现了信号在频域特性的离散化，使得频域也能够用计算机进行特性的离散化，使得频域也能够用计算机进行处理。并且这种处理。并且这种DFTDFT变换可以有多种实用的快变换可以有多种实用的快速算法。使信号处理在时、频域的处理和转换速算法。使信号处理在时、频域的处理和转换均可离散化和快速化。因而均可离散化和快速化。因而具有重要的理论意具有重要的理

2、论意义和应用价值，是本课程学习的一大重点义和应用价值，是本课程学习的一大重点。 连续连续非周期非周期 离散离散周期周期信号特性的信号特性的时频时频域对应关系域对应关系 周期周期？如何对周期为如何对周期为N的周期序列进行频域分析的周期序列进行频域分析 如：如： 周期序列周期序列不能进行不能进行Z变换变换，因为其在，因为其在 n=- 到到+ + 都都周而复始永不衰减，周而复始永不衰减，即即 z z 平面上没有收敛域，所以平面上没有收敛域，所以其其DTFTDTFT亦不存在。但是，亦不存在。但是，如同连续时间周期信号可用如同连续时间周期信号可用傅氏级数表达，周期序列也可用离散的傅氏级数来表傅氏级数表达

3、，周期序列也可用离散的傅氏级数来表示。示。)()(kNnxnxnNjene/21)(knNjkene/2)(周期为周期为N N的正弦序列其基频成分为：的正弦序列其基频成分为：K次谐波序列为：次谐波序列为：2/()2/jNkN njN knee 但离散级数所有谐波成分中只有但离散级数所有谐波成分中只有N个是独立的个是独立的，这是与连，这是与连续续傅傅氏级数不同。氏级数不同。( )( )kNkenen 将周期序列展成离散傅里叶级数时，只需取将周期序列展成离散傅里叶级数时，只需取 k=0 到到(N-1) 这这N个独立的谐波分量，所以一个周期序列个独立的谐波分量，所以一个周期序列的离散傅里叶级数只需包

4、含这的离散傅里叶级数只需包含这N个复指数。个复指数。 10/2)(1)(NKknNjekXNnx10)()(102NkenxkXNnknNj 1） 也是一个由也是一个由 N 个独立谐波分量组成的傅立叶级数个独立谐波分量组成的傅立叶级数 2） 为周期序列，周期为为周期序列，周期为N)(kX)(kX小结：小结：2/jNNWe若令： DFS变换对公式表明，一个周期序列虽然是无穷长变换对公式表明，一个周期序列虽然是无穷长序列，但是只要知道它一个周期的内容（一个周期内序列，但是只要知道它一个周期的内容（一个周期内信号的变化情况），其它的内容也就都知道了，所以信号的变化情况），其它的内容也就都知道了，所以

5、这种无穷长序列实际上只有这种无穷长序列实际上只有N个序列值的信息是有用个序列值的信息是有用的，的，因此周期序列与有限长序列有着本质的联系。因此周期序列与有限长序列有着本质的联系。1010)()(1)()()()(NkknNNnknNkXIDFSWkXNnxnxDFSWnxkXDFS 离散傅里叶级数变换离散傅里叶级数变换IDFS离散傅里叶级数反变换。离散傅里叶级数反变换。例例 ：求出下面周期序列的求出下面周期序列的 DFS DFS 表示式表示式 .3 , 2 , 1 , 0 , 3 , 2 , 1 , 0 , 3 , 2 , 1 , 0.,)(nx解：解：上述序列的基本周期为上述序列的基本周期为

6、 N=4，因而因而 W4 = e-j2/4 = -j， 304)()(nnkWnxkX)22()()() 3(2)()()2()22(320)()() 1 (6) 3()2() 1 ()0()()()0(3033034302302430304303004jjnxWnxXjnxWnxXjjjjnxWnxXxxxxnxWnxXnnnnnnnnnnnnnnn4( )( ), ( )8( )( )x nR nx nNx nx nDFS ：已已知知序序列列将将以以为为周周期期 进进行行周周期期延延拓拓成成，求求的的例例。 解法一：数值解1780038022223888( )( )( )1NnknkNnn

7、nknjkjkjkX kx n Wx n WWeee (1)121(3)12(0)4(2)0(1(5)121(7)1214)0(6)0XXXXXjXjXjXj 221780022243440488838( )11sin2sin8NjknjknNnnjkjkjkjkjknjkjkjkjknjkX kDFS x nx n ex n eeeeeeeeeekek 解解法法二二：公公式式解解 假设假设 都是周期为都是周期为 N 的两个周期序的两个周期序列，各自的离散傅里叶级数为：列，各自的离散傅里叶级数为： 1）线性）线性设a,b为任意常数)()(nynx、)()()()(nyDFSkYnxDFSkX(

8、 )( )( )( )DFS ax nby naX kbY k则：证：因为 及 都是以N为周期的函数，所以有 )()()()(nxwlkXIDFSkXwmnxDFSnlNmkN)(nxknNw101)()()(NnmNmikmNkiNknNwwixwmnxmnxDFS)()()(101kXwwixwwixwmkNNikiNmkNmNmikiNmkN()( )nlNIDFSX klw x n同理可证：3）共轭对称性）共轭对称性 对于复序列 ，其共轭序列为 ，则： nx nx* kXnx*DFS 1*01*0DFS( )( )NnkNnNnkNnxnx n Wx n WXk 证： kXnx*DFS

9、进一步可得：进一步可得： )()(21DFS21ReDFS*kNXkXnxnxnx *e1( )()( )2X kXNkXkX k为的共轭偶对称分量 )()(21ImDFS*okNXkXkXnxj共轭奇对称分量 4）周期卷积）周期卷积( )( ) ( )F kX k Y k若：10( )( )( ) ()Nmf nIDFS F kx m y nm则：10)()(Nmmnxmy这是一个卷积公式，但与前面讨论的线性卷积的这是一个卷积公式，但与前面讨论的线性卷积的差别在于，这里的卷积过程只限于一个周期内差别在于，这里的卷积过程只限于一个周期内（即（即 m=0N-1），称为周期卷积。），称为周期卷积。

10、10( )( )( )1( )( )NknNkf nIDFSX k Y kX k Y k wN证： 1010)()(1NkNmnkNmkNwkYwmxN11()00101()( )() ()NNn m kNmkNmx mY k wNx m y nm( )( ) ( )f nx n y n若：10101( )( )( ) ()1() ( )NlNlF kDFS f nX l Y klNX kl Y lN则： 由于由于DFS与与IDFS的对称性，对周期序列乘积，的对称性，对周期序列乘积，存在着频域的周期卷积公式。存在着频域的周期卷积公式。0N-Nm1( )x m0N-Nm2( )x m0N-Nm2

11、20()()xmxm 0N-Nm21 ()xm （1）x1(n)和和x2(n)是周期的。是周期的。 （2）求和范围为）求和范围为一个周期一个周期（3）周期序列周）周期序列周期卷积后，序期卷积后，序列的长度仍然列的长度仍然是周期的；是周期的；位置保持位置保持不变不变n序列的线性卷积与周期卷积的几点区别：序列的线性卷积与周期卷积的几点区别：线性卷积的求和对参与卷积的两个序列无任何线性卷积的求和对参与卷积的两个序列无任何 要求，要求，而周期卷积要求两个序列是周期相同的周期序列。而周期卷积要求两个序列是周期相同的周期序列。线性卷积的求和范围由两个序列的长度线性卷积的求和范围由两个序列的长度 和所在的区

12、和所在的区间决定，间决定，而周期卷积的求和范围是一个周期而周期卷积的求和范围是一个周期 N。线性卷积所得序列的长度线性卷积所得序列的长度 (M+N-1) 由参与卷积的两由参与卷积的两个序列的长度确定，个序列的长度确定，而周期卷积的结果仍是周期序而周期卷积的结果仍是周期序列列 ，且周期与原来的两个序列周期相同。，且周期与原来的两个序列周期相同。周期卷积等同于两个周期序列在一个周期上的线性卷周期卷积等同于两个周期序列在一个周期上的线性卷积计算。积计算。 15121200( )()()()()Nmmy nx m x nmx m x nm 解：解：例：例： 已知序列已知序列 x1(n)=R4(n)，x

13、2(n)=(n+1)R5(n)，分别将序列以周期为分别将序列以周期为 N=6 拓展成周期序列，求拓展成周期序列，求两个周期序列的周期卷积和。两个周期序列的周期卷积和。154512设序列设序列x(nx(n) )有效长度为有效长度为M M，定义x(nx(n) )的的N N点点DFTDFT为为式中，式中，N N称为离散傅里叶变换区间长度，要求称为离散傅里叶变换区间长度，要求N MN M。为为书写简单，书写简单，令 ，因此通常将，因此通常将N N点点DFTDFT表示为表示为定义X(kX(k) )的的N N点离散傅里叶逆变换点离散傅里叶逆变换(IDFT)(IDFT)为为 21j0( )DFT ( )(

14、)e, 0, 1, , 1Nk nNNnX kx nx nkN 10( )DFT ( )( ), 0, 1, , 1Nk nNNnX kx nx n WkN2jeNNW 101( )IDFT( )( ), 0, 1, , 1Nk nNNkx nX kX k WnNN长度为N的离散序列101jj010( )ZT ( )( )(e) ( )( )e( )DFT ( )( ), 0,1,1MnnMnnMknNNnX zx nx n zXDTFT x nx nX kx nx n WkNDFT有明确的物理意义，我们可以通过比较序列的有明确的物理意义，我们可以通过比较序列的DFT、DTFT、ZT，并将，并

15、将DFT与周期序列的与周期序列的DFS联系起来，得联系起来，得到到DFT的物理意义。的物理意义。 1.DFT和DTFT、ZT之间的关系 假设序列的长度为假设序列的长度为M，NM将将N点点DFT和和DTFT、ZT的定义重写如下的定义重写如下 比较前面三式，得到比较前面三式，得到 ，k=0, 1, 2, k=0, 1, 2, , N-1 , N-1 ，k=0, 1, 2, k=0, 1, 2, , N-1 , N-1 2je( )( )kNzX kX zj2( )(e)kNX kX DFT与与z变换变换2X(ej)X(k)ok1N00 ImjZ Re Z1234567(N-1)2Nk=0 DFT与

16、与DTFT变换变换 序列序列x(n)的的N点点DFT是是 x(n)的的Z变换在单位圆上的变换在单位圆上的N点等点等间隔采样；间隔采样； X(k)为为x(n)的傅立叶变换的傅立叶变换 在区间在区间 上的上的N点等间隔采样。点等间隔采样。0, 2 ()jX e结论：结论：解解: x(nx(n) )的的8 8点点DFTDFT为为 x(nx(n) )的的1616点点DFTDFT为为8( )( )x nR n 277j888008, 0( )( )e0,1, 2, 3, 4, 5, 6, 7k nk nnnkX kR n Wk 2j8781616162j1601611e( )11ekkk nkknWX

17、kWW7j16sin2e , 0,1,2,15sin16kkkk例：例： ，分别计算，分别计算x(n)的的8点、点、16点点DFT。()Xk()jXe2.DFT2.DFT和和DFSDFS之间的关系之间的关系： 周期延拓周期延拓 取主值取主值 有限长序列有限长序列 周期序列周期序列 主值区序列主值区序列有限长序列有限长序列周期序列周期序列主值区间序列主值区间序列( )0,1, 2,1x nnM()()Nmxnxnm N 0001nNnmNn0( )Nnn( )( )( )NNNxnxn Rn ,( )( )NNMxnx n( )Nx n8( )x n4( )x n周期序列的周期序列的DFS:DF

18、S:有限长序列的有限长序列的DFT:DFT:对比二者发现：对比二者发现： 是是 的主值区序列，条件的主值区序列，条件N NMM1010()()()()NknNNNnNknNnXkD F Sxnxn Wxkn W 1010( )0( )( )1)NknNnNknnX kDFT x nx n WNx n Wk( )X k( )X k( )()( )( )( )NmX kX kmNX kX k Rk( )NxnnN0N2NN0n)(nx1N 0k)(kXDFSDFT( )X k02NNk2N()()()()()()()()()()NNNNNx nx n RnxnxnXkXk RkXkXkNM:()(

19、):()()D F Tx nXkD F Sx nXkDFT引用了引用了DFS的结论，隐含着周期性，但是当的结论，隐含着周期性，但是当注意力都集中在所谓的主值区间（注意力都集中在所谓的主值区间（0N-1）时，所）时，所看到的时域、频域特性都是有限序列，并且之间看到的时域、频域特性都是有限序列，并且之间的对应关系依然是一一对应的。的对应关系依然是一一对应的。也可以表示成矩阵形式也可以表示成矩阵形式式中，式中，X是是N N点点DFTDFT频域序列向量频域序列向量: :x是时域序列向量是时域序列向量: :WN N称为称为N N点点DFTDFT矩阵，定义为矩阵，定义为 10( )DFT ( )( ),

20、0, 1, , 1Nk nNNnX kx nx n WkNNXW xT(0) (1) (2) (1)XXX NX NXT (0) (1) (2) (1)xxx Nx Nx121242(1)12(1)(1)(1)1111111NNNNNNNNNNNNNNNNWWWWWWWWWW也可以表示为矩阵形式也可以表示为矩阵形式: : 称为称为N N点点IDFTIDFT矩阵，定义为矩阵，定义为从式从式(3.1.12)(3.1.12)和式和式(3.1.14)(3.1.14)，我们可以发现，我们可以发现 101( )IDFT( )( ), 0, 1, , 1Nk nNNkx nX kX k WnNN1NxWX1

21、NW12(1)1242(1)(1)2(1)(1)(1)11111111NNNNNNNNNNNNNNNNWWWWWWNWWWW1*1NNNWW与序列的与序列的DTFTDTFT类似，类似，DFTDFT也有许多重要的性质。其中一些性质也有许多重要的性质。其中一些性质本质上与本质上与DTFTDTFT的相应性质相同，但是某些其他性质稍微有些的相应性质相同，但是某些其他性质稍微有些差别。差别。p 线性性质线性性质 p DFT的隐含周期性的隐含周期性 p 循环移位性质循环移位性质 p 复共轭序列的复共轭序列的DFT p DFT的共轭对称性的共轭对称性 p 循环卷积定理循环卷积定理p 离散巴塞伐尔定理离散巴塞

22、伐尔定理（1 1）线性性质）线性性质 设有限长序列设有限长序列 的长度分别为的长度分别为 ， ，a a和和b b为常数。为常数。则则式中式中 ， 。12( )( )x nxn和12NN和12( )( )( )x nax nbxn12( )( )( ) , 0, 1, 2, , 1X kaXkbXkkN12 max, NNN11( )DFT( ) ,NXkx n22( )DFT( )NXkx n（2 2）循环移位性质）循环移位性质1.1.循环移位循环移位 设序列设序列x(nx(n) )的长度为的长度为M M，对，对x(nx(n) )以以N N（N MN M）为周期进行）为周期进行周周期延拓，得到

23、期延拓，得到定义定义x(nx(n) )的循环移位序列为的循环移位序列为上式表示将序列上式表示将序列x(nx(n) )以以N N为周期进行周期延拓，再左移为周期进行周期延拓，再左移m m个个单位并取主值序列，单位并取主值序列， 就得到就得到x(nx(n) )的循环移位序列的循环移位序列y(ny(n) )。下图中下图中(a)(a)、(b)(b)、(c)(c)和和(d)(d)分别描述了分别描述了x(nx(n) )、 、 和和y(ny(n) )。图中。图中M=6M=6，N=8N=8，m=2m=2。 ( )( )NNxnx n( )()( )()( )NNNNy nxnm Rnx nmRn( )Nxn(

24、)Nxnm序列的循环移位过程示意图移位前移位前左移两位后左移两位后oo圆周移位圆周移位)()()()(nxwlkXIDFSkXwmnxDFSnlNmkN()( )( )()( )( )mkNNNnlNNNDFT x nmRkwX kIDFT XklRkw x n2.循环移位性质循环移位性质（3 3）循环卷积）循环卷积若若 F（k）=X（k）Y（k）则 或 10)()()()()(NmNNnRmnymxkFIDFTnf10)()()()()(NmNNnRmnxmykFIDFTnf证：这个卷积可看作是周期序列证：这个卷积可看作是周期序列 卷积后再取卷积后再取其主值序列。将其主值序列。将F（k）周期

25、延拓，得：周期延拓，得： 则根据则根据DFS的周期卷积公式：的周期卷积公式：因因0mN-1时，时，x(m)N=x(m)，因此因此经过简单的换元可证明：经过简单的换元可证明：)()(nynx与)()()(kYkXkF1010)()()()()(NmNNNmmnymxmnymxnf)()()()()()(10nRmnymxnRnfnfNNmNN10)()()()(NmNNnRmnxmynf这一卷积过程这一卷积过程与与周期卷积周期卷积比较，过程是一样的，只是这里只取比较，过程是一样的，只是这里只取结果的主值序列结果的主值序列，由于卷积过程只在主值区间，由于卷积过程只在主值区间0mN-1内进行，内进行

26、，所以所以 RN（n）实际上就是实际上就是 y（-m）的循环移位，的循环移位，称为称为“循环卷积循环卷积”，习惯上常用符号，习惯上常用符号“ ”表示循环卷积，以表示循环卷积，以区别于线性卷积。区别于线性卷积。 )()()()()()()()()()(1010nxnynRmnxmynRmnymxnynxNmNNNmNNNmny)( 1）由有限长序列）由有限长序列 x(n)、y(n) 构造周期序列构造周期序列)()(nynx与2）计算周期卷积）计算周期卷积 10)()()(Nmmnymxnf3）卷积）卷积 结果取主值结果取主值)()()(nRnfnfN10)()()(1)()(NlNNkRlkYl

27、XNnfDFTkF10)()()(1NlNNkRlkXlYN同样，若同样，若 f(n)=x(n)y(n)f(n)=x(n)y(n)，则则（4 4）有限长序列的线性卷积与循环卷积（循环卷积的）有限长序列的线性卷积与循环卷积（循环卷积的应用）应用） 实际问题的大多数是求解线性卷积，如实际问题的大多数是求解线性卷积，如信号信号 x（n）通过系统通过系统 h（n），），其输出就是线性卷积其输出就是线性卷积 y（n）=x（n）*h（n）。）。而循环卷积比起线性卷积，在运算速度上而循环卷积比起线性卷积，在运算速度上有很大的优越性，它可以采用快速傅里叶变换（有很大的优越性，它可以采用快速傅里叶变换（FFT）

28、技术，若能技术，若能利用循环卷积求线性卷积，会带来很大的方利用循环卷积求线性卷积，会带来很大的方便。便。 现在我们来讨论上述现在我们来讨论上述 x（n）与）与h（n）的线性卷积，的线性卷积，如果如果x（n）、）、h（n）为有限长序列，则在什么条件下为有限长序列，则在什么条件下能用循环卷积代替而不产生失真。能用循环卷积代替而不产生失真。 设设 x（n）长度为）长度为N， y（n）长度为）长度为M，100( )( )* ( )( ) ()( ) ()Nmmf nx ny nx m y nmx m y nm则：f（n）是一个长度为）是一个长度为N+M-1的有限长序列。的有限长序列。 重新构造两个有限

29、长序列重新构造两个有限长序列 x（n）、）、y（n），），长度均为长度均为L maxN,M ，序列序列 x（n）只有前只有前N个是非零值，个是非零值，后后L-N个补零值个补零值；序列；序列 y（n）只有前只有前M个是非零值，个是非零值，后后L-M个为补零值个为补零值。为了分析。为了分析 x（n）与）与y（n）的循环卷积，对的循环卷积，对补零后的补零后的x（n），），y（n）进行周期延拓：）进行周期延拓：rqrLnynyqLnxnx)()()()(1100( )() ()() ()LLLmmfnx m y nmx m y nm rrLmLmrrLnfmrLnymxmrLnymx)()()()()

30、(1010其中其中f（n）就是线性卷积，也就是说，就是线性卷积，也就是说，x（n）、）、y（n）周期延拓后的周期卷积，是周期延拓后的周期卷积，是x（n）、）、y（n）线性卷积的线性卷积的周期延拓，周期为周期延拓，周期为L。它们的周期卷积序列为：它们的周期卷积序列为： 根据前面的分析，根据前面的分析，f（n）具有具有 N+M-1 个非零序列值，因此，如果周个非零序列值，因此，如果周期卷积的周期期卷积的周期 LN+M-1，那么那么 f（n）周期延拓后，必然有一部分非零序周期延拓后，必然有一部分非零序列值要重叠，出现混淆现象。列值要重叠，出现混淆现象。只有只有 LN+M-1 时，才不会产生交叠，这时

31、时，才不会产生交叠，这时 f（n）的周期延拓的周期延拓 中每一个周期中每一个周期L内，前内，前N+M-1个序列值个序列值是是f（n）的全部非零序列值，而剩下的的全部非零序列值，而剩下的 L -（N+M-1）点的序列则是补充点的序列则是补充的零值。的零值。循环卷积正是周期卷积取主值序列：循环卷积正是周期卷积取主值序列： 所以使圆周卷积等于线性卷积而不产生混淆的必要条件圆周卷积等于线性卷积而不产生混淆的必要条件是： LN+M-1 ()Lfn( )( )( )( )( )LLLfnx ny nfn R n)()(nRrLnfLr（5 5）共轭对称性）共轭对称性 设设 x*（n）为）为 x（n）的共轭

32、复数序列，则）的共轭复数序列，则 DFTx*（n）=X*(N-k)利用DFS相应性质*1Re( ) ( )( )2DFTx nDFT x nx n*1( )()2( )eX kXNkXk*1 Im ( ) ( )( )2DFT jx nDFT x nxn*01( )()2( )X kXNKXk( )( )( )eoXkXkX k显然，推论：推论：*)()(21)(kNNXkNXkNXe)()(21*kXkNX)()(*kNXkXeeXe(k) 称为称为X(k)的共轭偶对称分量的共轭偶对称分量用同样的方法可得到用同样的方法可得到 X0(k)= - X*0(N-k)*1( )( )()2eXkX

33、kXNk 根据根据x（n）与）与X（k）的对称性，同样可找到的对称性，同样可找到X（k）的实的实部、虚部与部、虚部与x（n）的共轭偶部与共轭奇部的关系。的共轭偶部与共轭奇部的关系。 分别以分别以xe（n）及）及x0（n）表示序列表示序列x（n）的共轭偶部与共的共轭偶部与共轭奇部：轭奇部：可证明可证明: DFTxe（n）=ReX（k） DFTx0（n）=jImX（k） )()(21)()()(21)(*nNxnxnjxnNxnxnxoe实信号实信号DFTDFT的特点：的特点：设设x(nx(n) )是长度为是长度为N N的实序列，其的实序列，其N N点点DFTDFT用用X(kX(k) )表示，我们

34、表示，我们从前面的结论可知道从前面的结论可知道X(kX(k) )具有共轭对称性质，即具有共轭对称性质，即如果将如果将X(kX(k) )写成极坐标形式写成极坐标形式 ，由共轭对称，由共轭对称性质，说明性质，说明X(kX(k) )的模关于的模关于 k = N/2k = N/2点偶对称点偶对称 ，利用利用DFTDFT的共轭对称性质可以减小实序列的的共轭对称性质可以减小实序列的DFTDFT计算量。计算量。( )()X kXNkj ( )( )( ) ekX kX k( )() X kX Nk( )()kNk （6 6）选频性）选频性 （对（对0 0有限制）有限制） 对复指数函数对复指数函数 进行采样得

35、复序列进行采样得复序列 x（n） 其中其中q为整数。当为整数。当0=2/N时，时，x（n）=ej2nq/N,其离散傅里叶变换为其离散傅里叶变换为 写成闭解形式写成闭解形式可见，当输入频率为可见，当输入频率为q0时，变换时，变换X（K）的）的N个值中只有个值中只有 X（q）=N，其其余皆为零，如果输入信号为若干个不同频率的信号的组合，经离散傅里余皆为零，如果输入信号为若干个不同频率的信号的组合，经离散傅里叶变换后，不同的叶变换后，不同的k上，上，X（k）将有一一对应的输出，因此，离散傅里将有一一对应的输出，因此，离散傅里叶变换算法实质上对频率具有选择性。叶变换算法实质上对频率具有选择性。 njq

36、oenx)(10/2/2)(NnNnkjNnqjeekXqkqkNeekXNkqjkqj011)(/ )(2)(2tjqoenx)(（7 7）DFTDFT形式下的形式下的ParsevalParseval定理定理1010*)()(1)()(NnNkkYkXNnynx101022| )(|1| )(|NnNkkXNnx 虽然频谱分析和虽然频谱分析和DFT运算很重要，但在很长一运算很重要，但在很长一段时间里，由于段时间里，由于DFT运算复杂，并没有得到真正运算复杂，并没有得到真正的运用，而频谱分析仍大多采用模拟信号滤波的的运用，而频谱分析仍大多采用模拟信号滤波的方法解决，直到方法解决，直到1965年

37、首次提出年首次提出DFT运算的一种运算的一种快速算法以后，情况才发生了根本变化，人们开快速算法以后，情况才发生了根本变化，人们开始认识到始认识到DFT运算的一些内在规律，从而很快地运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法发展和完善了一套高速有效的运算方法快速快速付里变换（付里变换（FFT）算法。算法。FFT的出现，使的出现，使DFT的的运算大大简化，运算大大简化，运算时间缩短一二个数量级运算时间缩短一二个数量级，使使DFT的运算在实际中得到广泛应用。的运算在实际中得到广泛应用。101, 1 , 0)()()(NnnkNNkwnxnxDFTkX)()()()()(10nk

38、NemnkNmeNnnkNmmnkNeewRnxIwInxRjwInxIwRnxRkX1.DFT的运算特点的运算特点完成全部完成全部DFT运算，需要运算，需要N2次复数相乘和次复数相乘和N（N-1）次复数相加次复数相加，在这些运算中，乘法比加法复杂，需要，在这些运算中，乘法比加法复杂，需要的运算时间多，尤其是复数相乘，每个复数相乘包括的运算时间多，尤其是复数相乘，每个复数相乘包括4个实数相乘和个实数相乘和2个实数相加，如下：个实数相加，如下： 从前面的分析看到，在从前面的分析看到，在DFT计算中，不论是计算中，不论是乘法和加法，运算量均与乘法和加法，运算量均与N2成正比。因此，成正比。因此，N

39、较大较大时，运算量十分可观。例，计算时，运算量十分可观。例，计算N=10点点的的DFT，需要需要100次复数相乘次复数相乘，而，而N=1024点点时，需要时，需要1048576（一百多万）次复数乘法（一百多万）次复数乘法，如果要求实时，如果要求实时处理，则要求有很高的计算速度才能完成上述计处理，则要求有很高的计算速度才能完成上述计算量。算量。 反变换反变换IDFT与与DFT的运算结构相同，只是多的运算结构相同，只是多乘一个常数乘一个常数1/N，所以二者的计算量相同。所以二者的计算量相同。考察考察DFT与与IDFT的运算发现，利用其中两个特性可减少运的运算发现，利用其中两个特性可减少运算量：算量

40、： 系数系数 是一个周期函数，它的周期性和对称性是一个周期函数，它的周期性和对称性可用来改进运算，提高计算效率。可用来改进运算，提高计算效率。 共轭偶对称性：共轭偶对称性： 半周期对称：半周期对称： 周期性：周期性： 利用这些周期性和对称性，把长度为利用这些周期性和对称性，把长度为N点的大点数的点的大点数的DFT运运算依次分解为若干个小点数的算依次分解为若干个小点数的DFT。nkNjnkNew2()()()*n N kk N nnknkNNNNwwwwkNNkNww)2/()()nkn kNnN kNNNwww1965年年,库利库利(cooley)和图基和图基(Tukey)首先提出首先提出FF

41、T算法算法.对于对于N点点DFT,仅需仅需(N/2)log2N 次复数次复数乘法运算乘法运算.例如例如N=1024=210 时，需要时，需要(1024/2)log2 210 =512*10=5120次。次。5120/1048576=4.88% ,速度提高速度提高20倍倍库利库利-图基算法图基算法 先从一个特殊情况开始，假定先从一个特殊情况开始，假定N是是2的整数次方：的整数次方： N=2M，M：正整数正整数 首先将序列首先将序列x（n）分解为两组，一组为偶数项，分解为两组，一组为偶数项，一组为奇数项：一组为奇数项： r=0,1，（，（N/2） -1 )() 12()()2(21rxrxrxrx

42、2011)()(NnNnnkNnkNwnxwnx偶数奇数10( )( )( )NnkNnX kDFT x nx n w12/0)12(12/02) 12()2(NrkrNNrrkNwrxwrx12/0212/02) 12()2(NrrkNNrkNrkNwrxwwrx因为因为 故故 其中其中nNnNjnNjnNweew222222 kHWkGWrxWWrxkXkNrkNNrkNNrrkN/)()( /)(NrrkNWrxkG rkNNrWrxkH/)(/2 1/2 12200( )(2 )(21)NNrkkrkNNNrrX kxr wwxrwH(k)、G(k)有有N/2个点个点:即即k=0,1,

43、N/2-1/222r NkrkNNww由W因子的对称性： (),0,1,122kNNNX kG kW H kk则：()2WNkkNNWW 又由因子的半周期对称性有： kHWkGWrxWWrxkXkNrkNNrkNNrrkN/)()(可以看出，可以看出，N点的点的DFT被分成了两个被分成了两个N/2点点DFT运算，运算，这两个这两个N/2点的点的DFT再合成得到原来的再合成得到原来的N点的点的DFT；而这其中的而这其中的G(k)和和H(k)可以继续分下去。可以继续分下去。这种按时间抽取算法是在输入序列分成越来越小的子这种按时间抽取算法是在输入序列分成越来越小的子序列上执行序列上执行DFT运算，最

44、后再合成为运算，最后再合成为点的点的DFT。 (),0,1,122kNNNX kG kW H kk ( ),0,1,12kNNX kG kW H kk将这种分解运算可归结为：将这种分解运算可归结为： bWabWa-1-1abWa bWa bWabWa bWa bWW蝶蝶形形运运算算 x x(0) (0) x x(2) (2) N/2N/2点点 x x(4) (4) DFTDFT x x(6) (6) x x(1) (1) x x(3) (3) N/2N/2点点 x x(5) (5) DFTDFT x x(7)(7) G(0)G(0)G(1)G(1)G(2)G(2)G(3)G(3)H(0)H(0

45、)H(1)H(1)H(2)H(2)H(3)H(3)WN0-1-1-1-1X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)WN1WN2WN3 (0)(0) (4) (4) (2) (2) (6) (6) (1) (1) (5) (5) (3) (3) (7) (7)WN0WN0WN0W0N-1-1-1-1-1-1-1-1-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)xxxxxxxx计算量计算量（复数乘法）（复数乘法） ：4x3=N/2log2NWWWWN0N1N2N3WN0WN2WN

46、0WN2（1）蝶形运算）蝶形运算（2）原位计算）原位计算 （3）序数重排）序数重排（4）蝶形类型随迭代次数成倍增加）蝶形类型随迭代次数成倍增加（1）蝶形运算）蝶形运算对于对于N=2M，总是可以总是可以通过通过M次分解最后成为次分解最后成为2点的点的DFT运算运算。这样构成从。这样构成从x(n)到到X(k)的的M级运算过程。级运算过程。每一级运算都由每一级运算都由N/2个蝶形运算构成个蝶形运算构成。因此。因此每一级运算每一级运算都需要都需要N/2次复乘和次复乘和N次复加次复加。这样，经过时间抽取后这样，经过时间抽取后M级运算总共需要的运算：级运算总共需要的运算： 复乘复乘 复加复加 而直接运算时

47、则与而直接运算时则与N2 成正比。成正比。例例N=2048，N2=4194304，(N/2)log2N=11264，N2 / (N/2)log2N=392.4。FFT显然要比直接法快得多。显然要比直接法快得多。NNMN2log22NNMN2log（2）原位计算）原位计算 当数据输入到存储器中以后，当数据输入到存储器中以后，每一级运算的结果每一级运算的结果仍然储存在同一组存储器中仍然储存在同一组存储器中，直到最后输出，中间，直到最后输出，中间无需其它存储器，这叫原位计算。无需其它存储器，这叫原位计算。 每一级运算均可在原位进行，这种原位运算结构每一级运算均可在原位进行，这种原位运算结构可节省存储

48、单元，降低设备成本，还可节省寻址的可节省存储单元，降低设备成本，还可节省寻址的时间。时间。11( )( )( ),0,1,pllNlx nxmW xnlM11( )( )( )pllNlx mxmW xn（3）蝶形类型随迭代次数成倍增加）蝶形类型随迭代次数成倍增加以以8点点FFT的三次迭代运算为例的三次迭代运算为例:第一级迭代，有一种类型的蝶形运算系数第一级迭代，有一种类型的蝶形运算系数W08，两个，两个数据点间隔为数据点间隔为1。第二级迭代，有二种类型的蝶形运算系数第二级迭代，有二种类型的蝶形运算系数W08、W28，运算的两个数据点间隔为运算的两个数据点间隔为2。第三级迭代，有四类蝶形运算系

49、数第三级迭代，有四类蝶形运算系数W08、W18、W28、W38，参加运算的两个数据点间隔为参加运算的两个数据点间隔为4。 结论：每迭代一次，蝶形类型增加一倍，数据点间结论：每迭代一次，蝶形类型增加一倍，数据点间隔也增大一倍。隔也增大一倍。每一级的取数间隔和蝶形类型种类均为每一级的取数间隔和蝶形类型种类均为2i-1,i =1,2, M （4）序数重排）序数重排 对按时间抽取对按时间抽取FFT的原位运算结构，当运算完毕时的原位运算结构，当运算完毕时，正好，正好顺序输出：顺序输出： X（0）,X（1）,X（2）,X（7）,但原位运算的输入但原位运算的输入 x（n）却不能按这种自然顺序存入却不能按这种

50、自然顺序存入存储单元中存储单元中，而是按，而是按x(0)，x(4)，x(2)，x(6)，x(7)的顺序存入存储单元，这种顺序看起来相当杂乱，然的顺序存入存储单元，这种顺序看起来相当杂乱，然而它也是有规律的。而它也是有规律的。 当用二进制表示这个顺序时，它正好是当用二进制表示这个顺序时，它正好是“码位倒置码位倒置”的顺序。的顺序。 例如，原来的自然顺序应是例如，原来的自然顺序应是 x(1)的地方，现在放着的地方，现在放着 x(4)，用二进制码表示这一规律时，用二进制码表示这一规律时， 则是在则是在 x（0 0 1）处放着处放着 x（1 0 0） x（0 1 1）处放着处放着 x（1 1 0）码位

51、倒置顺序码位倒置顺序自然顺序自然顺序二进码表示二进码表示码位倒置码位倒置倒置后顺序倒置后顺序0000000010011004201001023011110641000011510110156110011371111117 在实际运算中，一般直接将输入数据在实际运算中，一般直接将输入数据 x（n）按码位倒置的按码位倒置的顺序排好输入很不方便，总是顺序排好输入很不方便，总是先按自然顺序输入存储单元先按自然顺序输入存储单元，然后再然后再通过变址运算将自然顺序的存储转换成码位倒置顺序通过变址运算将自然顺序的存储转换成码位倒置顺序的存储的存储，然后进行，然后进行FFT的原位计算。目前有许多通用的原位计算

52、。目前有许多通用DSP芯芯片支持这种码位倒置的寻址功能。片支持这种码位倒置的寻址功能。 周周 期期 卷卷 积积 1.相同点相同点 (1)进行原位运算；进行原位运算； (2)运算量相同运算量相同,均为（均为（N/2)N/2) LogLog2 2N N次复乘次复乘,N N LogLog2 2N N次复加。次复加。 2.不同点不同点 (1)DIT输入为倒位序输入为倒位序, ,输出为自然顺序；输出为自然顺序； DIF正好与此相反。但正好与此相反。但DIT也有输入为自然顺序也有输入为自然顺序, ,输出为倒输出为倒位序的情况。位序的情况。DIFDIF与与DITDIT的异同的异同桑德桑德-图基算法图基算法r

53、NmmmWjXkXjX)()()(11rNmmmWjXkXkX)()()(11)(1kXm)(1jXmrNW1(2)(2)蝶形运算不同蝶形运算不同a.a.(DIT)(DIT)用矩阵表示：用矩阵表示：)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11rNmmmWjXkXjX)()()(11)()()(11jXkXkXmmm)(1kXm)(1jXmrNW1b.b.(DIF(DIF) )用矩阵表示：用矩阵表示：)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11(3)两种蝶形运算的关系两种蝶形运算的关系：互为转置（矩阵）；互为转置（矩阵）；将流图的所有支路方向都反向将流图的所有

54、支路方向都反向, ,交换输入和输交换输入和输出，即可得到另一种蝶形。出，即可得到另一种蝶形。 a.a.(DIT)(DIT)b.b.(DFT)(DFT)rNWrNW1111rNWrNW 如如N不能人为确定不能人为确定 , N的数值也不是以的数值也不是以2为基数的为基数的整数次方整数次方,处理方法有两种处理方法有两种: 补零补零:将将x(n)补零补零 , 使使N=2M. 例如例如N=30,补上补上x(30)=x(31)=0两点两点,使使N=32=25,这这样可直接采用以样可直接采用以2为基数为基数M=5的的FFT程序。程序。 若要准确度若要准确度N点点DFT，在，在N 为复合数时，可分解为复合数时

55、，可分解为两个整数为两个整数p与与q的乘积的乘积.类似前面基二算法类似前面基二算法 ，FFT的基本思想是将的基本思想是将DFT的运的运算尽量分小算尽量分小,因此因此,在在N=pq情况下情况下,也希望将也希望将N点的点的DFT分解为分解为p个个q点点DFT或或q个个p点点DFT,以减少计算量。以减少计算量。问题的提出：问题的提出： 不需要计算整个单位圆上不需要计算整个单位圆上z变换的取样变换的取样，如对，如对于窄带信号，只需要对信号所在的一段频带进行分于窄带信号，只需要对信号所在的一段频带进行分析，这时析，这时,希望频谱的采样集中在这一频带内，以获希望频谱的采样集中在这一频带内，以获得较高的分辨

56、率，而频带以外的部分可不考虑。得较高的分辨率，而频带以外的部分可不考虑。 对非单位圆上的对非单位圆上的z变换取样感兴趣变换取样感兴趣，例如，例如语音语音信号处理中，需要知道信号处理中，需要知道z变换的极点所在频率变换的极点所在频率，如，如极点位置离单位圆较远，则其单位圆上的频谱就很极点位置离单位圆较远，则其单位圆上的频谱就很平滑平滑，如果采样不是沿单位圆而是沿一条接近这些，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在频率上的将出现明极点的弧线进行，则在极点所在频率上的将出现明显的尖峰，由此可较准确地测定极点频率。显的尖峰，由此可较准确地测定极点频率。 要求能有效地计算当要

57、求能有效地计算当N是素数时序列的是素数时序列的DFT螺旋线采样螺旋线采样是一种适合于这种需要的变换，是一种适合于这种需要的变换，且可以采用且可以采用FFT来快速计算。来快速计算。 已知已知x（n），），0nN-1 令令zk=AW-k ，k=0，M-1 M ：采样点数采样点数 A、W：任意复数任意复数其中：其中：A0表示起始取样点的半径长度，通常表示起始取样点的半径长度，通常A010表示起始取样点表示起始取样点z0的相角的相角0表示两相邻点之间的等分角表示两相邻点之间的等分角W0螺旋线的伸展率，螺旋线的伸展率，W01则线内缩则线内缩（反时针）（反时针）W0=1则表示半径为则表示半径为A0的一段圆

58、弧，若的一段圆弧，若A0=1，这段圆弧则是单位这段圆弧则是单位圆的一部分。圆的一部分。00jojoeWWeAA计算计算z变换在采样点变换在采样点 zk 的的值值 k=0,1, ,M-1计算量：计算量： NM 次复乘和（次复乘和（N-1）M次复加，当次复加，当N及及M较大时，计算量迅速增加。较大时，计算量迅速增加。将将zk的表示式代入的表示式代入:10)()(NnnkkznxzX其中其中 的的nk用以下用以下Bluestein式来替换式来替换: 10)()(NnnknkWAnxzX)(21222nknknk2222)(1022)()(nkNnnnkkWWAnxWzX则则:222)(,)()(2n

59、nnWnhWAnxng定义：定义：1, 1 , 0)()()()()(210222MkkhkgWnkhngWzXkNnkk则则: 上式说明，如对信号上式说明，如对信号x（n）先进行一次加权处理，加先进行一次加权处理，加权系数为权系数为 ，然后通过一个单位脉冲响应为，然后通过一个单位脉冲响应为h（n）的线性系统，最后，对该系统的前的线性系统，最后，对该系统的前M点输出再作一次点输出再作一次 的加权的加权 ，就可得到全部，就可得到全部M点螺旋线采样值点螺旋线采样值。 22nnWA22kWx22)(nWnhxx(n)g(n)X(zk)22nnWA22kW1, 1 , 0)()()()()(21022

60、2MkkhkgWnkhngWzXkNnkk10)()(NnnkkznxzX即即Chirp -z变换转换变换转换为两个序列的为两个序列的线性卷积线性卷积g(k)*h(k),可用循环（圆周）卷积通过可用循环（圆周）卷积通过FFT来实现。来实现。(1) 求h（n）对应的主值序列 (2) 用FFT求 的傅里叶变换: H(r)=FFT , L点(3) 对x（n）加权并补零1110)(2/)(2/22LnNLWMnWnhnLn)(nh)(nh1010)()(2/2LnNNnWAnxngnn(4)G（r）=FFT g（n） , L点(5)Y（r）=G（r）H（r） , L点(6)y（k）=IFFTY（r）