离散傅里叶变换及其快速计算方法

离散傅里叶变换及其快速计算方法第1页/共269页2

连续信号xa(t)，其傅里叶变换为：

xa(t)为时域连续信号

Xa(Ω)为频域连续信号3.1问题的提出：连续信号的傅里叶变换第2页/共269页3离散信号在两种变换域中的表示方法（1）离散时间傅里叶变换DTFT--提供了绝对可加的离散时间序列在频域（ω）中的表示方法。（2）Z变换--提供任意序列的z域表示。

这两种变换有两个共同特征：（1）变换适合于无限长序列（2）它们是连续变量ω或z的函数3.1问题的提出：离散信号的变换第3页/共269页4问题：X(z)，X(ejw)都是连续的，利用计算机处理有困难，例如使用Matlab，因此提出了在频域内取样，使频谱离散化的问题；必须截断序列，得到有限个点的序列。目标：我们需要得到一个可进行数值计算的变换方法：

（1）DTFT-频域中原始信号频谱的周期拓展（2）对DTFT在频域中采样--DFS

（3）将DFS推广到有限持续时间序列DFT

（DFT避免了前面提到的那两个问题，并且它是计算机可实现的变换方式。）DFT已成为DSP算法中的核心变换，原因：（1）有限长序列傅里叶变换的重要方法（2）有快速算法3.1问题的提出：可计算性第4页/共269页5

时间函数频率函数3.1问题的提出：傅里叶变换的四种形式（1）非周期连续时间—傅里叶变换(FT)－连续频率周期连续时间—傅里叶级数(FS)－离散频率非周期离散时间—离散时间傅里叶变换(DTFT)－连续频率周期离散时间—离散傅里叶级数(DFS)－离散频率第5页/共269页63.1问题的提出：傅里叶变换的四种形式（2）1.连续信号（非周期）的付氏变换时域连续函数造成频域是非周期的谱时域的非周期造成频域是连续的谱第6页/共269页7

2.周期连续时间信号：傅里叶级数FS时域连续函数造成频域是非周期的谱。频域的离散对应时域是周期函数。3.1问题的提出：傅里叶变换的四种形式（3）时域周期频域离散)(0WnXWTp20=W)(~txtT第7页/共269页83.非周期离散信号：离散时间傅里叶变换DTFT时域的离散化造成频域的周期延拓时域的非周期对应于频域的连续3.1问题的提出：傅里叶变换的四种形式（4）时域离散频域周期取样定理第8页/共269页94.周期离散时间信号：离散傅里叶级数DFS一个域的离散造成另一个域的周期延拓离散傅里叶级数的时域和频域都是离散的和周期的3.1问题的提出：傅里叶变换的四种形式(5)kTT1n周期取样间隔时域周期、离散频域周期、离散第9页/共269页10四种傅里叶变换形式的归纳总结：形式时间函数频率函数傅里叶变换FT连续非周期非周期连续傅里叶级数FS连续周期(T0)非周期离散(Ω0=2π/T0)离散时间傅里叶变换DTFT离散(T)非周期周期(Ωs=2π/T)连续离散傅里叶级数DFS离散(T)周期(T0)周期(Ωs=2π/T)离散(Ω0=2π/T0)离散时间函数的取样间隔：T1，取样频率：离散频率函数的取样间隔：F0，时间周期：3.1问题的提出：傅里叶变换的四种形式（6）结论：①时域中函数取样(离散)

（映射）频域中函数周期重复；②频域中函数取样（映射）时域中函数周期重复；③取样间隔（映射）

周期（2π/间隔）第10页/共269页0nN(d)DFSk0N-N1/T-N(c)FSW-ΩmXa(kΩ1)tTm0T1-T11Ω1Ωmnx(n)=xa(nT)Tm0(b)DTFTWΩm-ΩmΩs-Ωs1/TTtxa(t)Tm0(a)FTWΩm-ΩmXa(Ω)时域中函数的取样和频域中函数的取样3.1问题的提出：傅里叶变换的四种形式(7)第11页/共269页12由以上讨论可以清楚地看到，时域取样将引起频域的周期延拓，频域取样也将引起时域的周期延拓。因此可以设想，如果同时对频域和时域取样，其结果是时域和频域的波形都变成离散、周期性的波形，从而我们可以利用付氏级数这一工具，得到它们之间的离散付氏级数DFS关系。3.2DFS及其性质第12页/共269页13基本关系式

若r，m都是整数,则:其中:DFS定义：预备知识证明:对于r=m：不论k取何值，显然等式成立。对于r≠m：第13页/共269页14为了推导的关系，作下列变量代换：时域：频域：则得：?DFS定义：正变换第14页/共269页15周期离散序列的Z变换存在（收敛）的问题

因为周期离散序列，而对于周期信号，严格数学意义上讲，其Z变换不收敛，因为：

而对于

找不到衰减因子使它绝对可和（收敛）。为此，定义新函数，其Z变换：DFS定义：正变换第15页/共269页16其频谱：（ω是连续变量，需要对其离散化）DFS定义：正变换（取的一个主周期进行Z变换）第16页/共269页17频域取样X(ejω)是连续变量ω的周期函数，周期为2π。把ω离散化，即在0～2π区间内等间隔取N个点，取样间隔为2π/N。另一个角度看，

X(ejω)是Z平面单位圆上的Z变换。连续变量ω的离散化也可以认为是把单位圆分N等分，每分为2π/N。其中：

称为频域中的取样间隔，也称为频率分辨率。

DFS定义：正变换第17页/共269页18DFS定义：正变换则其中第18页/共269页19DFS：DFS定义：正变换也仅有0，1，…，N-1个独立值,周期为N。因为随k周期变化，仅有0，1，…，N-1个独立值。仅有0，1，…，N-1个独立值。所以第19页/共269页20反变换IDFS

正变换两端乘以，m=0,1,…,N-1

然后令k=0，1，…，N-1求和，得：DFS定义：反变换

用正交条件：第20页/共269页21DFS定义：反变换即（只有m=n时，才有值，而m不等于n时，为零，因此，x(n)只取x(m)）变量m替换为n，得第21页/共269页22DFS变换对：时域周期序列与频域周期序列间的关系DFS定义：反变换其中第22页/共269页23在什么条件下不产生混迭失真？

—频率取样频率取样：若时间信号有限长，当满足下列条件时，X(ejω)的样本值X(k)能不失真的恢复成原信号。为了避免时间上的混迭：（1）必须是时间限制（有限时宽）（2）取样频率间隔小于DFS定义：几点说明第23页/共269页24

频率分量

如果变量DFS可表示为：

因此，时域n及频域k都是有物理意义的。DFS定义：几点说明（指数项kn不变）第24页/共269页25更具体地，傅里叶系数的标号

k和频率f的关系为：所以：对应关系：傅里叶系数标号k：0～N

数字频率ω：0～2π

模拟频率

f：0～fs

DFS定义：几点说明第25页/共269页26DFS定义：几点说明频率成份直流分量：当k=0时，，此时得到的傅里叶级数的系数称为信号的直流分量（DCComponent），是信号的平均值；交流分量：其它频率（k>0）称为周期信号的谐波，此时的傅里叶级数系数称为信号的交流分量。k=1时的频率为信号的一次谐波，或基频，频率大小为fs/N，时间为NTs，等于完成一个周期所需要的时间。其它谐波为基频的整数倍。离散傅里叶级数包含了0到(N-1)fs/N的频率，因而N个傅里叶级数的系数位于从0直到接近取样频率的频率上。时域频域第26页/共269页27DFS定义：几点说明周期信号的频谱由傅里叶系数可得到的幅度频谱和相位频谱，不难证明，如果是实序列，那么幅度频谱是周期性偶函数，相位频谱是周期性奇函数。周期信号由离散傅里叶级数DFS得到的频谱，和非周期信号由离散时间傅里叶变换DTFT得到的频谱之间有重要区别。①DTFT产生连续频谱，这意味着频谱在所有的频率处都有值，因而非周期信号的幅度和相位频谱是光滑无间断的曲线。②与之相反，DFS仅有N点的频谱，仅包含有限个频率，因而周期信号的幅度和相位频谱是线谱，即相等间隔的竖线，当频谱的横坐标变量用实际频率f代替k时，谱线间隔为fs/N。并不是所有的周期信号都含有全部谐波，例如有些频谱只有奇次谐波，比如三角波，偶次谐波为0，而有些频谱仅在一些谐波处的值为0。第27页/共269页28DFS的Matlab的实现由DFS的定义可以看出它是一种可进行数值计算表示式，它可由多种方式实现。

（1）利用循环语句for…..end实现为了计算每个样本，可用for…..end语句实现求和。为了计算所有的DFS系数，需要另外一个for…..end循环，这将导致运行嵌套的两个for….end循环。显然，这种方法的效率较低。第28页/共269页29设和代表序列x(n)和X(k)主周期的列向量，则DFS的正反变换表达式由下式给出：

其中矩阵

WN

由下式给出：

矩阵

WN

为方阵，叫做

DFS矩阵.

（2）利用矩阵——矢量乘法第29页/共269页30function[Xk]=dfs(xn,N)n=[0:1:N-1];%rowvectorfornk=[0:1:N-1];%rowvecorforkWN=exp(-j*2*pi/N);%Wnfactornk=n'*k;%createsaNbyNmatrixofnkvaluesWNnk=WN.^nk;%DFSmatrixXk=xn*WNnk;%rowvectorforDFScoefficients

function[xn]=idfs(Xk,N)n=[0:1:N-1];%rowvectorfornk=[0:1:N-1];%rowvecorforkWN=exp(-j*2*pi/N);%Wnfactornk=n'*k;%createsaNbyNmatrixofnkvaluesWNnk=WN.^(-nk);%IDFSmatrixxn=(Xk*WNnk)/N;%rowvectorforIDFSvaluesDFS的Matlab的实现第30页/共269页例：求出下面周期序列的

DFS表示式

解：上述序列的基本周期为

N=4，因而

W4=e-j2π/4=-j，

第31页/共269页第32页/共269页第33页/共269页例:下面给出一周期“方波”序列：

其中，m=0,±1,±2,…，N是基本周期，L/N是占空比。(a)确定一种用L与N描述的的表达式。(b)分别画出当L=5,N=20；L=5，N=40；L=5，N=60；L=7，N=60时表达式。(c)对所得结果进行讨论。第34页/共269页解：(a)由DFS定义可得而：

的幅值可表示为：

第35页/共269页b.Matlab程序如下：%Chapter3:Example3.03L=5;N=20;(改变参数）x=[ones(1,L),zeros(1,N-L)];xn=x'*ones(1,3);xn=(xn(:))';n=-N:1:2*N-1;subplot(1,1,1);subplot(2,1,2);stem(n,xn);xlabel('n');ylabel('xtilde(n)')title('Threeperiodsofxtilde(n)')axis([-N,2*N-1,-0.5,1.5])-20-100102030-0.500.511.5nxtilde(n)Threeperiodsofxtilde(n)第36页/共269页%Part(b)L=5;N=20;(改变参数）xn=[ones(1,L),zeros(1,N-L)];Xk=dfs(xn,N);magXk=abs([Xk(N/2+1:N)Xk(1:N/2+1)]);k=[-N/2:N/2];subplot(2,2,1);stem(k,magXk);axis([-N/2,N/2,-0.5,5.5])xlabel('k');ylabel('Xtilde(k)')title('DFSofSQ.wave:L=5,N=20')第37页/共269页5个峰值5个峰值5个峰值7个峰值注意：是周期信号，图中只画出了从–N/2到N/2的部分。

c.从图中可以看到，方波的DFS系数的包络像“Sinc”函数，①K=0时的幅度等于L；②同时函数的零点位于N/L（占空比的倒数）的整数倍处；③L=5不变，N变大（即填0，但有效信息没有增加），则形状不变，只是更平滑，即获得了一个高密度谱；④N=60不变，L变大（即增加了原始数据长度），则变换后得形状发生了变化，获得了更多的信息，即高分辨率谱。第38页/共269页例：设当N=5、10、20、50时，分别对其Z变换在单位圆上取样，研究不同的N对时域的影响。可用Matlab来实现取样运算：用IDFS计算，确定相应的时域序列。解：可得x(n)的Z变换为：第39页/共269页%Frequency-domainsampling%x(n)=(0.7)^n*u(n)%X(z)=z/(z-0.7);|z|>0.7

subplot(1,1,1)N=5;(改变参数）k=0:1:N-1;wk=2*pi*k/N;zk=exp(j*wk);Xk=(zk)./(zk-0.7);xn=real(idfs(Xk,N));%只取实部，去掉产生的虚部误差xtilde=xn'*ones(1,8);%画出8个周期xtilde=(xtilde(:))';subplot(2,2,1);stem(0:39,xtilde);axis([0,40,-0.1,1.5]);xlabel('n');ylabel('xtilde(n)');title('N=5')第40页/共269页0204000.511.5nxtilde(n)N=50204000.511.5nxtilde(n)N=100204000.511.5nxtilde(n)N=200204000.511.5nxtilde(n)N=40从图中清楚地表明在时域中出现的混叠，尤其是当N=5与N=10时。对于大的N值，其x(n)的尾部足够小，实际上不会导致明显的混迭。这对于变换前，有效截取无限序列，是非常有效的。1.20201.02911.00081.0000第41页/共269页42线性且：则－－a,b为任意常数DFS的性质：线性第42页/共269页43序列的周期移位（时域）若是周期序列，其周期为N，移位后仍为周期序列，且：DFS的性质：序列的周期移位证明：第43页/共269页44调制特性（频域周期移位）DFS的性质：调制特性证明：第44页/共269页45

周期卷积（时域）若则频域相乘时域卷积周期卷积：两个周期序列在一个周期上的线性卷积，是一种特殊的卷积计算形式。DFS的性质：周期卷积（1）第45页/共269页46DFS的性质：周期卷积（2）证明：第46页/共269页47DFS的性质：周期卷积（3）0N-Nm0N-Nm0N-Nm0N-Nm（1）x1(n)和x2(n)是周期的。（2）求和范围为一个周期 （3）周期序列周期卷积后，序列的长度仍然是周期的；位置保持不变第47页/共269页48序列的线性卷积与周期卷积的几点区别：线性卷积的求和对参与卷积的两个序列无任何要求，而周期卷积要求两个序列是周期相同的周期序列。线性卷积的求和范围由两个序列的长度和所在的区间决定，而周期卷积的求和范围是一个周期N。线性卷积所得序列的长度(M+N-1)由参与卷积的两个序列的长度确定，而周期卷积的结果仍是周期序列，且周期与原来的两个序列周期相同。周期卷积等同于两个周期序列在一个周期上的线性卷积计算。

DFS的性质：周期卷积（4）第48页/共269页解：例：已知序列x1(n)=R4(n)，x2(n)=(n+1)R5(n)，分别将序列以周期为N=6拓展成周期序列，求两个周期序列的周期卷积和。第49页/共269页154512第50页/共269页51频域周期卷积

利用DFS的对偶性有：

若则时域相乘频域卷积DFS的性质：周期卷积(5)注意频域卷积的求和号前面有1/N。第51页/共269页52DFS的性质：共轭对称性由任一周期性序列，定义如下两个序列：共轭偶对称周期性序列共轭奇对称周期性序列

且具有如下关系：其它对称性质见教科书第52页/共269页53DFS定义和性质：小结时域周期序列与频域周期序列的关系DFSDFS的性质重点：周期移位

调制特性周期卷积第53页/共269页54对于一段有限长信号（连续），分析频谱问题是付氏积分问题，进行时域周期重复和取样两过程，就可把广义积分问题变成有限项求和，即由CTFTDFS。DFS变换：周期离散时间函数与一周期离散频率函数的组合，它们是有限求和（而不是积分），常用DFS来逼近连续时间过程的傅氏变换。也即要用数字运算能完全计算出付氏积分，必须对时间函数和频率函数取样（即DFS），选择时间有限和频率有限的信号。①时间取样：取样频率大于信号最高频率两倍；②频率取样：取样间隔足够小，使时间函数的周期（单位圆上等分（取样）的点数）大于信号的时域长度。结果：频域和时域中均不出现混迭现象。3.3有限离散傅里叶变换及其性质(1)第54页/共269页55离散傅氏级数提供了一种对离散时间傅氏变换作数值计算的技巧，它在时域和频域都是周期的，但在实际中大多数信号不具有周期性，它们很可能具有有限持续时间。对这些信号，怎样探讨一种可数值计算的傅氏表达式？理论上，可通过构造一周期信号，其基本形状为有限持续时间信号，然后计算此周期信号的DFS。实际上，这也就是定义了一种新的变换，称为离散傅氏变换（DFT），它是DFS的主周期。DFT是对任意有限持续时间序列可数值计算的傅氏变换。3.3有限离散傅里叶变换及其性质(2)第55页/共269页56同样：X(k)也是一个N点的有限长序列关系?其中:DFT定义：表达式(1)周期序列的表示第56页/共269页57DFT定义：表达式(2)若n=n1+n2N成立，且n1

满足0≤n1≤N-1，则把n1

称做n对N的模数，用符号((n))N

表示，即：n模N=((n))N=n1，也就是n对N取余数。例:是周期为N=6的序列，求n=19及n=-2两数对N的余数。解：n=19=1+3×6，((19))6=1 n=-2=(-1)×6+4，((-2))6=4即： 第57页/共269页58在无混迭的情况下，我们看如何把DFS变成DFT?DFS:DFT定义：表达式(3)因无混迭，则时域中一个周期长的主值序列对应于频域中一个周期长的主值序列。从DFS的时域和频域中各取出一个周期，即得到有限长度离散序列的时域和频域傅氏变换。第58页/共269页59

有限长序列的DFT正变换和反变换：其中：DFTDFT定义：表达式(4)或注意：从工程角度看，DFS和DFT的表达式没有本质区别。第59页/共269页60DFT的矩阵表示形式若令：则：DFT定义：表达式(5)第60页/共269页61DFT定义：表达式(6)

DFT图形解释第61页/共269页62

不仅浓缩了的全部内容，同时也浓缩了的全部内容。能够如实、全面地表示的频域特征，所以DFT具备明确的物理含义。DFT定义：表达式（7）DFT意义第62页/共269页63由上面的讨论可知，在0≤n≤N-1上，DFS和DFT相同。因此，可用类似的方法实现DFT。把原先名为dfs和idfs的Matlab函数改名为dft和idft函数，即可实现离散傅氏变换DFT。实际中，我们用的更多的是DFT的快速算法FFT，见后续内容。DFT定义：Matlab实现第63页/共269页64例：

x(n)是一个4点序列：（1）计算离散时间傅氏变换X(ejw)，并画出它的幅度和相位。（2）计算x(n)的4点DFT。DFT定义：举例第64页/共269页65解：（1）离散时间傅氏变换为：因而DFT定义：举例第65页/共269页6600.511.5201234frequencyinpiunits|X|MagnitudeoftheDTFT00.511.52-200-1000100200frequencyinpiunitsDegreesAngleoftheDTFTDFT定义：举例第66页/共269页67(2)用

X4(k)表示

4点

DFT:DFT定义：举例%b)4-pointDFTN=4;w1=2*pi/N;k=0:N-1;X=dft(x,N);magX=abs(X),phaX=angle(X)*180/pisubplot(2,1,1);plot(w*N/(2*pi),magH,'--');axis([-0.1,4.1,-1,5]);holdonstem(k,magX);

第67页/共269页68k00.511.522.533.54-1012345k|X(k)|MagnitudeoftheDFT:N=400.511.522.533.54-200-1000100200DegreesAngleoftheDFT:N=4DFT定义：举例第68页/共269页69例:

怎样得到DTFTX(ejw)的其他样本？解：显然，我们的采样频率应更小一些，也就是说，应增加

N的长度。有两种方法，一种是采样时就采样更多的样本；另一种是在序列后面添加一定长度的零，叫做填零运算，在实际中，为了得到一个较密的频谱，这种运算是必要的。

3.3.1DFT定义：举例第69页/共269页70（a）给

x(n)后附加

4个零得到一个

8点序列。

x(n)={1,1,1,1,0,0,0,0}

设

X8(k)为一

8点

DFT，

则在这种情况下，频率分辨率为

w1=2π/8=π/4。

DFT定义：举例第70页/共269页71%b)8-pointDFTN=8;w1=2*pi/N;k=0:N-1;x=[x,zeros(1,4)];X=dft(x,N);magX=abs(X),phaX=angle(X)*180/pi

结果如下：

magX=4.00002.61310.00001.08240.00001.08240.00002.6131

phaX=0-67.5000-153.4349-22.5000-90.000022.5000-53.130167.5000DFT定义：举例第71页/共269页72DFT定义：举例第72页/共269页73（b)更进一步，给

x(n)填充

12个零，变成一个

16点序列，

即：

x(n)={1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0}

在这种情况下，频率分辨率为

w1=2π/16=π/8。

DFT定义：举例第73页/共269页74%c)16-pointDFTsubplot(1,1,1)N=16;w1=2*pi/N;k=0:N-1;x=[x,zeros(1,8)];X=dft(x,N);magX=abs(X),phaX=angle(X)*180/pisubplot(2,1,1);plot(w*N/(2*pi),magH,'--');axis([-0.1,16.1,-1,5]);holdonstem(k,magX);xlabel('k');ylabel('|X(k)|');title('MagnitudeoftheDFT:N=16')holdoffsubplot(2,1,2);plot(w*N/(2*pi),phaH*180/pi,'--');axis([-0.1,16.1,-200,200]);holdonstem(k,phaX);xlabel('k');ylabel('Degrees');title('AngleoftheDFT:N=16')DFT定义：举例第74页/共269页75DFT定义：举例第75页/共269页76结论：基于以上两个例子，可以得到以下结论。填零是给原始序列填零的运算。这导致较长的DFT，它会给原始序列的离散时间傅氏变换提供间隔更密的样本。在Matlab中，用zeros函数实现填零运算。为精确地画出离散时间傅氏变换X(ejw)，只需要4点DFTX4(k)。这是因为x(n)仅有4个非零样本，因此，可通过填零得到X8(k)、X16(k)等等，用它们来填充X(ejw)的值。填零运算提供了一个较密的频谱和较好的图示形式，但因为在信号中只是附加了零，而没有增加任何新的信息，因此，它不能提供更高分辨率的频谱。为了得到更高分辨率的频谱，需要获得更多的数据。其他的先进方法则是利用边缘信息和非线性技术。

DFT定义：举例第76页/共269页77例：为了说明高密度频谱和高分辨率频谱之间的区别，考察序列

求出它基于有限个样本的频谱。（a）当0≤n≤10时，确定并画出x(n)的离散傅氏变换。（b）当0≤n≤100时，确定并画出x(n)的离散傅氏变换。DFT定义：举例第77页/共269页78(a)首先确定

x(n)的

10点DFT，得到其离散时间傅氏变换的估计

%Highresolutionspectrumbasedon100samplesofthesignalx(n)subplot(1,1,1);n=[0:1:99];x=cos(0.48*pi*n)+cos(0.52*pi*n);%Spectrumbasedonthefirst10samplesofx(n)n1=[0:1:9];y1=x(1:1:10);subplot(2,1,1);stem(n1,y1);title('signalx(n),0<=n<=9');xlabel('n')axis([0,10,-2.5,2.5]);Y1=dft(y1,10);magY1=abs(Y1(1:1:6));k1=0:1:5;w1=2*pi/10*k1;subplot(2,1,2);stem(w1/pi,magY1);%(只画了一半的点，原因是镜像对称的点）title('SamplesofDTFTMagnitude');xlabel('frequencyinpiunits');axis([0,1,0,10]);disp('PressRETURNtocontinue');pause;DFT定义：举例第78页/共269页79频谱的密度比较低，没有足够的样本数来下结论

DFT定义：举例第79页/共269页80填充

90个零以得到较密的频谱

%Highdensityspectrum(100samples)basedonthefirst10samplesofx(n)n2=[0:1:99];y2=[x(1:1:10)zeros(1,90)];subplot(2,1,1);stem(n2,y2);title('signalx(n),0<=n<=9+90zeros');xlabel('n')axis([0,100,-2.5,2.5])

Y2=dft(y2,100);magY2=abs(Y2(1:1:51));k2=0:1:50;w2=2*pi/100*k2;subplot(2,1,2);plot(w2/pi,magY2);Holdon;stem(w2/pi,magY2);title('DTFTMagnitude');xlabel('frequencyinpiunits')axis([0,1,0,10])disp('PressRETURNtocontinue');holdoff;pause;

DFT定义：举例第80页/共269页81DFT定义：举例从结果图中可以看到，此序列在

w=0.5π

处有一主频率，原始序列则没有说明这一点。填零运算提供了更加平滑,高密度的频谱曲线

第81页/共269页82（b）为得到更多的频谱信息，采集更多的样本，用

x(n)的

100个样本来确定它的

DFT。%Highresolutionspectrumbasedon100samplesofthesignalx(n)subplot(2,1,1);stem(n,x);title('signalx(n),0<=n<=99');xlabel('n')axis([0,100,-2.5,2.5])

X=dft(x,100);magX=abs(X(1:1:51));k=0:1:50;w=2*pi/100*k;subplot(2,1,2);plot(w/pi,magX);title('DTFTMagnitude');xlabel('frequencyinpiunits')axis([0,1,0,60])disp('PressRETURNtocontinue');

DFT定义：举例第82页/共269页83DFT清楚地表明了两个靠得很紧的频率，这是

x(n)的高分辨率的频谱采样更多的数据提供了更多的信息DFT定义：举例第83页/共269页84DFT从整体上可看成是由窄带相邻滤波器组成的滤波器组DFT的每个分量X(k)可看成是窄带滤波器的输出，此窄带滤波器的中心位于数字频率2πk/N弧度，带宽为2π/N。此概念的一个典型应用是数字音频压缩中的分析滤波器，例如AC3和MPEGAudio都是如此。分辨率（子带带宽）N点DFT覆盖了0到fs（取样频率）的频率范围。因此，频率取样点以fs/N为间隔。该频率间隔称为DFT的频率分辨率，它描述了DFT分辨相邻信号频率的程度。频率间隔越小，分辨率越好；间隔越大，DFT分辨率越差。假定取样频率保持不变，当取样点越大时，DFT分辨率就会越好，这样频率间隔小，可获得频谱的许多细节。从滤波器组的角度看，分辨率好的DFT是由大量非常窄的带通滤波器构成的。DFT定义：DFT频谱第84页/共269页85DFT定义：DFT频谱滤波器的中心频率DFT分量X(k)位于以下频率处：如果画出对频率f（Hz）而不是对k的频谱，则更容易从实际角度解释DFT频谱。当k=N/2时，f到达了fs/2奈奎斯特频率。因而，k=0到k=N/2的DFT点携带了DFT全部必要的幅度和相位信息。其余点只是基带重要信号频率的镜像副本，是取样的人为结果。即幅度频谱是周期性的偶对称。第85页/共269页86例:

为了体会DFT的滤波器组解释，x(t)由两个余弦信号和随机噪声构成：取样频率fs=6.4Hz。请分析其频谱。解：

x(t)包含两个频率1/16Hz和3/8Hz，以6.4Hz取样后，相应的数字频率由ω=ΩT=2πf/fs，分别为ω1=2π/102.4和ω2=6π/51.2弧度。则在40秒内以6.4Hz进行取样，共得40×6.4=256个取样点。DFT定义：DFT频谱第86页/共269页873.3.1DFT定义：DFT频谱15第87页/共269页88在上图中随机噪声采用的是正态分布的高斯白噪声（randn函数），由于白噪声信号中所有频率的贡献均相等，所以白噪声频谱近似平坦。对于N=256点DFT，每个标号k对应于数字频率2πk/256弧度。由于DFT可以看作一组相邻窄带滤波器构成，每个滤波器以数字频率2πk/256弧度为中心。因而频谱峰值应位于2πk/256=2π/102.4和2πk/256=6π/51.2，即k=2.5（非整数）和k=15（整数）处。由于k必须是整数，k=2.5处的峰值又分成k=2和k=3处的两个小峰。当DFT变换的长度N是多个数字频率公倍数的整数倍时，即数字频率正好位于子带滤波器的中心频率上时，则得到理想的谱线。DFT是在频谱中对连续频谱进行取样，因此DFT不能超过DFT频率分辨率所允许的范围而去准确定位频率。即当信号谱线所在位置与DFT频率分辨率位置保持一致时，则能准确定位此谱线；当DFT中没有频率与所分析信号的重要频率相符时，DFT就将导致真实频谱的模糊。DFT定义：DFT频谱第88页/共269页89例:

以256Hz取样频率对信号取样，得到离散信号x(n)，计算其频谱。解：数字频率：

数字信号：

数字周期：数字周期为64，覆盖了15个模拟信号周期。DFT定义：DFT频谱第89页/共269页90

对上述离散信号进行N=128和N=130点DFT，因为128是64的整数倍（2倍），从图中看，128点DFT的幅度频谱中有两个理想尖锋，第二个尖锋是第一个的镜像，频谱中的理想尖锋就标志着正弦的频率。而当N=130不是该数字信号的数字周期64的整数倍，尖锋变宽并变小了，这就是频谱模糊现象。3.3.1DFT定义：DFT频谱30第90页/共269页91序列x(n)的Z变换在单位圆上进行N等分，即＝2/N，就是序列的DFT变换。(取样）Z变换和DFT的关系是取样和内插的关系，这在实际应用中很重要。DFT与DTFT和Z变换的关系第91页/共269页92取样Z变换设x(n)为一个长度为N的有限长序列，则有：DFT与Z变换的关系：取样Z变换第92页/共269页93从DTFT的角度看：有限长序列的DFT结果包含了N个离散频率点处的DTFT结果，这个离散频率点等间隔地分布在区间[0，2π)内；从Z变换的角度看：

DFT结果包含了z平面上N个离散点处的Z变换结果，这N个离散点均匀地分布在单位圆上，由此也称DFT为单位圆上的取样Z变换。

DFT与Z变换的关系：取样Z变换第93页/共269页94频域取样定理：若序列长度为M，则只有当频域采样点数N满足N≥M时，才有:即可由频域取样X(k)不失真地恢复原信号x(n)，否则产生时域混叠现象。此时可由N个取样值X(k)内插恢复出X(z)或X(ejw)。DFT与Z变换的关系：

z域内插时域取样定理：在满足奈奎斯特定理条件下，时域取样信号可以不失真地还原原连续信号。频域取样情况如何？取样条件？内插公式？第94页/共269页95Z域内插公式：由DFTX(k)

可以确定z平面上任一点处的X(z)DFT与Z变换的关系：z域内插z平面内插公式

内插函数

第95页/共269页96内插函数的零极点分布极点：(N-1)阶极点z=0；一阶极点z=1；零点：N个一阶零点:

抵消：z=1处的一阶极点和一阶零点互相抵消，一阶零点数量变为（N-1）个。3.3.2DFT与Z变换的关系：z域内插Φ(z)的零、极点分布

零、极点互相抵消第96页/共269页973.3.2DFT与Z变换的关系：F域内插F域内插公式：由频域取样DFTX(k)表示DTFTX(ejw)第97页/共269页98即:其中:频域内插函数

频域内插公式

3.3.2DFT与Z变换的关系：F域内插第98页/共269页99F内插函数的零极点分布根据Φ(z)的零极点分布规律可知：(零极点对系统频率响应的影响)极点：ejω到极点z=0的距离恒为1，对幅频特性没有影响零点：在区间[0,2π]内，|Φ(ω)|存在(N-1)个零值点存在(N-1)个极值点，分别为：Φ(z)的零、极点分布

零、极点互相抵消3.3.2DFT与Z变换的关系：F域内插第99页/共269页100插值函数的幅度特性与相位特性（N=5)DFT与Z变换的关系：F域内插第100页/共269页101频域内插的物理含义

k0N-NnN0-Nnx(n)0只有当频域取样点数N大于序列长度M时，中不会出现混迭现象，这时能够从中如实恢复x(n)，即能够由X(k)准确重建X(z)和X(ejw)。对序列作DFT变换点数不应低于序列的长度。X(k)浓缩了x(n)在变换域中的全部特性。DFT与Z变换的关系：F域内插第101页/共269页102这里，序列长度及DFT点数均为N若不等，分别为N1、N2，则需补零使两序列长度相等，均为N，且

若两序列x1(n)和x2(n)的长度均为N，且其N点DFT分别为：则：DFT的性质：线性a,b为任意常数第102页/共269页103对于周期序列，有：

其中：

—周期共轭偶对称分量

—周期共轭奇对称分量又定义：

又由于 则：

即有限长序列由共轭偶对称和共轭奇对称两部分组成。DFT的性质：对称性—共轭奇对称分量—共轭偶对称分量第103页/共269页104DFT的性质：对称性第104页/共269页105若存在有限长序列x(n)，长度为N，其N点DFT的结果为X(k)，则有，证明：DFT的性质：帕斯瓦尔定理该定理表明:可利用序列的DFT结果表示信号的能量，序列在时域计算的能量与在频域计算的能量相等，即变换前后的能量保持不变。这进一步说明，虽然DFT有别于DTFT，但其仍然具有明确的物理含义。第105页/共269页106DFT的性质：反转定理

循环反转的定义如果x(n)是长度为N的序列，则称x((-n))NRN(n)为x(n)的循环反转运算。

循环反转运算是有限长序列所特有的一种运算，其结果仍然是集合{0,1,…..,(N-1)}上的有限长序列，特别注意n=0时情况。

计算过程：（1）补零为N；（2）周期延拓；（3）纵轴镜像；（4）取主值序列。第106页/共269页107DFT的性质：反转定理

循环反转的DFT若则证明：第107页/共269页108DFT的性质：序列的循环移位(圆周移位)

循环移位的定义：称其为循环移位的原因在于，当序列从一端移出范围时，移出的部分又会从另一端移入该范围。线性移位：若N点序列沿一方向线性移位，它将不再位于区间0≤n≤N-1上。第108页/共269页109DFT的性质：序列的循环移位(圆周移位)有的书上称为圆周移位。把x(n)看作排列在N等分的圆周上，循环移位就相当于序列x(n)在圆周上移动，故称为圆周移位。实际上重复观察几周时，看到的就是周期序列。第109页/共269页110例：设x(n)=10(0.8)n，0≤n≤10为11点序列(a)画出x((n+4))11R11(n)，也就是向左循环移位4个样本的序列；(b)画出x((n-3))15R15(n)，也就是假定x(n)为15点序列，向右循环移位3个样本。DFT的性质：序列的循环移位(圆周移位)解：x((n+4))11R11(n)，也就是向左循环移位4个样本的序列；特别注意当样本从一个方向移出

[0,N-1]，它们将从相反方向再现。这就是循环移位的含义，它不同于线性移位。

第110页/共269页111(b)在这种情况下，给x(n)后填充4个零，将其看作一个15点序列。此时的循环移位与N=11时不同，看起来像线性移位x(n-3)。因此，序列的周期长度是非常重要的一个参数。DFT的性质：序列的循环移位(圆周移位)第111页/共269页112结论：有限长序列的循环移位，在离散频域中只引入了一个和频率成正比的线性相移，对幅频特性没有影响。DFT的性质：序列循环移位后的DFT若，则证明：第112页/共269页113时域序列的调制等效于频域的循环移位DFT的性质：频域循环移位后的IDFT

频域循环移位后的IDFT（调制特性）由DFT所具有的对偶特性不难看出，在频域内循环移位时，将有类似的结果，即：证明：第113页/共269页114DFT的性质：频域循环移位后的IDFT证明：第114页/共269页115DFT的性质：循环卷积(圆周卷积)

循环卷积定义：设x1(n)和x2(n)都是长度为N的有限长序列，把它们分别拓展为周期序列和，定义循环卷积为：

——周期序列卷积后取主值第115页/共269页116因为上式的求和范围是m由0到N-1，因此第一个序列x1(m)可以不作周期拓展，即注意两个N点序列的线性卷积将导致一个更长的序列。而循环卷积将区间限制在0≤n≤N-1，结果仍为N点序列，它与线性卷积的结构类似。不同点在于求和范围和N点循环移位。它与N有关，也叫做N点循环卷积。DFT的性质：循环卷积(圆周卷积)N窗函数限定了循环卷积的范围第116页/共269页117循环卷积过程：（1）补零（2）周期延拓（3）反转，取主值序列

（循环反转）（4）对应位相乘，然后求和，得到n=0时的卷积结果。（5）向右循环移位（圆周移位）（6）重复，n=1~(N-1)DFT的性质：循环卷积(圆周卷积)mx2(m)mx1(m)00NNmx2((0-m))N0Nmx2((1-m))N0Nn0N注意n=0时的循环反转第117页/共269页118循环卷积的时频映射关系由DTFT的性质可知，两个序列时域上的线性卷积运算在频域上表现为两个序列DTFT结果的乘积。同样的，若 则 即当在频域中进行两个N点DFT相乘时，在时域中映射为循环卷积（而不是通常的线性卷级！！！）。DFT的性质：循环卷积(圆周卷积)第118页/共269页119证明：

将X1(k)和X2(k)作周期延拓，分别得到X1((k))N

和X2((k))N。则再设于是DFT的性质：循环卷积(圆周卷积)令第119页/共269页120因为所以

此时上式最后一个求和号中，已不对r求和，故此求和号可以去掉，因此，因而，即DFT的性质：循环卷积(圆周卷积)第120页/共269页121利用时域、频域的对偶性可得频域循环卷积:若则

时域循环卷积可在频域中完成:DFT的性质：循环卷积(圆周卷积)第121页/共269页122（1)同心圆法（2)利用求周期卷积的作图法（3)解析式法（4)Matlab方法DFT的性质：循环卷积计算方法第122页/共269页123同心圆法

可用两个同心圆来表示：

x1(n)：内圆顺时针方向排列

x2(n)：外圆逆时针方向排列

x1(0)与x2(0)对齐。DFT的性质：循环卷积计算方法第123页/共269页124两圆上对应数两两相乘后求和，得x3(0);将x2(n-m)移位一位，即外圆顺时针转动一位，重复（1）步骤，得x3(1)；依次下去，求得 DFT的性质：循环卷积计算方法第124页/共269页125作图法

(1)x1(m)和x2(m)在m轴上周期延拓，成为

(2)将反转；

(3)计算周期卷积

(4)取一个周期，得到DFT的性质：循环卷积计算方法第125页/共269页

mx2(m)0Nmx1(m)mx2((0-m)NRN(m)0Nmx2((1-m)NRN(m)0Nn0图示两个序列的循环卷积

0N上述过程：只需将x1(n)和x2(n)分别做周期延拓，得到和，再按照计算周期卷积的作图法，计算出n由0到N-1的周期卷积，即为循环卷积。第126页/共269页127DFT的性质：循环卷积计算方法例:

设x1(n)={1,2,2}，x2(n)={1,2,3,4}，计算4点循环卷积解：注意x1(n)为3点序列，进行循环卷积之前在其尾部填一个零，使其成为4点序列，分别在时域和频域中求解这个问题。第127页/共269页128（1）时域方法

4点循环卷积由下式给出对每个n产生一个循环移位序列，将它的样本逐个与x1(m)相乘，然后求和，得此n值的循环卷值，在0≤n≤3上重复此过程。考虑x1(m)={1,2,2,0}和x2(m)={1,2,3,4}。n=0时,DFT的性质：循环卷积计算方法注意此为x2(0)，而不是{4,3,2,1}第128页/共269页129n=2时，DFT的性质：循环卷积计算方法n=3时，因此，第129页/共269页130(2)频域方法：

首先计算x1(n)和x2(n)的4点DFT，逐个样本相乘，取IDFT，得到循环卷积。DFT的性质：循环卷积计算方法则（注意：X1(k)和X2(k)对应位相乘）

IDFT后，得表面看来，这样做反而更复杂，且涉及复数运算。但后面我们会看到，DFT有快速算法FFT，特别是当N很大时，效率会显著提高。第130页/共269页131利用DFT求离散线性卷积条件：N≥N1+N2-1方法：时域转换到频域，处理后再转换回时域用DFT进行信号频谱分析参数选择频谱泄漏栅栏效应DFT的应用第131页/共269页132

线性移不变离散系统

当长度N增大时，线性卷积的运算量较大，需寻找实用的线性卷积的快速计算方法！DFT的应用：线性卷积求解

循环卷积的时频映射

频域中进行两个N点DFT相乘时，在时域中映射为循环卷积（而不是通常的线性卷级！！！）。快速算法FFT第132页/共269页133线性卷积：N点循环卷积：DFT的应用：线性卷积求解循环卷积和线性卷积的关系第133页/共269页134

讨论线性卷积y(n)=x(n)*h(n)的长度

从x(m)看，非零值区为：0≤m≤N-1从h(n-m)看，非零值区为：0≤n-m≤M-1将二不等式相加，得到y(n)的非零区：

0≤n≤M+N-2在此区间之外，不是x(m)=0，就是h(n-m)=0，即y(n)=0，因此，y(n)的长度为

M+N-1DFT的应用：线性卷积求解第134页/共269页135讨论循环卷积的长度循环卷积是周期卷积的主值序列。为了研究长度不等的两个序列的周期卷积，构造周期序列，使它们的长度相等，且均为L。表示为DFT的应用：线性卷积求解第135页/共269页136周期卷积如下：周期卷积是线性卷积的周期延拓，周期为L。当周期为L≥N+M-1时，不会发生混迭，线性卷积正好是周期卷积的一个周期。循环卷积又是周期卷积的主值序列。DFT的应用：线性卷积求解因为，即0≤m≤L-1范围内x(m+qL)只有一个周期。第136页/共269页137由于循环卷积是周期卷积的主值序列。因此，此时循环卷积与线性卷积完全相同。即：

因此，循环卷积等于线性卷积的条件是：即对于N长度的x(n)，M长度的h(n)，在它们后面补零，使其长度均变为L≥M+N-1。DFT的应用：线性卷积求解第137页/共269页第138页/共269页139讨论若序列的长度为，序列的长度为，且有大于，那么，和的点循环卷积结果为：

其中，第139页/共269页此时，两序列的线性卷积结果的长度，对其在时域作周期为的延拓相加得到序列

主值序列的前个点存在混迭。因此，在中也就是说，序列中最后个点与两序列的线性卷积结果相同。

第140页/共269页例：现存在两个有限长序列（）和（），其20点循环卷积结果为，而其线性卷积结果为，问：

(1)中哪些点与相同；(2)需要进行多少点循环卷积才能保证和完全相同。

答：（1）7～19点（2）27点第141页/共269页142

即时域循环卷积频域相乘DFT的应用：线性卷积求解设若则用DFT求解线性卷积第142页/共269页143如果循环卷积的长度N满足N≥N1+N2-1，则此循环卷积Y(k)就等于x(n)和h(n)的线性卷积。用流程图表示法求y(n)=x(n)*h(n)的过程如下：因为DFT、IDFT都有快速算法，因此，线性卷积可以实现快速算法。DFT的应用：线性卷积求解IDFTN点DFTN点DFTN点)(kX)(kH)(kH)(kX)(ny)(nx)(nh2N长度1N长度121-+=NNN第143页/共269页144DFT的应用：线性卷积求解乘法次数循环卷积：在上述DFT求解线性卷积过程中，需要3次