离散傅里叶变换(DFT)及其快速算法(FFT)

《离散傅里叶变换(DFT)及其快速算法(FFT)》由会员分享，可在线阅读，更多相关《离散傅里叶变换(DFT)及其快速算法(FFT)（91页珍藏版）》请在金锄头文库上搜索。

1、第三章 离散傅里叶变换(DFT) 及其快速算法(FFT) 3.1 离散傅里叶变换的定义及物理意义 3.2 DFT的主要性质 3.3 频域采样 3.5 DFT(FFT)应用举例 3.4 DFT的快速算法快速傅里叶变换(FFT)3.1 离散傅里叶变换的定义及物理意义 模拟域FT、LT数字域FT、ZT数字域DFT时间域t:连续频率域、s:连续时间域n:离散频率域k：离散频率域 、z：连续返回离散傅立叶变换（DFT）实现了信号首次在频域 表示的离散化，使得频域也能够用计算机进行处理 。 并且这种DFT变换可以有多种实用的快速算法。使信 号处理在时、频域的处理和转换均可离散化和快速 化。因而具有重要的理

2、论意义和应用价值，是本课 程 学习的一大重点。本节主要介绍返回p 3.1.1 DFT定义p 3.1.2 DFT与ZT、FT、DFS的关系p 3.1.3 DFT的矩阵表示3.1.1 DFT定义设序列x(n)长度为M，定义x(n)的N点DFT为式中，N称为离散傅里叶变换区间长度，要求N M。为 书写简单，令 ，因此通常将N点DFT表示为定义X(k)的N点离散傅里叶逆变换(IDFT)为长度为 N的离 散序列返回回到本节例3.1： ，分别计算x(n)的8点、16点DFT。 解: x(n)的8点DFT为x(n)的16点DFT为返回回到本节 LT3x1是 在频率区间上的等间隔采样返回回到本节程序运行结果点

3、数81632643.1.2 DFT与ZT、FT、DFS的关系 DFT有明确的物理意义，我们可以通过比较序列的DFT、FT 、 ZT，并将DFT与周期序列的DFS联系起来，得到DFT的物理意 义。 DFT和FT、ZT之间的关系 假设序列的长度为M，NM 将N点DFT和FT、ZT的定义重写如下 返回回到本节比较前面三式，得到，k=0, 1, 2, , N-1 ，k=0, 1, 2, , N-1 结论： (1)序列的N点DFT是序列傅里叶变换在频率区间0，2 上的N点等间隔采样，采样间隔为2 /N。 (2)序列的N点DFT是序列的Z变换在单位圆上的N点等间隔 采样，频率采样间隔为2 /N。 返回回到

4、本节DFT与z变换X(ej)X(k)o12 345 67(N-1)k=0DFT与DTFT变换 序列x(n)的N点DFT是 x(n)的Z变换在单位圆上的N点等 间隔采样； X(k)为x(n)的傅立叶变换 在区间 上的N 点等间隔采样。这就是DFT的物理意义。变量周期分辨率返回回到本节DFT和DFS之间的关系：周期延拓 取主值有限长序列 周期序列 主值区序列有限长序列周期序列主值区间序列返回回到本节返回回到本节周期序列DFS:有限长序列的DFT:对比二者发现：是 的主值区序列，条件NM返回回到本节DFSDFT返回回到本节DFT与DFS之间的关系:有限长序列x(n)的DFT变换X(k)，就是x(n)

5、的周期延拓序列的DFS系数 的主值序列返回回到本节DFS与FT之间的关系: 周期延拓序列 的频谱特性由其傅里叶级数的 系数 确定，幅度相差一个常数因子 。 DFT的 是 的主值区序列，所以x(n)的 DFT表示的是 周期序列的频谱特性。返回回到本节3.1.3 DFT的矩阵表示周期序列 的DFS以及有限长序列x(n)的DFT如下可以发现它们右边的函数形式一样，但k的定义域不同， X(k)只是 的主值区序列，或者说X(k)以N为周期进行 周期延拓即是 ，用后面两式表示二者的关系： 返回回到本节式(3.1.5)(3.1.8)说明了DFT和DFS之间的关系。 这些关系式成立的条件是N M，即DFT的变

6、换区间N不能 小 于x(n)的长度M。如果该条件不满足，按照式(3.1.5)将 x(n) 进行延拓时， 中将发生时域混叠，由式(3.1.8)得到 的 X(k)不再是x(n)的DFT，这时以上讲的DFS和DFT之间的关 系 不再成立。 (3.1.7)(3.1.8)返回回到本节也可以表示成矩阵形式式中，X是N点DFT频域序列向量:x是时域序列向量:DN称为N点DFT矩阵，定义为(3.1.12)返回回到本节也可以表示为矩阵形式:称为N点IDFT矩阵，定义为从式(3.1.12)和式(3.1.14)，我们可以发现(3.1.14)返回回到本节3.2 DFT的主要性质与序列的FT类似，DFT也有许多重要的性

7、质。其中一些性 质 本质上与FT的相应性质相同，但是某些其他性质稍微有些 差别。返回p 线性性质 p DFT的隐含周期性 p 循环移位性质 p 复共轭序列的DFT p DFT的共轭对称性 p 循环卷积定理p 离散巴塞伐尔定理 线性性质设有限长序列 的长度分别为 ，a和b为常数。 则式中 ， 。返回回到本节 DFT的隐含周期性 在第一节中，DFT和IDFT只定义了X(k)和x(n)在变换区间 上 的N个值。如果使DFT中k的取值域为-，就会发现 X(k)是以N为周期的，即X(k + mN) = X(k) 称X(k)的这一特性为DFT的隐含周期性。l物理意义：X(k)为 在区间 上的N点等间隔采

8、样。 l 以2为周期，X(k)以N为周期。返回回到本节 循环移位性质 有限长序列的循环移位 设序列x(n)的长度为M，对x(n)以N（N M）为周期进行 周 期延拓，得到定义x(n)的循环移位序列为上式表示将序列x(n)以N为周期进行周期延拓，再左移m个 单位并取主值序列， 就得到x(n)的循环移位序列y(n)。 下图中(a)、(b)、(c)和(d)分别描述了x(n)、 、和y(n)。图中M=6，N=8，m=2。 返回回到本节序列的循环移位过程示意图返回回到本节 循环移位性质 设序列x(n)长度为M，x(n)的循环移位序列为， N M 则 复共轭序列的DFT 假设用 表示x(n)的复共轭序列，

9、长度为N， 且 ，则， k=0,1,2,N-1 式中， 。同样：返回回到本节 DFT的共轭对称性 上一章介绍了序列FT的共轭对称性，DFT也有类似的共轭 对称性质。但FT中的共轭对称是指对坐标原点的共轭对 称，在DFT中指的是对变换区间的中心，即N/2点的共轭对 称。 有限长共轭对称序列和共轭反对称序列 假设有限长序列 满足下式， n=0,1,2,N-1 则称 为共轭对称序列。 假设有限长序列 满足下式， n=0,1,2,N-1 则称其为共轭反对称序列。 返回回到本节任一有限长序列x(n)都可以用它的共轭对称分量和共轭 反对称分量之和表示，即将上式中的n用N-n代替，并两边取共轭，得到 由上面

10、两式得到 和 与原序列x(n)的关系为 返回回到本节 DFT的共轭对称性质 假设序列x(n)长度为N，其N点DFT用X(k)表示。 将序列x(n)分成实部和虚部，相应x(n)的DFT分成共 轭 对称和共轭反对称两部分。 即式中， ， 则 返回回到本节 将序列x(n)分成共轭对称和共轭反对称两部分，相 应 x(n)的DFT分成实部和虚部两部分， 即式中， ， ， 则返回回到本节 实信号DFT的特点 设x(n)是长度为N的实序列，其N点DFT用X(k)表示，我们 从的结论可知道X(k)具有共轭对称性质，即如果将X(k)写成极坐标形式 ，由共轭对 称 性质，说明X(k)的模关于 k = N/2点偶对

11、称 ， 利用DFT的共轭对称性质可以减小实序列的DFT计算量： a) 利用计算一个复序列的N点DFT，很容易求得两个不 同的实序列的N点DFT； b) 实序列的2N点DFT，可以用复序列的N点DFT得到。 返回回到本节a) 设 是实序列，长度均为N，用它们构成一个 复序列 对上式进行N点DFT，得到利用的结论可以得到这样只计算一个N点DFT，得到X(k)，用上面两式容易得到 两个实序列的N点DFT。 (3.2.18)(3.2.19)返回回到本节b) 通过复序列的N点DFT得到实序列的2N点DFT。 设 是一个长度为2N的实序列，首先分别用 中的偶 数 点和奇数点形成两个长度为N的新序列 ， 即

12、 再由 构造长度为N的复序列x(n)， 即 计算x(n)的N点DFT，因为 均是实序列，利用 式 (3.2.18)和式(3.2.19)得到 。最后由 以得到实序列v(n)的2N点DFT，即V(k)。 返回回到本节实序列2N点的DFT，拆分重组为N点复序列DFT例如 是实序列，长度为2Nu拆分u重组uN点DFT返回回到本节 循环卷积定理 时域循环卷积定理是DFT中很重要的定理，具有很强的实用 性。已知系统输入和系统的单位脉冲响应，计算系统的输 出，以及FIR滤波器用FFT实现等，都是该定理的重要应用 。1. 两个有限长序列的循环卷积 设序列h(n)和x(n)的长度分别为N和M。h(n)与x(n)

13、的L点循 环卷积定义为式中，L称为循环卷积的长度，LmaxN，M。 为了区别线性卷积，用 表示循环卷积，用 表示L点循 环卷积，即 x(n)。 LL返回回到本节有限长序列循环卷积的矩阵形式上式中右边第一个矩阵称为x(n)的L点循环矩阵，它的特 点 是： (a)第一行是x(n)的L点循环倒相。x(0)不动，后面其它反 转180放在他的后面。 (b)第二行是第一行向右循环移一位； (c)第三行是第二行向右循环移一位；依次类推。 返回回到本节例3.2： 计算下面给出的两个长度为4的序列h(n)与x(n) 的 4点和8点循环卷积。解: 按照式(3.2.21)写出h(n)与x(n)的4点循环卷积矩阵 形

14、 式为返回回到本节h(n)与x(n)的8点循环卷积矩阵形式为返回回到本节2. DFT的时域循环卷积定理 设h(n)和x(n)长度分别为N和M，yc(n)为序列h(n)和x(n) 的L点循环卷积，即x(n) 则 式中 时域循环卷积定理表明，DFT将时域循环卷积关系，变换 成频域的相乘关系。用时域循环卷积定理计算两个序列 循 环卷积运算的方框图如下图所示 图3.2.3 用DFT计算两个有限长序列L点循环卷积运算的方框图 L返回回到本节3. DFT的频域循环卷积定理 设h(n)和x(n)长度分别为N和M，并且 ， 则 式中，LmaxN, M。 DFT： 时域循环卷积 频域乘积 离散巴塞伐尔定理 设长度为N的序列x(n)的N点DFT为X(k)，则 L返回回到本节3.3 频域采样时域和频域的对偶原理 对时间序列x(n)的连续频谱 函数在频域等间隔采样，则采样得到的离散频谱对应的时 域 序列必然是原时间序列x(n)的周期延拓序列。而且仅对时域有限长序列，当满足频域采用定理时， 才 能由频域离散采样恢复原来的连续频谱函数（或原时间序 列）。时域采样 频域周期延拓时域周期延拓 频域采样本节讨论：频域采样定理、频率采样条件、频域内插公式 。 返回 频域采样与频域采样定理 设任意序列x(n)的Z变换为而且X(z)的收敛