《数字信号处理时间抽取FFT》由会员分享，可在线阅读，更多相关《数字信号处理时间抽取FFT（41页珍藏版）》请在金锄头文库上搜索。
1、数字信号处理数字信号处理(Digital Signal Processing) 信号与系统系列课程组信号与系统系列课程组 国家电工电子教学基国家电工电子教学基地地1离散傅里叶变换快速算法离散傅里叶变换快速算法(FFT)v问题的提出问题的提出v解决问题的思路与方法解决问题的思路与方法 v基基2时间抽取时间抽取FFT算法算法v基基2频率抽取频率抽取FFT算法算法vFFT算法的实际应用算法的实际应用 实序列的实序列的实序列的实序列的DFTDFT计算，计算，计算，计算，IDFTIDFT的快速计算方法的快速计算方法的快速计算方法的快速计算方法2问题的提出问题的提出4点序列点序列2，3，3，2 DFT的计
2、算复杂度的计算复杂度复数加法复数加法复数加法复数加法N N( (N N- - - -1)1)复数乘法复数乘法复数乘法复数乘法 N N 2如如何何提提高高DFT的的运运算算效效率率?解决问题的思路解决问题的思路1. 1. 将将将将长序列长序列长序列长序列DFTDFT分解为分解为分解为分解为短序列短序列短序列短序列的的的的DFTDFT2. 2. 利用旋转因子利用旋转因子利用旋转因子利用旋转因子 的的的的周期性周期性周期性周期性、对称性对称性对称性对称性、可约性可约性可约性可约性。旋转因子旋转因子 的性质的性质(1) (1) 周期性周期性周期性周期性(2) (2) 对称性对称性对称性对称性(3) (
3、3) 可约性可约性可约性可约性5解决问题的方法解决问题的方法 将时域序列逐次将时域序列逐次将时域序列逐次将时域序列逐次分解分解分解分解为一组为一组为一组为一组子序列子序列子序列子序列，利用，利用，利用，利用旋转因旋转因旋转因旋转因子的特性子的特性子的特性子的特性，由子序列的，由子序列的，由子序列的，由子序列的DFTDFT来实现整个序列的来实现整个序列的来实现整个序列的来实现整个序列的DFTDFT。 基基基基2 2时间抽取时间抽取时间抽取时间抽取(Decimation in time)FFT(Decimation in time)FFT算法算法算法算法 基基基基2 2频率抽取频率抽取频率抽取频率
4、抽取(Decimation in frequency)FFT(Decimation in frequency)FFT算法算法算法算法基基2时间抽取时间抽取FFT算法算法基基基基2 2时间抽取时间抽取时间抽取时间抽取FFTFFT算法推导算法推导算法推导算法推导基基基基2 2时间抽取时间抽取时间抽取时间抽取FFTFFT算法流图算法流图算法流图算法流图基基基基2 2时间抽取时间抽取时间抽取时间抽取FFTFFT算法的计算复杂度算法的计算复杂度算法的计算复杂度算法的计算复杂度基基基基2 2时间抽取时间抽取时间抽取时间抽取FFTFFT算法流图规律算法流图规律算法流图规律算法流图规律基基2时间抽取时间抽取F
5、FT算法推导算法推导基基2时间抽取时间抽取FFT算法推导算法推导因此有因此有:由于X1m 和X2m隐含有周期性，可得基基2时间抽取时间抽取FFT算法推导算法推导1j-1-j基基2时间抽取时间抽取FFT算法的基本关系算法的基本关系基基2时间抽取时间抽取FFT算法流图算法流图N=2xk=x0, x14点基点基2时间抽取时间抽取FFT算法流图算法流图x0x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 3124点基点基2时间抽取时间抽取FFT算法流图算法流图138点基点基2时间抽取时间抽取FFT算法流图算法流图4点DFT4点DFTx0x2x4x6x1x3x
6、5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-1144点DFT4点DFTx0x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基点基2时间抽取时间抽取FFT算法流图算法流图15第一级第一级第一级第一级第二级第二级第二级第二级第三级第三级第三级第三级8点基点基2时间抽取时间抽取FFT算法流图算法流图16算法的计算复杂度算法的计算复杂度复乘次数复乘次数复乘次数复乘次数复乘次数NN 2计算速度的比较计算速度的比较N=1024*4;x =
7、rand(N,1);tic; y1=fft(x); t1=toc; fprintf(nFFT time =%.6en,t1) ;tic; y2=dftmtx(N)*x; t2=toc;fprintf(DFT time =%.6en,t2);fprintf(FFT/DFT =%.6f%n,t1*100/t2);stem(abs(y1-y2), r. ) ; 基基2时间抽取时间抽取FFT算法流图算法流图第一级第一级第一级第一级第二级第二级第二级第二级第三级第三级第三级第三级19FFT算法流图算法流图旋转因子旋转因子 规律规律第二级第二级第二级第二级的蝶形系数为的蝶形系数为的蝶形系数为的蝶形系数为
8、，蝶形节点的距离为，蝶形节点的距离为，蝶形节点的距离为，蝶形节点的距离为2 2。第一级第一级第一级第一级的蝶形系数均为的蝶形系数均为的蝶形系数均为的蝶形系数均为 ，蝶形节点的距离为，蝶形节点的距离为，蝶形节点的距离为，蝶形节点的距离为1 1。第三级第三级第三级第三级的蝶形系数为的蝶形系数为的蝶形系数为的蝶形系数为 ，蝶形，蝶形，蝶形，蝶形节点的距离为节点的距离为节点的距离为节点的距离为4 4。第第第第MM级级级级的蝶形系数为的蝶形系数为的蝶形系数为的蝶形系数为 ，蝶形节点，蝶形节点，蝶形节点，蝶形节点的距离为的距离为的距离为的距离为N N /2 /2。20倒倒 序运算序运算(Bit-rever
9、se Computations)21倒序的实现倒序的实现变址变址A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存储单元存储单元x000x001 x010 x011 x100 x101 x110 x111x000 x100 x010 x110 x001x101 x011 x111自然顺序输入倒序变址变址xk2k1k0存储单元数据不对换存储单元数据对换22原位运算原位运算(In-place Computations)23原位运算原位运算x0x4x2x6x1x5x3x7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)输入序列 存储单元存储单元第一级输出第二级输入第二
10、级输出第三级输入X10X11X20X21X30X31X40X41A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X50X51X52X53X60X61X62X63A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X 0X 1X 2X 3X 4X 5X 6X 7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)第三级输出24例：已知xk=1,2,3,4，利用基2-FFT算法流图计算13244 6-22 j10-2-2+2j-2-2jDFTxk= 10, -2+2j,-2,-2-2j04W14Wx0x3x1x2X3X1X2X0-1-1-1-1例：例：例：例
11、：试利用试利用N=4基基2时间抽取的时间抽取的FFT流图计算流图计算8点序列点序列xk=1, -1, 1, -1, 2, -1, 1,-1的的DFT。解：解：解：解： 根据基根据基2时间抽取时间抽取FFT算法原理，算法原理，8点序列的点序列的DFT Xm可由两个可由两个4点序列的点序列的DFT X1m和和X2m表达。如果表达。如果按照序列按照序列xk序号的奇偶分解为序号的奇偶分解为x1k和和 x2k，则存在，则存在 其中其中 x1k=1, 1, 2, 1， x2k=-1, -1, -1,-1X1m和和X2m可通过可通过4点的点的FFT来计算。来计算。26例：例：例：例：试利用试利用N=4基基2
12、时间抽取的时间抽取的FFT流图计算流图计算8点序列点序列xk=1, -1, 1, -1, 2, -1, 1,-1的的DFT。解：解：解：解： x1k=1, 1, 2, 13-12051-1-1x10=1x12=2x11=1x13=1 X1m=5,- 1, 1,- 127例：试利用例：试利用N=4基基2时间抽取的时间抽取的FFT流图计算流图计算8点序列点序列xk=1, -1, 1, -1, 2, -1, 1,-1的的DFT。 x2k=-1, -1, -1, -1 X2m=-4, 0,0,0 X1m=5,- 1, 1,- 1X0=5+(-4)=1X1= -1+0=-1X2= 1+0=1X3= -1
13、+0=-1X4=5-(-4)=9X5=-1-0= -1X6=1-0= 1X7=-1-0= -1Xm= 1 -1 1 -1 9 -1 1 -128序列补零序列补零,序列插零的序列插零的DFTx1k=1,2,3,4x2k=1,2,3,4,0,0,0,0x3k=1,0,2,0,3,0,4,0DFTx1k=10, -2+2j, -2, -2-2jDFTx2k=10, -0.4142-7.2426j, -2+2j, 2.4142-1.2426j, -2, 2.4142+1.2426j , -2-2j, -0.4142-7.2426jDFTx3k=10, -2+2j, -2, -2-2j, 10, -2+
14、2j, -2, -2-2j基基2时间抽取时间抽取FFT算法的基本关系算法的基本关系基基3时间抽取时间抽取FFT算法的基本关系算法的基本关系基基4时间抽取时间抽取FFT算法的基本关系算法的基本关系任意基时间抽取FFT算法30基基4时间抽取时间抽取FFT算法算法1j-1-j31基基4时间抽取时间抽取FFT算法推导算法推导基基4时间抽取时间抽取FFT算法推导算法推导基基4时间抽取时间抽取FFT算法流图算法流图算法的计算复杂度算法的计算复杂度l基基基基2 2时间抽取时间抽取时间抽取时间抽取FFTFFT复乘次数：复乘次数：复乘次数：复乘次数：l基基基基4 4时间抽取时间抽取时间抽取时间抽取FFTFFT复
15、乘次数：复乘次数：复乘次数：复乘次数：混合基时间抽取混合基时间抽取FFT算法算法 混合基时间抽取混合基时间抽取混合基时间抽取混合基时间抽取FFTFFT算法推导算法推导算法推导算法推导 混合基时间抽取混合基时间抽取混合基时间抽取混合基时间抽取FFTFFT算法流图算法流图算法流图算法流图混合基时间抽取混合基时间抽取FFT算法算法若序列的长度可表示为N=pq，将序列按时间抽取方式分解为p个q点序列则根据时间抽取FFT算法原理可得基p时间抽取FFT算法基本表示式为 分别为其DFT混合基时间抽取混合基时间抽取FFT算法算法混合基时间抽取混合基时间抽取FFT算法算法， 混合基时间抽取混合基时间抽取FFT算法算法， 混合基时间抽取混合基时间抽取FFT流图流图，
