信号分析与处理(第3版) 课件 第3章3.3FFT-3.4

信号分析与处理SignalAnalysisandProcessing

第3章

离散傅里叶变换和快速傅里叶变换主

要

内

容1、连续时间信号的傅里叶变换2、离散傅里叶变换及性质3、快速傅里叶变换第3章DFT和FFT4、与本章内容有关的MATLAB函数四种变换前节知识回顾DTFT是单位圆上的z变换。DFS是DTFT单位圆上的N点等间隔采样。DFT是DFS的一个周期z变换：DTFT：DFSDFT：DFT应用中的问题现象原因改善措施混叠现象当fs<2fm时，采样信号的频谱中周期延拓分量相互重叠。离散采样引起的采样频率足够高，fs>>2fm。考虑频率分辨率

∆f=fs/N。频谱泄漏时域窗函数截断后，频谱发生了拖尾现象。时域截断引起的增加采样点数N或采用合适的窗函数。栅栏效应离散的频谱，仿佛透过“栅栏”看风景。离散采样引起的增加频域采样点数N，先加窗再补零。前节知识回顾1.已知

；x(n)的傅里叶变换为X(ejω)，则=（

）2π5π19π38πABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为D利用DTFT的性质：Pasavel定理答案解析单选题10分2、非周期序列对应的频谱特点是()连续周期连续非周期离散周期离散非周期ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为A。一个域的连续对应另一个域的非周期,一个域的离散对应另一个域的周期。DTFT:时域：非周期离散频域：连续周期答案解析单选题10分3、周期序列对应的频谱特点是()连续周期连续非周期离散周期离散非周期ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为C。一个域的连续对应另一个域的非周期,一个域的离散对应另一个域的周期。DFS:时域：周期离散频域：离散周期答案解析单选题10分4、序列x(n)=R6(n)，其16点DFT记为X(k)，k=0,1,…,15，则X(0)为(

)。11656ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为D。答案解析单选题10分5、已知有限长序列：x(n)=δ(n-2)+3δ(n-4)，那么它的8点DFT结果X(k)是（

）ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为B答案解析单选题10分6、某序列的频谱

，该序列的8点DFT中的X(4)=（

）。1/332/33/2ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为CX(z)、DTFT和DFT之间的关系答案解析单选题10分7、已知x(n)=δ(n)，N点的DFT[x(n)]=X(k)，则X(3)=()。N10-NABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为B。答案解析单选题10分8、利用离散傅里叶变换(DFT)来计算信号频谱时，时域的截断会造成()现象。频谱泄露时域混叠谱间干扰频谱混叠ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为A。频谱泄露是由截断引起的。答案解析答案解析答案解析答案解析单选题10分9、序列x(n)长度为M，当频率采样点数N<M时，由频率采样X(k)恢复原序列时会产生()现象。频谱泄露时域混叠谱间干扰频谱混叠ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为B。当频率采样点数N<M时,不满足采样定理，时域会发生混叠现象。答案解析答案解析答案解析答案解析单选题10分ABCD提交10、已知

求x(n)与h(n)的6点循环卷积。（

）可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案是A6点循环卷积=线性卷积x(n)={1,-1,3}h(n)={1,2,2,3}x(n)*h(n)={1,1,3,7,3,9}答案解析单选题10分FFT并不是一种新的变换形式，它只是DFT的一种快速算法。并且根据对序列分解与选取方法的不同而产生了FFT的多种算法。时间抽取基-2FFT算法频率抽取基-2FFT算法FFT的基本思想DFT：计算一个x(k)值，计算量：N次复数乘法和N-1次复数加法要完成整个DFT运算，其计算量为：N×N次复数相乘，N×(N-1)次复数加法DFT的计算量对称性周期性可约性特殊点

的性质设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。其中基数2----N=2M，M为整数。若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到N=2M。时间抽取基-2FFT算法（DIT）设序列点数N=2M，M

为整数。若不满足，则补零。N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：算法推导x(n)的DFT一个N点的DFT被分解为两个N/2点DFT。X1(k)，X2(k)这两个N/2点的DFT按照：这是N点DFT中的前半部分。再应用W系数的周期性，求出用X1(k)，X2(k)表达的后半部的X(k+N/2)的值。前半部分X1(k)，X2(k)是以N/2为周期的，后半部分后半部的k值所对应的X1(k)、X2(k)则完全重复了前半部分的k值所对应的X1(k)、X2(k)的值。频域中的N个点频率成分为：-1前半部分：后半部分：结论：只要求出（0~N/2-1）区间内的各个整数k值所对应的X1(k)、X2(k)值，即可以求出(0~N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。由于N=2^L，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。-1即蝶式计算结构，也即为蝶式信号流图。上面频域中前/后半部分表示式可以用蝶形信号流图表示。蝶形结作图要素：(1)左边两路为输入(2)右边两路为输出(3)中间以一个小圆表示加、减运算（右上路为相加输出、右下路为相减输出)(4)如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。(5)当支路上没有箭头及系数时，则该支路的传输比为1。.（1）先按N=8→N/2=4，做4点的DFT：举例：求N=8的FFT将N=8的DFT分解成2个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列

x(1),x(3),x(5),x(7)为奇子序列

频域上：X(0)~X(3)，由X(k)给出

X(4)~X(7)，由X(k+N/2)给出前半部分后半部分8点：2个4点DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)x1(r)x2(r)(2)N/2(4点)-->N/4(2点)FFT

a、先将4点分解成2点的DFT：因为4点DFT还是比较麻烦，所以再继续分解。若将N/2(4点)子序列按奇/偶分解成两个N/4点（2点）子序列。即对将x1(r)和x2(r)分解成奇、偶两个N/4点（2点）点的子序列。b、求2点的DFT4点：2个2点DFT2点：2个1点DFT(3)将N/4（2点）DFT再分解成2个1点的DFT

(4)一个完整N=8的按时间抽取FFT的运算流图

FFT：N=2M，流图中共有M级蝶形，每一级有N/2个蝶形。每个蝶形需要一次复数乘法和两次复数加法，所以每一级运算都需要N/2次复数乘法和N次复数加法。M级运算总共需要的复数乘次数为：

复数加次数为：FFT的计算量例如，N=210=1024时运算效率提高200多倍计算量比较对于N=2M，FFT分级的级数：每级蝶形算子个数：N/2蝶形算子的总个数：总的复数乘法：总的复数加法：FFT小结原位运算（in-place)、同址运算码位倒序规则FFT算法的特点原位运算（in-place)、同址运算m表示第m级迭代，p，q表示数据所在的行数FFT算法的特点——同址运算-1分级运算、同址运算举例：N=8FFT运算，

暂存器x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)=X(0)A(1)=X(1)A(2)=X(2)A(3)=X(3)A(4)=X(4)A(5)=X(5)A(6)=X(6)A(7)=X(7)R1R1R1R1R1R2R1R1R2R2R3R4看出：用原位运算结构后，A(0)…A(7)正好顺序存放X(0)…X(7)，可以直接顺序输出。举例我们从输入序列的序号及整序规律得到码位倒读规则。由N=8蝶形图看出：原位计算时，FFT输出的X(k)的次序正好是顺序排列的，即X(0)…X(7)，但输入x(n)都不能按自然顺序存入到存储单元中，而是按x(0),x(4),(2),x(6)….的顺序存入存储单元即为乱序输入，顺序输出。这种顺序看起来相当杂乱，然而它是有规律的。即码位倒读规则。FFT算法的特点——码位倒序规则01234567000001010011100101110111自然顺序二进制码表示码位倒读码位倒置顺序00010001011000110101111104261537看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。举例倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n200011011001101举例1、在DIT基-2FFT算法中，下列关于

的关系式，其中正确的是（）ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为C。答案解析单选题10分2、64点的基2-FFT算法流图中共有（

)个蝶形运算。664192384ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为CM级运算，每一级含有N/2个蝶形单元。64点：6级，每级有32个，共6*32=192个蝶形单元答案解析单选题10分算法原理：设序列点数N=2M，M为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半。频率抽取基2-FFT相同之处

DIF与DIT两种算法均为原位运算。

DIF与DIT运算量相同。运算量：复数乘法：复数加法：DIT和DIF是两种等价的FFT算法。DIT和DIF的比较不同之处DIF与DIT两种算法结构倒过来DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。蝶形结不同DIT的复数相乘出现在减法之前。DIF的复数相乘出现在减法之后。

DIT和DIF的比较3、一般来说，按时间抽取基2-FFT的（

）序列是按位反转重新排列的。输入输出输入和输出输入和输出都不是ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为A。按时间抽取基二FFT:乱序输入，顺序输出。答案解析单选题10分以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速傅里叶反变换。从IDFT的定义出发，可以导出下列两种利用FFT来计算IFFT的方法。IFFT（1）只要把DFT运算中的每个系数（2）将运算结果都除以N（3）以上讨论的时间抽取或频率抽取FFT算法都可以拿来运算IDFT利用FFT计算IFFT的思路1把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k)，原来按x(n)的奇、偶次序分组的时间抽取法FFT，现在就变成了按X(k)的奇偶次序抽取了。同样，频率抽取的FFT运算用于IDFT运算时，也应改变为时间抽取的IFFT。利用FFT计算IFFT的思路2此为DFT，可用FFT程序共轭FFT共轭乘1/N直接调用FFT子程序计算IFFT的方法：FFT的应用——快速卷积分段卷积重叠相加法举例FFT的应用——快速相关4、两个时域序列长度都是50，如果想用基2快速卷积计算两个序列的线性卷积，快速卷积的点数应该选择（）点？506499128ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为D。50+50-1=99，快速卷积点数是2的整数次幂，所以128点。答案解析单选题10分1、对于N=2M，FFT分级的级数：每级蝶形算子个数：N/2蝶形算子的总个数：课堂小结2、FFT算法特点：原位运算、同址运算码位倒序规则3、FFT应用：快速卷积快速相关知识延伸及反思1、FFT的基本思想是什么？你是怎样理解的？2、如果用FFT实现线性卷积，所需要的运算量是多少？和直接计算线性卷积的计算量相比是否有优势？3、试着利用MATLAB工具来验证今天所学的内容。作业：P127习题3.15主

要

内

容1、连续时间信号的傅里叶变换2、离散傅里叶变换及性质3、快速傅里叶变换第3章DFT和FFT4、与本章内容有关的MATLAB函数fftfilty=fftfilt(h,x)fftX=fft(x),X=fft(x,N)ifft

MATLAB函数例：已知信号

，求N点DFT的幅值谱和相位谱。

％M文件如下：N=64;