DFT以及FFT概念详解.ppt

第二章 离散傅里叶变换 及其快速算法 1753年，Bernoulli就推断一振动的弦可以表示成正弦 加权和的形式，但是他未能给出所需的加权系数。 Jean-Baptiste-Joseph Fourier于1768年3月出生在法国的 Auxerre，当他8岁时不幸成了一名孤儿。Fourier对数 学产生了浓厚的兴趣。21岁那年，Fourier在巴黎学术 界论述了有关数值方程解的著名论作，这一工作使他 在巴黎的数学界出名。 1798年，拿破仑侵略埃及，在侵略队伍中一些有名的 数学家和科学家，Fourier就是其中的一位， 回国后，Fourier被任命为格勒诺布尔伊泽尔省的长官 ，就是在此期间，Fourier完成了其经典之作Theorie analytiquede la chaleur(热能数学原理)。在该著作中， 他证明了任一周期函数都可以表示成正弦函数和的形 式，其中正弦函数的频率为周期频率的整数倍。 Fourier 离散傅里叶变换不仅具有明确的物理意义 ，相对于DTFT他更便于用计算机处理。但是 ，直至上个世纪六十年代，由于数字计算机 的处理速度较低以及离散傅里叶变换的计算 量较大，离散傅里叶变换长期得不到真正的 应用，快速离散傅里叶变换算法的提出，才 得以显现出离散傅里叶变换的强大功能，并 被广泛地应用于各种数字信号处理系统中。 近年来，计算机的处理速率有了惊人的发展 ，同时在数字信号处理领域出现了许多新的 方法，但在许多应用中始终无法替代离散傅 里叶变换及其快速算法。 2.1 离散傅里叶变换（DFT） 为了便于更好地理解DFT的概念，先讨论周期序列及其 离散傅里叶级数（DFS）表示。 2.1.1 离散傅里叶级数（DFS） 一个周期为N的周期序列，即 ， k为任意整数，N为周期 周期序列不能进行Z变换，因为其在 n=-到+ 都 周而复始永不衰减，即 z 平面上没有收敛域。但是 ，正象连续时间周期信号可用傅氏级数表达，周期 序列也可用离散的傅氏级数来表示，也即用周期为 N的正弦序列来表示。 周期为N的正弦序列其基频成分为： K次谐波序列为： 但离散级数所有谐波成分中只有N个是独立的 ，这是与连续傅氏级数的不同之处， 即 因此 将周期序列展成离散傅里叶级数时，只需取 k=0 到 (N-1) 这N个独立的谐波分量，所以一个周期序列的离 散傅里叶级数只需包含这N个复指数， 利用正弦序列的周期性可求解系数 将上式两边乘以 ，并对一个周期 求和 k=r ,N=8kr ,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）周期卷积 若 则 或 周期卷积周期为5 x (n) h(n) n n 周期卷积 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 先计算主值区间，再周期延拓，求得 最终的周期卷积的结果，如下图所示 。 证： 这是一个卷积公式，但与前面讨论的线性卷积的差 别在于，这里的卷积过程只限于一个周期内（即 m=0N-1），称为周期卷积。 例： 、 ，周期为 N=7, 宽度分别为 4 和 3 ，求周期卷积。 结果仍为周期序列，周期为 N =7。 由于DFS与IDFS的对称性，对周期序列乘 积，存在着频域的周期卷积公式， 若 则 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)。 数学表示： 再看周期序列的离散傅里叶级数变换（DFS）公式： 这两个公式的求和都只限于主值区间（0N-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)=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 位。 循环移位 f(n)=x(n+2)NRN(n) 循环移位 移位前 左移两位后 证：利用周期序列的移位特性： 实际上，利用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）的循环移位，称为“循 环卷积”，习惯上常用符号“”表示循环卷积，以区别于线性卷 积。 1）由有限长序列 x(n)、y(n) 构造周期序列 循环卷积过程: 2）计算周期卷积 3）卷积 结果取主值 循环卷积 x (n) h(n) n n 循环卷积 x (k) k y(n) =x(n) * h(n) n h(0-k) 循环卷积 x (k) k y(n) =x(n) * h(n) n h(1-k) 循环卷积 x (k) k y(n) =x(n) * h(n) n h(2-k) 循环卷积 x (k) k y(n) =x(n) * h(n) n h(3-k) 循环卷积 x (k) h(4-k) k y(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)为有限长序列，则在什么条件下能用循环卷积代 替而不产生失真。 有限长序列的线性卷积： 假定 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)就是线性卷积，也就是说，x(n)、 y(n) 周期延拓后的周期卷积，是x(n) 、 y(n)线性卷积 的周期延拓，周期为L。 它们的周期卷积序列 为： 根据前面的分析，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 比较线性卷积与循环卷积 例: 设有两个序列，x(n)为N=4矩形序列，y(n)为M=6 矩形序列，观察其线性卷积和圆周卷积。 由线性卷积定义可直接验证，两者的线性卷积 f(n)=x(n)*y(n)具有N+M-1=9个非零值,其结果见下图左 半部分(c)，不同L下的圆周卷积结果在图的右半部分。 图 线性卷积和循环卷积 图中（d）、（e）、（f），反映了不同L下循环卷积 与线性卷积之间的关系，图（d）中L=6，产生严重的 混淆，致使fl(n)与f（n）已完全不同，图（e）中L=8， 这时有两点（n=0，n=8）发生混淆失真，只有图（f） 中，满足条件LN+M-1=9，循环卷积与线性卷积相同 （与图（c）比较）。 （5）共轭对称性 设 x*(n)为 x(n)的共轭复数序列，则 DFTx*(n)=X*(N-k) 证： DFTx*(n) 0kN-1 由于 因此， DFTx*(n) 说明： 当k=0时，应为X*(N-0)=X*(0)，因为按定义X（k） 只有N个值，即0kN-1，而XN已超出主值区间，但 一般已习惯于把X（k）认为是分布在N等分的圆周上 ，它的末点就是它的起始点，即XN= X0，因此仍采 用习惯表示式 DFTx*（n）=X*（N-k） 以下在所有对称特性讨论中，XN均应理解为 XN=X0， 同样，x(N)=x(0)。 2.复序列的实部与虚部的DFT变换 以 xr(n）和 xi(n)表示序列x(n)的实部与虚部 即 x(n)=xr(n)+jxi(n) 则 Xe(k)和X0(k)表示实部与虚部序列的DFT，则 显然， Xe(k)与Xo(k)对称性： 故 因此,Xe(k)具有共轭对称性，称为X(k)的共轭偶对称分量。 用同样的方法可得到 X0(k)= - X*0(N-k) 即Xo(k)具有共轭反对称特性，称其为X(k)的共轭奇对称分量。 对于纯实数序列 x（n），即x（n）=xr（n），X（k）只有共轭 偶对称部分，即X（k）=Xe（k），表明实数序列的DFT满足共 轭对称性，利用这一特性，只要知道一半数目的 X（k），就 可得到另一半的 X（k），这一特点在DFT运算中可以加以利用 ，以提高运算效率。 根据x(n)与X(k)的对称性，同样可找到X(k)的实部 、虚部与x(n)的共轭偶部与共轭奇部的关系。 分别以xe (n)及x0 (n)表示序列x(n)的圆周共轭偶部 与圆周共轭奇部： 同样应从圆周意义上理解 x(N-0)=x(0)。 可证明: DFTxe(n)=ReX（k） DFTx0(n)=jImX（k） （6）选频性 （对0有限制？） 对复指数函数 进行采样得复序列 x(n) 0nN-1 其中q为整数。当0=2/N时，x（n）=ej2nq/N,其离散傅里叶变换为 写成闭解形式 可见，当输入频率为q0时，变换X（K）的N个值中只有 X（q）=N，其 余皆为零，如果输入信号为若干个不同频率的信号的组合，经离散傅里 叶变换后，不同的k上，X（k）将有一一对应的输出，因此，离散傅里叶 变换算法实质上对频率具有选择性。 例:求余弦序列 的DFT （7）DFT与Z变换 有限长序列可以进行z变换 比较z变换与DFT变换，可见，当z=w-kN时， 即 图 DFT与z变换 o o o o oo 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计算连续信号的频谱 采样 截短DFT （1）混迭 对连续信号xa(t)进行数字处理前，要进行采 样 采样序列的频谱是连续信号频谱的周期延拓 ，周期为fs，如采样率过低，不满足采样定理 ，fs2fh，则导致频谱混迭，使一个周期内的谱 对原信号谱产生失真，无法恢复原信号，进一 步的数字处理失去依据。 （2） 泄漏 处理实际信号序列 x（n）时，一般总要将它截 断为一有限长序列，长为N点，相当于乘以一个矩形窗 w(n)=RN(n)。 矩形窗函数，其频谱有主瓣，也 有许多副瓣，窗口越大，主瓣越窄，当窗口趋于无穷 大时，就是一个冲击函数。 我们知道，时域的乘积对应频域的卷积，所以 ，加窗后的频谱实际是原信号频谱与矩形窗函数频谱 的卷积，卷积的结果使频谱延伸到了主瓣以外，且一 直延伸到无穷。当窗口无穷大时，与冲激函数的卷积 才是其本身，这时无畸变，否则就有畸变。 例如，信号为 ，是一单线谱，但当加 窗后，线谱与抽样函数进行卷积，原来在0处的一 根谱线变成了以0为中心的，形状为抽样函数的谱 线序列，原来在一个周期（s）内只有一个频率上 有非零值，而现在 一个周期内几乎所有频率上都有非零值，即 的频率成份从0处“泄漏”到其它频率处去了。 考虑各采样频率