大连理工大学信号8离散傅里叶变换与快速傅里叶变换

1、2021-11-11大连理工大学1Part III数字信号处理数字信号处理大连理工大学硕士研究生校管课程大连理工大学硕士研究生校管课程信号处理与数据分析信号处理与数据分析电子信息与电气工程学部电子信息与电气工程学部邱天爽邱天爽2013年年11月月2021-11-11大连理工大学2第第8章章离散傅里叶变换与快速傅里叶离散傅里叶变换与快速傅里叶变换变换大连理工大学硕士研究生校管课程大连理工大学硕士研究生校管课程信号处理与信号处理与数据分析数据分析电子信息与电气工程学部电子信息与电气工程学部邱天爽邱天爽2013年年11月月 内容概要内容概要 8.1 8.1 离散傅里叶变换（离散傅里叶变换（DFTDF

2、T） 8.2 8.2 离散傅里叶变换的性质离散傅里叶变换的性质 8.3 8.3 与与DFTDFT相关的几个问题相关的几个问题 8.4 8.4 快速傅里叶变换（快速傅里叶变换（FFTFFT） 8.5 FFT8.5 FFT的应用的应用 推荐教材：程佩青，数字信号处理教程（第三推荐教材：程佩青，数字信号处理教程（第三版），清华大学出版社，版），清华大学出版社，201120112021-11-11大连理工大学48.1 离散傅里叶变换（离散傅里叶变换（DFTDFT）2021-11-11大连理工大学5 0. 为什么要学习离散傅里叶变换（为什么要学习离散傅里叶变换（DFT）？）？数字信号处理，要求信号是数字

3、化的，也希望频谱或频率响应也是数字化的。实际应用中的信号总是有限时宽的、且为非周期的。希望信号频谱也是有限频宽、且非周期的。考察前面介绍的4种傅里叶级数或傅里叶变换，没有任何一种能够满足这种需求。因此，发展新的傅里叶变换方法以适应数字信号处理实际应用的要求称为数字信号处理理论的一个重要任务。这就为DFT的发展提供了需求和动力2021-11-11大连理工大学6 1. 已学过的几种傅里叶级数和傅里叶变换已学过的几种傅里叶级数和傅里叶变换 （1）FS： 连续、周期连续、周期 ； 离散、非周期；离散、非周期； （2）DFS： 离散、周期；离散、周期； 离散、周期；离散、周期； ( )x tka x n

4、ka002jj2jj11( )ed( )ed( )eektktTkTTktktTkkkkax ttx ttTTx taa002jj2jj11( )e( )e( )eeknknNknNnNknknNkkkNkNax nx nNNx naa2021-11-11大连理工大学7 （3）FT： 连续、非周期连续、非周期 ； 连续、非周期；连续、非周期； （4）DTFT： 离散、非周期；离散、非周期； 连续、周期；连续、周期； ( )x t x n(j )Xj(e )Xjj(j )( )ed1( )(j )ed2ttXx ttx tX jjjj2(e ) e1 (e )ed2nnnXx nx nX2021

5、-11-11大连理工大学8 分析：分析：注意到，在注意到，在DFSDFS中，时间序列中，时间序列 是周期性的，周期是周期性的，周期为为N N。另一方面，周期为另一方面，周期为N N的序列只有的序列只有N N点点独立样本独立样本，其余的，其余的都重复。都重复。 DFS中，实际上只用了中，实际上只用了 的的N点数据。点数据。这样，这样，可以把可以把N N点长的非周期序列看成周期为点长的非周期序列看成周期为N N的序列的序列的一个周期。的一个周期。 x n x n2021-11-11大连理工大学9 离散傅里叶变换（离散傅里叶变换（DFTDFT） 【假设假设】 设设 为有限长序列，点数为为有限长序列，

6、点数为N，可将其看作周期，可将其看作周期为为N的周期序列的周期序列 的一个周期；而把的一个周期；而把 看作看作是是 的周期延拓，即：的周期延拓，即： 称称 是是 的主值序列。的主值序列。 记为：记为： 表示表示“ “ 对对 取余数取余数”，或，或 对对 取模值。取模值。( )x n( )x n( )x n( )x n( ) 01 ( )0 x nnNx nn，（主值），其他( )x n( )x n( )()( )Nx nx nNx n模( )Nx nnnNN( )()rx nx nrN2021-11-11大连理工大学10 【例例8.1】 设设 为周期为周期 的序列，求的序列，求 两数对两数对

7、的余数。的余数。 【解解】 因为：因为： ，故：，故： 因为：因为： ，故：，故： 这样：这样：( )x n9N N25,5nn 252 97n 9(25)75( 1)94n 9( 5)499(25)(25)(7)( 5)( 5)(4)xxxxxx2021-11-11大连理工大学11 DFT的定义：的定义： 【定义定义】式中，式中，211j00211j00( )DFT ( )( )e( ),0,1,11( )IDFT( )( )e( ),0,1,1NNknknNNnnNNknknNNkkX kx nx nx n WkNx nX kX kX k WnNN2jeNNW离散，离散，非非周期周期 离散

8、离散非非周期周期 二者均隐二者均隐含含周期周期性性( )x n( )X k22jj e, eknknknknNNNNWW002jj2jj11( )e( )e( )eeknknNknNnNknknNkkkNkNax nx nNNx naaDFS：2021-11-11大连理工大学12 定义定义加窗函数加窗函数 则则DFT定义式改写为：定义式改写为： 即即DFT是是DFS的一个周期的一个周期。1 01 1 01 ( )( )0 0 NNnNkNR nR knk ，或，其它，其它1010( )( )( )( )( )1( )( )( )( )( )NnkNNNnNnkNNNkX kx n WRkX k

9、 Rkx nX k WRnx n RnN2021-11-11大连理工大学13 DFT的图形解释的图形解释2021-11-11大连理工大学14 说明（参考上页图）说明（参考上页图） (a) 长度为长度为T的连续时间信号，其频谱为的连续时间信号，其频谱为 。 (b) 时域采样信号：时域采样信号： ，其频谱仍为，其频谱仍为同周期脉冲序列。同周期脉冲序列。 (c) 采样，连续时间信号离散化，频谱周期性延拓。采样，连续时间信号离散化，频谱周期性延拓。 (d) 频域采样信号。频域采样信号。 (e) 频域采样的结果，频谱离散化，信号周期性延拓。频域采样的结果，频谱离散化，信号周期性延拓。 (j )X( )(

10、)SSnp tTtnT2021-11-11大连理工大学15 DFTDFT与与DTFTDTFT及及z z变换的关系变换的关系设设 长为长为N N点，则：点，则：其中：其中： 定义在整个定义在整个z z平面；平面； 仅在仅在z z平面单位圆平面单位圆上取值；上取值； 是单位圆上是单位圆上N个等个等间距点上取值间距点上取值 是是 的主值周期。的主值周期。( )x nj11j001jje021jj20( )( )( )( e )(e )( )e( )( )( )e(e )NNnnnnNnznNnkNknNX zx n zx n rXx nX zX kx nX( )X zj(e)X( )X k( )X

11、kka( )( )kNX ka Rk2021-11-11大连理工大学168.2 离散傅里叶变换的性质离散傅里叶变换的性质2021-11-11大连理工大学17 【线性性质线性性质】 若：若： 则：则： 【序列的圆周位移性质序列的圆周位移性质】 将将 延拓为延拓为 ，将，将 位移，取主值区间上的位移，取主值区间上的序列值序列值。即：即： 圆周位移：圆周位移： 若：若： 则：则：1122DFT( )( ), DFT( )( )x nX kx nXk1212DFT( )( )( )( )ax nbx naX kbXk( )x n( )x n( )x n( )()( )()( )mNNNxnx nmRn

12、x nm Rn( )DFT( )( )mkmmNXkxnWX kDFT( )( )x nX k2021-11-11大连理工大学18 【圆周位移的图形解释圆周位移的图形解释】左移左移=顺时针旋转顺时针旋转右移右移=逆时针旋转逆时针旋转2021-11-11大连理工大学19 【对偶性对偶性】 若：若： 则：则： 【帕色伐尔定理帕色伐尔定理】 若：若： 则：则：DFT( )( )x nX kDFT( )()( )()( )NNNNX nNxkRkNxNkRkDFT( )( )x nX k11*001( )( )( )( )NNnnx n y nX k YkN2021-11-11大连理工大学20 【圆周

13、共轭对称性圆周共轭对称性】 若：若： 则：则：DFT( )DFT Re( )jIm( )x nx nx n*ep*op*1 DFT( )()( )=()( )2 DFT( )( )( )13 DFT Re ( )( )( )()( )214 DFT jIm ( )( )( )()( )25( )()( ), ( ) NNNNNNNNNNNNNNx nXkR kXNkR kxnR nX kx nXkX kXNkR kx nXkX kXNkR kX kXNkR kx n若* real6( )()( ) ( ) imagenaryNNX kXNkR kx n， 若2021-11-11大连理工大学21

14、 【满足圆周共轭对称性的序列满足圆周共轭对称性的序列】2021-11-11大连理工大学22 【圆周卷积和性质圆周卷积和性质】 若：若： 若：若： 则：则：1122DFT( )( ), DFT( )( )x nX kx nXk12( )( )( )Y kX kXk11201210( )IDFT( )( ) ()( ) ( ) ()( )NNNmNNNmy nY kx m xn mR nx m xn mR n2021-11-11大连理工大学23【圆周卷积和图示圆周卷积和图示】 把主值周期左边一个把主值周期左边一个周期的数据反折到主周期的数据反折到主值区间。值区间。 右移，最右边的移右移，最右边的移

15、至最左边至最左边2021-11-11大连理工大学24 【圆周相关性质圆周相关性质】 若：若： 若：若： 则：则：DFT( )( ), DFT( )( )x nX ky nY k*( )( )( )xyRkX k Yk1*01*0( )IDFT( )( ) ()( ) ( )()( )NxyxyNNnNNNnrmRky n x nmRmx n ynmRm2021-11-11大连理工大学25 有限长序列的线性卷积和圆周卷积有限长序列的线性卷积和圆周卷积 （1）线性卷积）线性卷积 非零值区间：非零值区间： ，其中，其中 和和 分别为分别为两序列的长度。两序列的长度。 其中，其中， 的非的非0区间为区

16、间为 ； 的非的非0区间为区间为 线性卷积的长度：线性卷积的长度： 1112120( )( )()( )()Nlmmy nx m x nmx m x nm120,2NN121NNN1N2N1( )x m101mN2()x nm201nmN2021-11-11大连理工大学26 （2）圆周卷积）圆周卷积 将将 看成看成L点序列，点序列， ，不足补，不足补0. 则则 结论：结论： L点圆周卷积点圆周卷积 是线性卷积以是线性卷积以L为周期的周期为周期的周期延拓序列的主值序列。延拓序列的主值序列。 若若 ，则，则L点圆周卷积能代表线性卷积。点圆周卷积能代表线性卷积。 12( )( )( )y nx nx

17、 n12( ),( )x nx n12,LNLN11221212( ), 01( ), 01( ),( )0, 10, 1x nnNx nnNx nx nNnLNnL1120( )( )()( )()( )LLLlLmry nx m xnmR ny nrlR n( )y n121LNN2021-11-11大连理工大学27 离散傅里叶变换的逆变换离散傅里叶变换的逆变换逆变换与正变换的区别：逆变换与正变换的区别： 有系数有系数 指数有负号指数有负号具体应用时：具体应用时： 10101IDFT( )( ),0,1,1DFT( )( ),0,1,1NnkNkNnkNnx nX kX k WnNNX k

18、x nx k WkN1/ NnknkNNWW *1*011( )DFT( )NnkNnx nXk WXkNN2021-11-11大连理工大学288.3 与与DFT有关的几个问题有关的几个问题2021-11-11大连理工大学29 1.1.频率分辨率及频率分辨率及DFTDFT参数的选择参数的选择 分辨率分辨率 时间分辨率时间分辨率：通过时窗所看到时间的宽度：通过时窗所看到时间的宽度； 频率分辨率频率分辨率：通过频窗所看到频率的宽度：通过频窗所看到频率的宽度；或能或能将信号中两个靠的很近的频谱分开的能力。将信号中两个靠的很近的频谱分开的能力。 频率分辨率分析频率分辨率分析 设信号设信号 ，时长为，时

19、长为T秒，其傅里叶变换的秒，其傅里叶变换的 频率分辨率为频率分辨率为： 将将 抽样为抽样为 ，采样点数：，采样点数：( )Tx t(j )TX1/ (Hz)fT ( )Tx t( )Mxn1,sssTMfTT2021-11-11大连理工大学30经过经过DTFT（假设用矩形窗），（假设用矩形窗），频率分辨率仍为频率分辨率仍为：序列长度对分辨率的影响：序列长度对分辨率的影响： 由于由于 ，故若，故若 不变，会引起不变，会引起 ； 这相当于使数据长度这相当于使数据长度 ，或，或 。 若若T不能不能增加，则可：增加，则可：对对 的分点加密（插值）；的分点加密（插值）；在在 后面补后面补0 0。11ss

20、ffMMTT sffM ,sMff ()sTTMTM ( )X k( )Mxn2021-11-11大连理工大学31 说明：说明： 以上方法（频域插值或时域补以上方法（频域插值或时域补0）可使）可使 ，但不能改善分辨率但不能改善分辨率，原因是，原因是M（或（或T）未变。）未变。 在信号处理的实际应用中，往往在信号处理的实际应用中，往往M和和T不能不能改变了；改变了； 这时需要发展新的信号处理方法来改善分辨这时需要发展新的信号处理方法来改善分辨率，例如现代谱估计等。率，例如现代谱估计等。f 2021-11-11大连理工大学32 举例举例 【例例8.2】 设设 的最高频率的最高频率 ，采样频率，采样

21、频率 设信号时长设信号时长 ，即采样得的信号点数为，即采样得的信号点数为256点点。对对 做做DFT时，时， 。 【解解】：( )x t3Hzcf 10Hz, 0.1ssfTs25.6Ts( )x n?f 100.0390625Hz256sffM 2021-11-11大连理工大学33 【例例8.3】 条件同条件同【例例8.1】，若：，若： 且：且： 问：用问：用DFT求频谱时，可否分辨这三个频率。求频谱时，可否分辨这三个频率。 【解解】：因：因： 故：不能分辨故：不能分辨 ，可以分辨，可以分辨 。 若加长数据，即令若加长数据，即令N=1024，T=10240.1=102.4s 则：则： 故：可

22、以分辨故：可以分辨 。 见程序演示见程序演示 【fenbian.m】( )x t( )x n123( )sin(2)sin(2)sin(2)x tf tf tf t1232Hz 2.02Hz 2.07Hzfff，210.02Hz0.039Hzfff 2f3f100.01Hz1024sffN 210.02Hz0.01Hzfff 2f2021-11-11大连理工大学34 在应用中需要注意的问题：在应用中需要注意的问题：若信号最高频率为若信号最高频率为 ，则需满足：，则需满足： 根据需要的根据需要的 来选择数据长度来选择数据长度N： 对应的时间长度：对应的时间长度： cf2scfffsfNfssNT

23、NTf2021-11-11大连理工大学35 2.2.信号补信号补0 0问题问题 补零不能提高分辨率，因为补零未对原始信号增加补零不能提高分辨率，因为补零未对原始信号增加新信息；新信息； 但补零可使数据但补零可使数据N为为2的整次幂，以便的整次幂，以便FFT的使用；的使用； 补零可对补零可对 插值；插值； 插值有助于缓解频谱泄漏。插值有助于缓解频谱泄漏。 【例例】见程序演示见程序演示 【buling.m】( )X k2021-11-11大连理工大学36 应用举例应用举例 【例例8.48.4】：补补0 0的效果的效果三个信号频率：三个信号频率：1232.67Hz 3.75Hz 6.75Hzfff，

24、2021-11-11大连理工大学37 【例例8.48.4续续】由图由图(a)(a)，不能看出有几个频率；，不能看出有几个频率；由图由图(b)(b)，补，补N N个个0 0，仍不明显；，仍不明显；由图由图(c)(c)，补，补7N7N个个0 0，效果比较显著，基本可以分辨，效果比较显著，基本可以分辨三个信号频率；三个信号频率；由图由图(d)(d)，补，补29N29N个个0 0，效果明显。，效果明显。2021-11-11大连理工大学38 3. 信号的时宽与频宽问题信号的时宽与频宽问题 信号的时宽与频宽不可能同时缩小，也不可能同时扩大信号的时宽与频宽不可能同时缩小，也不可能同时扩大（例：（例：FT的比

25、例变换性质）的比例变换性质） ； 信号的时宽与频宽也不能同时为有限值信号的时宽与频宽也不能同时为有限值（例：矩形）（例：矩形）； 时宽和频宽的测量方法：时宽和频宽的测量方法： 方法方法1： 要求：要求： 是实对称、非递增的信号。有：是实对称、非递增的信号。有： 方法方法2： 不定原理：不定原理： uncertainty principle ( )iz t/211/2( )/ (0),( )d /(0)ssffnTWx nxFWX ffX( )x n/2/22222222222/2/2()| ( )| /| ( )| ,()|( )| d /|( )| dssssffffnnTWnx nx nF

26、WfX ffX ff2214TW FW111TW FW 2021-11-11大连理工大学39 4. 二维傅里叶变换二维傅里叶变换 二维二维DTFT： 二维二维DFT121 11 212121 11 2jjj12jjjj12122(e,)(,)ee1(,)(e,e)eedd(2 )jnnnnnnXex n nx n nX 121 12 212121 12 2122211jj12121122002211jj121211220012( ,)(,)ee,0,1,0,11(,)( ,)ee,0,1,0,1NNn kn kNNnnNNn kn kNNkkX k kx n nkNkNx n nX k knN

27、nNN N 2021-11-11大连理工大学40 5. 频谱泄漏问题频谱泄漏问题 频谱泄漏的含义：频谱泄漏的含义：截断信号的能量扩散到无穷宽的截断信号的能量扩散到无穷宽的频带中去，称为频谱泄漏。频带中去，称为频谱泄漏。 频谱泄漏的原因：频谱泄漏的原因： 在实际应用中，观测信号总是要限制在一定的时在实际应用中，观测信号总是要限制在一定的时间范围内。间范围内。 这相当于信号这相当于信号 与矩形窗函数与矩形窗函数 相乘。相乘。 时域乘积对应于频域卷积，卷积的结果使时域乘积对应于频域卷积，卷积的结果使 的频谱的频谱 发生了变化发生了变化 。 1( )x n( )w n1( )x nj1(e )Xj2(

28、e )X2021-11-11大连理工大学41 频谱泄漏的图示：频谱泄漏的图示：2021-11-11大连理工大学42频谱泄漏的危害频谱泄漏的危害泄漏的危害：泄漏的危害：使频谱的分辨率下降；使频谱的分辨率下降； 在频谱中引入虚假的频率分量（由窗引起）。在频谱中引入虚假的频率分量（由窗引起）。减小泄漏的方法：减小泄漏的方法： 取更长的数据，即增加窗宽；取更长的数据，即增加窗宽；数据不要突然截断，即不要矩形窗，加各种缓变数据不要突然截断，即不要矩形窗，加各种缓变窗，使窗旁瓣的能量更小。窗，使窗旁瓣的能量更小。 2021-11-11大连理工大学43 6. 栅栏效应栅栏效应 概念：概念：因因DFT的谱是限

29、制在离散点上的频谱，是一的谱是限制在离散点上的频谱，是一种限制为基频种限制为基频 整数倍处的谱，而不是连续的频整数倍处的谱，而不是连续的频谱。就像通过谱。就像通过“栅栏栅栏”观看景象一样，只能在离散观看景象一样，只能在离散点处看到真实景象，称为栅栏效应。点处看到真实景象，称为栅栏效应。 02021-11-11大连理工大学44 减小栅栏效应的方法减小栅栏效应的方法 增加频域采样点数增加频域采样点数N； 在不改变时域数据的情况下，补在不改变时域数据的情况下，补0； 频率采样为频率采样为 ，随着，随着N增大，导致采样点增大，导致采样点更近，谱线更密。更近，谱线更密。 2kN2021-11-11大连理

30、工大学45 7. 频率混叠问题频率混叠问题 由采样定理：由采样定理： 若采样定理不满足，则产生混叠，即频率响应周期若采样定理不满足，则产生混叠，即频率响应周期延拓分量互相重叠。延拓分量互相重叠。 若信号的频谱无限宽，则需要抗混叠滤波器进行预若信号的频谱无限宽，则需要抗混叠滤波器进行预处理。处理。 可选占信号能量可选占信号能量98%左右的频带宽度的左右的频带宽度的 作为信作为信号的最高频率，从而进一步确定采样频率号的最高频率，从而进一步确定采样频率 。 max2sffmaxfsf2021-11-11大连理工大学468.4 快速傅里叶变换（快速傅里叶变换（FFTFFT）2021-11-11大连理工

31、大学47 0. 引言：引言： 【DFTDFT算法的计算量算法的计算量】 N点点DFT的复乘法次数的复乘法次数： ；加法次数：加法次数： 若若 ，则复乘法次数，则复乘法次数1048576次，次， 折合实数乘折合实数乘法法4194304次。次。10102( )( ),0,1,1( )( ),0,1,1NnkNnNnkNkjNNX kx n WkNx nX k WnNWe2N(1)N N 1024N 2021-11-11大连理工大学48 【FFTFFT算法的出现算法的出现】 1965年，库利（年，库利（J.W.Cooley）和图基（）和图基（J.W.Tukey）在在Mathematics of Co

32、mputation上发表论文，提出上发表论文，提出了一种了一种DFT的快速计算法。的快速计算法。 后来又经过不断完善和发展，形成后来又经过不断完善和发展，形成FFT。 FFT算法的计算量：算法的计算量： FFT出现，才使傅里叶变换的理论方法得以方便地出现，才使傅里叶变换的理论方法得以方便地实现。实现。 可以说，可以说，FFT有力地推动了傅里叶理论方法的发展。有力地推动了傅里叶理论方法的发展。 22log2NNN2021-11-11大连理工大学49 【DFTDFTFFTFFT的一个特例的一个特例】定义定义 矩阵：矩阵： 定义信号矢量与频谱矢量定义信号矢量与频谱矢量NW000001210242(1

33、)012(1)(1)(1)NnkNNNNNNWWWWWWWWWWWWWWWWWWTT(0)(1)(1) (0)(1)(1)NNXXX Nxxx NXx10( )( ),0,1,1NnkNnX kx n WkN2021-11-11大连理工大学50这样，这样，离散傅里叶变换（离散傅里叶变换（DFT）可以写成矩阵形式，）可以写成矩阵形式，如下：如下： 的特点与性质：的特点与性质： 利用上述周期性和对称性，利用上述周期性和对称性，4点点DFT可以写为：可以写为： NNNXW xNW0/21,1;NNNWW /2,NrrNrrNNNNWWWW 1111(0)1111(0)(1)11(1)(2)1111(

34、2)(3)11(3)XxXWWxXxXWWx2jeNNW2021-11-11大连理工大学51 将上述矩阵的第将上述矩阵的第2列与第列与第3列交换，有列交换，有 这样，有：这样，有：1111(0)1111(0)(1)11(2)(2)1111(1)(3)11(3)XxXWWxXxXWWx11(0) (0)(2) (1)(3)(1) (0)(2) (1)(3)(2) (0)(2) (1)(3)(3) (0)(2) (1)(3)NNXxxxxXxxxxWXxxxxXxxxxW2021-11-11大连理工大学52比较计算量：比较计算量：DFT算法的计算量：算法的计算量： 次复数乘法；次复数乘法；FFT算

35、法的计算量：只需算法的计算量：只需1次复数乘法。次复数乘法。24162021-11-11大连理工大学53 1. 直接计算直接计算DFTDFT的问题和改进途径的问题和改进途径 DFT的正变换与逆变换式的差别很小，仅两点：的正变换与逆变换式的差别很小，仅两点： 的指数符号；乘法因子的指数符号；乘法因子 。仅考虑正变换。仅考虑正变换。 【可以用于减小可以用于减小DFTDFT计算量的特性计算量的特性】 具有共轭对称性：具有共轭对称性： 具有周期性：具有周期性： 具有可约性：具有可约性： 并且，并且，NW1/ NnkNW*nknkNNWWnkNWnkNWn N kkN nnkNNNWWW/,nkmnkn

36、knk mNmNNN mWWWW()()/22,1,Nkn N kk N nnkNkNNNNNNWWWWWW 2021-11-11大连理工大学54 【上述特性的利用上述特性的利用】 DFT运算中的有些项可以合并；运算中的有些项可以合并； 利用利用 的对称性、周期性和可约性，可以将长序的对称性、周期性和可约性，可以将长序列的列的DFT分解为短序列的分解为短序列的DFT； 越小，越有利于计算量的减小。越小，越有利于计算量的减小。 nkNWN2021-11-11大连理工大学55 2.2.按时间抽选的基按时间抽选的基2FFT2FFT算法算法 【算法原理算法原理】：设序列点数设序列点数 ， 为正整数。为

37、正整数。 将将 先按先按 的的奇偶分成两组奇偶分成两组： 这样，可将这样，可将DFT化为：化为： 2LN L( ), (0,1,1)x nnN121 (2 )( )0,1,122 (21)( )x rx rNrx rx r 111000(/2) 1(/2) 1(2r)(2r+1)00(/2) 1(/2) 1221200( )DFT( )( )( )+( )=(2 )+(21)=( )+( )NNNnknknkNNNnnnnnNNkkNNrrNNrkrkkNNNrrX kx nx n Wx n Wx n Wxr WxrWx rWWx rW（ 为偶数）（ 为奇数）n2021-11-11大连理工大学

38、56 按时间抽选的基按时间抽选的基2 FFT2 FFT算法（续）算法（续） 【算法原理算法原理】（续）：（续）： 根据根据 ，上式表示为：，上式表示为： 其中其中 和和 分别是分别是 和和 的的 点点DFT。 这样：这样：22j2j2/2/2=e=eNNNNWW(/2) 1(/2) 11/212/2020( )()()( )kNNrkkrkNrNNNrX kx r WWx rX kWWXk1( )X k2( )Xk1( )x r2( )xr/2N(/2) 1(/2) 111/2/200(/2) 1(/2) 122/2/200( )( )(2 )0,1,12( )( )(21)0,1,12NNr

39、krkNNrrNNrkrkNNrrNX kx r Wxr WkNXkx r WxrWk，2021-11-11大连理工大学57 按时间抽选的基按时间抽选的基2 FFT2 FFT算法（续算法（续2 2） 【算法原理算法原理】（续（续2 2）：）： 说明：说明：一个一个 点点DFT已分解为两个已分解为两个 点的点的DFT；再进行组合成再进行组合成 点点DFT（上页（上页红色红色部分，前半段）。部分，前半段）。 再利用系数的周期性：再利用系数的周期性： 则有：则有： （蓝色蓝色部分，后半段）部分，后半段） 这样，前半段这样，前半段 和后半段和后半段 的的数据都做了数据都做了DFT。 频谱的后半段与前半

40、段相等频谱的后半段与前半段相等。N/2NN()2/2/2Nr krkNNWW(/2) 1(/2) 1/21/21/2022011( )2( )( )2( )NNr NkrkNNrrx r Wx rNXkX kNXkXWk0,1,12N,12NN2021-11-11大连理工大学58 按时间抽选的基按时间抽选的基2 FFT2 FFT算法（续算法（续3 3） 【算法原理算法原理】（续（续3 3）：）： 再考虑性质：再考虑性质： 则前半段：则前半段： 后半段：后半段： 即只要求出前半段即只要求出前半段 和和 ，就可以得到完整，就可以得到完整的的 ，节省计算量。，节省计算量。 ()22NNkkkNNNN

41、WWWW 2121( )( ),( )( )( ),00,1,122,1,12kNkNNNX kX kW XNX kX kW Xkkkk1( )X k2( )Xk( )X k2021-11-11大连理工大学59 按时间抽选的基按时间抽选的基2 FFT2 FFT算法（续算法（续4 4） 【蝶形信号流图蝶形信号流图】：上述算法可用下面的蝶形流图表示。上述算法可用下面的蝶形流图表示。1212( )( )( ),0,1,12( )( ),0,1,122kNkNNX kX kW XkkNNX kX kW Xkk2021-11-11大连理工大学60 N=8N=8的蝶形信号流图：的蝶形信号流图：2021-1

42、1-11大连理工大学61 按时间抽选的基按时间抽选的基2FFT2FFT算法（续算法（续5 5） 由于由于 仍为偶数，还可以继续分解。仍为偶数，还可以继续分解。将每个将每个 的子序列再按照奇部、偶部分解为两个的子序列再按照奇部、偶部分解为两个 子序列。子序列。例如：例如：将将 分解如下：分解如下： 这样：/2N/2N/4N1( )x r1314(2 )( )0,1,1(21)( )4xlx lNlxlx l(/4 1)(/4 1)21211/21/200(/4 1)(/4 1)3/4/24/4003/2413/24( )(2 )(21)( )( )0,1,14( )( )( )( )4NNlkl

43、kNNllNNlkklkNNNllkNkNX kxl WxlWx l WWx l WNkXkWXkNXkXkWXk2021-11-11大连理工大学62 按时间抽选的基按时间抽选的基2FFT2FFT算法（续算法（续6 6） 这样：这样：(/4 1)(/4 1)21211/21/200(/4 1)(/4 1)3/4/24/4003/2413/24( )(2 )(21)( )( )0,1,14( )( )( )( )4NNlklkNNllNNlkklkNNNllkNkNX kxl WxlWx l WWx l WNkXkWXkNXkXkWXk2021-11-11大连理工大学63 按时间抽选的基按时间抽

44、选的基2FFT2FFT算法（续算法（续6 6） 对对 也可以继续分解，有：也可以继续分解，有：由由2 2个个N/4N/4点点DFTDFT组合的组合的N/2N/2点点DFTDFT：2( )x r25/2625/26( )( )( )0,1,14( )( )4kNkNXkXkWXkNkNXkXkWXk2021-11-11大连理工大学64 按时间抽选的基按时间抽选的基2FFT2FFT算法（续算法（续6 6） 将系数统一为将系数统一为 ，则一个，则一个8点的点的DFT可以分解可以分解为为4个个N/4点点DFT，如图，如图。一直一直分解分解到到2点数据为止点数据为止。2/2kkNNWW2021-11-1

45、1大连理工大学65 【完整的完整的8 8点点FFTFFT流图流图】2021-11-11大连理工大学66 【运算量问题运算量问题】 当数据长度当数据长度 ，需要计算量：，需要计算量： 复数乘法：复数乘法： 复数加法：复数加法： DFT与与FFT计算量之比计算量之比：2LN 2log22FNNmLN2logFaNLNN22222loglog22NNNNNNLN2021-11-11大连理工大学67 【时间抽取时间抽取FFTFFT算法的特点算法的特点】 原位计算（同址计算），节省存储空间。原位计算（同址计算），节省存储空间。 倒位序规律。倒位序规律。1111( )( )( )( )( )( )rmmm

46、NrmmmNXkXkXj WXjXkXj W2021-11-11大连理工大学68 【时间抽取时间抽取FFTFFT算法的特点算法的特点】 蝶形运算两节点的距离：蝶形运算两节点的距离： 第第1段段1 第第2段段2 第第3段段4 第第m段段 12m2021-11-11大连理工大学69 【按时间抽选的按时间抽选的FFTFFT算法的其他形式流图算法的其他形式流图】（略）（略）FFTFFT算法按时间抽取还有许多其他算法，请同学们自算法按时间抽取还有许多其他算法，请同学们自行参考相关书籍进行学习。行参考相关书籍进行学习。2021-11-11大连理工大学70 按频率抽选的基按频率抽选的基2FFT2FFT算法算法 设设 ，把，把 换为奇偶分组，有：换为奇偶分组，有： 继续以此分解，最后，有：继续以此分解，最后，有： 2LN ( )X k11120021122200120( ) ,0,1,12