第三章离散傅立叶变换及其快速算法课件

第三章

离散傅立叶变换及其快速算法3.1周期序列的离散傅里叶级数3.2离散傅立叶变换3.3

频域采样定理3.4DFT的快速算法——FFT3.5

DFT与FFT的应用13.1

周期序列的离散傅里叶级数周期序列的傅立叶级数离散傅立叶级数（DFS）的性质周期序列的傅立叶变换2周期序列的傅里叶级数用基序列{}将其展开。对于周期为N的周期序列的基频为，其基波为,第k次谐波为∴也是以N为周期的周期序列故基序列{}

只有N个是独立的，可以用这N个基序列将展开。3周期序列的傅里叶级数WN的性质1.周期性2.共轭对称性3.可约性4.正交性4周期序列的傅里叶级数周期序列的傅立叶级数正变换反变换5周期序列的傅里叶级数周期序列的离散傅立叶级数表明：可将周期为N的序列分解成N个离散的谐波分量的加权和，各谐波的频率为，幅度为，其中注意：和都可取任何整数值，这表明和都是无限长的，但由于它们的周期性，只需要知道一个周期，其它周期可通过周期延拓得到。周期序列的离散傅立叶级数的意义6离散傅立叶级数（DFS）的性质1、线性性2、移位性证明7离散傅立叶级数（DFS）的性质3、频域移位（调制）性4、周期卷积定理设和具有相同的周期N，定义：为这两个序列的周期卷积。8离散傅立叶级数（DFS）的性质周期卷积与第二章所讨论的线性卷积不同，其特点是：和都是周期为N的序列。注意9离散傅立叶级数（DFS）的性质5、频域周期卷积定理例：两个周期为N=6的序列和的周期卷积过程类似于线性卷积，首先进行变量代换：，再将其中一个序列进行反褶、移位、相乘，然后相加。运算仅在m=0到m=N-1内进行，计算出一个周期的结果，再进行周期延拓得到整个序列。1011周期序列的傅立叶变换序列傅立叶变换存在的条件是满足绝对可和或平方可和，对周期序列这两个条件都不满足，因为当n±时，序列的值或平方值都不趋于0。若引入频域的冲击函数()，也可求得其傅立叶变换。设是周期为N的周期序列，其傅立叶变换可表示成脉冲串的形式：12周期序列的傅立叶变换为了证明，求上式的傅立叶反变换：最后结果是由于在（0，2p）内，只包含k=0~N-1个脉冲13周期序列的傅立叶变换例：下列序列常称为离散系统的取样序列，求它的傅立叶级数和傅立叶变换。-N0Nn解：傅立叶级数傅立叶变换其中：为数字取样频率143.2

离散傅里叶变换由第二章曾讨论过的“序列的傅立叶变换”我们知道：序列的傅立叶变换就是序列的频谱，它是数字频率的连续变量函数，且序列的长度不受限制。但在实际利用计算机或数字设备进行频谱分析时，只能处理有限长数据且必须将离散化。有限长序列的傅立叶变换及频率离散化问题:离散傅立叶变换（DFT）153.2

离散傅里叶变换有限长序列的离散傅立叶变换离散傅立叶变换的性质离散频率、数字频率和模拟频率间的关系16有限长序列的离散傅立叶变换DFT的定义长度为N的因果序列x(n)其频谱为：上式中仅管x(n)是离散序列，但却是连续变量，且X(ej)

是的周期为2的周期函数，故实际上只需计算在区间[0~2)上的值。同时，由于为连续变量，在[0~2)中有无限多个点，而实际只能计算有限个点，故必须将离散化。17有限长序列的离散傅立叶变换其中为序列在离散频率点上的频谱值。在[0~2)上从0开始等间隔的取N个点，相应的（k=0,…,N-1),则上式变为：定义式18有限长序列的离散傅立叶变换DFT的意义有限长序列x(n)的离散傅立叶变换（简称DFT）的意义：1、X(k)为序列x(n)在离散频率点上的频谱值。2、X(k)相当于频谱X(ej)在[0~2)范围内实施了等间隔采样，采样间隔为离散傅立叶反变换(IDFT)19有限长序列的离散傅立叶变换DFT的周期性以及与DFS的关系据DFT和IDFT的定义知：X(k+mN)=X(k)

x(n+mN)=x(n)∴有限长序列的DFT是k的周期序列，周期为N；而由IDFT所求得的x(n)也变成了一个周期为N的周期序列，即通过IDFT将原x(n)进行了周期延拓。20有限长序列的离散傅立叶变换将由有限长序列x(n)以N为周期进行延拓后所得的序列记为x((n))N，并称原x(n)为x((n))N的主值区。其中((n))N表示n对N除法求余，即若n=MN+n1,0n1N-1,M为整数，则((n))N=n1，例如：N=8则x((9))8=x(1)，x((5))8=x(5)N=16则x((9))16=x(9)，x((-5))16=x(11)21有限长序列的离散傅立叶变换有限长序列x(n)与周期序列

的关系有限长序列x(n)是周期序列的主值序列，即：有限长序列x(n)的DFTX(k)与周期序列的DFS

之间的关系22有限长序列的离散傅立叶变换DFT与Z变换的关系长度为N的序列x(n)其Z变换：与离散傅立叶变换（DFT）相比较有：可见序列的N点DFT是x(n)的Z变换在单位圆上N点的等间隔采样。显然，对于同一序列当频率采样点数不同时，其DFT的值也不同。23有限长序列的离散傅立叶变换例：已知，分别求和时的。解：24有限长序列的离散傅立叶变换25离散傅立叶变换的性质DFT的性质1、线性性若x(n)与y(n)是同样长的序列，则对任何实数或复数a1、a2有：26若x(n)

是长为n的有限长序列，定义：为x(n)的循环移位序列。离散傅立叶变换的性质2、循环移位性27离散傅立叶变换的性质循环移位示意图循环移位的实质：将原序列x(n)左移m位，而移出主值区的各序列值又依次从右侧进入主值区。28离散傅立叶变换的性质证明：令n+m=nl,则有29离散傅立叶变换的性质4、共轭复序列的DFT3、频域移位定理30离散傅立叶变换的性质证明：31离散傅立叶变换的性质实部虚部5、共轭对称性32离散傅立叶变换的性质说明：∵和均是有限长序列，定义区间为（0～N-1），与第二章中的对称性不同，这里所谓的对称是指关于N/2点的对称，而不是关于原点的对称。33离散傅立叶变换的性质关于N/2点的共轭对称性34离散傅立叶变换的性质特别地：若x(n)为实序列，则其DFT满足共轭对称特性若x(n)为纯虚序列，则其DFT满足共轭反对称性35离散傅立叶变换的性质例：设，和为实序列，已知求:和解：36离散傅立叶变换的性质6、循环卷积定理设x1(n)和x2(n)是两个具有相同长度N的有限长序列，定义循环卷积：37离散傅立叶变换的性质38离散傅立叶变换的性质【循环卷积的计算】反褶循环移位乘积累加例：已知作N=8的循环卷积解：①变量代换：将变成②将周期延拓为③反褶后得到④从n=0开始，对每一个n=0,1…,N-1,分别对进行循环移位并取主值形成⑤分别将与对应的m点从m=0,1…,N-1逐点相乘，并将乘积累加就得到了各个点n=0,1,…,N-1的y(n)。其计算过程见下图：3940离散傅立叶变换的性质7、频域循环卷积定理41离散傅立叶变换的性质8、循环相关定理设x(n)和y(n)是两个具有相同长度N的有限长实序列，定义以下序列为x(n)和y(n)的循环互相关序列：当x(n)=y(n)时，称为序列的循环自相关称为序列的功率谱，它不包含相位信息。42离散傅立叶变换的性质与循环卷积的关系：并且有：43离散傅立叶变换的性质说明时域中的能量与频域中的能量相等当x(n)=y(n)时，则有：9、Parseval定理44离散傅立叶变换的性质证明：

=

===45离散频率、数字频率和模拟频率间的关系模拟频率

f或，分别表示模拟频率与模拟角频率。单位分别为赫兹（Hz）和弧度/秒（rad/s）。两者关系为：46离散频率、数字频率和模拟频率间的关系离散信号数字频率

，单位为弧度（rad）。通过采样信号的频谱，可建立模拟频率与离散（信号数字）频率之间的关系：

的取值范围：对应于模拟频率能取的最高频率fs/2∴=就是离散（信号数字）频率能取的最高频率此时，虽然信号在时域时离散的，但仍然是连续的注意47离散频率、数字频率和模拟频率间的关系离散频率它是将离散（信号数字）频率离散化后的结果，用k表示。，因此可得出离散频率

、数字频率k和模拟频率f之间的对应关系为：以上所讨论的三种频率变量之间的关系，在对模拟信号进行数字处理以及利用模拟滤波器设计数字滤波器乃至整个数字信号处理中十分重要，望同学们高度重视。483.3频域采样定理频域采样是指对有限长序列的傅氏变换在频域离散化得到x(k)的过程。本节讨论两个基本问题：a：频域采样（DFT）不失真的条件，即由X(k)不失真地恢复x(n)的条件b：用X(k)表示X(z)和的插值公式(内插公式)493.3频域采样定理频域采样不失真恢复的条件内插公式50频域采样不失真恢复的条件频域采样后能不失真恢复原序列的条件频率离散化的采样点数N必须大于序列的长度L【推导过程】设x(n)的长度为L（没有限制）频域采样欲恢复原信号，即51频域采样不失真恢复的条件52频域采样不失真恢复的条件由该式可知：xN(n)是原序列x(n)的周期延拓，周期为N，然后取主值。结论：若序列长度为L，频域采样点数（或DFT的长度）为N，且L<N，则频域采样后可不失真地恢复原序列；但若L>N，则频域采样后不能不失真地恢复原序列。53频域采样不失真恢复的条件54内插公式用X(k)表示X(z)设序列长度为N，由傅里叶变换对得55内插公式用X(k)表示X(ejω)时域采样定理中的内插函数相似56内插公式以上所讨论的两种情形的内插公式是用频域采样法设计FIR数字滤波器重要的理论基础，虽然此处无从体现，但后面有关FIR数字滤波器的结构与设计中常用到这些结论。57内插公式内插函数零极点与Φ（ω）的幅频特性示意图58内插公式例：已知，对在单位圆上等间隔采样N点解：593.4DFT的快速算法——FFT

DFT的快速算法（FFT）综述时域抽取基-2FFT算法（DIT-FFT）频域抽取基-2FFT算法（DIF-FFT）逆DFT的快速算法（IFFT）

N为合数的FFT算法（混合基）60DFT的快速算法（FFT）综述DFT的运算量减少DFT运算量的方法①将长度N变短。例如若将长度变为N/2，则运算量变成：②利用的性质周期性：共轭对称性：可约性：61DFT的快速算法（FFT）综述FFT的算法分类FFT算法首先由Cooly-Tuky提出了基－2FFT算法，它对DFT的发展起到了极大推进作用。随后又出现了混合基算法。本节仅对基－2FFT算法作介绍，内容包括：FFT的基本思想、时域与频域抽取的基－2FFT算法及其程序实现。62DFT的快速算法（FFT）综述基-2FFT算法（DIT-FFT）指要求长度N满足（M为整数），若不满足可将序列补零延长，使其满足长度要求。时域抽取与频域抽取63时域抽取基-2FFT算法（DIT-FFT）算法的推导时域抽取算法是按n的奇偶把时间序列x(n)分解为两个长为N/2点的序列，即：64时域抽取基-2FFT算法（DIT-FFT）上式中分别为的N/2点DFT，即：这是前N/2点DFT65时域抽取基-2FFT算法（DIT-FFT）对于后N/2点的DFT显然，可采用蝶式运算图来表示上述前N/2和后N/2两式，如下图所示：66时域抽取基-2FFT算法（DIT-FFT）例如N=8时的DFT,可以分解为两个N/2=4点DFT,如下图：67时域抽取基-2FFT算法（DIT-FFT）同理：,∴N/2仍可能是偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。68时域抽取基-2FFT算法（DIT-FFT）其中对也可进行同样的分解：69时域抽取基-2FFT算法（DIT-FFT）这样又一次的分解得到4个N/4点DFT，见下图。70时域抽取基-2FFT算法（DIT-FFT）例：试画出N=8时的完整的基-2DIT-FFT运算流图。71时域抽取基-2FFT算法（DIT-FFT）运算量由有关算法的讨论知：当时，总共应有M级分解，每级有N/2个“蝶式运算”。每个“蝶式运算”需一次复数乘、两次复数加运算，这样M级总共需要的运算量为：如：若N＝1024，直接计算DFT与采用FFT运算量之比约为205，“快速”得以充分体现。若N足够大，通过直接计算DFT与采用FFT计算其运算量之比为：72时域抽取基-2FFT算法（DIT-FFT）FFT算法的特点①倒码观察完整的FFT流图能发现有两个特点：倒码和原位运算倒码即码位倒置：是指将原二进制数的码位倒过来按从低位到高位排列。如：N=8时，序号“4”用三位二进制表示正常码为“100”，而其倒码为“001”，变成了序号“1”。73时域抽取基-2FFT算法（DIT-FFT）顺序二进制数倒码倒码顺序

01234567

000001010011100101110111

000100010110001101011000

04261537顺序与倒码顺序对照表74时域抽取基-2FFT算法（DIT-FFT）②原位运算由完整的FFT流图可见：从左到右计算下一级蝶式运算时，仅需要用到本级的数据而不需要前一级的数据。例如在实施第二级蝶式运算时，仅需要第一级蝶式运算的结果，而不需要用到原来的输入数据x(n)。据此就可在数据输入到存储器以后，每一级运算的结果存储在同一组存储单元中。直到最后输出，中间无需其他存储器。利用同一存储单元存放蝶式运算输入和输出数据的方法称为原位运算。原位运算可节省存储单元，降低FFT硬件实现的设备成本，从而使得FFT算法简单、快速、高效。75时域抽取基-2FFT算法（DIT-FFT）DIT-FFT算法其他形式的流图由信号流图理论知道：只要保证各节点所连接的支路及其传输系数不变，无论各节点相对位置如何排列，所得到的流图等效，DFT的结果相同。例如将N=8时基－2DIT-FFT信号流图中与x(4)、x(6)水平相连的所有节点分别同与x(1)、x(3)水平相连的所有节点对调，保持其余节点位置不变，得到新形式的信号流图。76时域抽取基-2FFT算法（DIT-FFT）N=8时输入是正序、输出是倒码的DIT-FFT运算流图77频域抽取基－2FFT算法（DIF-FFT）算法的推导频域抽取算法是把时间序列前后对半分解为两个长为N/2点的序列，则：78频域抽取基－2FFT算法（DIF-FFT）当k取偶数时（k=2r，r=0,1,...,N/2－1）∴x(n)的N点DFTX(k)按k的奇偶分组可分为两个N/2的DFT79频域抽取基－2FFT算法（DIF-FFT）当k取奇数时（k=2r＋1，r=0,1,...,N/2－1）80频域抽取基－2FFT算法（DIF-FFT）这一结论表明：求的N点DFT再次分解成求两个N/2点DFTDIF-FFT的蝶式运算流图81频域抽取基－2FFT算法（DIF-FFT）DIF-FFT的一次分解运算流图先蝶式运算，后DFT。例如：N=8时82频域抽取基－2FFT算法（DIF-FFT）DIF-FFT的二次分解运算流图83频域抽取基－2FFT算法（DIF-FFT）按照以上方法继续分解下去，经过M-1次分解，最后分解为N/2个两点DFT，这N/2个2点DFT的输出就是N点DFT的结果X(k)，如下图所示：84频域抽取基－2FFT算法（DIF-FFT）有关说明以上给出了N=8时完整的DIF-FFT

的运算流图。由于这种方法是按X(k)在频域进行奇偶分解，因此称之为频域抽取基－2ＦＦＴ运算。比较ＤＩＦ－ＦＦＴ与ＤＩＴ－ＦＦＴ相同点：运算次数与存储量相同不同点：①

ＤＩＦ－ＦＦＴ输入序列为自然序列而输出为码位倒置序列

②

蝶式运算过程不同ＤＩＴ－ＦＦＴ是序列先乘旋转因子后相加减ＤＩＦ－ＦＦＴ是序列先相加减后乘旋转因子85逆DFT的快速算法（IFFT）IFFT算法的推导比较两式可知：只要将FFT中的旋转因子改为，再乘以1/N即可得到IDFT的快速算法IFFT。IFFT基本思想，∴还可将常数1/N分配到每级运算中，也就是每级蝶形运算均乘以½。这样就实现了FFT与IFFT运算的统一。86逆DFT的快速算法（IFFT）87逆DFT的快速算法（IFFT）直接利用FFT程序88逆DFT的快速算法（IFFT）1、纯软件实现2、硬件实现3、DSP（软硬件结合）FFT（IFFT）算法的实现89N为合数的FFT算法（混合基）基－2FFT的各种算法要求。若该条件不满足，虽可通过在序列尾部补0的方法使N增加到最邻近的一个值，从而采用DIT-FFT或DIF-FFT算法。该方法并不影响DFT的结果，只是增加了采样频率点的位置和点数，但该方法至少存在以下两个缺陷：①补0太多，长度增加，运算量加大，效率降低②若欲求得指定频率点上的DFT,无法做到故必须探索新方法90N为合数的FFT算法（混合基）将每隔点抽取一点，则可形成个长度为点的序列如下：算法的推导若序列的长度是合数，即：91N为合数的FFT算法（混合基）例如：按以上的方法将分为3组，每组长度为692N为合数的FFT算法（混合基）将代入序列的N点DFT有：93N为合数的FFT算法（混合基）如此进行下去直到最后变为点DFT显然此算法中采用了不同长度来进行抽取，故有时又将该算法称为混合基FFT算法。例：试作出时混合基一次分解为3个6点DFT的流程图94N为合数的FFT算法（混合基）95N为合数的FFT算法（混合基）经一次分解后的3个6点DFT，每个又可分解为3个2点的DFT，如图：96N为合数的FFT算法（混合基）算法的运算量第一次抽取后的运算量：第二次抽取后的运算量：总运算量：总乘法运算次数973.5DFT与FFT的应用利用FFT进行频谱分析用FFT计算线性卷积线性调频Z变换（Chirp-Z变换）及快速算法98利用FFT进行频谱分析利用FFT进行频谱分析的基本方法设x(n)为长为N的有限长序列，则：利用FFT进行频谱分析的实现过程框图为：99利用FFT进行频谱分析几个常用基本概念1、数字频率分辨率：2、模拟频率分辨率：3、用于FFT的采样点数：4、频率刻度值：5、模拟信号长度：6、分辨率：100利用FFT进行频谱分析例：用FFT来分析信号的频谱，若已知信号的最高频率为 ，要求频率分辨率为，试确定：1、采样间隔T；2、采用基-2FFT的最小样点数N，以及与此相对应的最小记录长度；3、按您确定的参数所获得的实际分辨率。解：1、据采样定理，采样间隔2、基-2FFT的最小样点数N当采用基-2FFT算法时，要求101利用FFT进行频谱分析与此相对应的最小记录长度为：3、按确定的参数所获得的实际分辨率102利用FFT进行频谱分析用FFT进行频谱分析存在的两个问题1、频谱泄漏在实际应用中，通常将所观测与处理的信号限制在一定的时间间隔内，即在时域对信号进行“截断操作”，或称作加时间窗（用时间窗函数乘以信号）。由卷积定理可知：时域相乘、频域卷积，这就造成“拖尾现象”，称之为频谱泄漏。103利用FFT进行频谱分析解决办法：①采用其它形式的窗函数（第六章详论）

②对于周期序列，取其过零点截取显然，两种频谱是有差别的，该现象就是频谱泄漏若序列的长度为无限长，为了利用FFT进行频谱分析，首先必须将其截断为有限长序列104利用FFT进行频谱分析信号截断时产生的频谱泄漏现象105利用FFT进行频谱分析2、栅栏效应利用FFT进行频谱分析时，只知道离散频率点fk的整数倍处的频谱。在两个谱线之间的情况就不知道，这如同通过一个栅栏观察景象一样，故称作栅栏效应。解决办法：在序列后面补零点加大FFT点数，可使谱线间隔变小来提高分辨力，以减少栅栏效应。注意：若需要加窗，则应先加窗再补零。106用FFT计算线性卷积线性卷积设是和的线性卷积：

总运算量为：可见，直接运算时运算量很大，必须寻找新思路。思路：利用FFT,通过循环卷积来计算线性卷积107用FFT计算线性卷积利用循环卷积计算线性卷积的条件设是x(n)和h(n)长为L的循环卷积：其中L>Max[N,M],108用FFT计算线性卷积上式表明：是将以L为周期进行延拓后再取主值区间所得的序列。∴利用循环卷积计算线性卷积的条件为：109用FFT计算线性卷积利用循环卷积计算线性卷积如下图110用FFT计算线性卷积利用FFT进行线性卷积的步骤①、将已知序列（长为N）和（长为M）补零延长，使它们的长度。若采用基-2FFT算法，还应使

大于或等于的2的最小整数次幂。②、做和的长为点的FFT得到和，并求它们的积。③、求的

IFFT并取前点获得线性卷积的结果为111用FFT计算线性卷积长序列FFT卷积的计算方法实际中常常出现两个待卷积序列长度相差很大的情形，例如输入序列的长度远远大于滤波器的脉冲响应的长度时,若仍然取FFT的长度,则必须对补很多0，同时也做不到“实时处理”。此时常采用以下两种分段处理方法。112用FFT计算线性卷积是两个长度接近且分别为和的序列的线性卷积，可很有效地求其L点的FFT.设长度为,为无限长。取“段长”尽可能

与接近。则：1、重叠相加法113用FFT计算线性卷积分别求得各段卷积后再将结果相加，即可求得和的完整的线性卷积。该方法中由于运用了“分段卷积的重叠”和“各段卷积结果的相加”，故称为重叠相加法。用重叠相加法计算两个长度悬殊序列线性卷积的步骤如下：①将补零延长到，并计算其点FFT，得到

②分别将各补零延长到，并计算其点FFT，得到

③计算，并求其L点的反变换，即：④将的重叠部分相加，最后得到结果114用FFT计算线性卷积115用FFT计算线性卷积2、重叠保留法设序列的长度为，则对长序列的分段方法如下：先在序列前补个0，然后对补0后的序列进行分段，每段的长度为,即：对每一段，通过循环卷积，获得俩者的线性卷积。而输入的每段序列重叠N-1点，故每段的循环卷积的输出应去掉前面N-1点只保留后面M点，即：116重叠保留法分段方法示意图117118用FFT计算线性卷积119线性调频Z变换(Chirp-Z变换)算法问题的引入仅管采用FFT可计算出有限长序列的DFT，但它要求序列长度为2的整数幂或合数。实际中①有时只对信号的某一频段感兴趣，即只需要计算单位圆上某一段的频谱值，例如对窄带信号进行频谱分析时，总是要求在窄带范围内的抽样点足够密集，而窄带范围外则不需考虑。此时若依然采样以上方法，则需增加频域抽样点数，增加了窄带范围外的不需要的计算量；②在语声信号处理时信号极点处的频谱十分关键，而极点位置往往离单位圆较远，此时不能采用FFT；③若是大素数时也无法采用FFT。上述几种情形可采用线性调频Z变换(Chirp-Z变换)算法加以解决。120线性调频Z变换(Chirp-Z变换)算法算法的基本原理设是有限长序列，沿Z平面上的一段螺线做M点抽样，得到以下抽样点：其中A和W为复数,极坐标形式分别为：式中和为实数，当K=0时有121线性调频Z变换(Chirp-Z变换)算法Chirp-Z变换的频率抽样点122线性调频Z变换(Chirp-Z变换)算法如果，则的抽样点位于半径为r的圆上；如果，则的抽样点位于单位圆上（常规的DFT变换）