数字信号第七讲fft变换

1、第四章 快速傅里叶变换4.1 直接计算N点DFT的运算量4.2 按时间抽取的FFT算法4.3 按频率抽取的FFT算法4.4 IDFT的快速算法4.5 实序列的DFT计算1直接计算N点DFT的运算量结论：运算量：4.1 直接计算N点DFT的运算量2减少运算量的基本途径4.2 按时间抽取（DIT）的基2 FFT算法当N =2L时，将x(n)按奇偶分成的序列：1基2 DIT-FFT算法原理DIT:库利-图基算法（1965年库利提出的）1805年高斯提出，未得到重视。则x(n)的DFT为:4.2 按时间抽取（DIT）的基2 FFT算法由于所以4.2 按时间抽取（DIT）的基2 FFT算法代换利用对称性

2、及同理X(k)的前一半X(k)的后一半?4.2 按时间抽取（DIT）的基2 FFT算法X(k)的后一半为:4.2 按时间抽取（DIT）的基2 FFT算法蝶形流图表示:4.2 按时间抽取（DIT）的基2 FFT算法4.2 按时间抽取（DIT）的基2 FFT算法4.2 按时间抽取（DIT）的基2 FFT算法2点DFT2点DFT4.2 按时间抽取（DIT）的基2 FFT算法4.2 按时间抽取（DIT）的基2 FFT算法2DIT-FFT算法的运算量特点：运算量：DFT与FFT的运算量之比：表1 DFT与FFT算法的比较 结论：N越大，FFT算法的优越性越明显。NN22414.041644.086412

3、5.416256328.03210248012.864409619221.41281638444836.625665536102464.05122621442304113.8102410485765120204.82048419430411264372.44.2 按时间抽取（DIT）的基2 FFT算法4.2 按时间抽取（DIT）的基2 FFT算法3DIT-FFT算法的特点(1)原位计算4.2 按时间抽取（DIT）的基2 FFT算法(2)输入序列倒序顺序与倒序二进制数对照表 倒序（输入）顺序（输出）十进制数I二进制数二进制数十进制数J0000000041000011201001026110011

4、310011004510110153011110671111117(3)旋转因子的变化规律4.2 按时间抽取（DIT）的基2 FFT算法-1-1-1-1-1-1-1-1-1x(0)x(14)x(6)x(8)x(12)x(2)x(10)x(4)x(1)x(15)x(7)x(9)x(13)x(3)x(11)x(5)-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)-1-1-1-1-1-1-1-1-1-1-1X(8)X(9)X(10)X(11)X(12)X(13)X(14)X(15)N=16,按时间抽取FFT流图4.2 按时间抽取（DIT

5、）的基2 FFT算法原位计算解：N=4，按时间抽取FFT流图-1-1x(0)x(2)x(3)x(1)-1X(0)X(1)X(2)X(3)X1(0)X1(1)X2(0)X2(1)-1例1.已知x(n)=1,-1,0,1 0n3，利用基2 DIT计算x(n)的DFT。4.2 按时间抽取（DIT）的基2 FFT算法4.2 按时间抽取（DIT）的基2 FFT算法将x(n)前后对半分开，得到两个序列:1基2 DIF-FFT算法原理4.3 按频率抽取（DIF）的基2 FFT算法DIF:桑德-图基算法（1966年桑德提出的）4.3 按频率抽取（DIF）的基2 FFT算法4.3 按频率抽取（DIF）的基2 F

6、FT算法4.3 按频率抽取（DIF）的基2 FFT算法4.3 按频率抽取（DIF）的基2 FFT算法 DIF-FFT蝶形运算流图:4.3 按频率抽取（DIF）的基2 FFT算法N=8时一次分解的运算流图如图所示4.3 按频率抽取（DIF）的基2 FFT算法4点DFT4点DFT按频率抽取FFT流图（N=8）4.3 按频率抽取（DIF）的基2 FFT算法4.3 按频率抽取（DIF）的基2 FFT算法2DIF-FFT算法的运算量特点：运算量：DFT与FFT的运算量之比：4.3 按频率抽取（DIF）的基2 FFT算法3DIF-FFT算法的特点(1)原位计算4.3 按频率抽取（DIF）的基2 FFT算法(2)输出序列倒序顺序（输入）倒序（输出）十进制数I二进制数二进制数十进制数J000