发布时间 : 星期一 文章数字信号处理实验报告3 DSP信号与系统实验报告 信号加窗及谱分析 电子科技大学 2018版更新完毕开始阅读
点序列分成两个（N/2）点序列，那么计算N点DFT将只需要约[(N/2)2 ·2]=N2/2次复数乘法。即比直接计算少作一半乘法。因子（N/2）2表示直接计算（N/2）点DFT所需要的乘法次数，而乘数2代表必须完成两个（N/2）DFT。上述处理方法可以反复使用，即（N/2）点的DFT计算也可以化成两个（N/4）点的DFT（假定N/2为偶数），从而又少作一半的乘法。这样一级一级地划分下去一直到最后就划分成两点DFT运算的情况。
a）基2按时间抽取（DIT）的FFT算法思想：
设序列长度为N?2L，L为整数（如果序列长度不满足此条件，可通过在后面补零让其满足）。
将长度为N?2L的序列x?n?(n?0,1,?,N?1)，先按n的奇偶分成两组：
DFT化为：
nkX[k]?DFT{x[n]}??x[n]WNn?0N/2?1N?1x[2r]?x1[r]x[2r?1]?x2[r],r?0,1,2,L,N2
?
?x[2r]Wr?02rkNN/2?1??x[2r?1]Wr?0kNN/2?1r?0(2r?1)kNN/2?1???x[r]W1r?02rkN?W?W?x[r]W2r?02rkN
N/2?1?r?0x1[r]WrkN/2kNN/2?1?rkx2[r]WN/2（3.10）
2rkrk上式中利用了旋转因子的可约性，即：WN?WN2。又令
N2?1r?0N2?1r?0 X1?k??则式（3.10）可以写成：
?x?r?W1rkN2,X2?k???x?r?W2rkN2，
X[k]?X1[k]?WNkX2[k]，k?0,1,LN2?1
（3.11）
可以看出，X1?k?,X2?k?分别为从X?k?中取出的N/2点偶数点和N/2点奇数点
序列的N/2点DFT值，所以，一个N点序列的DFT可以用两个N/2点序列的DFT组合而成。但是，从式（3.11）可以看出，这样的组合仅表示出了X?k?前N/2点的DFT值，还需要继续利用X1?k?,X2?k?表示X?k?的后半段本算法推导才完整。
rkr?k?N2?利用旋转因子的周期性，有：WN，则后半段的DFT值表达式： ?WN2N2?1r?0?N?r??k??2?N2N2?1?N? X1??k???2??x?r?W1??x?r?W1r?0rkN2?X1?k?
?N?同样，X2??k??X2?k? （k=0,1,…,N/2-1），所以后半段（k=N/2,…,N-1）的DFT
2??kk??WN值可以用前半段k值表达式获得，中间还利用到WNN2?k?WNN2WN，得到后
半段的X?k?值表达式为：
X[k]?X1[k]?WNkX2[k]，k?0,1,LN2?1 （3.12）
这样，通过计算两个N/2点序列x1?n?,x2?n?的N/2点DFTX1?k?,X2?k?，可以组合得到N点序列的DFT值X?k?，其组合过程如图3.3所示：
图3.3 两个N/2点DFT组合成一个N点DFT
比如，一个N = 8点的FFT运算按照这种方法来计算FFT可以用图3.4来表示：
x(0)W0x(1)W0x(2)W0x(3)x(4)W0x(5)W0x(6)W0x(7)W2W3W2W2W0W1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)
图3.4 8点基2按时间抽取（DIT）算法流程图
b）基2按频率抽取（DIF）的FFT算法思想：
设序列长度为N?2L，L为整数（如果序列长度不满足此条件，通过在后面补零让其满足）。
在把X?k?按k的奇偶分组之前，把输入按n的顺序分成前后两半：
X[k]?DFT{x[n]}??x[n]Wn?0N/2?1N?1nkNN/2?1??n?0x[n]WnkN?n?N/2?N?1x[n]WNnk???n?0x[n]WNnk?N/2?1?n?0)kN(n?N2x[n?]WN2N/2?1?n?0kNNnk2[x[n]?x[n?]WN]gWN,k?0,1,...,N?12
k?N2?k因为WNN2??1，则有WN???1?，所以：
N/2?1X[k]???[x[n]?(?1)n?0kx[n?Nnk]]gWN,k?0,1,...,N?12
按k的奇偶来讨论，k为偶数时：
N/2?1X[2r]??n?0[x[n]?x[n?N2rn]]gWN,k?0,1,...,N?12
k为奇数时：
N/2?1X[2r?1]??[x[n]?x[n?2]]gWn?0N(2r?1)nN,k?0,1,...,N?1
2rkrk前面已经推导过WN?WN2，所以上面的两个等式可以写为：
N/2?1X[2r]??n?0[x[n]?x[n?Nrn]]gWN/2,r?0,1,...,N/2?12 Nnnr]]gWN}WN/2,r?0,1,...,N/2?12
N/2?1X[2r?1]??n?0{[x[n]?x[n?通过上面的推导，X?k?的偶数点值X?2r?和奇数点值X?2r?1?分别可以由组合而成的N/2点的序列来求得，其中偶数点值X?2r?为输入x[n]的前半段和后半段之和序列的N/2点DFT值，奇数点值X?2r?1?为输入x[n]的前半段和后半段
n之差再与WN相乘序列的N/2点DFT值。
令
x1[n]?x[n]?x[n?则有：
N/2?1NNn]x2[n]?[x[n]?x[n?]]gWN2，2
X[2r]??n?0x1[n]gWrnN/2N/2?1,X[2r?1]??n?0rnx2[n]gWN/2,r?0,1,...,N?12
这样，也可以用两个N/2点DFT来组合成一个N点DFT。 （3）在FFT计算中使用到的MATLAB命令：
函数fft(x)可以计算R点序列的R点DFT值；而fft(x,N)则计算R点序列的N点DFT，若R>N，则直接截取R点DFT的前N点，若R 四、实验目的： 1、理解信号时域加窗后频谱的所发生的变化。 2、观察时域选择加不同的窗频域的变化情况，从而分析各种窗的特性。 3、深刻理解FFT基本思想，学习基2 DIT和基2 DIF算法。重点理解FFT算法在计算DFT方面的时间优化。