第三章 离散傅里叶变换DFT: Discrete Fourier Transform学习目标• 理解傅里叶变换的几种形式• 了解周期序列的傅里叶级数及性质，掌握 周期卷积过程• 理解离散傅里叶变换及性质，掌握圆周移 位、共轭对称性，掌握圆周卷积、线性卷 积及两者之间的关系• 了解频域抽样理论• 理解频谱分析过程• 了解序列的抽取与插值过程作业练习 P138: • 1 • 3 • 5(1)(2)( 3) • 8 • 9 • 11(选做)• 14 • 20• 1753年，Bernoulli就推断一振动的弦可以表示成正弦 加权和的形式，但是他未能给出所需的加权系数 • Jean-Baptiste-Joseph Fourier于1768年3月出生在法国的 Auxerre，当他8岁时不幸成了一名孤儿Fourier对数 学产生了浓厚的兴趣21岁那年，Fourier在巴黎学术 界论述了有关数值方程解的著名论作，这一工作使他 在巴黎的数学界出名 • 1798年，拿破仑侵略埃及，在侵略队伍中一些有名的 数学家和科学家，Fourier就是其中的一位， • 回国后，Fourier被任命为格勒诺布尔伊泽尔省的长官 ，就是在此期间，Fourier完成了其经典之作Theorie analytiquede la chaleur(热能数学原理)。
在该著作中， 他证明了任一周期函数都可以表示成正弦函数和的形 式，其中正弦函数的频率为周期频率的整数倍 Fourier离散傅里叶变换不仅具有明确的物理意义 ，相对于DTFT他更便于用计算机处理但是 ，直至上个世纪六十年代，由于数字计算机 的处理速度较低以及离散傅里叶变换的计算 量较大，离散傅里叶变换长期得不到真正的 应用，快速离散傅里叶变换算法的提出，才 得以显现出离散傅里叶变换的强大功能，并 被广泛地应用于各种数字信号处理系统中 近年来，计算机的处理速率有了惊人的发展 ，同时在数字信号处理领域出现了许多新的 方法，但在许多应用中始终无法替代离散傅 里叶变换及其快速算法 3.2、Fourier变换的几种可能形式时间函数 频率函数连续时间、连续频率—傅里叶变换连续时间、离散频率—傅里叶级数离散时间、连续频率—序列的傅里叶变换离散时间、离散频率—离散傅里叶变换(DFS：离散傅里叶级数，DTFT：序列的傅里叶变换， DFT：离散傅里叶变换）为了便于更好地理解DFT的概念，先讨论周期序列及其 离散傅里叶级数（DFS）表示 §3.3 离散傅里叶级数（DFS） 一个周期为N的周期序列，即， k为任意整数，N为周期 周期序列不能进行Z变换，因为其在 n=-到+ 都 周而复始永不衰减，即 z 平面上没有收敛域。
但是 ，正象连续时间周期信号可用傅氏级数表达，周期 序列也可用离散的傅氏级数来表示，也即用周期为 N的正弦序列来表示周期为N的正弦序列其基频成分为：K次谐波序列为：但离散级数所有谐波成分中只有N个是独立的 ，这是与连续傅氏级数的不同之处，即 因此 将周期序列展成离散傅里叶级数时，只需取 k=0 到 (N-1) 这N个独立的谐波分量，所以一个周期序列的离 散傅里叶级数只需包含这N个复指数，利用正弦序列的周期性可求解系数 将上式两边乘以 ，并对一个周期求和 k=r ,N=8k≠r ,N=8上式中[ ]部分显然只有当k=r时才有值为1,其他任意k值时均为 零,所以有或写为1) 可求 N 次谐波的系数2） 也是一个由 N 个独立谐波分量组成的傅里 叶级数3） 为周期序列，周期为N•时域上周期序列的离散傅里叶级数在频域上仍是一个 周期序列是一个周期序列的离散傅里叶级数 (DFS)变换对，这种对称关系可表为 习惯上：记DFS变换对公式表明，一个周期序列虽然是无穷 长序列，但是只要知道它一个周期的内容（一个周期 内信号的变化情况），其它的内容也就都知道了，所 以这种无穷长序列实际上只有N个序列值的信息是有 用的，因此周期序列与有限长序列有着本质的联系。
则DFS变换对可写为DFS[·] ——离散傅里叶级数变换IDFS[·]——离散傅里叶级数反变换可看作是对 的 一个周期 做 变换 然后将 变换在 平面单位圆上按等间隔角 抽样得到假设 都是周期为 N 的两个周期序 列，各自的离散傅里叶级数为：1）线性a,b为任意常数DFS的几个主要特性：证:因为 及 都是以N为周期的函数， 所以有2）序列移位由于 与 对称的特点，同样可证明证:同理:对于复序列 其共轭序列 满足 3）共轭对称性进一步可得共轭偶对称分量 共轭奇对称分量 4）周期卷积若 则 或 证： 这是一个卷积公式，但与前面讨论的线性卷积的差 别在于，这里的卷积过程只限于一个周期内（即 m=0~N-1），称为周期卷积例： 、 ，周期为 N=5, 宽度分别为 4 和 3 ，求周期卷积 结果仍为周期序列，周期为 N =5。
周期卷积周期为5~ x (n)~ h(n)nn周期卷积~ x (k)~ h(0-k)k~ y(0)n周期卷积~ x (k)~ h(1-k)k~ y(1)n周期卷积~ x (k)~ h(2-k)k~ y(2)n周期卷积~ x (k)~ h(3-k)k~ y(3)n周期卷积~ x (k)~ h(4-k)k~ y(4)n周期卷积~ y(n)n先计算主值区间，再周期延拓，求得 最终的周期卷积的结果，如下图所示 由于DFS与IDFS的对称性，对周期序列乘 积，存在着频域的周期卷积公式，若则 §3.5 离散傅里叶变换（DFT）我们知道周期序列实际上只有有限个序列值有意义，因此 它的许多特性可推广到有限长序列上一个有限长序列 x(n)，长为N，为了引用周期序列的概念，假定一个周期序列 ，它 由长度为 N 的有限长序列 x(n) 延拓而成，它们的关系：周期序列的主值区间与主值序列：对于周期序列 ，定义其第一个周期 n=0~N-1，为的“主值区间”，主值区间上的序列为主值序列 x(n)x(n)与 的关系可描述为：数学表示：RN(n)为矩形序列。
符号((n))N 是余数运算表达式，表示 n 对 N 求余数例： 是周期为 N=8 的序列，求 n=11 和 n=-2 对 N的余数频域上的主值区间与主值序列：周期序列 的离散傅氏级数 也是一个 周期序列，也可给它定义一个主值区间 ，以及主值序列 X(k)数学表示：再看周期序列的离散傅里叶级数变换（DFS）公式：这两个公式的求和都只限于主值区间（0~N-1），它 们完全适用于主值序列 x(n) 与 X(k) ，因而我们可得到 一个新的定义——有限长序列离散傅里叶变换定义长度为N的有限长序列 x(n) ，其离散傅里叶变换 X(k) 仍是 一个长度为N 的有限长序列，它们的关系为：x(n) 与 X(k) 是一个有限长序列离散傅里叶变换对，已知 x(n) 就能唯一地确定 X(k) ，同样已知 X(k) 也就唯一地确定 x(n) ，实际上 x(n) 与 X(k) 都是长度为 N 的序列（复序列）都 有N个独立值，因而具有等量的信息有限长序列隐含着周期性。
DFT的矩阵方程表示DFT特性：以下讨论DFT的一些主要特性，这些特性都与周期序列 的DFS有关假定x(n)与y(n)是长度为N的有限长序列，其各自的离 散傅里叶变换分别为：X(k)=DFT[x(n)]Y(k)=DFT[y(n)](1) 线性DFT[ax(n)+by(n)]=aX(k)+bY(k) ,a,b为任意常数(2) 圆周（循环）移位有限长序列x(n)的圆周移位定义为：f(n)=x((n+m))NRN(n)所以f(n)仍然是一个长度为N的有限长序列f(n)实际上可看作 序列 x(n)排列在一个N等分圆周上，并顺时针旋转 m 位圆周（循环）移位f(n)=x((n+2))NRN(n)圆周（循环）移位移位前左移两位后证：利用周期序列的移位特性：实际上，利用WN-mk的周期性，将f(n)=x((n+m))NRN(n)代入DFT 定义式，同样很容易证明序列圆周移位后的DFT为F（k）=DFT[f（n）]= x（k）同样，对于频域有限长序列X(k)的循环移 位，有如下反变换特性：IDFT[X((k+l))NRN(k)]= x（n）（3）圆周卷积和（循环卷积）若 F（k）=X（k）Y（k）则 或 证：这个卷积可看作是周期序列 卷积后再取 其主值序列。
将F（k）周期延拓，得：则根据DFS的周期卷积公式：因0≤m≤N-1时，x((m))N=x(m)，因此经过简单的换元可证明：这一卷积过程与周期卷积比较，过程是一样的，只是这里只取 结果的主值序列，由于卷积过程只在主值区间0≤m≤N-1内进行 ，所以 实际上就是 y（m）的圆周（循环）移位 ，称为“圆周（循环）卷积”，习惯上常用符号“ ”表示圆周（ 循环）卷积，以区别于线性卷积NNN圆周卷积过程:1）由有限长序列 x(n)、y(n) 补零构造周期序列2）计算周期卷积 3）卷积 结果取主值五点圆周卷积x (n)h(n)nn例 子圆周卷积x (k)ky(n) =x(n) h(n)n~ h(0-k)圆周卷积x (k)ky(n) =x(n) h(n)n~ h(1-k)圆周卷积x (k)ky(n) =x(n) h(n)n~ h(2-k)圆周卷积x (k)ky(n) =x(n) h(n)n~ h(3-k)圆周卷积x (k)~ h(4-k)ky(n) =x(n) h(n)n圆周卷积y(n) =x(n) h(n)n由有限长序列 x(n)、h(n) 构造周期序 列,计算周期卷积, 卷积 结果取主值,如 下图所示。
同样，若 f(n)=x(n)y(n)，则（4）有限长序列的线性卷积与圆周卷积（循环卷 积）实际问题的大多数是求解线性卷积，如信号 x(n)通过 系统 h(n) ，其输出就是线性卷积 y(n) = x(n) * h(n)而圆 周卷积比起线性卷积，在运算速度上有很大的优越性， 它可以采用快速傅里叶变换（FFT）技术，若能利用圆 周卷积求线性卷积，会带来很大的方便现在我们来讨论上述 x(n)与h(n)的线性卷积，如果 x(n) 、 h(n)为有限长序列，则在什么条件下能用循环卷积代 替而不产生失真线性卷积：N点圆周卷积：NN讨论圆周卷积和线性卷积之间的关系：对x1(n)和x2(n)补零，使其长度均为N点；对x2(n)周期延拓：圆周卷积：N小结：线性卷积求解方法• 时域直接求解 补N-N1个零x(n)N点DFT补N-N2个零h(n)N点DFTN点IDFTy(n) = x(n)*h(n)• z变换法• DFT法比较线性卷积与循环卷积例:p123（5）共轭对称性设 x*(n)为 x(n)的共轭复数序列，则DFT[x*(n)]=X*(N-k) 证： DFT[x*(n)] 0≤k≤N-1由于因此， DFT[x*(n)]说明：当k=0时，应为X*(N-0)=X*(0)，因为按定义X（k） 只有N个值，即0≤k≤N-1，而X[N]已超出主值区间，但 。