数字信号处理 黄海 课件第八章-离散傅里叶变换

第八章离散傅立叶变换TheDiscreteFourierTransform8.0引言几种傅立叶变换的形式（1）傅立叶级数-----连续周期时间函数，周期为TX(jkΩT)----频率成分的幅度，ΩT

=2π/T称为基频，离散序列

傅里叶级数的系数

时域：连续周期频域：离散非周期（2）傅立叶积分x

(t)-----连续非周期时间函数X(jΩ)----连续频域函数（频谱）Ω表示频率

时域：连续非周期频域：连续非周期（3）序列的傅立叶变换x[n]-----

非周期离散序列（无限长、有限长）X(ejω)-----连续周期函数

时域：离散非周期频域：连续周期用于实际计算（计算机）的傅立叶变换的要求：（1）时域序列-----有限长（2）其傅立叶变换-----离散序列-----有限长 时域：离散有限长频域：离散有限长称：离散傅立叶变换（DFT）离散傅立叶变换-------数字信号处理算法核心（基本）算法推导离散傅立叶变换：周期序列有限长序列之间关系第一步：周期序列的傅立叶变换-----离散傅立叶级数（DFS）第二步：周期序列有限长序列关系-----DFT8.1周期序列的表示：离散傅立叶级数定义为周期为N的周期序列，对任一整数n和r有：

考虑到：连续周期信号基频的各次谐波（复指数函数）之和则，离散周期序列基频为2π/N的复指数序列之和-----表示为离散傅立叶级数复指数序列：

周期序列离散傅立叶级数表示式（定义）：k为整数连续周期信号的傅立叶级数无穷多个谐波（频率）（之和）离散周期信号的傅立叶级数l为整数，表示N个独立周期复指数e0[n],e1[n],…,eN-1[n]则：N个独立谐波（频率）（之和）即：离散傅立叶级数的一半，直接构造（定义）出，作为变换，需求出（推导）另一半（反变换）：对上述两边乘以e-j(2π/N)rn，并从n=0

到n=N-1求和，可得交换右边求和次序，考虑到复指数的正交性：可得：即得傅立叶级数的系数：由于

--------周期序列，周期为N（对于所有k）也可以看成：有限长序列，对于k=0,…,(N-1),其它k，值为零合理性：只用到0≤k≤(N-1)的离散傅立叶级数（DFS）的表示式：时域：离散周期频域：离散周期定义符号：DFS可表示为：记号：分析式（Analysisequation）综合式（Synthesisequation）均为周期为N的周期序列例8.1周期脉冲串的离散傅立叶级数考虑一个周期脉冲串：周期为N的脉冲对于根据DFS定义式求出DFS系数为：再将结果代入综合式：正交性：当n=rN，指数序列和为1，否则为零DFS的对偶性例8.2离散傅立叶级数的对偶性令DFS的系数为一周期为N的周期脉冲串：代入DFS公式，得：与例8.1相比较，可以看到：非常相似，只相差常数因子和指数的符号例8.3周期矩形脉冲串的离散傅立叶级数周期N=10的矩形脉冲串（N=0~9）：求DFS,DFS-----离散周期时间序列的傅立叶变换（频域表示）

有限长离散时间序列傅立叶变换（DFT）的基础先讨论DFS的性质，然后导出DFT表示式8.2离散傅立叶级数的性质傅立叶变换（不同形式）、拉氏变换、z变换性质的相似性。注意点：，周期性重要差别8.2.1线性8.2.2序列的移位注意大于周期N的移位，即m≥N，若m=m1+m2N情况（无法区分）相似有频域移位：8.2.3对偶性DFS的分析式与综合式十分相似时域与频域对偶性原因：周期离散时间信号

（非周期信号与它的傅立叶变换是两类十分不同的函数）对偶性8.2.4对称性8.2.5周期卷积若：则有：或：说明： （1）两个序列均为同周期N

（2）求和只在一个周期上进行证明：交换求和次序由DFS的移位性质代入上式，可得表示为：例8.4周期卷积由对称性，若有：8.2.6周期序列DFS表示的性质汇总8.3周期信号的傅立叶变换序列傅立叶变换的收敛性一致收敛-----序列绝对可和均方收敛-----序列平方可和周期信号------既不满足绝对可和也不满足平方可和将周期信号的离散傅立叶级数(并入)傅立叶变换的框架

即：同为离散序列

或：回顾第二章序列傅立叶变换的推广：如果序列能够表示为复指数的和则其傅立叶变换可以表示为脉冲串的形式，即：表示每个指数序列对于离散周期序列，DFS的形式为：周期信号的傅立叶变换

------频域的脉冲幅值正比于序列DFS

系数的一个脉冲串定义：周期序列的傅立叶变换：周期，周期为N，脉冲串的间隔是2π/N的整数倍

-----周期，周期为2π。证明：将上式代入序列的傅立叶变换式其中ε

满足不等式0<ε

<(2π/N),包含ω

=0处的脉冲，而不包括ω

=2π处的脉冲。交换求和与积分次序ω=0~2π

的积分区间-----只包括对应于k=0,1,….(N-1)的脉冲上述的工作表明：尽管周期序列的傅立叶变换在通常意义下是不收敛的但引入脉冲函数后，可以将周期序列纳入傅立叶变换分析的框架内------傅立叶变换的扩展（如双边常数序列、复指数序列等）例8.5周期脉冲串的傅立叶变换周期为N的周期脉冲串：由例8.1的结果知，对所有的k，其傅立叶变换为：周期信号有限长信号之间的关系（傅立叶变换意义上）有限长信号x[n]，在0≤n≤N-1区间外x[n]=0考虑其与周期脉冲串（周期为N）的卷积：表示周期序列可以看成是由有限长序列的周期重复序列组成：周期序列的傅立叶变换可以表示为：比较周期信号傅立叶变换的定义式：可以得出：表示：DFS系数的周期序列可以看成有限长序列傅立叶变换的等间隔采样。该有限长序列是周期序列的一个周期：上述结果也可以简单获得：比较可得：例8.6傅立叶级数系数与一个周期的傅立叶变换之间的关系例8.3中周期序列的一个周期为（周期N=10）：其傅立叶变换为：可以证明，在本题情况下，将ω

=2πk/10代入上式，即可满足周期序列的傅立叶级数：与例8.3结果相同。傅立叶级数与傅立叶变换之间的关系

之间的关系：周期信号有限长信号之间的关系有限长信号x[n]，在0≤n≤N-1区间外x[n]=0考虑其与周期脉冲串（周期为N）的卷积：表示周期序列可以看成是由有限长序列的周期重复序列组成：该有限长序列是周期序列的一个周期：由：比较可得：表示：DFS系数的周期序列可以看成有限长序列傅立叶变换的等间隔采样。例8.6傅立叶级数系数与一个周期的傅立叶变换之间的关系例8.3中周期序列的一个周期为（周期N=10）：其傅立叶变换为：可以证明，在本题情况下，将ω

=2πk/10代入上式，即可满足周期序列的傅立叶级数：与例8.3结果相同。傅立叶级数与傅立叶变换之间的关系

之间的关系：8.4对傅立叶变换采样非周期序列：傅立叶变换X(ejω)周期序列：其DFS的系数为X(ejω)在频率上等间隔的采样（前提：周期序列是非周期序列的重复叠加产生）讨论：周期序列与非周期序列的更一般关系考虑一非周期序列x[n]，其傅立叶变换为X(ejω)序列是通过对X(ejω)在ωk=2πk/N频率处采样得到，即为周期序列，周期为N，也可以表示为X(z)在单位圆上的N个等间隔采样：图是当N=8时的采样点，具有周期（重复）序列样本序列是周期为N的周期序列，可以是一个序列的离散傅立叶级数的系数序列：因为已假定存在x[n]的傅立叶变换将上式代入并将结果代入前式，可得交换求和次序，得到：式中最终可以得出：表明：是一个周期序列（x[n]与周期单位脉冲串的卷积）与对应的周期序列：x[n]平移（无数个）相加而是x[n]X(ejω)进行采样结果图中，x[n]的长度为9，平移的周期N=12，平移相加后序列没有重叠。上图表示取N=12，x[n]X(ejω)相同序列当N取7时平移后的结果：序列有重叠。表示：为X(ejω)的采样（频域），N为每个周期（2π）的采样点数。如果N大于x[n]的长度，得到的周期序列没有重叠（时域混叠），从中可以得到（恢复）x[n]，同样，X(ejω)也可以从恢复得到。时域采样频域混叠（现象）-----避免混叠频域采样时域混叠（现象）-----避免混叠归纳：非周期序列x[n]傅立叶变换X(ejω)的采样===

x[n]周期重复得到的DFS的系数如果x[n]为有限长，只要对X(ejω)的采样点数足够多（≥x[n]

的长度N）,则X(ejω)可以由恢复得到，同样，X(ejω)的恢复------内插公式利用DFS表示有限长序列-------离散傅立叶变换（DFT）须记住：（1）有限长序列x[n]

实际上代表周期序列的一个周期 （2）同时也表示离散傅立叶变换隐含着周期性8.5有限长序列的傅立叶表示：离散傅立叶变换（DFT）DFT：时域有限长序列x[n]

频域有限长序列X[k]DFS：时域周期序列频域周期序列

表示为：N------x[n]

的长度，也是的周期表示为：或：由DFS求和区间：可得：有DFT表示为：说明：x[n]----N

点

没有混叠意味着上式中等号表示为“等同于”频域之间关系

由于DFT由DFS导出，并有 和x[n]和X[k]隐含着周期性DFT一般解释：（1）有限长序列x[n]

的离散傅立叶变换X[k]是其序列傅立叶变换X(ejω)

主值周期[0,2π]的抽样。（2）有限长序列x[n]

是周期序列的一个周期一个思考问题：x[n]

无限长？x[n]

截断？x[n]

补零？例8.7矩形脉冲的DFT一矩形序列：可以看成一个长度N≥5的任意有限长序列若作为一个N=5的序列其相应的周期序列为：求出DFS:表示只有在k=0和k=5的倍数处才有非零值，如图所示：X(ejω)与的抽样关系，的周期序列，X[k]可表示为：若将x[n]看成是一个N=10的有限长矩形序列，相应的周期序列为：其X(ejω)和DFS为：

注意X(ejω)是相同的DFT为：表明：x[n]的上述改变，不影响其傅立叶变换X(ejω)

，但对X[k]的影响很大。------信号的补零问题，截断的误差问题哪个X[k]准确？8.6离散傅立叶变换的性质关注点（差异性）：DFT隐含的周期性8.6.1线性两个有限长序列x1[n]和x2[n]的线性组合：

x3[n]=ax1[n]+bx2[n]则x3[n]的DFT为：

X3[k]=aX1[k]+bX2[k]若x1[n]-----N1

x2[n]-----N2则X3[k]的计算长度N=N3=max[N1,N2]，需补零。

N≥max[N1,N2]情况？8.6.2序列的循环移位（circularshift）移位:(1)通常意义的移位，(2)周期移位，(3)循环移位相对应的数学运算:(1)线性卷积,(2)周期卷积,

(3)循环卷积定义：有限长序列x[n]，长度为Nx[n]（周期延拓）（周期移位）（截取主值周期，0≤n≤N-1）记为x1[n]

即：若则例8.8序列的循环移位与线性移位的区别在区间内移出移进8.6.3对偶性若则例8.9DFT的对偶关系长度N=10X[k]实部X[k]虚部8.6.4对称性x[n]的共轭对称、共轭反对称、实数 与相应的X[k]的共轭对称、共轭反对称、实数之间特性注意：或对称特性8.6.5循环卷积定义：两个长度均为N的有限长序列x1[n]和x2[n]或为循环卷积，记为：例8.10与延迟脉冲序列的循环卷积x2[n]------长度为N的有限长序列x1[n]------延迟脉冲序列

x1[n]=δ[n-n0]，0<n0<N可以表示为：其DFT为：若将其乘以x2[n]的DFTX2[k]:由DFT的移位性质，相应的时间序列x3[n]是x2[n]右移n0的结果也是循环卷积的结果。如下图（n0=1）：例8.11两个矩形脉冲的循环卷积若L=6=N，DFT为：将X1[k]和X2[k]直接相乘，得由此可得：x2[((n-m))N]若作2L点的循环卷积，两个序列均补L个零，即N=2L与线性卷积结果相同DFT:DFT的循环卷积性质可表示为：或式中N=L时等于18.6.6DFT性质汇总8.7用离散傅立叶变换实现线性卷积卷积的快速计算方法：利用傅立叶变换的卷积性质即，时域卷积频域相乘（1）分别计算两个时间序列的傅立叶变换，X1[k]，X2[k]（2）将两个傅立叶变换相乘，X1[k]X2[k]（3）对结果进行傅立叶反变换，DFT的快速算法（FFT）上述过程的计算速度>>直接的卷积计算问题：实际问题的卷积运算------线性卷积线性系统的输入输出关系DFT的卷积（性质）------循环卷积解决：循环卷积===线性卷积8.7.1两个有限长序列的线性卷积x1[n]-----L点长；x2[n]-----P点长线性卷积：x3[n]-----(L+P-1)点长很显然，与DFT相应的循环卷积不同：（1）长度不同

x1[n]，x2[n]-----N点长（同长度）

x3[n]-----N点长（同长度）（2）结果不同

与所取的序列长度N有关（补零）8.7.2循环卷积作为带有混叠的线性卷积讨论循环卷积计算的长度线性卷积的关系循环卷积作为线性卷积产生误差的原因------时域混叠（从理论上）线性卷积：

x1[n]-----L点长；x2[n]-----P点长定义一个DFT，即对X3(ejω)的主值周期（0--2π）N点抽样：亦即，

(L+P-1)点长均为N点长相应的时间序列：和-------循环卷积

是否有混叠也就是X3[ejω]抽样过程中是否保证

N≥（L+P-1）------x3[n]的长度循环卷积==线性卷积的条件（从图示上）例8.12循环卷积作为带有混叠的线性卷积x1[n]=x2[n]-----常数序列，长度L=P=6x3[n]长度L+P–1=11有混叠的循环卷积++=有贡献有贡献无贡献很显然，当N=2L时，周期叠加的结果不产生混叠，其结果也与线性卷积相同。（此时只有x3[n]

对结果有贡献）N=2L=12，在0≤n≤N-1内结果一样。8.7.3用DFT实现线性时不变系统系统输入：x

[n]-----L点长系统脉冲响应：h

[n]-----P点长系统输出：-----(L+P-1)点长x

[n]，h

[n]

均补零到(L+P-1)点长X

[k]H

[k]y

[n]

许多实际情况：（1）输入无限长，或很长（2）输出延迟要小直接用DFT进行线性卷积运算不能满足要求解决的方法：块卷积

-----对输入进行分段计算系统的输出衔接得到输出每一段输入对应的系统输出-------应用DFT实现脉冲响应h[n]长度P输入序列x[n]分段长度LL>P输入序列可表示为：输出的卷积运算可表示为：其中：xr[n]非零点（长度）------Lh[n]非零点（长度）------Pyr[n]非零点（长度）------L+P-1可用N

≥L+P-1点DFT计算注意：xr[n]的起点：0，L，2L，3L，…

每一个yr[n]重叠（P-1）点，须参与求和运算称为重叠相加法（overlap-addmethod）分段卷积块卷积的另一种算法------重叠保留法（overlap-savemethod）（1）P点h[n]与L点xr[n]的L点循环卷积（2）保留循环卷积结果中对应于线性卷积的部分（3）每段结果最后组合成输出y[n]L点序列与P点序列（L>P）循环卷积（P点序列补零到L长度）：即L点循环卷积：前（P-1）点不正确，其余点与线性卷积结果相等输入序列的分段：每段长度仍为L前后段重叠（P-1）点即：每一段卷积结果yrp[n]的前面（P-1）部分必须去掉，再将结果头尾相接组成输出序列y

[n]：式中8.8离散余弦变换（DCT）信号变换-------信号分解： 一组（可以是无穷）函数的线性组合如DFT，一组指数序列（函数）的线性组合（加权和）X(ejω)即为加权系数------物理意义不同的函数组------不同的信号变换存在无穷多个不同的函数组--------具有无穷多个不同的信号变换傅立叶变换只是其中具有特殊意义的一种变换这种函数组------基函数（basisfunction）对应于矢量分解中的基矢量矢量空间（线性代数）-------函数空间（泛函）基函数（序列）特性： 正交性（最主要特性之一）

DFT是典型的一种由上述的理论与思想，一般类有限长变换可以表示为：很显然，DFT可以看成其中的一个例子式中φk[n]为基序列，它们相互正交：对应于DFT，基序列φk[n]=ej2πkn/N寻找一组基序列（当x[n]为实序列时）：（1）基序列本身是实序列；（2）变换序列A[k]也是实序列。8.8.1DCT的定义参考DFT的推导：有限长序列周期序列频域关系表示（恢复）原序列DCT:（根据DFT的实偶对称性质）（实质：DFT的一种特殊形式）有限长序列周期的对称序列能够唯一恢复原有限长序列构成周期的对称序列方式------多种-----不同种类的DCT例一个N=4点序列的例子：原4点序列作为周期对称序列的前4点-------周期可以不同周期:(2N-2)=6关于n=0和n=(N-1)=3偶对称周期:

2N=8关于n=-1/2和n=7/2偶对称（半样本点对称）周期:

4N=16关于n=0和n=8偶对称4种类型的周期延拓分别对应于4种离散余弦变换，即DCT-1，DCT-2，DCT-3和DCT-4常用：DCT-1和DCT-2周期:

4N=16关于n=-1/2和n=15/2偶对称（半样本点对称）8.8.2DCT-1和DCT-2的定义周期延拓：N点序列