数字信号处理（第3版）课件 第07章 FFT

第7章快速傅里叶变换（FFT）17.1时域抽选基2FFT算法7.2频域抽选基2FFT算法7.3实现中的具体问题7.4实序列的FFT算法7.5IDFT的快速算法2复数乘法:复数加法:实数乘法:实数加法:直接计算的运算量37.1时域抽选基2FFT算法

1.

第1次分解4推导信号流图由支路和节点组成。支路由箭头表示信号的流向，箭头旁的常数表示乘法运算；节点值等于所有输入支路之和，也就是包含了加法运算。加法乘法节点值=所有输入支路之和信号流图简介第1次分解后信号流图（N=8）N/2PointsDFTN/2PointsDFT基本蝶形计算782.第2次分解9第2次分解后信号流图103.完全分解后信号流图114.计算量举例125.其他形式13147.2频域抽选基2FFT算法

1.

第1次分解15推导第1次分解后信号流图（N=8）N/2PointsDFTN/2PointsDFT基本蝶形运算17182.第2次分解后信号流图193.完全分解后信号流图204.计算量同DIT-FFT215.其他形式22237.3实现中的具体问题

1.同址计算基本蝶形：若将和分别存放在原存放和的同一存储器中，则实现全部的计算只需要一列存储N个复数的存储器。我们称这种数据的存储方式为同址计算.24DIT可以同址运算不可以同址运算252.位反转或倒位序排列要确定在输入数列中的位置，我们必须将序号的二进制位序颠倒一下。我们称这种操作为倒位序。倒位序是由抽选导致的，N必须是2的整数幂次倒位序的实现方法专用硬件法：DSP芯片有硬件支持的倒位序寻址，编程简单，倒位

序过程不占用执行时间软件法事先做好倒位序表供使用时查表（反向进位法、生成法、

Matlab的bin2dec(fliplr(dec2bin([0:N-1])))）需要取数时顺次递推出下一个序号（反向进位法）26生成法N=2：倒位序[01]N=4：[01]*2=[02][02]+1=[13]所以倒位序：[0213]N=8：[0213]*2=[0426][0426]+1=[1537]所以倒位序：[04261537]N=16：[04261537]*2=[08412210614][08412210614]+1=[19513311715]所以倒位序：[0841221061419513311715]反向进位法

(最高bit加1，向低位进位)0000 01000 80100 41100 120010 21010 100110 60001 11001 90101 51101 130011 31101117111115N=16的倒位序排列确定x[n]后面是x[?]的软件实现步骤：(1)序号n与N/2比较：大于等于则表示最高位是1，向下进位后该位变成0，所以n=n-N/2，继续下一步；小于则表示最高位是0，所以n=n+N/2，结束，n就是接下来的序号。(2)n与N/4比较，大于等于则表示次高位是1，向下进位后该位变成0，所以n=n-N/4，继续下一步；

小于则n=n+N/4，结束。……….考虑128点基2FFT算法输入正常位序，输出倒位序排列的信号流图，排在X[98]后面的是

。X[18]98=62H=(110,0010)2

位置编码(010,0011)2+1=(010,0100)2(001,0010)2=12H=18反向进位法：最高位加1，向下进位例题按蓝色的路径求解：写出98的编码，倒位序得到位置的编码，加1得到下一个位置编码，再倒位序得到下一个信号的序号；按照红色的路径求解：写出98的编码，最高位加1向下进位，得到下一个信号的序号。303.系数30N=8的基2FFT，r的取值规律:DIT从左到右第1级是4的倍数0~N/2-4，重复4遍

第2级是2的倍数0~N/2-2，重复2遍

第3级是连续取值0~N/2-1DIF正好相反（1）用到时计算系数的值：

省存储空间，但费计算时间（2）事先做成数据表格供查表：

省计算时间，但费存储空间N=16DIT-FFT31x[0]x[8]x[4]x[12]x[2]x[10]x[6]x[14]x[1]x[9]x[5]x[13]x[3]x[11]x[7]x[15]x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]x[8]x[9]x[10]x[11]x[12]x[13]x[14]x[15]WN0WN0WN0WN0WN0WN0WN0WN0WN0WN4WN0WN4WN0WN4WN0WN4-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1WN2WN0WN0WN2WN4WN4WN6WN6-1-1-1-1-1-1-1-1WN4WN5WN6WN1WN0WN2WN3WN7-1-1-1-1-1-1-1-1-1327.4实序列的FFT算法1.计算两个N点实序列的N点DFT332.计算一个N点实序列的N点DFT复乘： 复加：347.5IDFT的快速算法方案1：对FFT算法流图加以改动得到IFFT快速算法流图35DIT-FFTIFFT36DIF-FFTIFFT37步骤：（1）X*[k]（2）FFT{}（3）()*/N优点：可直接调用FFT子程序方案2：

利用FFT算法，增加一些预处理和后处理

38方案3：

利用FFT算法，根据DFT的对偶性质

步骤：（1）FFT{X[k]}=g[n]（2）x[n]=g[N-n]/N优点：可直接调用FFT子程序第7章总结397.1 时域抽选FFT算法7.2

频域抽