DSP-5-2014(新)

1、第五章第五章 快速傅里叶变换快速傅里叶变换(FFT)数字信号处理数字信号处理 Digital Signal Processing中国民航大学 航空自动化学院第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)FFT：引言Q直接计算直接计算DFT的问题及改进的途径的问题及改进的途径Q按按时间抽取时间抽取的基的基2-FFT算法算法 (掌握掌握)Q按按频率抽取频率抽取的基的基2-FFT算法算法 (掌握掌握)本章主要内容本章主要内容Q进一步减少运算量的措施进一步减少运算量的措施 (理解理解)第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)v FFT: Fast Fourie

2、r Transformv 1965 年，年，James W. Cooley 和和 John W. Tukey 在在计算数学计算数学（Mathematics of Computation）上发表了）上发表了“ 一种用机器计算复一种用机器计算复序列傅立叶级数的算法（序列傅立叶级数的算法（An algorithm for the machine calculation of complex Fourier series）” 论文。论文。v 自此之后，新的算法不断涌现。一种是自此之后，新的算法不断涌现。一种是对对N等于等于 2 的整数次幂的算法的整数次幂的算法，如基如基 2 算法，基算法，基 4 算法

3、。算法。另一种是另一种是N不等于不等于 2 的整数次幂的算法的整数次幂的算法，例如，例如 Winagrad 算法，素因子算法。算法，素因子算法。Dr. James W. CooleyWorked at IBM Watson Research Center in Yorktown Heights, N.Y.After his retirement from IBM in 1991, he joined the Electrical Engineering Department at the University of Rhode Island. 2022-2-283FFT：直接计算 DFT 的运

4、算量分析第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)N 点有限长序列 x(n) 的 DFT 变换对的定义为：10( )( )NnkNnX kx n W 0,1kN2jNNWe 101( )( )NnkNkx nX k WN 0,1nN 其中假设 x(n) 是复序列， 同时 X(k) 一般也是复数。FFT：直接计算 DFT 的运算量分析第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)FFT：直接计算 DFT 的运算量分析第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)10102X(k)=( )( )NnNnkNnjnkNx nn eWx FFT

5、：直接计算 DFT 的运算量分析计算量分析计算量分析N次复数次复数相乘相乘N-1次复次复数相加数相加N2次复数相乘次复数相乘N（N-1）次复数相加）次复数相加第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)v 如如 N=512、1024 和和 8192 时，时，DFT 的乘法运算的乘法运算 N2 = 5122 = 218 = 262144（26万次）万次） N2 = 10242 = 220 = 1048576（105万次）万次） N2 = 81922 = 226 = 67108864（6千千7百万次）百万次）N2次复数相乘次复数相乘N（N-1）次复数相加）次复数相加一次复数乘法

6、需四次实数乘法和二次实数加法一次复数乘法需四次实数乘法和二次实数加法一次复数加法需两次实数加法一次复数加法需两次实数加法1010ImRe)(Im)(Re)()(NnnkNnkNnkNNnWjWnxjnxWnxkXFFT：直接计算 DFT 的运算量分析采用通用计算机，速度为平均每次复乘为采用通用计算机，速度为平均每次复乘为5s，每次复加为，每次复加为1 s，所用，所用时间时间:T=5*10-6 *10242+ 10-6 *1024*1023=6.290s第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)1.如果一台通用计算机的速度为平均每次复乘 ，每次复加 ，用它来计算512点的

7、，问直接计算需要多少时间，用 运算需要多少时间。 5 s0.5 s DFT x nFFT解：(1)直接利用 计算： 复乘次数为 ，复加次数为 。 DFT2N1N N 复乘所需时间 626215 105 105121.31072TNs 复加所需时间 6260.5 1010.5 10512512 10.130816TNNs所以直接利用DFT 计算所需时间： 121.441536TTTsFFT：直接计算 DFT 的运算量分析第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)Q对于大对于大 N，在实际中是不能接受的，无法，在实际中是不能接受的，无法“实时实时”应应用用 DFT。 一般地，

8、在计算机中，一次加法比一次乘法所需时一般地，在计算机中，一次加法比一次乘法所需时间要短间要短; 在在DSP中，由于乘法用特殊的硬件电路专门完成，中，由于乘法用特殊的硬件电路专门完成，因此乘法和加法所需机器周期相同。因此乘法和加法所需机器周期相同。QCooley 与与 Turkey 提出的提出的 FFT 算法，大大减少了计算算法，大大减少了计算次数。如次数。如 N =512 时，时，FFT 的乘法次数约为的乘法次数约为 2000 次，次，提高了约提高了约 128 倍，而且倍，而且简化随简化随 N 的增加而巨增的增加而巨增，因而，因而，用数值方法计算频谱得到实际应用。用数值方法计算频谱得到实际应用

9、。FFT：直接计算 DFT 的运算量分析第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)FFT：旋转因子的特点把长序列分解成短序列计算，然后再组合出结果。nkNW主要原理是利用系数主要原理是利用系数 的以下特性对的以下特性对DFT进行分解：进行分解： nkNW（1）对称性）对称性 ()nkNW()k N nNW（2）周期性）周期性 ()()n N kn k NnkNNNWWW（3）可约性）可约性 mnknkmNNWW/nknk mNN mWW另外，另外，12/NNWkNNkNWW)2/(第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)vDFT高效运算的可能性分析

10、：高效运算的可能性分析：假定假定x(n)为为4点长的信号，对其做点长的信号，对其做4点点DFT：04040404)3()2() 1 ()0()0(WxWxWxWxX34241404)3()2() 1 ()0() 1 (WxWxWxWxX64442404)3()2() 1 ()0()2(WxWxWxWxX94643404)3()2() 1 ()0()3(WxWxWxWxX利用利用旋转因子旋转因子的的4个特点：个特点：)3() 1 ()2()0()0(xxxxX14)3() 1 ()2()0() 1 (WxxxxX-14)3() 1 ()2()0()3(WxxxxX-)3() 1 ()2()0()

11、2(xxxxX计算量？计算量？计算量？计算量？FFT：旋转因子的特点显然显然N值越小越有利！值越小越有利！第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)vFFT 算法分类算法分类: 时间时间抽选法抽选法 DIT: Decimation-In-Time 频率频率抽选法抽选法 DIF: Decimation-In-Frequencyv基本思路：基本思路：Q虽然存在不同的虽然存在不同的 FFT 方法，但其核心思想大致相同，方法，但其核心思想大致相同，即通过即通过迭代迭代，反复利用，反复利用低点数低点数的的 DFT 完成高点数的完成高点数的 DFT 计算，以此达到降低运算量的目的。计

12、算，以此达到降低运算量的目的。Q迭代：迭代：利用利用 WNkn 的周期性、特殊点和对称性，合并的周期性、特殊点和对称性，合并 DFT 计算中很多重复的计算，达到降低运算量的目的。计算中很多重复的计算，达到降低运算量的目的。Q低点数：低点数：将傅氏变换将傅氏变换 DFT 分解成相继小的分解成相继小的DFT计算，计算，即即 N 变小，而计算量与变小，而计算量与 N2 成正比。成正比。FFT：基本思想第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)FFT：基2时间抽选法-算法原理v算法原理算法原理 设序列点数设序列点数 N = 2M，M 为整数。若不满足，则补零。为整数。若不满足，则

13、补零。 将序列将序列 x(n) 按按 n 的奇偶分成两组：的奇偶分成两组：N 为为 2 的整数幂的的整数幂的 FFT 算法称基算法称基-2 FFT算法。算法。即一组由偶数序号组成，另一组由奇数序号组成。即一组由偶数序号组成，另一组由奇数序号组成。12( )(2 )0,1,12( )(21)x rxrNrx rxr 偶偶序序列列奇奇序序列列注意其长度为注意其长度为 N/2 第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT) 111000NNNnknknkNNNnnnX kx n Wx n Wx n Wn为为偶偶数数n为为奇奇数数2 1212 1200221/NNrkrkNNrrxr

14、 WxrW 2 12 1221200/NNrkrkkNNNrrxrWWxrW 2 12 1120202/NNNrkkrkrNNrxr WWxr W 12kNXkW Xk0 112, ,.k= 0,1,.N-1Nr 注意：注意：这里的这里的k的的取值范围为取值范围为0，1，N-1FFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)偶数取样点偶数取样点DFT为：为： NN-1-122krkr1N 21N 2r=0r=0X (k) =x(2r)W=x (r)W112222002122X ( )()(r)NNkrkrNNrrkxrWxW0 12 1, ,./

15、k= 0,1,.N-1rN奇数取样点奇数取样点DFT为：为： k 的整个范围为的整个范围为 0(N-1)，而，而X1(k)、X2(k) 是由是由 N/2 个样点形成的个样点形成的 DFT，x(2r) 和和 x(2r1）的长度为）的长度为 N/2； 由这两个偶数和奇数由这两个偶数和奇数 N/2 个时域样值可以计算出前个时域样值可以计算出前 N/2 个个 DFT 系数，也可系数，也可以计算出后以计算出后 N/2 个个 DFT 系数。系数。 问题：这前后问题：这前后 N/2 个个 DFT 有无关系？有无关系？k 在在 N/2 (N-1) 时，时， X1(k)、X2(k)、WN 情况如何？情况如何？F

16、FT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)1122 , NNkN当当时时0122 , ,NNkll令令观察观察21( )()(kNXkXWX kk 分分为为三三部部分分第第一一第第三三第第二二则则2221122()22110012102( )()(2 )(2 )2(2 )( )NNNNNNNrlrrlrrNrlNrNX kXlxr Wxr WWxr WX l 2222221NjrNNrjrNWee N-12kr1N 2r=0X (k) =x(2r)WFFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT

17、)因此：整个因此：整个 X(k) 的计算，可以分解为的计算，可以分解为前、后半部分前、后半部分的运的运算。而算。而只要求出前一半只要求出前一半，就可以由上式求出整个序列。，就可以由上式求出整个序列。同理同理2222( )()( )NXkXlXl 而而2()222(1) NNNljkljNNNNNWWWWee 因此因此1122( )( )( )()( )( )2 kNkNNX kX kWX XkkX kWXk0,1,12Nk FFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)上式表示为信号流程图：上式表示为信号流程图：此信号流程图也称为此信号流程图也

18、称为蝶形蝶形流程图流程图1122( )( )( )()( )( )2 kNkNNX kX kWX XkkX kWXk0,1,12Nk 偶数点的偶数点的 DFT奇数点的奇数点的 DFT( )X k ()2NX kMorpho Butterfly大闪蝶大闪蝶( 南美洲南美洲)FFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)122()( )( )kNNX kXkWXkFFT：基2时间抽选法-算法原理偶数序列偶数序列奇数序列奇数序列12( )( )( )kNX kXkWXk以以N=8为为例，例，分解分解为为2个个4点点的的DFT，然后做然后做8/2=4次

19、次蝶形运算蝶形运算即可求出即可求出所有所有8点点X(k)的值。的值。第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)复数乘法次数：复数乘法次数： N2复数加法次数：复数加法次数： N(N1)复数乘法次数：复数乘法次数： 2*(N/2)2+N/2=N2/2+N/2复数加法次数：复数加法次数： 2*(N/2)(N/21)+2*N/2=N2/2QN点点 FFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)二次分解：二次分解：Q 将将x1(r)按按r取奇、偶可分解成取奇、偶可分解成2个长度为个长度为N/4的子序列的子序列 x3(l)= x1(

20、2h)、 x4(l) = x1(2h+1)，根据上面推导可得：根据上面推导可得：X1 (k)= X3(k)+ WN/2k X4(k)， k=0,1,N/2-1Q 将将x2(r)按按r取奇、偶可分解成取奇、偶可分解成2个长个长N/4的子序列的子序列 x5(l)= x2(2h) ， h=0,1,，N/4 x6(l) = x2(2h+1) ； 同理得同理得h=0,1,，N/4-1；X1 (k+N/2)=X3(k) WN/2k X4(k)， k=0,1,N/4-1；X1 (k)=X3(k)+WN/2k X4(k)， k=0,1,N/4-1；X2(k) = X5(k)+ WN/2k X6(k)， k=0

21、,1,N/4-1 ；X2(k+N/2) = X5(k) WN/2k X6(k), k=0,1,N/4-1；FFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)FFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)由于由于 N=2M，这样逐级分解，直到，这样逐级分解，直到 2 点点 DFT当当 N = 8时，可分解三次时，可分解三次00033223010332230010410104( )( )( )( )( )( )( )( )( )( )NNXxWW xxW xXxWW xxW x / 4 1133/ 43

22、/ 400( )( )( )NlklkNNllXkxl Wxl W 0,1k0004422401044224(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxWW xxW xXxWW xxW x 4 114444400/( )( )( )NlklkNNllXkxl Wxl W 0,1kFFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)FFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)FFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)FFT：

23、基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)L=1L=2L=3FFT：基2时间抽选法-算法原理第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)由按时间抽取法由按时间抽取法FFT的信号流图可知，当的信号流图可知，当N=2L时，共有时，共有 级级蝶形运算；每级都由蝶形运算；每级都由 个蝶形运算组成，而每个蝶形有个蝶形运算组成，而每个蝶形有 次复乘、次复乘、 次复加，因此每级运算都需次复加，因此每级运算都需 次复乘和次复乘和 次复加。次复加。 LN/2 N/2 12N按时间抽取基2-FFT算法与直接计算DFT运算量的比较 第第5 5章章 快

24、速傅里叶变换快速傅里叶变换(FFT)(FFT)1.原位计算原位计算序列长为序列长为N=2M点的点的FFT，有，有M级蝶形级蝶形，每级有，每级有N/2个蝶形运算个蝶形运算。 同一级中，每个蝶形的两个输入数据只对本蝶形有用同一级中，每个蝶形的两个输入数据只对本蝶形有用，每，每个蝶形的输入、输出数据节点在用一条水平线上。这样，当计算个蝶形的输入、输出数据节点在用一条水平线上。这样，当计算完一个蝶形后，所得的输出数据可立即存入原输入数据所占用的完一个蝶形后，所得的输出数据可立即存入原输入数据所占用的存储单元。存储单元。经过经过M级运算后，原来存放输入序列数据的级运算后，原来存放输入序列数据的N个存储个

25、存储单元中可依次存放单元中可依次存放X(k)的的N个值。个值。v原位计算原位计算：利用同一存储单元存储蝶形计算输入、输出数据的：利用同一存储单元存储蝶形计算输入、输出数据的方法。方法。v优点优点：节约存储空间、降低设备成本。：节约存储空间、降低设备成本。FFT：DITFFT的运算规律及编程思想第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)2.旋转因子的变化规律旋转因子的变化规律N点点DITFFT运算流图中，每个蝶形都要乘以运算流图中，每个蝶形都要乘以旋转因子旋转因子WpN，p称称为旋转因子的指数。为旋转因子的指数。N8 23 时各级的旋转因子时各级的旋转因子 第一级：第一级：

26、L=1， 有有1个旋转因子：个旋转因子：WNp =WN/4J =W2LJ J=0 第二级：第二级：L=2，有，有2个旋转因子：个旋转因子：WNp =WN/2J =W2LJ J=0,1 第三级：第三级：L=3，有，有4个旋转因子：个旋转因子：WNp =WNJ =W2LJ J=0,1,2,3 对于对于N2M 的的一般情况，一般情况，第第L级级共有共有2L-1个不同的旋转因子：个不同的旋转因子： WNp =W2LJ J=0,1,2, ,2L-11 2L =2L M 2M = N 2L M 故：故： 按照上面两式可以确定第按照上面两式可以确定第L级运算的旋转因子。级运算的旋转因子。JJ 2M-LWNp

27、 =W2LJ =WN 2L-M = WNp=J2M-L， J=0,1,2, ,2L-11FFT：DITFFT的运算规律及编程思想第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)3、同一级中，同一旋转因子对应蝶形数目、同一级中，同一旋转因子对应蝶形数目 第第L级级FFT运算中，运算中，同一旋转因子同一旋转因子用在用在2M-L个蝶形中；个蝶形中；4、同一级中，蝶形运算使用相同旋转因子之间相隔的、同一级中，蝶形运算使用相同旋转因子之间相隔的“距离距离” 第第L级中，蝶距：级中，蝶距：D=2L。5、同一蝶形运算两输入数据的距离、同一蝶形运算两输入数据的距离 在输入倒序，输出原序的在输入

28、倒序，输出原序的FFT变换中，第变换中，第L级的每一个蝶形级的每一个蝶形的的2个输入数据相距：个输入数据相距：B=2L-1。 6、码位颠倒、码位颠倒 输入序列输入序列x(n)经过经过M级时域奇、偶抽选后，输出序列级时域奇、偶抽选后，输出序列X(k)的顺的顺序和输入序列的顺序关系为序和输入序列的顺序关系为倒位关系倒位关系。FFT：DITFFT的运算规律及编程思想第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)7、蝶形运算的规律、蝶形运算的规律 序列经过时域抽选后，存入数组中，如果蝶形运序列经过时域抽选后，存入数组中，如果蝶形运算的两个输入数据相距算的两个输入数据相距B个点，应用原

29、位计算，蝶形个点，应用原位计算，蝶形运算可表示成如下形式：运算可表示成如下形式： XL-1(J)X L-1 (J+B)XL (J)= XL-1(J)+ WNp X L-1 (J+B)XL (J) = XL-1(J) WNp X L-1 (J+B)p=J2M-L， J=0,1,2, ,2L-11FFT：DITFFT的运算规律及编程思想的运算规律及编程思想第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)8.输入位序重排输入位序重排 N 点点 DFT 分解为两个分解为两个 N/2 点点 DFT输入序列按奇偶分组输入序列按奇偶分组再分解再分解再奇偶重排再奇偶重排直到直到 2 点点DFT

30、。 即即 FFT 输出自输出自然序列然序列 输入序列输入序列 x(n) 位序重排位序重排。2 1 0210()()(000)(0)(001)(1)(010)(2)(011)(3)(100)(4)(101)(5)(110)(6)(111)(7)n n nxxxxxxxxxxxxxxxxxn n nx 十十进进制制01010101(000)(0)(100)(4)(010)(2)(110)(6)(001)(1)(101)(5)(011)(3)(111)(7)xxxxxxxxxxxxxxxx010011n0n1n2FFT：DITFFT的运算规律及编程思想第第5 5章章 快速傅里叶变换快速傅里叶变换(F

31、FT)(FFT)思考题：思考题：已知已知N=16点，在点，在DIT-FFT运算中，序数为运算中，序数为2的二进制的二进制经数倒序后为多少经数倒序后为多少?顺序数顺序数增加增加1，是在顺序数的是在顺序数的二进制数的二进制数的最最低位加低位加1，向，向左左进位进位到序数是在到序数是在M位 二 进 制 数位 二 进 制 数的的最高位加最高位加1，向右向右进位进位(0010-0100)(0010-0100)顺序和倒序二进制数对照表顺序和倒序二进制数对照表FFT：DITFFT的运算规律及编程思想第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)FFT：DITFFT的运算规律及编程思想N个存

32、储器个存储器FFT的实现的实现1. 输入输入x(n)-N个点；个点；2. 位倒序后存储在位倒序后存储在N个存储器中；个存储器中；3. 逐级蝶形运算，输逐级蝶形运算，输出结果仍存回存储出结果仍存回存储器中；器中；4. 最后最后N个存储器中个存储器中存放的是存放的是FFT的结的结果果X(k)。x(n)的位倒序的位倒序X(k)的自然顺序的自然顺序rNW输入序列输入序列x(n) : N个存储单元个存储单元系数系数 ： N / 2个存储单元个存储单元存储单元存储单元第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)v 算法原理：算法原理：根据时间根据时间-频率的对偶性频率的对偶性Q时间抽选

33、法：时间抽选法：是把输入是把输入 x(n) 按奇偶分解成两个子序列，即按奇偶分解成两个子序列，即 N 点点x(n) 序列序列 N/2 点子序列，而输出点子序列，而输出 X(k) 是按自然顺序是按自然顺序排列的。排列的。Q频率抽选法：频率抽选法：是把输入是把输入 x(n) 按照前后对半分开，而不是奇按照前后对半分开，而不是奇偶数分开，而输出偶数分开，而输出 X(k) 逐项分解成偶数点子序列和奇数点逐项分解成偶数点子序列和奇数点子序列。子序列。v DFT 变换表达式为：变换表达式为：10( )( )NnkNnX kx n W (1)2NnN如果将输入如果将输入 x(n) 按前后等分，即将求和分成两

34、部分，范围分别为：按前后等分，即将求和分成两部分，范围分别为：0 (1)2Nn FFT：基2频率抽选法 (DIF-FFT)第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)12 10201/( )( )( )( )NNnknkNn NnkNNNnnX kx n Wx n Wx n W0022 12 12/( )NNnknkNnNNnNx n WxnW22 102/( )NnkNNNknNx nxnWW 2 1021/()()NknkNnNx nxnW 0,1,.,1kN/21NNW FFT：基2频率抽选法 (DIF-FFT)第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(

35、FFT) 按按 k 的奇偶将的奇偶将X(k)分成两部分：分成两部分：221krkr0,1,.,12Nr 2 12022/()( )NnrNnNXrx nx nW2 1210212/()()( )NnrNnNXrx nx nW2 1202/( )NnrNnNx nx nW 2 1202/( )NnrNnnNWNx nx nWFFT：基2频率抽选法 (DIF-FFT)第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)令令: :1222( )( )( )( )nNNx nx nx nNxnx nx nkkW 为为偶偶数数： 数数 为为奇奇：0,1,.,12Nn 则则 X(2r) 和和 X(2r+1) 分别是分别是 x1(n) 和和 x2(n) 的的 N/2 点点 DFT，记为记为 X1(k) 和和 X2(k)。1211202()( )NnrNnXrxXWkkn 为为偶偶数数：12222021()( )NnrNnXrxnkXWk为为奇奇数数：FFT：基2频率抽选法 (DIF-FFT)第第5 5章章 快速傅里叶变换快速傅里叶变换(FFT)(FFT)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-