离散傅里叶变换及其快速算法.ppt

第二章 离散傅里叶变换及其快速算法,1753年，Bernoulli就推断一振动的弦可以表示成正弦加权和的形式，但是他未能给出所需的加权系数。Jean-Baptiste-Joseph Fourier于1768年3月出生在法国的Auxerre，当他8岁时不幸成了一名孤儿，被收养在一个宗教界主办的军事学校中。在此期间，Fourier对数学产生了浓厚的兴趣。21岁那年，Fourier在巴黎学术界论述了有关数值方程解的著名论作，这一工作使他在巴黎的数学界出名。Fourier不仅是公认的大数学家，而且他还是一位杰出的教师。他灵活运用历史典故使得他的讲座非常生动。实际上，Fourier所研究的主要领域是数学史。Fourier是最早以应用的眼光来解释抽象数学概念的研究者之一。1798年，拿破仑侵略埃及，在侵略队伍中一些有名的数学家和科学家，Fourier就是其中的一位，他负责组织修建第一条从格勒诺布尔到都灵的道路。Fourier也是一个拥有独特想法的一个怪才。例如，他认为酷热是理想的环境，因此，他喜欢居住在严热的小屋里，并穿上厚厚的衣服。1801，法国决心召回自己的军队，于是Fourier才得以重返家园。回国后，Fourier被任命为格勒诺布尔伊泽尔省的长官，就是在此期间，Fourier完成了其经典之作Theorie analytiquede la chaleur(热能数学原理)。在该著作中，他证明了任一周期函数都可以表示成正弦函数和的形式，其中正弦函数的频率为频率的整数倍。,Fourier,离散傅里叶变换不仅具有明确的物理意义，相对于DTFT他更便于用计算机处理。但是，直至上个世纪六十年代，由于数字计算机的处理速度较低以及离散傅里叶变换的计算量较大，离散傅里叶变换长期得不到真正的应用，快速离散傅里叶变换算法的提出，才得以显现出离散傅里叶变换的强大功能，并被广泛地应用于各种数字信号处理系统中。近年来，计算机的处理速率有了惊人的发展，同时在数字信号处理领域出现了许多新的方法，但在许多应用中始终无法替代离散傅里叶变换及其快速算法。,二、DFS离散付里级数的推导意义,用数字计算机对信号进行频谱分析时，要求信号必须以离散值作为输入，而且上面讨论可知：只有第四种形式(DFS)对数字信号处理有实用价值。但如果将前三种形式要么在时域上采样，要么在频域上采样，变成离散函数，就可以在计算机上应用。所以我们要先了解如何从以上三种形式推出DFS.,1.由非周期连续时间信号推出DFS,X(t)经过抽样为x(nT),对离散的时间信号进行DTFT得到周期连续频谱密度函数。再经过抽样，得到周期性离散频谱密度函数即为DFS.,x(t),t,取样,x(t),t,DTFT,X(ejT),采样,X(ejw),w,2.周期性连续时间信号函数,周期性连续时间信号函数经采样后，得到周期性的离散时间函数(DFS)。,x(t),X(ejw),t,w,采样,3.非周期离散时间信号,非周期离散时间信号经过序列付里时变换(即单位园上的Z变换)DTFT,得到周期连续谱密度函数，再经采样为周期离散频谱密度函数(DFS)。,x(t),t,X(ejT),w,X(ejw),DTFT,采样,三、推导DFS正变换,以下由第三种付里叶级数形式为例推导出离散付里叶级数变换。非周期信号x(n),其DTFT(单位园上Z变换)为其为周期连续频谱密度函数，对其进行采样，使其成为周期性离散频谱函数。设在一周期内采样N个点，则两采样点间距为：得到频间距为：代入DTFT式子中得：,四、DFS的反变换,即证：证明：已知两边同乘以,并对一个周期求和用n置换r得：,根据正交定理,回顾DFS,设 x(n)为周 期 为 N 的 周 期 序 列,则 其 离 散 傅 里 叶 级 数(DFS)变 换 对 为:正 变 换 反变换其中:,五、离散付里叶级数性质,可以由抽样Z变换来解析DFS，它的许多性质与Z变换性质类似。它们与Z变换主要区别为：(1)与 两者具有周期性，与Z变换不同。(2)DFS在时域和频域之间具有严格的对偶关系。它们主要性质分为：线性、序列移位(循环移位)、调制性、周期卷积和,(1)线性,(2)序列移位(循环、移位),时域频域,(3)调制性,(4)时域卷积,周期卷积和与以前卷积不同，它的卷积过程限在一个周期内称为周期卷积。时域卷积等于频域相乘。频域：,(5)频域卷积,时域：,证:,同理:,对于复序列 其共轭序列 满足,3）共轭对称性,已知序列x1(n)=R4(n),x2(n)=(n+1)R5(n),分别将序列以周期为6周期延拓成周期序列,本节涉及内容周期序列的离散傅立叶级数（DFS）正变换:反变换：,2.1.2 离散傅里叶变换（DFT）,我们知道周期序列实际上只有有限个序列值有意义，因此它的许多特性可推广到有限长序列上。一个有限长序列 x(n)，长为N，为了引用周期序列的概念，假定一个周期序列，它由长度为 N 的有限长序列 x(n)延拓而成，它们的关系：,周期序列的主值区间与主值序列：对于周期序列，定义其第一个周期 n=0N-1，为 的“主值区间”，主值区间上的序列为主值序列 x(n)。x(n)与 的关系可描述为：数学表示：RN(n)为矩形序列。符号(n)N 是余数运算表达式，表示 n 对 N 求余数。,例：是周期为 N=8 的序列，求 n=11 和 n=-2 对 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)=DFTx(n)Y(k)=DFTy(n)(1)线性 DFTax(n)+by(n)=aX(k)+bY(k),a,b为任意常数,(2)循环移位 有限长序列x(n)的循环移位定义为：f(n)=x(n+m)NRN(n)含义：1)x(n+m)N 表示 x(n)的周期延拓序列 的移位：2)x(n+m)NRN(n)表示对移位的周期序列 x(n+m)N 取主值序列,所以f(n)仍然是一个长度为N的有限长序列。f(n)实际上可看作序列 x(n)排列在一个N等分圆周上，并顺时针旋转 m 位。,循环移位,循环移位,移位前,左移两位后,证：利用周期序列的移位特性：实际上，利用WN-mk的周期性，将f(n)=x(n+m)NRN(n)代入DFT定义式，同样很容易证明。,序列循环移位后的DFT为 F（k）=DFTf（n）=x（k）,同样，对于频域有限长序列X(k)的循环移位，有如下反变换特性：IDFTX(k+l)NRN(k)=x（n）,（3）循环卷积若 F（k）=X（k）Y（k）则 或,证：这个卷积可看作是周期序列 卷积后再取其主值序列。将F（k）周期延拓，得：则根据DFS的周期卷积公式：因0mN-1时，x(m)N=x(m)，因此经过简单的换元可证明：,这一卷积过程与周期卷积比较，过程是一样的，只是这里只取结果的主值序列，由于卷积过程只在主值区间0mN-1内进行，所以 实际上就是 y（m）的圆周移位，称为“循环卷积”，习惯上常用符号“”表示循环卷积，以区别于线性卷积。,同样，若 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)为有限长序列，则在什么条件下能用循环卷积代替而不产生失真。,有限长序列的线性卷积：,假定 x(n)为有限长序列，长度为N，y(n)为有限长序列，长度为M，它们的线性卷积f(n)=x(n)*y(n)也应是有限长序列。因 x(m)的非零区间：0mN-1，y(n-m)的非零区间：0n-mM-1，这两个不等式相加，得：0nN+M-2，在这区间以外不是x(m)=0，就是y(n-m)=0，因而f(n)=0。因此，f(n)是一个长度为N+M-1的有限长序列。,循环卷积：,重新构造两个有限长序列 x(n)、y(n)，长度均为 L maxN,M，序列 x(n)只有前N个是非零值，后L-N个为补充的零值；序列 y(n)只有前M个是非零值，后L-M个为补充的零值。为了分析 x(n)与y(n)的循环卷积，先看x(n),y(n)的周期延拓：,根据前面的分析，f（n）具有 N+M-1 个非零序列值，因此，如果周期卷积的周期 LN+M-1，那么 f（n）周期延拓后，必然有一部分非零序列值要重叠，出现混淆现象。只有 LN+M-1 时，才不会产生交叠，这时 f（n）的周期延拓 中每一个周期L内，前N+M-1个序列值是f（n）的全部非零序列值，而剩下的 L（N+M-1）点的序列则是补充的零值。循环卷积正是周期卷积取主值序列：所以使圆周卷积等于线性卷积而不产生混淆的必要条件是：LN+M-1,三、DFT涉及的基本概念,1.主 值(主值区间、主值序列)2.移 位(线性移位、圆周移位)3.卷 积(线性卷积、圆周卷积)4.对 称(序列的对称性、序列的对称分量)5.相 关(线性相关、圆周相关),1.主 值(主值区间、主值序列),主 值 区 间：设 有 限 长 序 列 x(n),0nN-1,将 其 延 拓 为 周 期 序 列,周 期 序 列 长度为N,则 的 第 一 个 周 期 n=0 到 n=N-1 的 区 间 称 为 主 值 区 间.主 值 序 列:设 有 限 长 序 列 x(n),0nN-1,将 其 延 拓 为 周 期 序 列,周 期 为 N,则 主 值 区 间 内 的 序 列 x(n)=,0nN-1,即 为 主 值 序列。,2.移位,线 性 移 位：序 列 沿 坐 标 轴 的 平 移.圆周移位：将 有 限 长 序 列 x(n)以 长 度 N 为 周 期,延 拓 为 周 期 序 列,并 加 以 线 性 移 位 后,再 取 它 的 主 值 区 间 上 的 序 列 值,m 点 圆 周 移 位 记 作:其 中(.)N 表 示 N 点 周 期 延 拓.,(1)有 限 长 序 列 圆 周 移 位 的 实 现 步 骤,(2)例子1,2,1,3,1,0.5,(1)周期延拓：N=5时,n,x(n),2,1,3,1,x(n),0.5,2,1,3,1,0.5,1,1,2,0.5,n,(2)周期延拓：N=6时，补零加长,2,1,3,1,x(n),0.5,2,1,3,1,0.5,1,1,2,3,n,3,(2)例子,2,1,3,1,0.5,n,x(n),(3)M=1时，左移(取主值),1,3,1,x(n),0.5,2,(4)M=-2时，右移(取主值),2,1,3,1,n,x(n),0.5,n,3.卷 积,卷积在此我们主要介绍：(1)线性卷积(2)圆周卷积(3)圆周卷积与线性卷积的性质对比,(1)线性卷积,线 性 卷 积 定 义：有 限 长 序 列x1(n),0nN1-1;x2(n),0nN1-1则 线 性 卷 积 为 注意:线 性 卷 积 结 果 长 度 变 为 N1+N2-1.,(2)圆周卷积,令则圆 周 卷 积 结 果 长 度 不 变,为 N.,圆 周 卷 积 的 实 现 步 骤,例子线性卷积与圆周卷积步骤比较1,2,3,1,x(n),5,4,n,0,N1=5,2,1,3,h(n),n,0,N2=3,线性卷积：圆周卷积：(N=7)补零加长,2,3,1,x(k),5,4,k,0,N1=5,2,3,1,x(k),5,4,0,N=7,k,例子线性卷积与圆周卷积步骤比较2,2,3,1,h(k),0,k,(2)线卷积无需周期延拓，而圆周卷积需进行周期延拓：,线卷积的反折：圆卷积的反折(并取主值区间）：,2,3,1,2,3,1,2,3,1,h(-k),k,0,2,3,1,h(-k),k,0,例子线性卷积与圆周卷积步骤比较3,(3)平移,2,3,1,h(1-k),k,0,2,3,1,h(1-k),k,0,（4）相乘x(k)h(-k)=51=5x(k)h(1-k)=5*2+4*1=14x(k)h(2-k)=5*3+4*2+3*1=26,2,3,1,x(k),5,4,k,0,2,3,1,x(k),5,4,0,N=7,k,x(k)h(3-k)=4*3+3*2+2*1=20 x(k)h(4-k)=3*3+2*2+1*1=14x(k)h(5-k)=2*3+1*2=8x(k)h(6-k)=1*3=3,例子线性卷积与圆周卷积步骤比较4,(5)相加得到线性卷积的示意图,相加得到圆周卷积的示意图,14,26,5,n,y(n),20,14,8,3,0,14,26,5,n,y(n),20,14,8,3,0,可见,线性卷积与圆周卷积相同(当NN1(5)+N2(3)-1=7时),例子线性卷积与圆周卷积步骤比较5,若圆周卷积取长度为N=5,则求圆周卷积,2,3,1,x(k),5,4,0,N=5,k,2,3,1,h(-k),k,0,求得圆周卷积x(k)h(-k)=5*1+2*3+1*2=13x(k)h(1-k)=5*2+4*1+1*3=17x(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看出圆卷积与线卷积不同.,17,13,26,y(n),n,0,20,14,作业,求：(1)x(n)*x(n)的线卷积。(2),N=4(不加长)(3),N=6(补零加长)(4),N=7(补零加长)(5),N=8(补零加长),1,2,x(n),1,2,0,n,(3)圆 周 卷 积 与 线 性 卷 积 的 性 质 对 比,4.对称,分为：(1)序列的对称性(2)序列的对称分量,(1)序列的对称性,(a)奇 对 称(序 列)和 偶 对 称(序 列)(b)圆 周 奇 对 称(序 列)和 圆 周 偶 对 称(序 列)(c)共 轭 对 称(序列)和 共 轭 反 对 称(序 列)(d)圆 周 共 轭 对 称(序列)和 圆 周 共 轭 反 对 称(序 列),(a)奇 对 称(序 列)和 偶 对 称(序 列),称x(n)与-x(-n)互为奇对称。满足x0(n)=-x0(-n)的序列x0(n)称为奇对称序列。称x(n)与 x(-n)互 为 偶 对 称;满 足xe(n)=xe(-n)的 序 列 xe(n)称 为 偶 对 称 序 列,例子,0,xe(n),n,0,x(n),n,0,x(-n),n,互为偶对称,为偶对称序列,0,x(n),n,0,x(-n),n,互为奇对称,0,xo(n),n,为奇对称序列,(b)圆 周 奇 对 称(序 列)和 圆 周 偶 对 称(序 列),长 度 为N的 有 限 长 序 列 x(n)与-x(-n)NRN(n)互 为 圆 周 奇 对 称.长 度 为 N 的 有 限 长 序 列x0(n),若 满 足 x0(n)=-x0(-n)NRN(n),则x0(n)是 圆 周 奇 对 称 序 列.长 度 为 N 的 有 限 长 序 列 x(n)与x(-n)NRN(n)互 为 圆 周 偶 对 称.长 度 为 N 的 有 限 长 序 列 xe(n),若 满 足 xe(n)=-xe(-n)NRN(n)则 是 圆 周 偶 对 称 序 列.,(c)共 轭 对 称(序列)和 共 轭 反 对 称(序 列),序 列 x(n)与 x*(-n)互 为 共 轭 对 称.共 轭 对 称 序 列 是 满 足xe(n)=x*e(-n)的 序 列 xe(n),对 于 实 序 列 来 说,这 一 条 件 变 成 xe(n)=xe(-n),即 为 偶 对 称 序 列.序列 x(n)与-x*(-n)互 为 共 轭 反 对 称.共 轭 反 对 称 序 列 是 满 足xe(n)=-x*o(-n)的 序 列,对 于 实 序 列 来 说,即 为 xo(n)=xo(-n)奇 对 称 序 列.,(d)圆 周 共 轭 对 称(序列)和 圆 周 共 轭 反 对 称(序 列),N 点 有 限 长 序 列 x(n)与x*(-n)NRN(n)互 为 圆 周 共 轭 对 称.圆 周 共 轭 对 称 序 列 是 满 足 xep(n)=xep*(-n)NRN(n)的 序 列 即 xep(n)的 模是 圆 周 偶 对 称,辐 角是 圆 周 奇 对 称(或 说 实 部 圆 周 偶 对 称,虚 部 圆 周 奇 对 称).即把xep(n)看成分布在 N等分的圆上,在 n=0 的左半圆与右半 圆上,序列是共轭对称的。,圆 周 共 轭 对 称(序列)的例子,虚部,实部,实 部 圆 周 偶 对 称,虚 部 圆 周 奇 对 称,圆 周 共 轭 反 对 称(序 列),圆 周 共 轭 反对 称 序 列 是 满 足 xop(n)=-xop*(-n)NRN(n)的 序 列 即 xop(n)的 模是 圆 周 奇 对 称,辐 角是 圆 周 偶 对 称(或 说 实 部 圆 周 奇 对 称,虚 部 圆 周 偶 对 称).即把xop(n)看成分布在 N等分的圆上,在 n=0 的左半圆与右半 圆上,序列是共轭反对称的。,圆 周 共 轭 反 对 称(序 列)例子,实部,虚部,实 部 圆 周 偶 对 称,虚 部 圆 周 奇 对 称,(2)序列的对称分量,(a)奇 对 称 分 量 和 偶 对 称 分 量(b)圆 周 奇 对 称 分 量 和 圆 周 偶 对 称 分 量(c)共 轭 对 称 分 量 和 共 轭 反 对 称 分 量(d)圆 周 共 轭 对 称 分 量 和 圆 周 共 轭 反 对 称 分 量,(a)奇 对 称 分 量 和 偶 对 称 分 量,x(n)为任一序列(实 或 纯 虚 序 列),x(n)总能表示成一个奇对称序列 xo(n)和 一个偶对称序 列xe(n)之和,即x(n)=xo(n)+xe(n).其中,xo(n)奇对称序列称为x(n)的 奇 对 称 分 量;xe(n)偶 对 称 序 列 称 为 x(n)的 偶 对 称 分 量.看出这样得到的xo(n)和xe(n)分 别 满 足 奇 对 称 和 偶 对 称 的 条 件,且 二 者 之 和 为 x(n)。,说明,若 x(n)为 有 限 长 序 列 且0nN-1,则 与 点 数 均 为(2N-1).区 别 于 奇 对 称(序列)和 偶 对 称(序列).,(b)圆周奇对称分量和圆周偶对称分 量,设 x(n)是 一 长 度 为 N 的 有 限 长 序 列,总 能 表 示 成 一 个 圆 周 奇 对 称 序 列xop(n)和 一 个 圆 周 偶 对 称 序 列xep(n)之 和，即x(n)=xep(n)+xop(n).其 中 xop(n)称 为 x(n)的 圆 周 奇 对 称 分 量;xep(n)称 为 x(n)的 圆 周 偶 对 称 分 量.看 出 满 足 圆 周 奇 对 称 和 圆 周 偶 对 称 的 条 件,且 二 者 之 和 为 x(n).,(c)共轭对称分量和共轭反对称分量,任 一 序 列 x(n)总能表示成一个共轭对称序列 xo(n)和 一个共轭反对称序 列xe(n)之和,即x(n)=xo(n)+xe(n).其中,xo(n)共轭反对称序列称为x(n)的 共轭反 对 称 分 量;xe(n)共轭 对 称 序 列 称 为 x(n)的 共轭 对 称 分 量.看出xo(n)和xe(n)分 别 满 足 奇 对 称 和 偶 对 称 的 条 件,且 二 者 之 和 为 x(n)。,(d)圆 周 共 轭 对 称 分 量 和 圆 周 共 轭 反 对 称 分 量,设 x(n)是 一 长 度 为 N 的 有 限 长 序 列,总 能 表 示 成 一 个 圆 周 共轭反 对 称 序 列xop(n)和 一 个 圆 周 共轭 对 称 序 列xep(n)之 和，即x(n)=xep(n)+xop(n).其 中 xop(n)称 为 x(n)的 圆 周共轭反 对 称 分 量;xep(n)称 为 x(n)的 圆 周 共轭 对 称 分 量.看 出 满 足 圆 周 奇 对 称 和 圆 周 偶 对 称 的 条 件,且 二 者 之 和 为 x(n).,（f）选频性（对0有限制？）对复指数函数 进行采样得复序列 x(n)0nN-1其中q为整数。当0=2/N时，x（n）=ej2nq/N,其离散傅里叶变换为 写成闭解形式可见，当输入频率为q0时，变换X（K）的N个值中只有 X（q）=N，其余皆为零，如果输入信号为若干个不同频率的信号的组合，经离散傅里叶变换后，不同的k上，X（k）将有一一对应的输出，因此，离散傅里叶变换算法实质上对频率具有选择性。,例:求余弦序列,的DFT,（g）DFT与Z变换 有限长序列可以进行z变换 比较z变换与DFT变换，可见，当z=w-kN时，即,图 DFT与z变换,o,o,o,o,o,o,o,o,o,o,o,X(ej),X(k),o,Rez,jImz,o,变量,周期,分辨率,是z平面单位圆上幅角为 的点，即将z平面上的单位圆N等分后的第k点。,1）X(k)也就是z变换在单位圆上等间隔的采样值。2）X(k)也可看作是对序列傅氏变换X(ej)的采样，采样间隔为：N=2/N。即,结论：,采样定律告诉我们，一个频带有限的信号，可以对它进行时域采样而不丢失任何信息；DFT变换进一步告诉我们，对于时间有限的信号（有限长序列），也可以对其进行频域采样，而不丢失任何信息，这正反应了傅立叶变换中时域、频域的对称关系。它有十分重要的意义，由于时域上的采样，使我们能够采用数字技术来处理这些时域上的信号（序列），而DFT的理论不仅在时域，而且在频域也离散化，因此使得在频域采用数字技术处理成为可能。FFT就是频域数字处理中最有成效的一例。,（8）DFT形式下的Parseval定理,令k=0,得到,2.2 利用DFT做连续信号的频谱分析,利用DFT计算连续信号的频谱,（1）混迭 对连续信号x(t)进行数字处理前，要进行采样 采样序列的频谱是连续信号频谱的周期延拓，周期为fs，如采样率过低，不满足采样定理，fs2fh，则导致频谱混迭，使一个周期内的谱对原信号谱产生失真，无法恢复原信号，进一步的数字处理失去依据。,（2）泄漏 处理实际信号序列 x（n）时，一般总要将它截断为一有限长序列，长为N点，相当于乘以一个矩形窗 w(n)=RN(n)。矩形窗函数，其频谱有主瓣，也有许多副瓣，窗口越大，主瓣越窄，当窗口趋于无穷大时，就是一个冲击函数。我们知道，时域的乘积对应频域的卷积，所以，加窗后的频谱实际是原信号频谱与矩形窗函数频谱的卷积，卷积的结果使频谱延伸到了主瓣以外，且一直延伸到无穷。当窗口无穷大时，与冲激函数的卷积才是其本身，这时无畸变，否则就有畸变。,例如，信号为，是一单线谱，但当加窗后，线谱与抽样函数进行卷积，原来在0处的一根谱线变成了以0为中心的，形状为抽样函数的谱线序列，原来在一个周期（s）内只有一个频率上有非零值，而现在一个周期内几乎所有频率上都有非零值，即 的频率成份从0处“泄漏”到其它频率处去了。考虑各采样频率周期间频谱“泄漏”后的互相串漏，卷积后还有频谱混迭现象产生。,（3）栅栏效应 N点DFT是在频率区间 0，2 上对信号频谱进行N点等间隔采样，得到的是若干个离散的频谱点 X（k），且它们限制在基频的整数倍上，这就好像在栅栏的一边通过缝隙看另一边的景象一样，只能在离散点处看到真实的景象，其余部分频谱成分被遮挡，所以称之为栅栏效应。减小栅栏效应方法：尾部补零，使谱线变密，增加频域采样点数，原来漏掉的某些频谱分量就可能被检测出来。,(4)DFT的分辨率,填补零值可以改变对DTFT的采样密度，人们常常有一种误解，认为补零可以提高DFT的频率分辨率。事实上我们通常规定DFT的频率分辨率为，这里的N是指信号x(n)的有效长度，而不是补零的长度。不同长度的x(n)其DTFT的结果是不同的；而相同长度的x(n)尽管补零的长度不同其DTFT的结果应是相同的，他们的DFT只是反映了对相同的DTFT采用了不同的采样密度。,参数选择的一般原则：,若已知信号的最高频率，为防止混叠，选定采样频率；根据频率分辩率，确定所需DFT的长度(3)和N确定以后，即可确定相应模拟信号的时间长度这里T是采样周期。,(5)周期信号的谱分析,对于连续的单一频率周期信号，为信号的频率。可以得到单一谱线的DFT结果，但这是和作DFT时数据的截取长度选得是否恰当有关，截取长度N选得合理，可完全等于 的采样。,6,8,10,k,X(k),(a),(b),(c),(d),不同截取长度的正弦信号及其DFT结果,第二章 离散傅里叶变换及其快速算法,2.3快速付里叶变换(FFT)Fast Fouriet Transformer,一、快速付里叶变换FFT,有 限 长 序 列 通 过 离 散 傅 里 叶 变 换(D F T)将 其 频 域 离 散 化 成 有 限 长 序 列.但 其 计算 量 太 大,很 难 实 时 地 处 理 问 题,因 此 引 出 了 快 速 傅 里 叶 变 换(FFT).FFT 并 不 是 一 种 新 的 变 换 形 式,它 只 是 DFT 的 一 种 快 速 算 法.并 且 根 据 对 序 列 分 解 与 选 取 方 法 的 不 同 而 产 生 了 FFT 的 多 种 算 法.FFT 在 离 散 傅 里 叶 反 变 换、线 性 卷 积 和 线 性 相 关 等 方 面 也 有 重 要 应 用.。,二、FFT产生故事,当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基(J.W.Turkey)正在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。1965年库利-图基在、Mathematic of Computation 杂志上发表了著名的“机器计算付里级数的一种算法”文章，提出一种快速计算DFT的方法和计算机程序-揭开了FFT发展史上的第一页，促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件，使DFT的运算大简化了。,三、本节主要内容,1.直接计算DFT算法存在的问题及改进途径。2.多种DFT算法(时间抽取算法DIT算法，频率抽取算法DIF算法，线性调频Z变换即CZT法)3.FFT的应用,直接计算DFT算法存在的问题及改进途径,一、直接计算DFT计算量,问题提出：设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算，共需多大的运算工作量?,1.比较DFT与IDFT之间的运算量,其中x(n)为复数，也为复数所以DFT与IDFT二者计算量相同。,2.以DFT为例，计算DFT复数运算量,计算一个X(k)(一个频率成分)值，运算量为例k=1则要进行N次复数乘法+(N-1)次复数加法所以，要完成整个DFT运算，其计算量为：N*N次复数相乘+N*(N-1)次复数加法,3.一次复数乘法换算成实数运算量,复数运算要比加法运算复杂，需要的运算时间长。一个复数乘法包括4个实数乘法和2个实数相法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad),4次复数乘法,2次实数加法,4.计算DFT需要的实数运算量,每运算一个X(k)的值，需要进行4N次实数相乘和 2N+2(N-1)=2(2N-1)次实数相加.整个DFT运算量为：4N2次实数相乘和2N(2N-1)次实数相加.由此看出：直接计算DFT时，乘法次数与加法次数都是和N2成比例的。当N很大时，所需工作量非常可观。,例子,例1:当N=1024点时，直接计算DFT需要：N2=220=1048576次，即一百多万次的复乘运算这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求-迫切需要改进DFT的计算方法，以减少总的运算次数。例2：石油勘探，24道记录，每道波形记录长度5秒，若每秒抽样500点/秒，每道总抽样点数=500*5=2500点24道总抽样点数=24*2500=6万点DFT运算时间=N2=(60000)2=36*108次,二、改善DFT运算效率的基本途径,利用DFT运算的系数 的固有对称性和周期性，改善DFT的运算效率。1.合并法：合并DFT运算中的某些项。3.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。,利用DFT运算的系数 的固有对称性和周期性，改善DFT的运算效率,的对称性：,的周期性：,因为：,由此可得出：,例子,例:,利用以上特性,得到改进DFT直接算法的方法.,(1)合并法：步骤1分解成虚实部,合并DFT运算中的有些项对虚实部而言所以带入DFT中：,(1)合并法：步骤2代入DFT中,展开：,(1)合并法：步骤3合并有些项,根据：,有：,(1)合并法：步骤4结论,由此找出其它各项的类似归并方法：乘法次数可以减少一半。例：,2、将长序更DFT利用对称性和周期性分解为短序列DFT-思路,因为DFT的运算量与N2成正比的如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。,2、将长序更DFT利用对称性和周期性分解为短序列DFT-方法,把N点数据分成二半：,其运算量为：,再分二半：,+,=,+,+,+,=,这样一直分下去，剩下两点的变换。,2、将长序更DFT利用对称性和周期性分解为短序列DFT-结论,快速付里时变换(FFT)就是在此特性基础上发展起来的，并产生了多种FFT算法，其基本上可分成两大类：按抽取方法分：时间抽取法(DIT);频率抽取法(DIF)按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性调频Z变换(CZT法),基-2按时间抽取的FFT算法Decimation-in-Time(DIT)(Coolkey-Tukey),一、算法原理,设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。其中基数2-N=2M，M为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M,例子,设一序列x(n)的长度为L=9,应加零补长为N=24=16 应补7个零值。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n,x(n),二、算法步骤1.分组，变量置换,DFT变换：,先将x(n)按n的奇偶分为两 组，作变量置换:当n=偶数时，令n=2r;当n=奇数时，令n=2r+1;得到：x(2r)=x1(r);x(2r+1)=x2(r);r=0N/2-1;则其DFT可化为两部分：前半部分：后半部分：,2.代入DFT中,生成两个子序列,x(0),x(2)x(2r)奇数点x(1),x(3)x(2r+1)偶数点,代入DFT变换式：,3.求出子序列的DFT,上式得：,4.结论1,一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：,再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。,5.求出后半部的表示式,看出：后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。,6.结论2,频域中的N个点频率成分为：,结论：只要求出（0N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。,7.结论3,由于N=2L，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。,三、蝶形结,即蝶式计算结构也即为蝶式信号流图上面频域中前/后半部分表示式可以用蝶形信号流图表示。,X1(k),X2(k),作图要素：(1)左边两路为输入(2)右边两路为输出(3)中间以一个小圆表示加、减运算（右上路为相加输出、右下路为相减输出),(4)如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。,(5)当支路上没有箭头及系数时，则该支路的传输比为1。,例子：求 N=23=8点FFT变换（1）先按N=8-N/2=4，做4点的DFT：,先将N=8DFT分解成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)给出,(a)比较N=8点直接DFT与分解2个4点DFT的FFT运算量,N=8点的直接DFT的计算量为：N2次(64次）复数相乘,N(N-1)次(8(8-1)=56次)复数相加.共计120次。,（b)求 一个蝶形结需要的运算量,要运算一个蝶形结，需要一次乘法，两次加法。,（c）分解为两个N/2=4点的DFT的运算量,分解2个N/2点（4点）的DFT：,偶数其复数相乘为复数相加为,奇数其复数相乘为复数相加为,(d)用2个4点来求N=8点的FFT所需的运算量,再将N/2点（4点）合成N点(8点)DFT时，需要进行N/2个蝶形运算,还需N/2次（4次）乘法 及 次(8次）加法运算。,(e)将N=8点分解成2个4点的DFT的信号流图,4点DFT,x(0)x(2)x(4)x(6),4点DFT,x(1)x(3)x(5)x(7),X(0)X(1)X(2)X(3),X(4)X(5)X(6)X(7),X1(0),X1(1),X1(2),X1(3),X2(0),X2(1),X2(2),X2(3),偶数序列,奇数序列,X(4)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点的DFT,（c)一个2点的DFT蝶形流图,2点DFT,2点DFT,x(0)x(4),x(2)x(6),X3(0),X3(1),X4(0),X4(1),X1(0)X1(1),X1(2)X1(3),（d)另一个2点的DFT蝶形流图,2点DFT,2点DFT,x(1)x(5),x(3)x(7),X5(0),X5(1),X6(0),X6(1),X2(0)X2(1),X2(2)X2(3),同理：,(3)将N/4（2点）DFT再分解成2个1点的DFT(a)求2个一点的DFT,最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。,(b)2个1点的DFT蝶形流图,1点DFT,x(0),1点DFT,x(4),X3(0)X3(1),进一步简化为蝶形流图：,X3(0)X3(1),x(0),x(4),(4)一个完整N=8的按时间抽取FFT的运算流图,x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7),X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7),m=0,m=1,m=2,四、FFT算法中一些概念（1）“级”概念,将N 点DFT先分成两个N