《数字信号处理 教学课件 ppt 作者 张维玺 第4章 快速傅里叶变换》由会员分享，可在线阅读，更多相关《数字信号处理 教学课件 ppt 作者 张维玺 第4章 快速傅里叶变换（53页珍藏版）》请在金锄头文库上搜索。
1、第4章 快速傅里叶变换,4.1 引言 4.2 基-2时域抽选(DIT)FFT算法 4.3 基-2频域抽选(DIF)FFT算法 4.4 离散傅里叶反变换(IDFT)的快速算法 4.5 任意基FFT算法 4.6 调频z变换 4.7 其他的快速计算方法,4.1 引言,离散傅里叶变换实现了频域离散化，它可以直接用来分析信号的频谱、计算滤波器的频率响应，以及实现信号通过线性系统的卷积运算等，在数字信号处理中起着极其重要的作用。但是在其付诸实际应用时却遇到了计算量过于庞大的棘手问题。,4.2 基-2时域抽选(DIT)FFT算法,4.2.1 算法原理 4.2.2 运算特点 4.2.3 矩阵分解表示 4.2.
2、4 编程思想 4.2.5 硬件实现,4.2.1 算法原理,1.基本原理 2.处理过程,1.基本原理,DFT的乘法计算次数与序列的长度有关，复数乘法为N2次，加法为N(N-1)次。如果将N分为两个N2处理，乘法次数将是原来的一半，加法次数也比原来少。 另外由WnkN的周期性和对称性可知,DFT的乘法和加法次数减少就可以提高它的运算速度。,2.处理过程,图4-1 蝶式运算的信号流图,2.处理过程,图4-2 N点DFT一次时域抽选分解,2.处理过程,图4-3 N点DFT第二次时域抽选分解,2.处理过程,图4-4 8点DIT-FFT运算流图,2.处理过程,图4-5 FFT算法与直接计算DFT 所需乘法
3、次数的比较曲线,2.处理过程,图4-6 DIT蝶形,4.2.2 运算特点,1. 同址运算 2.蝶类、蝶距以及旋转因子的变化规律 3.数据重排及倒序二进制数 4.存储单元,1. 同址运算,由图4-4可以看出，DIT-FFT的每轮计算都是把N个存储单元中的复数，经N/2个蝶式运算变成另外N个复数，每个蝶式运算如图4-6所示，且可表达为下述的基本迭代运算。 Am+1(i)=Am(i)+Am+1(j)WkN Am+1(j)=Am(i)-Am+1(j)WkN,2.蝶类、蝶距以及旋转因子的变化规律,再次观察图4-4可以发现，第一轮只有一种类型的蝶形，蝶距为1，旋转因子为W0N。第二轮有两种类型的蝶形，蝶距
4、为2，旋转因子为W0N，W2N。第三轮则有4种类型的蝶形，蝶距为4，系数为W0N，W1N，W2N，W3N。推广到2M的一般情况，第一轮只有一种类型的蝶形，蝶距为1，旋转因子也只有一个W0N，以后每轮的蝶类、蝶距和旋转因子个数都比前列增加一倍，到第M轮时有N/2=2M-1个蝶式类型，蝶距也为N/2，旋转因子的个数也是2M-1= N/2，且为W0N，W1N，WN/2-1N,第L轮旋转因子的通式为 WPN=Wj2L,j=0,1,(2L-1-1),3.数据重排及倒序二进制数,由图4-4可见，对于同址运算结构，其输出结果X(k)是按自然顺序(正序)排列的，即X(0)，X(1)，X(2)，X(3)，,X(
5、N-1)。但输入序列x(n)的排列为x(0),x(4),x(2),x(6)，x(1),，似乎混乱无序，但其实它是很有规律的，谓之倒序排列。,4.存储单元,由于DIT-FFT是同址运算，只需输入序列x(n)(n=0,1,N-1)的N个存储单元，加上系数WrN(r=0,1,N/2-1)的N/2个存储单元，即一共仅需112N个存储单元即可。,4.2.3 矩阵分解表示,如果把DFT用矩阵来表示，那么FFT就相当于矩阵因式分解处理。,4.2.4 编程思想,1.变址(倒序)运算 2.M轮的递推计算,1.变址(倒序)运算,图4-7 雷德算法流程图,2.M轮的递推计算,(1)设N=2M，则共有M轮蝶式运算，每
6、轮有N/2个蝶式。 (2)由最后一轮向前每推进一轮，则旋转因子取后轮旋转因子中偶数序号那一半，第三轮的旋转因子为W0,W1,W2,W3，而第二轮的旋转因子为W0，W2。 (3)蝶距为2L-1，L为所在的轮数，显然，每当向前推进一轮，蝶距就变成原蝶距的一半。,(3)蝶距为2L-1，L为所在的轮数，显然，每当向前推进一轮，蝶距就变成原蝶距的一半。,表4-1 顺序和倒序二进制数对照表(N=8),(3)蝶距为2L-1，L为所在的轮数，显然，每当向前推进一轮，蝶距就变成原蝶距的一半。,图4-8 基2DIT-FFT流程图,4.2.5 硬件实现,1.顺序处理 2.级联处理 3.并行迭代处理 4.阵列处理,1
7、.顺序处理,(1)只用一个运算单元； (2)输入量、中间量、输出量使用同一存储器； (3)顺序执行N/2log2N次蝶式运算，设执行一次蝶式运算需费时TB(s) ，则完成N点FFT计算。,1.顺序处理,图4-9 基-2DIT-FFT算法的蝶式运算,(3)顺序执行N/2log2N次蝶式运算，设执行一次蝶式运算需费时TB(s) ，则完成N点FFT计算。,图4-10 N=8顺序处理的FFT流程图,2.级联处理,(1)用M=log2N个运算单元并行运算； (2)每个运算单元顺序执行N/2次蝶式运算； (3)每轮数据执行运算所需的时间为1/2NTB(s) (4)每个运算单元必须含有延时用的缓冲存储。,3
8、.并行迭代处理,(1)有N/2个处理单元； (2)并行执行N/2个蝶式运算； (3)顺序执行M=log2N次迭代； (4)完成N点FFT所需的时间为log2NTB(s) 。,4.阵列处理,(1)有N/2log2N个运算单元； (2)并行执行N/2log2N个蝶式运算； (3)执行运算的时间是TB(s) (4)由于采用流水线工作方式，使单位时间处理的数据增大了log2N倍，也就是说数据的吞吐率增大了log2N倍。,4.3 基-2频域抽选(DIF)FFT算法,图4-11 DIF-FFT一次分解运算流图(N=8),4.3 基-2频域抽选(DIF)FFT算法,图4-12 DIF-FFT二次分解运算流图
9、(N=8),4.3 基-2频域抽选(DIF)FFT算法,图4-13 DIF-FFT运算流图(N=8),4.4 离散傅里叶反变换(IDFT)的快速算法,(1)求X(k)的共轭X*(k)，取共轭仅需将虚部乘以(-1)，在FORTRAN语言中可直接引用CONJG内部函数，十分方便。 (2)以X*(k)作为输入序列，直接调用FFT子程序，计算得到Nx*(n)。 (3)对运算结果取共轭并乘以1/N即得到x(n)。,4.4 离散傅里叶反变换(IDFT)的快速算法,图4-14 DIT-IFFT运算流图,4.5 任意基FFT算法,4.5.1 抽选分解的一般原理 4.5.2 基-4DIF-FFT算法,4.5.1
10、 抽选分解的一般原理,cr(2)=Nlog2N。,4.5.2 基-4DIF-FFT算法,如果N=4444=4r就成为基-4FFT算法，在每步分解时，根据N=4q和N=q4的不同，可以分别得到DIT或DIF算法，由于基-4DIT-FFT算法的误差性能优于基-4DIF-FFT算法，故前者获得更多的应用。,4.6 调频z变换,4.6.1 问题的提出 4.6.2 算法原理 4.6.3 CZT的实现步骤 4.6.4 CZT运算量的估算 4.6.5 CZT算法的特点,4.6.1 问题的提出,上面介绍的N点DFT的快速算法，即有限长序列x(n)的z变换X(z)，在z平面单位圆上等间隔取样点zk处的取样值X(
11、zk)的快速算法，它要求为高度复合的数。,4.6.2 算法原理,(1)A0表示起始取样点z0的矢量半径长度，通常A01，否则z0将处于单位圆z=1的外部。 (2)z0表示起始取样点z0的相角(即角频率)，它可是正值或负值。 (3)zk表示两相邻zk点之角频率差，它也可是正值或负值。 (4)W0的大小控制着周线盘旋是向内弯曲还是向外弯曲。,4.6.2 算法原理,图4-15 线性调频z变换的z平面周线,(4)W0的大小控制着周线盘旋是向内弯曲还是向外弯曲。,1) M=N; 2) A=A0 =1(即A0=1，0=0); 3)W=W0= (即W0=1，0=2/M=2/N)时，就恢复到zk是均匀地等角度
12、分布于全部|z|=1单位圆上的情况，即变为求该序列的DFT。,图4-16 CZT的运算流程,4.6.3 CZT的实现步骤,(1)根据已知的A(=A0 )和W(=W0)，即由已知的A0， W0求出A-nW,(0nN-1)的各值，将这些数值与欲分析的信号x(n)( 0nN-1)相乘，即得g(n), 0nN-1。 (2)选择一个最小的L，使其满足L(N+M-1)同时又满足L=2m，以便用基-2FFT算法来求得g(n)与h(n)的卷积。 (3)采用补零的方法将(1)中所得的g(n)变为列长为L的序列 (4)为了使g(n)与h(n)的圆周卷积与g(n)、h(n)的线性卷积等效，并且根据要求，只对k=0，
13、M-1范围的卷积结果感兴趣，这样就要把h(n)取出适当的一段注意，式(4-42)的序列长度并未明确规定，只是规定了其函数关系为h(n)=。 (5)将列长为L的二序列F(r)和H(r)逐点相乘所得到的是列长仍为L的序列G(r)=,如图4-17g所示。,4.6.3 CZT的实现步骤,(6)根据式(4-43)，将所得的g(k),0kM-1,乘以系数W，即得所要求的M个值如图4-17i所示。,(3)采用补零的方法将(1)中所得的g(n)变为列长为L的序列,图4-17 CZT的波形,4.6.4 CZT运算量的估算,(1)形成g(n)=A-nx(n)(0nN-1)需要N次复乘。 (2)由g(n)求F(r)
14、需作L点FFT,约需L/2log2L次复乘运算。 (3)h(n)可用(1)中所述方法递推求得,则由h(n)用FFT方法计算H(r)需要L/2log2L次复乘。 (4)F(r)与H(r)相乘需要L次复乘运算。 (5)由G(r)进行快速傅里叶逆变换需要L/2log2L次复乘。 (6)形成M点的输出X(zk)=g(k)(0kM-1),需做M次复乘。,4.6.5 CZT算法的特点,(1) 输入序列列长N及输出序列列长M不需要相等； (2) N及M不必是高度合成数，二者均可为素数； (3)zk点的角间隔是任意的，因此频率分辨率也是任意的； (4) 周线不必是z平面上的圆，在信号分析中螺旋形周线具有某些优
15、点； (5) 起始点z0可任意选定，因此可从任意频率上开始对输入数据进行窄带的高分辨率的分析； (6) 若A=1,M=N,W=,则可用CZT来计算DFT，即使N为素数时也可以。,4.7 其他的快速计算方法,4.7.1 重叠相加法 4.7.2 重叠保留法 4.7.3 线性卷积的FFT算法,4.7.1 重叠相加法,(1)计算L点的FFT：H(k)=DFTh(n)； (2)计算L点的FFT：Xi(k)=DFTXi(n)； (3)计算Yi(k)=H(k)Xi(k)； (4) 计算L点的IFFT：Yi(n)=IDFTYi(k)； (5)计算各段和y(n)=i=0yi(n)。,4.7.1 重叠相加法,（4-52）,4.7.2 重叠保留法,(1)先将X(n)分解为 (2)用FFT计算出yi(n)=Xi(n)*h(n)； (3)抛弃yi(n)的前N1-1点； (4)将yi(n)顺序连接起来得到输出序列y(n)。,4.7.3 线性卷积的FFT算法,(1)计算L点的FFT: (2) 计算L点的FFT：X(k)=DFTx(n); (3)计算Y(k)=H(k)X(k); (4)计算L点的IFFT： y(n)=IDFTY(k)。,4.7.3 线性卷积的FFT算法,（4-54）,
