离散傅立叶变换及其快速算法(DSP3A).ppt
第三章 离散傅立叶变换及其快速算法周期序列的离散周期序列的离散周期序列的离散周期序列的离散傅里叶级数傅里叶级数傅里叶级数傅里叶级数离散傅立叶变换离散傅立叶变换离散傅立叶变换离散傅立叶变换频频频频域采样定理域采样定理域采样定理域采样定理D DFTFT的快速算法的快速算法的快速算法的快速算法FFTFFTDFTDFT与与与与FFTFFT的应用的应用的应用的应用1 11 周期序列的离散傅立叶级数周期序列的傅立叶级数周期序列的傅立叶级数周期序列的傅立叶级数周期序列的傅立叶级数对于周期为对于周期为N N的周期序列的周期序列 用用基序列基序列 将其展开。将其展开。的基频为的基频为 ，其，其基基波波为为 ,第第k k次谐波次谐波为为 也是以也是以N N为周期的周期序列为周期的周期序列故基序列故基序列 只有只有N N个是独立的，可以用这个是独立的，可以用这N N个基个基序列将序列将 展开。展开。2 2周期序列的傅立叶级数W W W WN N N N的性质的性质的性质的性质1.1.周期性周期性2.2.共轭对称性共轭对称性3.3.可约性可约性4.4.正交性正交性周期序列的傅立叶级数周期序列的傅立叶级数周期序列的傅立叶级数周期序列的傅立叶级数正变换正变换反变换反变换显然具有周期性3 3周期序列的傅立叶级数周期序列的傅立叶级数周期序列的离散傅立叶级数的意义周期序列的离散傅立叶级数的意义周期序列的离散傅立叶级数的意义周期序列的离散傅立叶级数的意义周期序列的离散傅立叶级数表明：周期序列的离散傅立叶级数表明：可将周期为可将周期为可将周期为可将周期为N N N N的序列的序列的序列的序列分解成分解成N N个离散的谐波分量的加权和，各谐波的频率为个离散的谐波分量的加权和，各谐波的频率为 ，幅度为幅度为 ，其中，其中注意：注意：和 都可取任何整数值，这表明 和 都是无限长的，但由于它们的周期性，只需要知道一个周期，其它周期可通过周期延拓得到。离散傅立叶级数（离散傅立叶级数（离散傅立叶级数（离散傅立叶级数（DFSDFSDFSDFS）的性质）的性质）的性质）的性质1 1、线性性、线性性2 2、移位性、移位性4 4周期序列的傅立叶级数周期序列的傅立叶级数离散傅立叶级数（离散傅立叶级数（离散傅立叶级数（离散傅立叶级数（DFSDFSDFSDFS）的性质）的性质）的性质）的性质3 3、频域移位（调制）性、频域移位（调制）性4 4、周期卷积定理、周期卷积定理设设 和和 具有相同的周期具有相同的周期N N，定义：，定义：为这两个序列的为这两个序列的周期卷积。周期卷积。周期卷积与第二章所讨论的线性卷积不同，其特点是：和 都是周期为N的序列。注注意意5 5周期序列的傅立叶级数周期序列的傅立叶级数离散傅立叶级数（离散傅立叶级数（离散傅立叶级数（离散傅立叶级数（DFSDFSDFSDFS）的性质）的性质）的性质）的性质5 5、频域周期卷积定理、频域周期卷积定理例：例：例：例：两个周期为两个周期为N=6N=6的序列的序列 和和 的周期卷积过程的周期卷积过程类似于线性卷积，首先进类似于线性卷积，首先进行变量代换：行变量代换：，再将其中一个序列进行反再将其中一个序列进行反褶、移位、相乘，然后相褶、移位、相乘，然后相加。加。运算仅在运算仅在m=0m=0到到m=N-1m=N-1内进行，计算出一个周期内进行，计算出一个周期的结果，再进行周期延拓的结果，再进行周期延拓得到整个序列得到整个序列 。6 6定义定义定义定义周期序列的傅立叶变换序列傅立叶变换存在的条件是满足绝对可和或平方可和，但对周期序列这两个条件都不满足，因为当 时，序列的值或平方值都不趋于0。若引入频域的冲击函数 ，也可求得其傅立叶变换。周期为周期为N N的周期序列的周期序列 的傅立叶变换为：的傅立叶变换为：傅立叶反变换为：傅立叶反变换为：7 72 离散傅立叶变换问题的引入：问题的引入：由第二章曾讨论过的“序列的傅立叶变换序列的傅立叶变换”我们知道：序列的傅立叶变换就是序列的频谱，它是数字频率序列的傅立叶变换就是序列的频谱，它是数字频率 的的连续变量函数，且序列的长度不受限制连续变量函数，且序列的长度不受限制。但在实际利用计算机或数字设备进行频谱分析时，只能处理有限长数据且必须将 离散化。有限长序列的傅立叶变换及频率离散化问题有限长序列的傅立叶变换及频率离散化问题离散傅离散傅立叶变换（立叶变换（DFT）有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换离散傅立叶变换的性质离散傅立叶变换的性质离散频率、数字频率和模拟频离散频率、数字频率和模拟频率间的关系率间的关系8 8有限长序列的离散傅立叶变换DFTDFT的定义的定义的定义的定义长度为长度为N N的因果序列的因果序列 其频谱为：其频谱为：上式中仅管 是离散序列，但 却是连续变量，且 是 的周期为 的周期函数，故实际上只需计算 在区间 上的值。同时，由于 为连续变量，在 中有无限多个点，而实际只能计算有限个点，故必须将 离散化。9 9有限长序列的离散傅立叶变换在在 上从上从0 0开始等间隔的取开始等间隔的取N N个点，相应的个点，相应的 （k=0,N-1),k=0,N-1),则上式变为：则上式变为：定义式其中 为序列 在离散频率点 上的频谱值。1010DFTDFT的意义的意义的意义的意义有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换有限长序列 的离散傅立叶变换（简称离散傅立叶变换（简称DFT）的意义：1、为序列 在离散频率点 上的频谱值。2、相当于频谱 在 范围内实施了等间隔采样，采样间隔为离散傅立叶反变换离散傅立叶反变换离散傅立叶反变换离散傅立叶反变换(IDFT)(IDFT)1111DFTDFT的周期性以及与的周期性以及与的周期性以及与的周期性以及与DFSDFS的关系的关系的关系的关系有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换据DFT和IDFT的定义知：有限长序列的有限长序列的DFTDFT是是 的周期序列，周期为的周期序列，周期为N N；而由而由IDFTIDFT所求得的所求得的 也变成了一个周期为也变成了一个周期为N N的周期的周期序列，即通过序列，即通过IDFTIDFT将原将原 进行了周期延拓。进行了周期延拓。将由有限长序列 以N为周期进行延拓后所得的序列记为 ，并称原 为 的主值区主值区。其中 表示 对N除法求余，即若 则，例如：1212有限长序列的离散傅立叶变换有限长序列的离散傅立叶变换有限长序列有限长序列有限长序列有限长序列 的的的的DFT DFT 与周期序列与周期序列与周期序列与周期序列 的的的的DFS DFS 之间的关系之间的关系之间的关系之间的关系DFTDFT与与与与Z Z变换的关系变换的关系变换的关系变换的关系长度为长度为N N的序列的序列 其其Z Z变换：变换：与离散傅立叶变换（与离散傅立叶变换（DFTDFT）相比较有：）相比较有：可见序列的可见序列的可见序列的可见序列的N N N N点点点点DFTDFTDFTDFT是是是是x x x x(n n n n)的的的的Z Z Z Z变换在单位圆上变换在单位圆上变换在单位圆上变换在单位圆上N N N N点的等间隔采样。点的等间隔采样。点的等间隔采样。点的等间隔采样。显然，对于同一序列当频率采样点数不同时，其显然，对于同一序列当频率采样点数不同时，其显然，对于同一序列当频率采样点数不同时，其显然，对于同一序列当频率采样点数不同时，其DFTDFTDFTDFT的值也不的值也不的值也不的值也不同。同。同。同。有限长序列有限长序列有限长序列有限长序列 与周期序列与周期序列与周期序列与周期序列 的关系的关系的关系的关系有限长序列有限长序列 是周期序列是周期序列 的主值序列，即：的主值序列，即：1313例例例例1 1：典典 型型 例例 题题已知 ，分别求 和 时的 。解：解：由该例可知：由该例可知：频率采样点数不同，DFT的长度不同，DFT 的结果也不同。1414DFTDFT的性质的性质的性质的性质1 1、线性性、线性性若x(n)与y(n)是同样长的序列，则对任何实数或复数有：2 2、循环移位性、循环移位性若x(n)是长为n的有限长序列，定义：为 的循环移位序列循环移位序列。离散傅立叶变换的性质1515循环移位示意图循环移位示意图循环移位的实质循环移位的实质：将原序列 左移 位，而移出主值区的各序列值又依次从右侧进入主值区。离散傅立叶变换的性质1616离散傅立叶变换的性质离散傅立叶变换的性质DFTDFT的性质的性质的性质的性质3、频域移位定理、频域移位定理4、共轭复序列的、共轭复序列的DFT5、共轭对称性、共轭对称性实部虚部虚部1717离散傅立叶变换的性质离散傅立叶变换的性质说明：说明：和和 均是有限长序列，定义区间为（均是有限长序列，定义区间为（0 0N-1N-1），与第二章中的对称性不同，这里所谓的对称），与第二章中的对称性不同，这里所谓的对称是指关于是指关于N/2N/2点的对称，而不是关于原点的对称。点的对称，而不是关于原点的对称。1818离散傅立叶变换的性质离散傅立叶变换的性质特别地：特别地：若若 为实序列，则其为实序列，则其DFTDFT满足共轭对称特性满足共轭对称特性若若 为纯虚序列，则其为纯虚序列，则其DFTDFT满足共轭反对称性满足共轭反对称性例：例：例：例：设 ，和 为实序列，已知求:和解：解：1919离散傅立叶变换的性质离散傅立叶变换的性质DFTDFT的性质的性质的性质的性质6、循环卷积定理、循环卷积定理设设 和和 是两个具有相同长度是两个具有相同长度N N的有限长序列，的有限长序列，定义循环卷积：定义循环卷积：7、频域循环卷积定理、频域循环卷积定理2020离散傅立叶变换的性质离散傅立叶变换的性质【附：附：附：附：循环卷积的计算循环卷积的计算循环卷积的计算循环卷积的计算】反褶反褶反褶反褶 循环移位循环移位循环移位循环移位 乘积乘积乘积乘积 累加累加累加累加例：例：例：例：已知已知作作N=8N=8的循环卷积的循环卷积解：解：变量代换：将变量代换：将 变成变成 将将 周期延拓为周期延拓为 反褶后得到反褶后得到 从从n=0n=0开始，对每一个开始，对每一个 n=0,1,N-1,n=0,1,N-1,分别对分别对 进行循环移位并取主值形成进行循环移位并取主值形成 分别将分别将 与与 对应的对应的mm点点从从m=0,1,N-1m=0,1,N-1逐点相乘，并将乘积累加就得到了各个逐点相乘，并将乘积累加就得到了各个点点n=0,1,N-1n=0,1,N-1 的的y(n)y(n)。其计算过程见下图：。其计算过程见下图：2121离散傅立叶变换的性质离散傅立叶变换的性质2222离散傅立叶变换的性质离散傅立叶变换的性质DFTDFT的性质的性质的性质的性质8、循环相关定理、循环相关定理设设 和和 是两个具有相同长度是两个具有相同长度N N的有限长实序列，的有限长实序列，定义以下序列为定义以下序列为 和和 的的循环互相关序列循环互相关序列循环互相关序列循环互相关序列：9、Parseval定理定理2323离散频率、数字频率和模拟频率间的关系模拟频率模拟频率模拟频率模拟频率离散（信号数字）频率离散（信号数字）频率离散（信号数字）频率离散（信号数字）频率 或或 ，分别表示，分别表示模拟频率模拟频率模拟频率模拟频率与与模拟角频率模拟角频率模拟角频率模拟角频率。单位分。单位分别为赫兹（别为赫兹（HzHz）和弧度）和弧度/秒（秒（rad/srad/s）。两者关系为：）。两者关系为：，单单位位为为弧弧度度（radrad）。通通过过采采样样信信号号的的频频谱谱，可可建建立模拟频率与离散（信号数字）频率之间的关系：立模拟频率与离散（信号数字）频率之间的关系：的取值范围：对应于模拟频率能取的最高频率对应于模拟频率能取的最高频率 就是离散（信号数字）频率能取的最高频率 此时，虽然信号在时域时离散的，但此时，虽然信号在时域时离散的，但 仍然是连续的仍然是连续的注意注意2424离散频率、数字频率和模拟频率间的关系离散频率、数字频率和模拟频率间的关系数字频率数字频率数字频率数字频率它是将它是将离散（信号数字）频率离散（信号数字）频率离散（信号数字）频率离散（信号数字）频率 离散化后的结果，用离散化后的结果，用 表示。表示。，因此可得出离散频率，因此可得出离散频率 、数字频数字频率率 和模拟频率和模拟频率 之间的对应关系为：之间的对应关系为：以上所讨论的三种频率变量之间的关系，在对模对模拟信号进行数字处理拟信号进行数字处理以及利用模拟滤波器设计数利用模拟滤波器设计数字滤波器字滤波器乃至整个数字信号处理中十分重要，望同学们高度重视。25253 频域采样定理频域采样不失真恢复的条件频域采样不失真恢复的条件内插公式内插公式问题的提出：问题的提出：时域：时域：通过满足通过满足“时域采样定理时域采样定理”的采的采样样频域：频域：？2626频域采样不失真恢复的条件频域采样后能不失真恢复原序列的条件频域采样后能不失真恢复原序列的条件频域采样后能不失真恢复原序列的条件频域采样后能不失真恢复原序列的条件频率离散化的采样点数频率离散化的采样点数N N必须必须大于大于大于大于序列的长度序列的长度L L【推导过程推导过程推导过程推导过程】设设 的长度为的长度为 （没有限制）（没有限制）频域采样频域采样欲恢复原信号，即2727频域采样不失真恢复的条件频域采样不失真恢复的条件由该式可知：由该式可知：是原序列是原序列 的周期延拓，周期为的周期延拓，周期为N N，然后取主值。然后取主值。2828频域采样不失真恢复的条件频域采样不失真恢复的条件结论：结论：结论：结论：若序列长度为若序列长度为若序列长度为若序列长度为L L，频域采样点数（或，频域采样点数（或，频域采样点数（或，频域采样点数（或DFT DFT 的长度）的长度）的长度）的长度）为为为为N N，且，且，且，且LNLNLN，则频域采样后不能不失真地恢复原序列。，则频域采样后不能不失真地恢复原序列。，则频域采样后不能不失真地恢复原序列。，则频域采样后不能不失真地恢复原序列。2929内插公式用用用用X(k)X(k)表示表示表示表示X(z)X(z)设序列长度为设序列长度为N N，由，由傅里叶变换对傅里叶变换对傅里叶变换对傅里叶变换对得得3030内插公式内插公式用用用用X(k)X(k)表示表示表示表示X(eX(ej j)时域采样定理中的内插函数相相似似3131内插公式内插公式以上所讨论的两种情形的内插公式内插公式是用频域采样法设用频域采样法设计计FIR数字滤波器数字滤波器重要的理论基础，虽然此处无从体现，但后面有关FIR数字滤波器的结构与设计中常用到这些结论。3232内插函数零极点与内插函数零极点与内插函数零极点与内插函数零极点与（）的幅）的幅）的幅）的幅频频特性示意特性示意特性示意特性示意图图内插公式内插公式3333典 型 例 题例：例：已知 ，对 在单位 圆上等间隔采样N点解：解：3434
