信号分析与处理(第3版) 课件 第3章 离散傅里叶变换和快速傅里叶变换

信号分析与处理SignalAnalysisandProcessing

第3章

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

要

内

容1、连续时间信号的傅里叶变换2、离散傅里叶变换及性质3、快速傅里叶变换第3章DFT和FFT4、与本章内容有关的MATLAB函数主

要

内

容1、连续时间信号的傅里叶变换2、离散傅里叶变换及性质3、快速傅里叶变换第3章DFT和FFT4、与本章内容有关的MATLAB函数信号以时间为自变量频谱函数以频率为自变量傅里叶变换逆傅里叶变换一种映射4连续时间信号的傅里叶变换周期信号与离散频谱

时间连续、频率离散周期连续时间信号

非周期离散频谱密度函数傅里叶级数FS时域：连续、周期频域：非周期、离散时间连续、频率离散通过变换对可以看出时域的连续函数造成频域是非周期的频谱函数，而频域的离散频谱就与时域的周期时间函数对应。(频域采样，时域周期延拓)例题讲解非周期信号与连续频谱非周期连续时间信号

非周期连续频谱密度函数傅里叶变换FT时间连续、频率连续时域：连续、非周期频域：非周期、连续例题讲解以上变换对可以看出时域连续函数造成频域是非周期的谱，而时域的非周期造成频域是连续的谱。FT主

要

内

容1、连续时间信号的傅里叶变换2、离散傅里叶变换及性质第3章DFT和FFT2.1、序列的傅里叶变换2.2、离散傅里叶变换2.3、离散傅里叶变换的性质2.4、DFT在应用中的问题定义正变换：序列的傅里叶变换（DTFT）反变换：DTFT与Z变换的关系序列的傅里叶变换（DTFT）勤于动脑，善于思考，勇于探索，敢于创造序列的傅里叶变换就是单位圆上的Z变换

时域的离散造成频域的周期延拓，而时域的非周期对应于频域的连续。0nx(n)02π2π-2πω序列的傅里叶变换（DTFT）实际频率角频率圆周频率归一化频率00001-11/2-1/2四种频率频率间的换算关系时域卷积特性频域卷积特性频率响应Parseval定理DTFT的性质线性变换时移特性频移特性周期性P94表3.2.1DTFT的主要性质DTFT是一个线性变换。线性变换证明：时移特性证明：频移特性证明：周期性DTFT是ω的周期函数，周期是2π证明：注意：连续信号的傅氏变换不是周期函数。推论：因此，在我们分析时，只需要知道

的一个周期（即：

或

）即可，而不需要在整个

域来分析。时域卷积特性时域内的卷积关系映射到频域内为相乘时域卷积频域乘积利用这一性质，可以方便地把时域内的卷积计算，化简到频域内的相乘计算。证明：频域卷积特性时域内的相乘关系映射为频域内的卷积时域乘积频域卷积证明：LTI系统的频率响应LTI系统的输入、输出关系：称为系统的频率响应，是单位采样序列h(n)的傅氏变换。例题讲解例：求下列差分方程所表示的滤波器的频率响应表达式解：对每一项都进行DTFT变换，得频率响应为：Parseval定理证明：变换前后能量保持不变信号在时域的总能量等于其在频域的总能量。解：P96页例题讲解例：设矩形窗

若，求系统的频率响应-同样可看出，时域的离散造成频域的周期延拓，而时域的非周期对应于频域的连续。

%求非周期序列x(n)=(0.8)^nu(n)的频率响应X(e^(jw))，化简得X(e^(jw))=e^(jw)/(e^(jw)-0.8)w=[0:5000]*5*pi/5000;%将[0,5pi]区间分成5000份X=exp(j*w)./(exp(j*w)-0.8*ones(1,5001));%计算频率响应magX=abs(X);%幅频响应subplot(2,1,1)plot(w,magX);grid;title('幅频响应');xlabel('频率');ylabel('幅度');angX=angle(X);%相频响应subplot(2,1,2)plot(w,angX);grid;title('相频响应');xlabel('频率');ylabel('相位');MATLAB画图1、下列关于序列的傅里叶变换描述正确的是()对应的频谱是离散的。是单位圆上的Z变换。对应的频谱是非周期的。是单位圆内的Z变换。ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为B。序列的傅里叶变换DTFT是单位圆上的Z变换。DTFT的时域：离散非周期频域：周期连续答案解析单选题10分1、x(n)的傅里叶变换为

，请求出下列序列的傅里叶变换：（1）

（2）2、已知n=[-3，-2，-1，0，1，2，3，4，5，6，7]，x(n)=[-1，0，1，2，1，0，1，2，1，0，-1]；已知x(n)的傅里叶变换为

，请完成下列计算：（1）（2）作答正常使用主观题需2.0以上版本雨课堂可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本解：答案解析主观题100分

时域频域连续非周期

非周期连续傅里叶变换（FT）连续周期

非周期离散 傅里叶级数（FS)离散非周期

周期连续

序列的傅里叶变换（DTFT)傅里叶变换形式课堂小结DTFT的性质灵活运用！DTFT：1、连续信号的傅里叶变换和DTFT、Z变换之间有怎样的联系？你是怎样理解的？2、通过本节课的学习，让我们了解到科学研究需要不断思考，不断探索才能得以进步。在生活和学习、科研过程中，学生们怎样锻炼自己？培养自己勤于动脑，善于思考，勇于探索，敢于创造的科研精神？3、试着证明一下DTFT的其它性质，并利用MATLAB工具来验证今天所学的内容。知识延伸及反思作业：P126习题3.2信号分析与处理SignalAnalysisandProcessing

第3章

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

要

内

容1、连续时间信号的傅里叶变换2、离散傅里叶变换及性质第3章DFT和FFT2.1、序列的傅里叶变换2.2、离散傅里叶变换2.3、离散傅里叶变换的性质2.4、DFT在应用中的问题

时域频域连续非周期

非周期连续傅里叶变换（FT）连续周期

非周期离散 傅里叶级数（FS)离散非周期

周期连续

序列的傅里叶变换（DTFT)傅里叶变换形式前节内容回顾DTFT的性质灵活运用！DTFT：1、x(n)的傅里叶变换为

，请求出下列序列的傅里叶变换：（1）

（2）2、已知n=[-3，-2，-1，0，1，2，3，4，5，6，7]，x(n)=[-1，0，1，2，1，0，1，2，1，0，-1]；已知x(n)的傅里叶变换为

，请完成下列计算：（1）（2）作答正常使用主观题需2.0以上版本雨课堂可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本解：答案解析主观题100分1.已知x(n)={-1，0，1，2，1，0，1，2，1，0，-1}，-3≤n≤7；已知x(n)的傅里叶变换为X(ejω)，则=（

）2π6π20π28πABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为D利用DTFT的性质：Pasavel定理答案解析单选题10分时域：连续、周期频域：非周期、离散连续周期信号：FS连续非周期信号：FT时域：连续、非周期频域：非周期、连续离散非周期序列：DTFTx(nT)T-T0T2Tt0------时域：离散、非周期频域：周期、连续

但是，这三种傅里叶变换对都不适于计算机上运算，因为它们至少在一个域（时域或频域）中函数是连续的。 因此，我们感兴趣的是时域和频域都是离散的情况。

时域频域离散周期周期离散离散傅里叶级数傅里叶变换形式我们先从周期性序列的离散傅里叶级数(DFS)开始讨论，然后再讨论可作为周期函数一个周期的有限长序列的离散傅里叶变换(DFT)。周期序列DFS定义设

为周期为N的周期序列，则其离散傅里叶级数(DFS)变换对：

正变换反变换

其中：周期序列：DFS非周期信号x(n)，其DTFT(单位圆上Z变换)为周期连续频谱密度函数，对其进行采样，使其成为周期性离散频谱函数。设在一周期内采样N个点，则两采样点间距为：

得到频间距为：代入DTFT式子中得：推导正变换证明：已知

两边同乘以，并对一个周期求和用n置换r得DFS反变换正交定理用数字计算机对信号进行频谱分析时，要求信号必须以离散值作为输入，而且上面讨论可知：只有第四种形式(DFS)对数字信号处理有实用价值。但如果将前三种形式要么在时域上采样，要么在频域上采样，变成离散函数，就可以在计算机上应用。DFS的推导意义x(t)经过抽样为x(nT)，对离散的时间信号进行DTFT得到周期连续频谱密度函数。再经过抽样，得到周期性离散频谱密度函数即为DFS。x(t)t取样x(t)tDTFTX(ejΩT)Ω采样X(ejw)w①由非周期连续时间信号推出DFS1次时域采样1次频域采样周期性连续时间信号函数经采样后，得到周期性的离散时间函数(DFS)。X(ejw)w采样x(t)t②由周期连续时间信号推出DFS1次时域采样非周期离散时间信号经过序列付里时变换(即单位圆上的Z变换)DTFT，得到周期连续谱密度函数，再经采样为周期离散频谱密度函数(DFS)。x(t)tΩX(ejΩT)wX(ejw)DTFT采样③由非周期离散时间信号推出DFS1次频域采样在计算机上实现信号的频谱分析要求：时域和频域都是离散的；时域和频域都是有限长的。

FT，FS，DTFT，DFS都不符合要求，但是，利用DFS时域和频域的周期性，各取一个周期就形成新的变换对。为什么DFS过渡到DFT另一种表示其中表示对n取模N运算(或模N的余数)。则若x(n)是一个N点的有限长序列周期序列与主值序列的关系举例：设周期为N=6。则有周期序列和求余运算：

这是因为：(19=3×6+1)

同理这是因为：(-2=-1×6+4)

同样：X(k)也是一个N点的有限长序列

有限长序列和周期序列其中：DFT的定义频域周期序列

与有限长序列周期序列实际上只有有限个序列值才有意义，因而它的离散傅里叶级数表示式也适用于有限长序列，这就得到有限长序列的傅里叶变换(DFT)。DFT的定义把时域周期序列看作是有限长序列x(n)的周期延拓；把频域周期序列看作是有限长序列X(k)的周期延拓；这样我们只要把DFS的定义式两边取主值区间，就得到关于有限长序列的时频域的对应变换对。这就是数字信号处理里最重要的变换——离散傅里叶变换(DFT)。DFT的定义DFT的图形解释FTDTFTDFS正变换反变换

X(k)、x(n)为有限长序列的离散付里叶变换对，已知其中一个序列就能确定另一个序列。

注意：在离散傅里叶变换关系中，有限长序列都作为周期序列的一个周期来表示，都隐含有周期性意义。DFT公式Z变换DTFT是单位圆上的Z变换各种变换之间的关系勤于动脑，善于思考，勇于探索，敢于创造DTFTDFTDFT是DTFT在单位圆上的N点等间隔采样

Z变换、DTFT、DFT的取值范围

z变换与DFT的关系（抽样z变换），在此基础上引出抽样z变换的概念，并进一步深入讨论频域抽样不失真条件。频域抽样理论（频域抽样不失真条件）频域内插公式频域采样定理与内插公式连续傅里叶变换引出离散傅里叶变换定义式。离散傅里叶变换看作是序列的傅里叶变换在频域再抽样后的变换对。在Z变换中，又可了解到序列的傅里叶变换就是单位圆上的Z变换。所以对序列的傅里叶变换进行频域抽样时，自然可以看作是对单位圆上的Z变换进行抽样。

z变换与DFT的关系Z变换的定义式(正变换)重写如下:取z=ejw

代入定义式，得到单位圆上Z变换为

DFT正变换再进行抽样——N等分。这样w=2kπ/N，即w值为0,2π/N,4π/N,6π/N…,考虑到x(n)是N点有限长序列,因而n只需0~N-1即可。将w=2kπ/N代入并改变上下限,得推导从以上推导中可看出，有限长序列x(n)的离散傅里叶变换X(k)序列的各点值等于对x(n)进行Z变换后在单位圆上N等分抽样的各点处所得的Z变换值,即这就是Z变换与DFT的关系。结论问题由Z变换与DFT的关系：x(n)的离散傅里叶变换X(k)序列值和x(n)的Z变换在单位圆N个等分点上的抽样值相等,这就是实现了频域的抽样。是否任何一序列(或说任何一个频率特性)都能用频域抽样的办法去逼近呢?其限制条件是什么?频域抽样定理将x(n)的频域函数

，按每周期N点抽样，得到一周期序列，再反变换回时域，得到变换结果，是一周期延拓的序列，且与原序列x(n)有如下关系频域按每周期N点抽样，时域便按N点周期延拓。频域抽样时域周期延拓分析长度为M的有限长序列，频域抽样不失真的条件：频域抽样点数N要大于或等于序列长度M，即满足N≥M。此时可得到长度为N(或小于N)的有限长序列可用它的z变换在单位圆上的N个均分点上的抽样值精确地表示。结论从频域抽样不失真条件可以知道：N个频域抽样X(k)能不失真的还原出长度为N的有限长序列x(n)。那么用N个X(k)也一定能完整地表示出X(z)以及频率响应——即单位圆上的X(z)。过程很简单,先把N个X(k)作IDFT得到x(n),再把x(n)作Z变换便得到X(z)。频域内插公式频域响应的内插公式例：x(n)=R4(n)，求x(n)的8点和16点DFT。设变换区间N=16，则：DFT的结果与N长度有关例题讲解解：设变换区间N=8，则：对同一序列x(n)：（1）DFT的变换区间长度N不同，变换结果不同。（2）当N足够大，|X(k)|的包络可逼近|X(ejω)|曲线。（3）|X(k)|表示ωk=(2π/N)k频点的幅度谱线。N=4长度为4的矩形窗序列的DTFTN=8N=12N=16N=20当N越大，DFT的包络线越逼近DTFT的曲线。MATLAB验证2、周期序列对应的频谱是()连续周期连续非周期离散周期离散非周期ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为C。一个域的连续对应另一个域的非周期,一个域的离散对应另一个域的周期。DFS:时域:周期离散,频域:离散周期答案解析单选题10分3、周期序列X(k)可以看成对x(n)的()个周期做Z变换，然后将Z变换在Z平面单位圆上按()间隔采样得到的。()N，2πN/2，π2，π/N1，2π/NABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为D。周期序列X(k)可以看成对x(n)的一个周期做Z变换,然后将Z变换在Z平面单位圆上按2π/N间隔采样得到的。答案解析单选题10分4、DFT的物理意义是：一个

的离散序列x(n)的离散付氏变换X(k)为x(n)的付氏变换

在区间[0,2π]上的

。()收敛；等间隔采样N点有限长；N点等间隔采样无限长；N点等间隔采样N点有限长；取值ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为B。DFT:答案解析单选题10分5、序列x(n)=R5(n)，其8点DFT记为X(k)，k=0,1,…,7，则X(0)为(

)。2345ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为D。答案解析单选题10分6、已知x(n)=δ(n)，N点的DFT[x(n)]=X(k)，则X(5)=()。N10-NABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为B。答案解析单选题10分离散傅里叶级数（DFS）离散傅里叶变换（DFT）频域采样定理：N≥M0≤k≤N-10≤n≤N-1课堂小结四种变换1、Z变换、DTFT、DFS、DFT这几种变换之间有怎样的联系？你是怎样理解的？2、时域采样定理和频域采样定理之间有什么相同与不同之处？谈谈你的理解？3、试着利用MATLAB工具来验证今天所学的内容。知识延伸及反思作业：P127习题3.11信号分析与处理SignalAnalysisandProcessing

第3章

离散傅里叶变换和快速傅里叶变换绪论内容回顾1、信号分类2、信号分析与处理系统（连续离散）信号分类不要怕，连续离散看时间。时间连续是连续，时间离散是离散。时间幅值都连续，这个信号必模拟。时间幅值都离散，数字信号不会错。（能量功率）能量功率有点难，记住公式变简单。先来求解能量W，再除时间得功率。信号平方求积分，区间负到正无穷。能量有限是能量，功率这时必为0。能量无限怎么办？快去求解功率P。功率有限是功率，功率这时不为0。非功非能还正常，既功既能不可能。（信号分析与处理系统）输入连续抗混叠，（抗混叠滤波器）连续A/D变离散，（A/D转换器）离散DSP处理完，（数字信号处理器）离散D/A变连续，（D/A转换器）输出之前要平滑。（输出平滑滤波器）在无限时间的幅值有限的周期信号为功率信号；能量信号一定为非周期信号；非周期信号又可分为三种：能量信号：持续时间有限的脉冲型信号

t→ꝏ时，f(t)→0功率信号：持续时间无限，但幅度有限的信号非功非能信号：t→ꝏ时，f(t)→ꝏ既功既能信号×能量信号和功率信号小结第1章内容回顾连续时间信号离散时间信号第2章内容回顾信号最高频率最小采样频率已知信号x1(t)和x2(t)的最高频率分别为fm1和fm2，且fm1>fm2。下列工程实际中的复杂信号，离散采样不失真的最小采样频率分别是多少？采样定理拓展四种变换1、x(t)=C（其中C为常数）是什么信号?()能量信号功率信号既不是能量信号也不是功率信号既是能量信号也是功率信号ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本解析：正确答案为B直流信号是功率信号。能量无限，功率有限。答案解析答案解析答案解析答案解析答案解析单选题10分2、信号

中含有的直流分量为（

）11/221+cos2ΩtABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为BFS,求直流分量a0/2答案解析单选题10分3、判断序列

是否是周期序列，如是周期序列，确定其周期。（

）周期序列，周期为2周期序列，周期为2π周期序列，周期为5π非周期序列ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为D一个周期，一个非周期所以x(n)是非周期的。答案解析单选题10分4、已知信号x(t)频谱的最高频率为fm，则信号x(t)sin(πfmt)经等间隔采样后，不会发生频率混叠的最小采样频率为（

）3fmfm3fm/2fm/2ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为A采样定理：x(t)最高频率为fmsin(πfmt)最高频率为fm/2x(t)sin(πfmt)最高频率为：fm+fm/2=3fm/2不会发生频率混叠的最小采样频率fs>2*3fm/2=3fm答案解析单选题10分5、某序列的频谱

，该序列的6点DFT中的X(3)=（

）。1/332/33/2ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为CX(z)、DTFT和DFT之间的关系答案解析单选题10分6、已知x(n)=δ(n)，N点的DFT[x(n)]=X(k)，则X(5)=()。N10-NABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为B。答案解析单选题10分主

要

内

容1、连续时间信号的傅里叶变换2、离散傅里叶变换及性质第3章DFT和FFT2.1、序列的傅里叶变换2.2、离散傅里叶变换2.3、离散傅里叶变换的性质2.4、DFT在应用中的问题DFT的性质线性选频性循环移位循环卷积对称性设x1(n)，x2(n)都是两个有限列长为N的有限序列，它们的离散付里叶变换分别为：则它们的线性组合：线性证明：如果x1(n)和x2(n)长度皆为N，即0≤n≤N-1范围有值，则aX1(k)+bX2(k)的长度也是N；若x1(n)和x2(n)长度不等，设x1(n)长度为N1，x2(n)长度为N2，则ax1(n)+bx2(n)的长度应为N=max[N1，N2]，故DFT必须按长度N计算。若N1<N2，则N=N2，那么需将x1(n)补上N2-N1个零值点后变成长度为N序列，然后都作N点的DFT。说明：当输入频率为rω的正弦波时，傅里叶变换后的离散频谱中只有一条谱线取值为N，其余的都为零。输入信号是若干频率不同的正弦波的线性组合，经过离散傅里叶变换后，将在不同的谱线位置有对应的输出。离散傅里叶变换算法实质上对频率具有选择性。选频性DFT有限长序列的圆周移位导致频谱线性相移，而对频谱幅度无影响。(1)圆周移位(2)时移特性循环移位从图中两虚线之间的主值序列的移位情况可以看出：当主值序列左移m个样本时，从右边会同时移进m个样本，好像是刚向左边移出的那些样本又从右边循环移了进来，因此取名“循环移位”。显然，循环移位不同于线性移位。左移m位的循环移位就是将该序列在圆周上顺时针旋转m位。有限长序列圆周移位的实现步骤21310.5nx(n)(1)周期延拓：N=5时2131x(n)0.521310.51120.5n3(2)周期延拓：N=6时，补零加长2131x(n)0.521310.51123n举例21310.5nx(n)(4)M=-2时，右移(取主值)2131nx(n)0.5(3)M=1时，左移(取主值)131x(n)0.52n同理可得：频移特性时域序列的调制等效于频域的圆周移位。7、对5点有限长序列[13052]进行向左2点圆周移位后得到序列()[13052][52130][05213][00130]ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为C。圆周移位，1和3从左边移出去的，从右边移进来。答案解析单选题10分卷积在此我们主要介绍：线性卷积圆周卷积（循环卷积）圆周卷积与线性卷积的性质对比卷积线性卷积定义：有限长序列

x1(n),0≤n≤N1-1；x2(n),0≤n≤N2-1

则线性卷积为：注意：线性卷积结果长度变为N1+N2-1。线性卷积四个步骤：翻转移位相乘相加（求和）令则圆周卷积结果长度不变，为N。圆周（循环）卷积x(n)逆时针，h(n)顺时针h(n)不动，x(n)顺时针移位对应位相乘再相加圆周卷积的实现步骤231x(n)54n0N1=5线性卷积：圆周卷积：(N=7)补零加长231x(k)54k0N1=5N2=3213h(n)n0x(k)231540N=7k举例讲解线性卷积无需周期延拓，圆周卷积需进行周期延拓：线性卷积的翻转：圆周卷积的翻转(并取主值区间）：231h(-k)k0231h(k)0k231231231h(-k)k0132平移231h(1-k)k00231h(1-k)k231x(k)54k0231x(k)540N=7k相乘∑x(k)h(-k)=5×1=5∑x(k)h(1-k)=5×2+4×1=14∑x(k)h(2-k)=5×3+4×2+3×1=26∑x(k)h(3-k)=4×3+3×2+2×1=20∑x(k)h(4-k)=3×3+2×2+1×1=14∑x(k)h(5-k)=2×3+1×2=8∑x(k)h(6-k)=1×3=3

相加得到线性卷积的示意图

相加得到圆周卷积的示意图14265ny(n)201483014265ny(n)2014830可见，线性卷积与圆周卷积相同

当N≥[N1(5)+N2(3)-1]=7时若圆周卷积取长度为N=5，则求圆周卷积231x(k)540N=5k求得圆周卷积∑x(k)h(-k)=5×1+2×3+1×2=13∑x(k)h(1-k)=5×2+4×1+1×3=17∑x(k)h(2-k)=5×3+4×2+3×1=26∑x(k)h(3-k)=4×3+3×2+2×1=20∑x(k)h(4-k)=3×3+2×2+1×1=14看出圆周卷积与线性卷积不同。171326y(n)n02014k231h(-k)0x=[5,4,3,2,1];h=[1,2,3];lenx=length(x);%求各序列原始长度lenh=length(h);N=lenx+lenh-1;%线性卷积长度N=7x=[xzeros(1,N-lenx)];%x(n)补零[5,4,3,2,1,0,0]subplot(231);%绘离散图stem(x,'.')xlabel('n');ylabel('x(n)');title('原始序列x(n)');h=[hzeros(1,N-lenh)];%h(n)补零[1,2,3,0,0,0,0]subplot(232);stem(h,'.')xlabel('n');ylabel('h(n)');title('原始序列h(n)');y1=cconv(x,h,N);

%求循环卷积subplot(234);stem(y1,'.')xlabel('n');ylabel('y1(n)');title('函数法求循环卷积y1(n)');H=fft(h);%求傅里叶变换X=fft(x);Y=H.*X;%性质:频域相乘后做IDFT等于时域卷积y2=real(ifft(Y));subplot(235);stem(y2,'.')xlabel('n');ylabel('y2(n)');title('性质法求循环卷积y(n)');z=conv(x,h);%再求线性卷积进行比较subplot(236);stem(z,'.')xlabel('n');ylabel('z(n)');title('线性卷积z(n)');MATLAB验证@2019214042董磊要用循环卷积实现线性卷积，那么循环卷积的长度L必须大于或者等于线性卷积的长度N+M-1，即：L≥N+M-1。否则，循环卷积周期延拓时会产生混叠。线性卷积循环卷积，L=7循环卷积，L=8圆周卷积与线性卷积的性质对比取L≥N1+N2-1情况下，圆周卷积代替线性卷积的实际实现的框图如下：上图依据的是圆周卷积定理，做的是圆周卷积。然而由于L选取符合条件，因而结果是与线性卷积结果一致的。L点DFTh(n)L点DFTL点IDFTx(n)y(n)圆周卷积代替线性卷积的实现方法令x(n),h(n),y(n)都是N点序列，其DFT分别是X(k),H(k),Y(k)。若：y(n)=x(n)h(n),则：Y(k)=X(k)H(k)若：y(n)=x(n)h(n)则：Y(k)=X(k)H(k)

时域循环卷积频域循环卷积两序列乘积的DFT等于它们的DFT的循环卷积乘以因子1/N。两个时域序列的循环卷积的DFT等于它们的DFT的乘积。8、对x1(n)(0≤n≤N1-1)和x2(n)(0≤n≤N2-1)进行8点的圆周卷积，其中（）的结果不等于线性卷积。N1=3，N2=4N1=5，N2=4N1=4，N2=4N1=5，N2=5ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为D。线性卷积后长度:N1+N2-1。答案解析单选题10分1、已知

和求x(n)与h(n)的6点循环卷积。作答正常使用主观题需2.0以上版本雨课堂011223434011-123可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本6点循环卷积=线性卷积{1，4，10，16，17，12}答案解析主观题100分解法一：线性卷积求解法1410161712(a+b=0)循环卷积与线性卷积两者等价。竖式法求解线性卷积：例题讲解解法二：圆圈法x(n)和h(n)补充N点，零点对齐，反方向排列。若一个顺时针，另一个则逆时针。对应位相乘并相加，得:移1位求z(1)：一个序列不动，另一个与它原排列方向的反方向移位。牢记两个反方向！........1132002..34..0002.00.........2132003..40..0001移2位求z(2)：移3位求z(3)：.........3132004..00..012.........4132000..01..023移4位求z(4)：移5位求z(5)：.........0132000..12..034.........0132001..23..040解法三：卷积定理求解法解法一：线性卷积求解法解法二：圆圈法解法三：卷积定理求解法

多角度看问题6点循环卷积：

2、已知5点序列x(n)=[1,0,2,1,3]，n=[0,1,2,3,4]，请求解：（1）x(n)线性卷积，x(n)*x(n)。（2）x(n)的5点循环卷积。（3）x(n)的10点循环卷积。作答正常使用主观题需2.0以上版本雨课堂可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本线性卷积[1,0,4,2,10,4,13,6,9]5点循环卷积[5,13,10,11,10]10点循环卷积：=线性卷积[1,0,4,2,10,4,13,6,9,0]答案解析主观题100分DFT的对称性质较为复杂，归为以下三类:共轭与圆周共轭对称在时、频域的对应关系；实(虚)部与圆周共轭对称(反对称)分量在时、频域的对应关系；时域为实序列时对应DFT特征；另外，在以上对称性质的基础上，可归纳总结出x(n)与X(k)的奇、偶、虚、实关系，利用这些关系，可减少计算DFT时的运算量。对称性奇对称(序列)和偶对称(序列)

x(n)与-x(-n)互为奇对称；满足x0(n)=-x0(-n)的序列x0(n)称为奇对称序列。

x(n)与x(-n)互为偶对称；满足xe(n)=xe(-n)

的序列xe(n)称为偶对称序列。0x(n)n0xe(n)n0x(-n)n互为偶对称为偶对称序列0x(n)n0x(-n)n互为奇对称0xo(n)n为奇对称序列设x(n)为实序列，X(k)=DFT[x(n)]。则有:(1)X(k)=X*(N-k)(2)若x(n)=x(N-n)，则X(k)=X(N-k)(3)若x(n)=-x(N-n)，则X(k)=-X(N-k)对实序列进行DFT时，利用以上性质可减少运算量，提高运算效率。实序列的对称性则：如果x(n)的DFT为X(k)，则x(n)的实部和虚部(包括j)的DFT分别为X(k)的共轭对称分量和共轭反对称分量；而x(n)的共轭对称分量和共轭反对称分量的DFT分别为X(k)的实部和虚部乘以j复序列的对称性若x(n)是实序列，则X(k)是有限长共轭对称序列；反之亦然时域x(n)取共轭，对应于频域X(k)取有限长共轭对称频域X(k)取共轭，对应于时域x(n)取有限长共轭对称若X(k)是实序列，则x(n)是有限长共轭对称序列；反之亦然两种情况为对偶关系复序列的共轭对称性设x*(n)为x(n)的共轭复序列，X(k)=DFT[x(n)]，9、设实序列x(n)的6点DFT为X(k)，已知X(0)=2，x(1)=1.5-0.866j,X(2)=0.5-0.866j,X(3)=0，则根据DFT的对称性可得到X(4)=(

)，X(5)=(

)。（

）0，0.5+0.866j1.5+0.866j，0.5+0.866j0.5+0.866j，1.5-0.866j0.5+0.866j，1.5+0.866jABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为D。当x(n)为实序列时，X(k)=X*(-k)=X*(N-k)。答案解析单选题10分DFT的性质:线性选频性循环移位卷积：线性卷积和圆周卷积L≥N1+N2-1对称性课堂小结1、FS、FT、DTFT、DFS、DFT几种变换之间有怎样的联系？你是怎样理解的？2、循环卷积与线性卷积的联系与区别有哪些？两者能否等价？等价的条件是什么？3、试着证明一下DFT的其它性质，并利用MATLAB工具来验证今天所学的内容。知识延伸及反思作业：P126习题3.1，3.8第3章

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

3.2.4

DFT在应用中的问题一、教学内容DFT在应用中为什么会产生问题？二、DFT在应用中会产生哪些问题？三、产生这些问题的原因是什么？四、解决这些问题的措施有哪些？混叠现象、频谱泄露、栅栏效应在我们的宇宙中很多东西都在振动。例如，语音就是人类声带的振动；星星随着他们的公转和自转改变亮度；轮船推进器产生周期性的海水移动等等。这些信号在时域中的波形并不重要，关键信息其实是各个正弦成分的频率，相位和幅值。DFT就是用来提取这些信息的一个工具。问题导入

DFT在提取信息的过程中会不会有问题？例、某序列的频谱

，该序列的6点DFT中的X(3)=（

C

）。A.1/3B.1C.2/3D.3/2解：z变换、DTFT和DFT的关系

另一种思路：利用DFT的定义求解为什么结果不一样？问题导入

FT：知识回顾DTFT是单位圆上的z变换。DFS是DTFT单位圆上的N点等间隔采样。DFT是DFS的一个周期z变换：DTFT：DFSDFT：DFT对FT的近似：采样、截短用DFT实现对连续信号谱分析的过程DFT在应用中为什么会产生问题？采样截短采样卷积周期延拓周期延拓取一个周期周期延拓取一个周期X(k)是否为Xa(jΩ)的准确采样？为了能在数字计算机上分析连续信号的频谱，常常用DFT来逼近连续时间信号的傅里叶变换，但同时也产生以下问题：混叠现象频谱泄漏栅栏效应DFT在应用中会产生哪些问题？利用DFT逼近连续时间信号的傅里叶变换，为避免混叠失真，要求满足采样定理，即奈奎斯特准则：

fs≥2fmax

其中fs为采样频率，fmax为信号最高频率。但此条件只规定出fs的下限为fmax，其上限要受采样间隔∆f的约束。采样间隔∆f即频率分辨力，它是记录长度的倒数，即Tp=1/∆f若采样点数为N，则采样间隔与fs的关系为：

∆f=fs/N≥2fmax/N1、混叠现象%对x(t)=sin(2πf1t)+sin(2πf2t)+sin(2πf3t)按不同分辨率进行采样f1=2;f2=2.02;f3=2.07;fs=10;%设置采样频率，大于2fm，不应发生混叠问题dt=1/fs;forN=128:128:512%将N=128递增到512Hz，其分辨率变小，观察频谱图n=0:N-1;x=sin(2*pi*f1*n*dt)+sin(2*pi*f2*n*dt)+sin(2*pi*f3*n*dt);y=fft(x,N);%傅里叶变换mag=2*abs(y)/N;%计算幅值f=n*fs/N;%fs/N为分辨率subplot(4,1,N/128);plot(f,mag);title(['N=',num2str(N),'；△f=',num2str(fs/N)]);xlabel('f/Hz');ylabel('X(e^jw)');axis([1.52.5-infinf]);end频率分辨率MATLAB验证采样点数N变大，频率分辨率△f变小，三个谱峰分开。P116例3.2.4@2019214042董磊由∆f=fs/N≥2fmax/N看出：在N给定时，为避免混叠失真而一味提高抽样频率fs，必然导致∆f增加，即频率分辨力下降；反之，若要提高频率分辨力即减小∆f，则导致减小fs，最终必须减小信号的高频容量。以上两点结论都是在记录长度内抽样点数N给定的条件下得到的。所以在高频容量fmax

与频率分辨力∆f参数中，保持其中一个不变而使另一个性能得以提高的唯一办法，就是增加记录长度内的点数N，即

fmax

和∆f都给定时，则N必须满足N≥2fmax/∆f。这是未采用任何特殊数据处理（例如加窗）情况下，为实现基本DFT算法所必须满足条件。混叠现象的结论辩证思维1、有一频谱分析仪用的FFT处理器，其抽样点数必须是2的整数幂。假定没有采用任何特殊的数据处理措施，已给条件为：

(1)频率分辨力≤10Hz(2)信号的最高频率≤4kHz试确定以下参量：

(1)最小记录长度Tp；(2)抽样点的最大时间间隔T；

(3)在一个记录中的最少点数N。作答正常使用主观题需2.0以上版本雨课堂主观题100分解：

(1)由分辨力的要求确定最小记录长度Tp。Tp=1/∆f=1/10=0.1(s)

故最小记录长度为0.1秒。

(2)从信号的最高频率确定最大的抽样时间间隔T。

fs≥2fmax,T=1/fs≤1/2fmax=0.125×10-3(s)(3)最小记录点数N，它应满足

N≥2fmax/∆f=800

该处理器所需最少采样点数为N=210=1024点。（因为N=29=512点不够）在实际中，要把观测的信号x(n)限制在一定的时间间隔之内，即采取截断数据的过程。

课堂讨论：设信号为x(n)=1/2π，经过矩形窗函数截断，求信号经过矩形窗函数前后的频谱函数。通过讨论，说一说为什么截断会产生频谱泄漏？2、频谱泄漏理论联系实际解：设信号经过矩形窗函数后的信号为x1(n)，矩形窗函数为w(n)，其频谱函数为X1(ejw)。

很明显：X1(ejw)≠X(ejw)，相当于X(ejw)失真，这种失真是由于X(ejw)的频谱泄漏引起，其现象为拖尾（扩展现象），称之为频谱泄漏。产生泄漏以w=0为中心的一根谱线。形状的连续谱线。即频谱成分从w=0处“泄漏”到其他频率处。时域的截断在数学上的意义为原连续时间信号乘上一个窗函数，使原连续时间函数成为两端突然截断，中间为原信号与窗函数相乘的结果。时域两函数相乘，在频域是其频谱的卷积。由于窗函数不可能取无限宽，即其频谱不可能为一冲激函数，信号的频谱与窗函数的卷积必然产生拖尾现象，造成频谱泄漏。频谱泄漏的原因由于我们无法取无数个点，所以在DFT时，时域的截断是必然的，因而泄漏也是必然存在的。为了减少频率泄漏可采用：适当加大窗口宽度，增加M值；采用适当形状的窗函数截断。频谱泄漏注意点频谱泄漏MATLAB验证矩形窗汉宁窗采用不同形状的窗函数截断，频谱泄漏情况不一样。例、某序列的频谱

，该序列的6点DFT中的X(3)=（

C

）。A.1/3B.1C.2/3D.3/2解：z变换、DTFT和DFT的关系

另一种思路：利用DFT的定义求解为什么结果不一样？例题讲解真实值：DFT：N=6DFT：N=12N取得越多，越接近真实值。加大窗口宽度，可以减少频谱泄漏。利用DFT逼近连续时间信号的傅里叶变换，其频谱将不再是连续函数而是基频F的整数倍。用DFT计算频谱，就如通过一个栅栏观看一个景色，只能在离散点的地方看到真实的景象，从而产生栅栏效应。如果在两离散的谱线间频谱有很大变化，不作特殊处理，则无法将其检测出来。3、栅栏效应减小栅栏效应的一个方法是在所取数据的末端加一些零值点，使一个周期内点数增加，但是不改变原有的记录数据。这种方法等效于加长了周期Tp。因公式∆f=1/Tp(∆f是抽样间隔)。Tp增加，抽样间隔变小，从而能保持原来频谱形式不变的情况下使谱线变密，也就使频谱抽样点数增加。

这样，原来看不到的频谱分量就有可能看到了。

减小栅栏效应的方法MATLAB验证：补零加长使谱线细化N=5N=10N=15N=20N=25补零加长、谱线细化长度为5的矩形窗序列的DTFT补加零点以改变周期时，所用窗函数宽度却不能变，亦即必须按数据记录原长来选择窗函数，而不能按补了零值点后的长度来选择窗函数。通俗地说，就是应先加窗，再补零。减小栅栏效应注意点2、利用离散傅里叶变换(DFT)来计算信号频谱时，时域的截断会造成()现象。频谱泄露时域混叠谱间干扰频谱混叠ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为A。频谱泄露是由截断引起的。答案解析答案解析答案解析答案解析单选题10分3、序列x(n)长度为M，当频率采样点数N<M时，由频率采样X(k)恢复原序列时会产生()现象。频谱泄露时域混叠谱间干扰频谱混叠ABCD提交可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本正确答案为B。当频率采样点数N<M时,不满足采样定理，时域会发生混叠现象。答案解析答案解析答案解析答案解析单选题10分DFT应用中的问题现象原因改善措施混叠现象当fs<2fm时，采样信号的频谱中周期延拓分量相互重叠。离散采样引起的采样频率足够高，fs>>2fm。考虑频率分辨率

∆f=fs/N。频谱泄漏时域窗函数截断后，频谱发生了拖尾现象。时域截断引起的增加采样点数N或采用合适的窗函数。栅栏效应离散的频谱，仿佛透过“栅栏”看风景。离散采样引起的增加频域采样点数N，先加窗再补零。课堂小结1、内容要点：2、解决问题的思想：辩证思维、理论联系实际知识延伸及反思1、补零的方法可以改变谱线的间距，根据∆f=fs/N，N增加，∆f会减小，是不是就提高了频率的分辨率呢？为什么？2、课堂上只讨论了加矩形窗会产生频谱泄漏的情况，还有哪些不同的窗函数？用不同的窗函数加窗后频谱会有什么样的变化？3、试着利用MATLAB工具来验证今天所学的内容。作业：P127习题3.14信号分析与处理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算法的特点——码位倒序规则012345670000