第九章 离散傅里叶变换

1、第九章第九章 离散傅里叶变换离散傅里叶变换 主要内容主要内容 n离散傅里叶级数（离散傅里叶级数（DFS） n离散傅里叶变换（离散傅里叶变换（DFT） n快速傅里叶变换（快速傅里叶变换（FFT） 一一.DFT是重要的变换是重要的变换 1.分析有限长序列的有用工具。分析有限长序列的有用工具。 2.在信号处理的理论上有重要意义。在信号处理的理论上有重要意义。 3.在运算方法上起核心作用，谱分析、在运算方法上起核心作用，谱分析、 卷积、相关都可以通卷积、相关都可以通DFT在计算机上在计算机上 实现。实现。 9-1 9-1引引 言言 二二.DFT是现代信号处理桥梁是现代信号处理桥梁 DFT要解决两个问题

2、：要解决两个问题： 一是一是离散离散与与量化量化， 二是二是快速运算。快速运算。 信号处理信号处理DFT(FFT) 傅氏变换傅氏变换离散量化离散量化 ()( ) jt X jx t edt 1 ( )() 2 j t x tX jed FT 傅立叶变换傅立叶变换 t )(tx 0 0 )( jX 时域：时域：连续、连续、非非周期周期，频域：，频域：非周期、连非周期、连续续 9.2 傅里叶变换的几种可能形式傅里叶变换的几种可能形式 FS 傅立叶级数傅立叶级数 时域：时域：连续、周期连续、周期，频域：，频域：非周期非周期、离散、离散 0 t 0 T )(tx - - 0 )( 1 jkX 0 0

3、2 T 1 1 1 1 1 1 1 1 1 1 ()( ) jj n n X ex n e 1 ( )() 2 jj n x nX eed DTFT x(nT) T -T 0T2T t )( Tjj eXeX 或 0 T s 2 - 时域：时域：离散、非周期离散、非周期 频域：频域：周期周期、连续、连续 时域时域 频域频域 v连续连续非周期非周期 非周期非周期连续连续 傅里叶变换傅里叶变换 v连续连续周期周期 非周期非周期离散离散 傅里叶级数傅里叶级数 v离散离散非周期非周期 周期周期连续连续 序列的傅里叶变换序列的傅里叶变换 v离散周期离散周期 周期离散周期离散 离散傅里叶级数离散傅里叶级数

4、 傅里叶变换形式傅里叶变换形式 傅里叶变换的傅里叶变换的4种形式种形式 但是，前三种傅里叶变换对都不适于计但是，前三种傅里叶变换对都不适于计 算机上运算，因为它们至少在一个域（时域算机上运算，因为它们至少在一个域（时域 或频域）中函数是连续的。或频域）中函数是连续的。 因此，我们感兴趣的是因此，我们感兴趣的是时域和频域都是时域和频域都是 离散离散的情况。的情况。 时域：时域：离散、周期离散、周期，频域：频域：周期、离散周期、离散 9.3 DFS与与DFT 连续周期信号连续周期信号: 抽样抽样（抽样周期为（抽样周期为T，一个，一个 周期周期 内抽样内抽样N个点）个点） 得周期序列得周期序列 一、

5、离散傅里叶级数 k nk N j p k nT T jk ppp ekX ekXnxnTx 2 )( )()()( 1 N T NT T T T NTT T 22 2 , 2 1 11 1 1 1 )(kX p 是周期为是周期为N的周期序列的周期序列 k tjk pp ekXtx 1 )()( 1 1 T 1、DFS的引入的引入 将将 两端乘两端乘 再从再从 n=0到到N-1求和，求和， nr N j e 2 1 0 2 )( N n nr N j p enx 1 0 1 0 )( 2 )( N n N k nrk N j p ekX 则：则： )( )( 1 0 )( 2 1 0 kNX e

6、kX p N n nrk N j N k p )(kX p 2、 的求取的求取 1 0 2 N k nk N j pp ekXnx kr e e krN e rk N j Nrk N j N n nrk N j ，0 1 1 , )( 2 )( 2 1 0 )( 2 1 0 2 1 0 2 )()( )( 1 )( N k kn N j pp N n kn N j pp ekXnx enx N kX 3、将定标因子、将定标因子1/N移到移到 表达式中。表达式中。)(nx p 1 0 2 1 0 2 )( 1 )( )()( N k kn N j pp N n kn N j pp ekX N n

7、x enxkX 保持与Z变换相同的形式？ 设设 则离散傅氏级数表示为：则离散傅氏级数表示为： N j N eW 2 1 0 1 0 2 ( 1 ( 1 )()( N k nk Np N k nk N j p pp WkX N ekX N kXIDFSnx 正变换：正变换： 反变换：反变换： 4、离散傅氏级数的表示：、离散傅氏级数的表示： 1 0 1 0 2 )()( )( N k nk Np N k nk N j p pp Wnxenx nIDFSxkX DFSDFS的图示说明的图示说明 n 0 N-N . nx p kX p k 0 N-N 5、 函数的几个性质：函数的几个性质： N W *

8、 () nn NN WW 1.共轭对称性： 2.周期性： nn iN NN WW i为整数 3.可约性：/ inn NN i WW inn NiN WW 4.正交性： 11 *() 00 1, 11 () 0, NN nkmkn m k NNN nn nmiN WWW nmiNNN i为整数 二、二、 离散傅里叶变换离散傅里叶变换 n在进行在进行DFSDFS分析时，时域、频域序列都是无限分析时，时域、频域序列都是无限 长的周期序列长的周期序列 n周期序列实际上只有有限个序列值有意义周期序列实际上只有有限个序列值有意义 n长度为长度为N N的有限长序列可以看成周期为的有限长序列可以看成周期为N

9、N的周期的周期 序列的一个周期（主值序列）序列的一个周期（主值序列） n借助借助DFSDFS变换对，取时域、频域的变换对，取时域、频域的主值序列主值序列可可 以得到一个新的变换以得到一个新的变换DFTDFT，即有限长序列的，即有限长序列的 离散傅里叶变换离散傅里叶变换 另一种表示 Np nxnx)()( 其中其中 表示对表示对 n 取模取模N 运算运算(或模或模 N的余数的余数)。 N n)( )()()( 1 nxnxnx pNp 则则 ImNnnnmNnn N , 10)( 111 若若 1 1、周期序列与主值序列的关系、周期序列与主值序列的关系 )()()(nRnxnx Np r p r

10、Nnxnx)()( 举例：举例：设周期为设周期为 N=6N=6。则有周期序列和求余运算：。则有周期序列和求余运算： 这是因为：这是因为： (19=3(19=36+1)6+1) 同理同理 这是因为：这是因为： (-2=-1(-2=-16+4)6+4) ) 1 ()19( pp xx ) 4() 2( pp xx 同样：同样：X(k)也是一个也是一个N点的有限长序列点的有限长序列 )()()( )( kRkXkX kXkX Np Np 1 0 1 0 2 )()()( N n kn N N n kn N j WnxenxnxDFTkX 1 0 1 0 2 )( 1 )( 1 )( N k kn N

11、 N k kn N j WkX N ekX N kXIDFTnx 1, 0 :Nk 1, 0 :Nn 2 j N N We 2 2、DFTDFT的定义的定义 3 3、DFTDFT的矩阵形式的矩阵形式 )()(nxWnxDFTkX nk N nk N WkXkXIDFTnx )()( 1 . 1 0 NX X X kX 1 . 1 0 Nx x x nx 11110 11110 000 . . . . NN N N NN N NNN NNN nk N WWW WWW WWW W 11110 11110 000 . . . . NN N N NN N NNN NNN nk N WWW WWW WW

12、W W 其中：其中： 4、离散傅里叶变换、离散傅里叶变换(DFT)的特点的特点 n序列序列x(n)在时域是有限长的在时域是有限长的(长度为长度为N)， 它的离散傅里叶变换它的离散傅里叶变换X(k)也是离散、有限也是离散、有限 长的长的(长度也为长度也为N)。 nn为时域变量，为时域变量，k为频域变量。为频域变量。 n离散傅里叶变换与离散傅里叶级数没有本离散傅里叶变换与离散傅里叶级数没有本 质区别，质区别，DFT实际上是离散傅里叶级数的实际上是离散傅里叶级数的 主值，主值，DFT也隐含有周期性。也隐含有周期性。 n离散傅里叶变换离散傅里叶变换(DFT)具有唯一性。具有唯一性。 例例1 1、计算、

13、计算 (N=12)(N=12)的的N N点点DFT.DFT. 解：解： )( 6 cos)(nRnnx N knjnjnj n N n kn N eeeWnxkX 12 2 12 2 12 2 11 0 1 0 2 1 )()( )( 2 1 )11( 12 2 11 0 )1( 12 2 nkj n nkj ee )11( 12 2 )11(2 )1( 12 2 )1(2 1 1 2 1 1 1 2 1 kj kj kj kj e e e e k k 其它,0 11, 1,6 ) 1(110Nk )( 6 cos)( 12 nR n nx N=12 0 12311 1 -1 n k k kX

14、 其它, 0 11, 1, 6 )( k 01 23 11 6 9.4 离散傅里叶变换的性质离散傅里叶变换的性质 1、线性、线性 , a b为任意常数 这里，序列长度及这里，序列长度及DFT点数均为点数均为N 若不等，分别为若不等，分别为N1，N2，则需补零使两序列长度，则需补零使两序列长度 相等，均为相等，均为N，且，且 12 max,NN N 若若 则则 )()()()(nyDFTkYnxDFTkX )()()()(kbYkaXnbynaxDFT )()()(kXWnRmnx mk NNN 周期 延拓 移位取主值 序列 v 有限长序列的圆周移位导致频谱线性相移，而有限长序列的圆周移位导致频

15、谱线性相移，而 对频谱幅度无影响。对频谱幅度无影响。 (1)(1)圆周移位圆周移位 2、时移特性、时移特性 (2)(2)时移特性时移特性 )()(nRmnx NN nx nx p mnx p q从图中两虚线之间的从图中两虚线之间的 主值序列的移位情况可主值序列的移位情况可 以看出：以看出： q当主值序列左移当主值序列左移m m个个 样本时，从右边会同时样本时，从右边会同时 移进移进m m个样本个样本 q好像是刚向左边移出好像是刚向左边移出 的那些样本又从右边循的那些样本又从右边循 环移了进来环移了进来 q因此取名因此取名“循环移循环移 位位”。 q显然，循环移位不同显然，循环移位不同 于线性移

16、位于线性移位 3 3、频移特性、频移特性 )()()(kRlkXnxW NN nl N v时域序列的调制等效于频域的圆周移位时域序列的调制等效于频域的圆周移位 21 ( )cos()()( ) 2 NNN nl DFT x nXklXklRk N 21 ( )sin()()( ) 2 NNN nl DFT x nX klX klR k Nj egeg： 4、时域圆周卷积、时域圆周卷积 设设 则则 )()( )( )( )( 1 0 1 0 nhnx mRmnxmh mRmnhmx kYIDFTny N N m N N N m N kHnhkXnx)(,)( (1)定理 kYnykHkXkY)(

17、, 圆周卷积步骤： 1）翻褶 2）圆周移位 3）相乘 4）相加 (2) 圆周卷积的计算 Eg1. N-10 n )(nx N-10 n )(nh 7),()( )(,)( Nnhnxny nhnx 其中求 如下图所示， )(0 )( mRmh mh NN p 0 m )(1mRmh NN 0 m )(2mRmh NN 0 m )(3mRmh NN 0 m 0 2 33 2 1 1 N-1 n )()()(nhnxny 最后结果： 1）.线性卷积线性卷积 的长度为 的长度为 )(nx) 10(NnN )(nh) 10(MnM m N m l mnhmxmnhmxny 1 0 )()()()()(

18、 )20( 1MNnMNnyl的长度为 2）圆周卷积）圆周卷积 ),max(:MN长度为 （3）线性卷积与圆周卷积线性卷积与圆周卷积的关系的关系 1 , MNLMN nhnxnhnx 3) 关系关系 补补0 加长加长 )(*)()()( nhnxnhnx x(n)的的N点点DFT是是 x(n)的的z变换在单位圆上的变换在单位圆上的N点等间隔抽样；点等间隔抽样； x(n)的的DTFT在区间在区间0,2上的上的N点等间隔抽样。点等间隔抽样。 1 0 ( )( ) N n n X zx n z 1 0 ( )( ) N nk N n X kx n W 1 0 ()( ) N jj n n X ex

19、n e 2 () j k N X e 2 ( ) jk k N N z We X z DFTz与序列的DTFT和 变换的关系： 9-5 一.DFT的计算工作量 两者的差别仅在指数的符号和因子两者的差别仅在指数的符号和因子1/N. . 1 0 1, 1 , 0 ,)( 1 )( N k nk N NnWkX N nx 1, 1 , 0 ,)()( 1 0 NkWnxkX N n nk N 9-6 FFT的应用 DFT与与IDFT运算特点运算特点 复数乘法复数乘法复数加法复数加法 一个一个X(k)NN 1 N个个X(k) (N点点DFT) N 2N (N 1) 1 0 ( ) N nk N n x

20、 n W )(kX 当当N N很大时很大时, ,运算量将是惊人的运算量将是惊人的, ,如如N=1024,N=1024, 要完成要完成1048576 1048576 次次( (一百多万次一百多万次) )运算运算. .这样这样, , 难以做到实时处理难以做到实时处理. . 二二.改进的途径改进的途径 1. 的对称性和周期性 . ),1( 1 ),1( ) 2/( 2/ )(2)()( 2 k N Nk N j N N N nkNn N Nk N nk N knN N kNn N WW eWW eWWWWW N 对称性对称性: : 周期性周期性: : nkmnk NmN WW可约性 / / nknk

21、 m NN m WW nk N W 2、N点点DFT 2个个N/2点点DFT 利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利(cooley)和图基 (Tukey)首先提出FFT算法.对于N点DFT,仅需 (N/2)log2N 次复数乘法运算.例如N=1024=210 时， 需要(1024/2)log2 210 =512*10=5120次。 5120/1048576=4.88% ,速度提高20倍 三、基三、基2FFT2FFT算法的思路算法的思路 n把一个序列分为长度减半的把一个序列分为长度减半的偶偶序列序列 和和奇奇序列序列, 原序列

22、的原序列的DFT就由这两个就由这两个 N/2序列求得序列求得. n进一步把进一步把N/2序列分解成两个序列分解成两个N/4 序列序列, 一直分解到一直分解到2点序列点序列. Eg. N=8的的FFT 1, 3, 5, 70, 2, 4, 6 0, 42, 6 1, 53, 7 x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) 第一级 第二级 第三级 四.算法原理(基2FFT) 1.先将 按n的奇偶分为两组N/2点 作DFT,设N=2M ,不足时,可补些零。 n n为偶数时为偶数时: n

23、 n为奇数时为奇数时: 1, 1 , 0 ),() 12( 1, 1 , 0 ),()2( 2 2 N N rrhrx rrgrx )(nx 因此因此 2 2 2 )/(22 2 N N N WeeW jj N 1 0 2 1 0 2 1 0 )12( 1 0 2 1 0 22 22 )()( ) 12()2( )()( NN NN r rk N k N r rk N r kr N r rk N N n nk N WrhWWrg WrxWrx WnxkX )()()()()( 1 0 1 0 2 2 2 2 kHWkGWrhWWrgkX k N r rkk N r rk N N N N 其中其

24、中, , 2.两点结论两点结论: : (1) G(k),H (k)均为均为N/2点的点的DFT。 (2) X(k)=G(k)+W H (k)只能确定出只能确定出 X(k)的的k= 0,1,(N/2-1)时的值； 即即前前N/2N/2点点的结果。的结果。 k N 1 0 1 0 1 0 1 0 2 2 2 2 2 2 2 2 ) 12()()( )2()()( N N N N N N N N r rk r rk r rk r rk WrxWrhkH WrxWrgkG 同理 , 3.X(k)3.X(k)后后N/2N/2个点的确定个点的确定 )()()() 2 ( 1 0 )( 1 0 2 2 2

25、2 2 kGWrgWrgk N G N N N N N r rk kr r rk kr N N N WW 2 2 2 )( )() 2 (kHk N H ) 2 () 2 () 2 ( 2 N kHW N kG N kX N k N 1, 1 , 0 ),()( 2 N k N kkHWkG k N k NN k N W WWW NN 22 )( *X(k)的后的后N/2N/2个点，也完全由个点，也完全由G(k), , H(k)确定确定 * *N N点的点的DFTDFT可由两个可由两个N/2N/2点的点的DFTDFT来计算。来计算。 实现上式运算的流图称作蝶形运算 k= 0,1,(N/2-1)

26、 4.4.蝶形运算蝶形运算 （N/2个蝶形个蝶形) 1 1 -1-1 )( 1 kX )( 2 kX k N W 由由X1(k)、X 2(k)表示表示X(k)的运算是一种特殊的运算的运算是一种特殊的运算-碟形运算碟形运算 )()() 2 ( )()()( kHWkG N kX kHWkGkX k N k N )()()(kHWkGkX k N )()() 2 (kHWkGk N X k N k= 0,1,(N/2-1) )(kH )(kG k N W 例例 N=8 时的时的FFT: );6(),4(),2(),0(xxxx );6()3( ),4()2( ),2()1( ),0()0( xg

27、xg xg xg );7()3( ),5()2( ),3()1( ),1()0( xh xh xh xh 1 2 ,.1 , 0 )2()( N r rxrg 1、 2个N/2点DFT （1）将 分成奇偶序列，并计算X(k) )(nx 1 2 ,.1 , 0 ) 12 ()( N r rxrh 3 , 2 , 1 , 0 ) 12()()( 3 0 4 3 0 422 k WrxWrxkX r rk r rk 3 , 2 , 1 , 0),()() 4( )()()( kkHWkGkX kHWkGkX k N k N 3 , 2 , 1 , 0 ) 12()()( 3 0 4 3 0 4 k

28、WrxWrhkH r rk r rk 3 , 2 , 1 , 0 )2()()( 3 0 4 3 0 4 k WrxWrgkG r rk r rk 其中其中 g(0)=x(0) g(1)=x(2) N/2点 g(2)=x(4) DFT g(3)=x(6) h(0)=x(1) h(1)=x(3) N/2点 h(2)=x(5) DFT h(3)=x(7) 1 2 G(0)G(0) G(1)G(1) G(2)G(2) G(3)G(3) H(0)H(0) H(1)H(1) H(2)H(2) H(3)H(3) W N 2 W N 1 WN 0 W N 3 -1 -1 -1 -1 X(0)X(0) X(1

29、)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) （2 2）对）对X X (k)(k)和和X X (k)(k)进行蝶形运算如下图所进行蝶形运算如下图所 示示: : 2 2、 4 4个个N/4N/4点点DFTDFT 1, 1 , 0 )2()( 4 1 N l lxlp （1）将 分成奇偶序列，并进行DFT )(ng )4()2()1( )0()0()0( xgp xgp 1, 1 , 0 ) 12()( 4 1 N l lxlq )6()3()1( )2()1()0( xgq xgq 1, 1 , 0 4 N k )()(

30、)()() 4 ( 2 2 kQWkP kQWkPk N G k N k N 1, 1 , 0 4 N k ) 4() 0 () 1 () 0 () 1 ( ) 4() 0 () 1 () 0 () 0 ( 01 2 00 2 xWxpWpP xWxpWpP N N )6()2() 1 ()0() 1 ( )6()2() 1 ()0()0( 01 2 00 2 xWxqWqQ xWxqWqQ N N 其中其中 )()( )()()( 2 2 kQWkP kQWkPkG k N k N 1, 1 , 0 )2()( 4 N l lhly （2）将 分成奇偶序列,并进行DFT)( 2 nx )5(

31、)2()1( )1()0()0( xhy xhy 1, 1 , 0 ) 12()( 4 N l lhlz )7()3()1( )3()1()0( xhz xhz 进行碟形运算，得：、由)()( 65 kXkX 1 4 , 1 , 0k, Z(k)WY(k) Z(k)W(k) Yk) 4 N ( H 2k 2N k N/2 N 1 4 , 1 , 0k, Z(k)WY(k) Z(k)W(k) YH(k) 2k 2N k N/2 N )5() 1 () 1 ()0() 1 ( )5() 1 () 1 ()0()0( 01 2 00 2 xWxyWyY xWxyWyY N N )7() 3() 1

32、()0() 1 ( )7() 3() 1 ()0()0( 01 2 00 2 xWxzWzZ xWxzWzZ N N WN 0 WN 0 WN 0 W 0 N -1 -1 -1 -1 P(0) P(1) Q(0) Q(1) Y(0) Y(1) Z(0) Z(1) WN 0 WN 2 WN 0 WN 2 -1 -1 -1 -1 G(0) G(1) G(2) G(3) H(0) H(1) H(2) H(3) W W W W N 0 N 1 N 2 N 3 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) x x x x 8 8点点DFTDFT的

33、的FFTFFT的运算流图如下的运算流图如下 0 x 4x 6x 2x 1x 5x 3x 7x 1.1.蝶形运算蝶形运算 蝶形单元蝶形单元 蝶距蝶距:2:2m-1 m-1 （第m级蝶形运算） 五五. FFT. FFT算法的特点算法的特点 输入数据、中间运算结果和最后输出均用同一存储器。输入数据、中间运算结果和最后输出均用同一存储器。 2.原位运算原位运算 WN 0 WN 0 WN 0 W 0 N -1 -1 -1 -1 P(0) P(1) Q(0) Q(1) Y(0) Y(1) Z(0) Z(1) WN 0 WN 2 WN 0 WN 2 -1 -1 -1 -1 G(0) G(1) G(2) G(

34、3) H(0) H(1) H(2) H(3) W W W W N 0 N 1 N 2 N 3 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) x x x x 0 x 4x 6x 2x 1x 5x 3x 7x 3 倒位序运算 FFT运算流程中，输出X(k)按正常顺序排 列在存储单元,而输入是按顺序: 这种顺序称作倒位序,即二进制数 倒位。 ）；）；7 (),3 (),5 (),1 (6 (),2 (),4 (),0 (xxxxxxxx 是由奇偶分组造成的是由奇偶分组造成的, ,以以N=8N=8为例说明如下为例说明如下: : ),( 012

35、nnnx 倒位序的实现 输入序列先按自然顺序存入存储输入序列先按自然顺序存入存储 单元单元, ,然后经变址运算来实现然后经变址运算来实现倒位序排倒位序排 列列。 设输入设输入序列的序号为序列的序号为n, ,二进制为二进制为 (n(n2 2 n n1 1 n n0 0 ) )2 2 ,倒位序倒位序顺序用顺序用 表示表示, ,其其 倒位序倒位序 二进制为二进制为(n(n0 0 n n1 1 n n2 2 ) )2 2 。 n 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1

36、 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 自然顺序n n 二进制n n n n n n 倒位序二进制n n n n n n 倒位顺序n n 2 1 0 0 1 2 码位倒序（码位倒序（N=8） 码位倒序（码位倒序（N=16） A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) 倒位序的变址处理方法倒位序的变址处理方法 存储单元 自然顺序 变址 倒位序 蝶距为1 蝶距为2

37、 WN 0 WN 0 WN 0 W 0 N -1 -1 -1 -1 P(0) P(1) Q(0) Q(1) Y(0) Y(1) Z(0) Z(1) WN 0 WN 2 WN 0 WN 2 -1 -1 -1 -1 G(0) G(1) G(2) G(3) H(0) H(1) H(2) H(3) W W W W N 0 N 1 N 2 N 3 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) x x x x 0 x 4x 6x 2x 1x 5x 3x 7x 4.WNr 的分布规律 第1级： 第2级： 第i级: 第L级: 0 N W 40 , N

38、NN WW iiii N N N N N NN WWWW 2122220 ,., ， 12210 ,., N NNNN WWWW， 5.存储单元 存输入序列存输入序列 (n),n=0,1, ,N-1, 计计N 个单元个单元; 存放系数存放系数 , r=0,1, ,N/2-1, 需需N/2个存储单元；个存储单元； 共计共计(N+N/2)个存储单元。个存储单元。 x r N W 三、三、FFT运算量运算量 1 N=2 时，共有时，共有L=log N级蝶形运算；每一级蝶形运算；每一 级有级有N/2个蝶形单元。个蝶形单元。 2每一级有每一级有N个输入中间数据，且每级只用到本个输入中间数据，且每级只用到

39、本 级的输入中间数据，适合于迭代运算。级的输入中间数据，适合于迭代运算。 3计算量：计算量： 每级每级N/2次复乘法，次复乘法，N次复加。（每蝶形只乘次复加。（每蝶形只乘 一次，加减各一次）。共有一次，加减各一次）。共有L*N/2=N/2log2N 次复乘法；复加法次复乘法；复加法L*N=Nlog2N 次。与直接次。与直接 DFT定义式运算量相比定义式运算量相比(倍数倍数) N2/(Nlog2N) 。当。当 N大时，此倍数很大。大时，此倍数很大。 2 L 9-7 DFT的应用 一、利用一、利用FFT计算线卷积计算线卷积 1、 时域时域 圆周圆周 卷积卷积 定理定理 设设 则则 )()( )(

40、)( )( 1 0 1 0 nhnx nRmnxmh nRmnhmx kYIDFTny N N m N N N m N kHnhkXnx)(,)( kYnykHkXkY)(, 1 , MNLMN nhnxnhnx 2、圆周卷积与线卷积的关系、圆周卷积与线卷积的关系 补补0 加长加长 )(*)()()( nhnxnhnx 3、方法 N点FFT N点FFT IFFT x x(n) h(n) y(n) m N LMN 2 1 补 “0” m N LMN 2 1 补 “0” M L n x nh kH kX kY 连续连续时间时间 非周期信号非周期信号 deXtx dtetxX tj tj 2 1 )( 1、时域的离散化与有限化、时域的离散化与有限化 s NTTTt 11 ),0(),(: n s TdtnTt, 二、利用二、利用DFT逼近连续时间信号的频谱逼近连续时间信号的频谱 1 0 )( )( )()( N n nTj ss n nTj s tj s s enTxT enTx dtetxX 2、频域的有限化与离散化、频域的有限化与离散化 sss s TN2, ),0(),(: 1 )()(nxDFTTkX s )( 1 )(kXIDFT T nx