数字信号处理-时间抽取FFT算法课件

数字信号处理

(DigitalSignalProcessing)

信号与系统系列课程组国家电工电子教学基地数字信号处理

(DigitalSignalProcess离散傅里叶变换快速算法(FFT)问题的提出解决问题的思路与方法基2时间抽取FFT算法基2频率抽取FFT算法FFT算法的实际应用——

实序列的DFT计算，IDFT的快速计算方法离散傅里叶变换快速算法(FFT)问题的提出时间抽取FFT问题的提出4点序列{2，3，3，2}DFT的计算复杂度复数加法N(N-1)复数乘法N

2如何提高DFT的运算效率?时间抽取FFT问题的提出4点序列{2，3，3，2}DFT的时间抽取FFT解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子的周期性、对称性、可约性。时间抽取FFT解决问题的思路1.将长序列DFT分解为短序旋转因子的性质(1)周期性(2)对称性(3)可约性旋转因子的性质(1)周期性(2)对时间抽取FFT解决问题的方法

将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。

基2时间抽取(Decimationintime)FFT算法

基2频率抽取(Decimationinfrequency)FFT算法时间抽取FFT解决问题的方法将时域序列逐次分时间抽取FFT基2时间抽取FFT算法基2时间抽取FFT算法推导基2时间抽取FFT算法流图基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律时间抽取FFT基2时间抽取FFT算法基2时间抽取FFT算法推时间抽取FFT基2时间抽取FFT算法推导时间抽取FFT基2时间抽取FFT算法推导时间抽取FFT基2时间抽取FFT算法推导因此有:由于X1[m]和X2[m]隐含有周期性，可得时间抽取FFT基2时间抽取FFT算法推导因此有:由于X1[m时间抽取FFT基2时间抽取FFT算法推导1j-1-j基2时间抽取FFT算法的基本关系时间抽取FFT基2时间抽取FFT算法推导1j-1-j基2时间时间抽取FFT基2时间抽取FFT算法流图N=2x[k]={x[0],x[1]}时间抽取FFT基2时间抽取FFT算法流图N=2x[k]={x4点基2时间抽取FFT算法流图x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFT-1-1-1-1X

[0]X

[1]X

[2]X

[3]4点基2时间抽取FFT算法流图x[0]x[2]x[1]x[34点基2时间抽取FFT算法流图4点基2时间抽取FFT算法流图8点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-18点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-18点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]第一级第二级第三级8点基2时间抽取FFT算法流图第一级第二级第三级8点基2时间抽取FFT算法流图时间抽取FFT算法的计算复杂度复乘次数复乘次数NN2时间抽取FFT算法的计算复杂度复乘次数复乘次数NN2时间抽取FFT计算速度的比较N=1024*4;x=rand(N,1);tic;y1=fft(x);t1=toc;fprintf('\nFFTtime=%.6e\n',t1);tic;y2=dftmtx(N)*x;t2=toc;fprintf('DFTtime=%.6e\n',t2);fprintf('FFT/DFT=%.6f%%\n',t1*100/t2);stem(abs(y1-y2),'r.');时间抽取FFT计算速度的比较N=1024*4;基2时间抽取FFT算法流图第一级第二级第三级基2时间抽取FFT算法流图第一级第二级第三级FFT算法流图旋转因子规律第二级的蝶形系数为，蝶形节点的距离为2。第一级的蝶形系数均为，蝶形节点的距离为1。第三级的蝶形系数为，蝶形节点的距离为4。第M级的蝶形系数为，蝶形节点的距离为N/2。FFT算法流图旋转因子规律第二级的蝶形系数为倒序运算(Bit-reverseComputations)倒序运算(Bit-reverseComputations倒序的实现——变址A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存储单元x[000]x[001]x[010]x[011]x[100]x[101]x[110]x[111]x[000]x[100]x[010]x[110]x[001]x[101]x[011]x[111]自然顺序输入倒序变址x[k2k1k0]存储单元数据不对换存储单元数据对换倒序的实现——变址A(1)存储单元x[000]x[000]原位运算(In-placeComputations)原位运算(In-placeComputations)原位运算x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)输入序列存储单元第一级输出第二级输入第二级输出第三级输入X1[0]X1[1]X2[0]X2[1]X3[0]X3[1]X4[0]X4[1]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X5[0]X5[1]X5[2]X5[3]X6[0]X6[1]X6[2]X6[3]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)第三级输出原位运算x[0]A(1)输入序列存储单元第一级输出第二级输入时间抽取FFT例：已知x[k]={1,2,3,4}，利用基2-FFT算法流图计算132446-22j10-2-2+2j-2-2jDFT{x[k]}={10,-2+2j,-2,-2-2j}04W14Wx[0]x[3]x[1]x[2]X[3]X[1]X[2]X[0]-1-1-1-1时间抽取FFT例：已知x[k]={1,2,3,4}，利用基2例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。解：

根据基2时间抽取FFT算法原理，8点序列的DFTX[m]可由两个4点序列的DFTX1[m]和X2[m]表达。如果按照序列x[k]序号的奇偶分解为x1[k]和

x2[k]，则存在

其中

x1[k]={1,1,2,1}，

x2[k]={-1,-1,-1,-1}X1[m]和X2[m]可通过4点的FFT来计算。例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。解：

x1[k]={1,1,2,1}3-12051-1-1x1[0]=1x1[2]=2x1[1]=1x1[3]=1X1[m]={5,-1,1,-1}例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。x2[k]={-1,-1,-1,-1}X2[m]={-4,0,0,0}X1[m]={5,-1,1,-1}X[0]=5+(-4)=1X[1]=-1+0=-1X[2]=1+0=1X[3]=-1+0=-1X[4]=5-(-4)=9X[5]=-1-0=-1X[6]=1-0=1X[7]=-1-0=-1X[m]={1-11-19-11-1}例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]时间抽取FFT序列补零,序列插零的DFTx1[k]={1,2,3,4}x2[k]={1,2,3,4,0,0,0,0}x3[k]={1,0,2,0,3,0,4,0}DFT{x1[k]}={10,-2+2j,-2,-2-2j}DFT{x2[k]}={10,-0.4142-7.2426j,-2+2j,2.4142-1.2426j,-2,2.4142+1.2426j,-2-2j,-0.4142-7.2426j}DFT{x3[k]}={10,-2+2j,-2,-2-2j,10,-2+2j,-2,-2-2j}时间抽取FFT序列补零,序列插零的DFTx1[k]={1,2基2时间抽取FFT算法的基本关系基3时间抽取FFT算法的基本关系基4时间抽取FFT算法的基本关系任意基时间抽取FFT算法基2时间抽取FFT算法的基本关系基3时间抽取FFT算法的基本基4时间抽取FFT算法1j-1-j基4时间抽取FFT算法1j-1-j时间抽取FFT基4时间抽取FFT算法推导时间抽取FFT基4时间抽取FFT算法推导时间抽取FFT基4时间抽取FFT算法推导时间抽取FFT基4时间抽取FFT算法推导时间抽取FFT基4时间抽取FFT算法流图时间抽取FFT基4时间抽取FFT算法流图时间抽取FFT算法的计算复杂度基2时间抽取FFT复乘次数：基4时间抽取FFT复乘次数：时间抽取FFT算法的计算复杂度基2时间抽取FFT复乘次数：基时间抽取FFT混合基时间抽取FFT算法

混合基时间抽取FFT算法推导混合基时间抽取FFT算法流图时间抽取FFT混合基时间抽取FFT算法混合基时间抽取FFT时间抽取FFT混合基时间抽取FFT算法若序列的长度可表示为N=pq，将序列按时间抽取方式分解为p个q点序列则根据时间抽取FFT算法原理可得基p时间抽取FFT算法基本表示式为

分别为其DFT时间抽取FFT混合基时间抽取FFT算法若序列的长度可表示为N时间抽取FFT混合基时间抽取FFT算法时间抽取FFT混合基时间抽取FFT算法时间抽取FFT混合基时间抽取FFT算法，时间抽取FFT混合基时间抽取FFT算法，时间抽取FFT混合基时间抽取FFT算法，时间抽取FFT混合基时间抽取FFT算法，时间抽取FFT混合基时间抽取FFT流图，时间抽取FFT混合基时间抽取FFT流图，数字信号处理

(DigitalSignalProcessing)

信号与系统系列课程组国家电工电子教学基地数字信号处理

(DigitalSignalProcess离散傅里叶变换快速算法(FFT)问题的提出解决问题的思路与方法基2时间抽取FFT算法基2频率抽取FFT算法FFT算法的实际应用——

实序列的DFT计算，IDFT的快速计算方法离散傅里叶变换快速算法(FFT)问题的提出时间抽取FFT问题的提出4点序列{2，3，3，2}DFT的计算复杂度复数加法N(N-1)复数乘法N

2如何提高DFT的运算效率?时间抽取FFT问题的提出4点序列{2，3，3，2}DFT的时间抽取FFT解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子的周期性、对称性、可约性。时间抽取FFT解决问题的思路1.将长序列DFT分解为短序旋转因子的性质(1)周期性(2)对称性(3)可约性旋转因子的性质(1)周期性(2)对时间抽取FFT解决问题的方法

将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。

基2时间抽取(Decimationintime)FFT算法

基2频率抽取(Decimationinfrequency)FFT算法时间抽取FFT解决问题的方法将时域序列逐次分时间抽取FFT基2时间抽取FFT算法基2时间抽取FFT算法推导基2时间抽取FFT算法流图基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律时间抽取FFT基2时间抽取FFT算法基2时间抽取FFT算法推时间抽取FFT基2时间抽取FFT算法推导时间抽取FFT基2时间抽取FFT算法推导时间抽取FFT基2时间抽取FFT算法推导因此有:由于X1[m]和X2[m]隐含有周期性，可得时间抽取FFT基2时间抽取FFT算法推导因此有:由于X1[m时间抽取FFT基2时间抽取FFT算法推导1j-1-j基2时间抽取FFT算法的基本关系时间抽取FFT基2时间抽取FFT算法推导1j-1-j基2时间时间抽取FFT基2时间抽取FFT算法流图N=2x[k]={x[0],x[1]}时间抽取FFT基2时间抽取FFT算法流图N=2x[k]={x4点基2时间抽取FFT算法流图x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFT-1-1-1-1X

[0]X

[1]X

[2]X

[3]4点基2时间抽取FFT算法流图x[0]x[2]x[1]x[34点基2时间抽取FFT算法流图4点基2时间抽取FFT算法流图8点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-18点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-18点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]第一级第二级第三级8点基2时间抽取FFT算法流图第一级第二级第三级8点基2时间抽取FFT算法流图时间抽取FFT算法的计算复杂度复乘次数复乘次数NN2时间抽取FFT算法的计算复杂度复乘次数复乘次数NN2时间抽取FFT计算速度的比较N=1024*4;x=rand(N,1);tic;y1=fft(x);t1=toc;fprintf('\nFFTtime=%.6e\n',t1);tic;y2=dftmtx(N)*x;t2=toc;fprintf('DFTtime=%.6e\n',t2);fprintf('FFT/DFT=%.6f%%\n',t1*100/t2);stem(abs(y1-y2),'r.');时间抽取FFT计算速度的比较N=1024*4;基2时间抽取FFT算法流图第一级第二级第三级基2时间抽取FFT算法流图第一级第二级第三级FFT算法流图旋转因子规律第二级的蝶形系数为，蝶形节点的距离为2。第一级的蝶形系数均为，蝶形节点的距离为1。第三级的蝶形系数为，蝶形节点的距离为4。第M级的蝶形系数为，蝶形节点的距离为N/2。FFT算法流图旋转因子规律第二级的蝶形系数为倒序运算(Bit-reverseComputations)倒序运算(Bit-reverseComputations倒序的实现——变址A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存储单元x[000]x[001]x[010]x[011]x[100]x[101]x[110]x[111]x[000]x[100]x[010]x[110]x[001]x[101]x[011]x[111]自然顺序输入倒序变址x[k2k1k0]存储单元数据不对换存储单元数据对换倒序的实现——变址A(1)存储单元x[000]x[000]原位运算(In-placeComputations)原位运算(In-placeComputations)原位运算x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)输入序列存储单元第一级输出第二级输入第二级输出第三级输入X1[0]X1[1]X2[0]X2[1]X3[0]X3[1]X4[0]X4[1]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X5[0]X5[1]X5[2]X5[3]X6[0]X6[1]X6[2]X6[3]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)第三级输出原位运算x[0]A(1)输入序列存储单元第一级输出第二级输入时间抽取FFT例：已知x[k]={1,2,3,4}，利用基2-FFT算法流图计算132446-22j10-2-2+2j-2-2jDFT{x[k]}={10,-2+2j,-2,-2-2j}04W14Wx[0]x[3]x[1]x[2]X[3]X[1]X[2]X[0]-1-1-1-1时间抽取FFT例：已知x[k]={1,2,3,4}，利用基2例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。解：

根据基2时间抽取FFT算法原理，8点序列的DFTX[m]可由两个4点序列的DFTX1[m]和X2[m]表达。如果按照序列x[k]序号的奇偶分解为x1[k]和

x2[k]，则存在

其中

x1[k]={1,1,2,1}，

x2[k]={-1,-1,-1,-1}X1[m]和X2[m]可通过4点的FFT来计算。例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。解：

x1[k]={1,1,2,1}3-12051-1-1x1[0]=1x1[2]=2x1[1]=1x1[3]=1X1[m]={5,-1,1,-1}例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。x2[k]={-1,-1,-1,-1}X2[m]={-4,0,0,0}X1[m]={5,-1,1,-1}X[0]=5+(-4)=1X[1]=-1+0=-1X[2]=1+0=1X[3]=-1+0=-1X[4]=5-(-4)=9X[5]=-1-0=-1X[6]=1-0=1X[7]=-1-0=-1X[m]={1-11-19-11-1}例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]时间抽