第三章 付里叶分析 离散付氏级数的数学解释(The Mathematical Explanation of DFS) 第三章 付里叶分析 离散付氏级数的数学解释(The Mathematical Explanation of DFS) 如前所述，连续信号x(t)或离散信号x(nT1)的频谱： 都是连续谱，无法用计算机直接处理。要用计算机研究处理（数字信号处理）必须将： 无穷积分(求和)近似为有限积分(求和)； 频率离散化。 本节主要讨论如何进行近似计算，和实施这些数学计算所需的一些必要的数学基础。

离散付氏级数的数学解释 泊松求和公式(The Poisson Sum Formula) 设一周期函数 是以f(t)为主值函数，以T为周期进行周期延拓而得，如下图左图所示。 在第二章中已经证明，若F()是f(t)的付氏变换，则： 此系时域泊松求和公式，是将无穷积分变换成有限求和的基础。

离散付氏级数的数学解释 下面将用线性系统理论证明泊松求和公式，以此来说明其系统意义。 设某系统的传递函数为F()，对应的冲激响应为f(t)，如下图所示。 f(t) F()

离散付氏级数的数学解释 若输入为： 则由线性系统理论知，其输出为： 另一方面，由付氏级数输入信号可展开成： 将上式右端通过系统，得到响应为：

离散付氏级数的数学解释 此即时域泊松求和公式。另外，在频域也有类似的公式成立： 设 为以F()为主值函数，以1为周期进行周期延拓而得的周期函数，见前图右图。f(t)是F()的付氏反变换，则有频域泊松求和公式：

离散付氏级数的数学解释 f(t)与F()为付氏变换对，而 与 不是付氏变换关系。 和 分别是f(t)和F()的周期延拓，其周期分别为T和1。 当f(t)为因果函数时，利用频域泊松求和公式(令=0)有： 利用泊松公式可以推导出一些有用的恒等式。

离散付氏级数的数学解释 例3-10：已知变换对： 试求序列 的付氏展开式。 解：由频域泊松公式有：

离散付氏级数的数学解释 令=0和T1=1，有： 题给出的变换对和=0和T1=1 ，可得

离散付氏级数的数学解释 付氏变换与付氏级数(Fourier Transform and Fourier Series) 由泊松公式可见，通过X()的样本X(n0)可求得 的付氏级数系数(频谱)，即： 频域取样（离散化）后，x(t)就周期化了，而且0=2/T，当0越小，则T越大；当T→∞时， 0→0； 若x(t)已知， 则可以精确地确定 ； 对于信号g(t)的截短函数：x(t)=g(t)Pa/2(t)，由上式可求得g(t)的付氏变换G ()的样本的近似值。

离散付氏级数的数学解释 X()为截短函数的付氏变换，一般情况下，它可近似G ()。 与时域取样类似，若x(t)严格限制在有限区间内，即x(t)满足：当|t|>a/2时，x(t)=0；则有：若T>a，则 可由x(t)唯一地确定；若T<a， 将产生混叠。 用窗函数w(t)代替Pa/2(t)（矩形窗），通过选择适当的w(t)，可使误差G(n0)-X(n0)减小。这类截短问题在数字信号处理中有许多应用，如数字滤波器设计和频谱分析等。

离散付氏级数的数学解释 付氏级数与离散付氏级数(Fourier Series and DFS) 通过对付氏级数与离散付氏级数关系的讨论，将可用一个有限和式来近似计算付氏级数系数。 设一个周期函数： 若对 进行取样，取N为一任意整数，而且有T=NT1，即在一个周期内取N点，则 的样值 由下式确定：

离散付氏级数的数学解释 式中，WN是1的N元根，称作旋转因子。 我们知道，在一个域内取样离散化，则在另一个域内周期化，而k又可写作： K=n+rN， n=0,1, …,N-1；r=…,-1,0,1, … 并且，旋转因子具有周期性： 和 ，所以上式又可写作： 令： ，显然 序列是周期的，即： 所以有：

离散付氏级数的数学解释 上式说明，周期函数 的样本值 由一组（一个周期） 来确定；而且， 也由一个周期内的样本值 来确定。 上式说明，周期函数 的样本值 由一组（一个周期） 来确定；而且， 也由一个周期内的样本值 来确定。 的付氏级数系数Cn与 由 来联系。 例3-11：设 ，N＝9；试求 解：因为|n|>10时，Cn=0，所以，由Cn与 关系式得：

离散付氏级数的数学解释 一般而言， 不能确定Cn，除非仅有N个不为0的 。例如三角多项式为： 若N>2M＋1，由Cn与 关系式知： Cn与 的图形如下图所示。这时，由 就能求出Cn。 由于 由 唯一地确定，从而，可以推定类似三角多项式这样的函数的付氏级数系数Cn能由它的样本值 来确定。亦即可由y(t)的样本求出Y()的样本，从而近似求得Y()。从数学上讲，这就是Y()的数值计算问题。

离散付氏级数的数学解释 数值计算的基本定理(The Basal Theorem of Numerical Computation) 对于x(t)的付氏变换：

离散付氏级数的数学解释 的计算基于如下定理： 若T是任意常数，N是任意整数，而且有： 则对任何m有： 式中： 由信号理论易知其合理性：时域取样导致频域周期化；频域取样对应时域周期化。

离散付氏级数的数学解释 因为有T=NT1，1=N0，所以无论时域或频域在一个周期均为N个样值，因此，在一个周期内，一组由定理等式定义的N个方程确定了 与 之间的关系。可以由N个 样本值通过求解方程组，求出 的样本值。 一般而言， 不能唯一确定X(n0)，但若X()满足：X()=0，当||>和1>2，=/T；则有下式成立： 上条件说明x(t)是带限信号，而且满足取样定理。

第三章 付里叶分析 离散付氏变换(Discrete Fourier Transform) 第三章 付里叶分析 若x(t)不是带限的，但只要1足够大，使得当||>1/2时的X()可以忽略不计，则当n<1/20=N/2时， 近似等于X(n0)。但存在一定的混叠误差： X(n0)- 。 离散付氏变换(Discrete Fourier Transform) DFT引入背景(The Inductive Background of DFT) 再次研讨信号时频域关系（见下图）可以发现在四种信号时频关系中，只有第四类信号时频域均是离散的，能进行计算机（数字）处理。第二类信号时域是离散的，但其频域却是连续的，不能直接应用数字信号处理技术，为了能

信号时频关系示意图

离散付氏变换 离散付氏变换定义(Definition of DFT) 够处理这类信号，故人为引入离散付立叶变换。 对一个N点的有限长序列x(n)，由序列的付氏变换定义，有：

离散付氏变换 对正变换，取频谱的一个周期（设取主值周期），按频域采样定理，在一个周期内取N点离散化，令 有： 对反变换，因为 ，故有：

离散付氏变换 DFT定义(Definition of DFT) ： 一N点的有限长序列x(n)，对它的频谱在一个周期内进行N点等间隔取样，则得其的频域序列，两者的关系称为离散付氏变换(Discrete Fourier Transform,DFT)，即： 式中， 称为旋转因子。

离散付氏变换 DFT的物理意义(The Physical Meaning of DFT) DFT与Z变换的关系：容易证明，有限长序列x(n)的DFT是其在单位圆上Z变换（序列的付氏变换）的N点等间隔采样。 由序列的付氏变换的物理意义容易推得DFT的物理意义：N点有限长序列x(n)的(频域序列)DFT[X(k)]为x(n)的频谱在一个周期里的N点等间隔取样。只要取样满足一定的规律（频域取样定理），即可无失真地反映X(ej)，进而可恢复信号x(n)。

离散付氏变换 DFT的隐含周期性(The Connotative Periodicity of DFT) 由信号时频关系的内在本质联系知，对DFT来说，时、频域均是离散的，故其时、频域均是周期序列，即时域对应的是由主值序列x(n)以N为周期进行周期性延拓后得到的周期序列 ；频域对应的是由主值序列X(k)以N为周期进行周期性延拓后得到的周期序列 。 由于在处理时仅需主值序列（或者说一个周期的序列），所以在DFT定义中，时频域均限制在主值序列范围内，即：0≤n≤N-1；0≤k≤N-1。

离散付氏变换 例3-12：考察一个离散系统：离散付氏变换分析器，其差分方程为y(n)- y(n-1)=x(n)。 解：易得系统的系统函数为： 所以其单位脉冲响应为： 若输入为0≤n≤N-1的N点有限长序列x(n)，由于x(n)和h(n)均为因果序列，由卷积公式易得：

离散付氏变换 DFT的基本性质(The Basal Properties of DFT) 当n=N时，因为有x(N)＝0，所以有： 即当系统输入x(n)时，N时刻系统的输出等于其对应的DFT变换X(k)值，改变系统常数 ；即可求得对应的DFT： 。 DFT的基本性质(The Basal Properties of DFT) 线性性(Linearity) 满足齐次性和叠加原理。设x1(n)和x2(n)是长度分别为N1和N2的有限长序列，若a、b为任意常数，且：

离散付氏变换 取N=max[N1，N2]，设X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT，则N点序列y(n)的DFT为： 循环移位性质(The Property of Circular Shift) 序列的循环移位(Circular Shift of Sequence) N点有限长序列x(n)的循环移位定义为： 式中：x(())N表示对x()中序号进行模N取余运算。 为0～N-1的窗口序列。

离散付氏变换 循环移位的几何意义和过程可如下图所示。m>0，左移；m<0，右移。循环移位概念也可用圆移位解释，所以有时又称为“圆位移”。下面（如图）用一个N=8，左移3位的圆位移的几何过程进一步说明循环移位。 时域循环移位定理(Time-Domain Circular Shift Theorem) 设x(n)是长为N的有限长序列，y(n)为循环位移m位后的序列，其DFT为：

循环移位几何意义示意图

用圆位移形象说明循环位移

离散付氏变换 频域循环移位定理(Frequency- Domain Circular Shift Theorem) 若 则 循环卷积定理(Circular Convolution Theorem) 循环卷积(Circular Convolution) 设有两有限长序列x1(n)和x2(n)，长度分别为N1和N2，取N=max[N1，N2]（较短的一个通过补零，达到N长），则两者的循环卷积定义为：

离散付氏变换 或者： 记作： 循环卷积中x(n)、x1(n)、x2(n)均等长，为N点。 从时域直接计算两序列的循环卷积通常有三种方法： 利用公式直接计算； 同心圆法； 波形作图法。 同心圆法和波形作图法计算示意见下图。

循环卷积计算图示 x2(0) x2(1) x2(1) x2(N-1) x2(0) x2(N-1) x1(n) x(n) x2(n)

离散付氏变换 时域卷积定理(Time-Domain Circular Convolution Theorem) 设x1(n)和x2(n)的N点DFT分别为： 若 则有： 利用卷积定理可将循环卷积变换到频域利用乘法运算实现，通过DFT的快速计算方法可以大大降低运算量。

离散付氏变换 频域卷积定理(Frequency-Domain Circular Convolution Theorem) 与时域对称，也存在频域卷积定理： 若 则：

离散付氏变换 复共轭序列的DFT(DFT of a Complex Conjugation Sequence) 设 为x(n)的复共轭序列，而且有：则: ， 0≤k≤N-1 且 X(N)=X(0) 共轭对称性(Conjugation Symmetry) 关于圆对称：关于圆周的中轴线对称。写成表达式如下： 设xep(n)为有限长共轭对称序列， xop(n)为有限长共轭反对称序列；有：

共轭对称示意 4 N=8 N=7 对称轴 7 1 1 6 2 6 5 2 3 5 3 4

离散付氏变换 序列的共轭对称性(Conjugation Symmetry of Sequences) 对N为偶数，将上式中n换成N/2－n，有： 下图给出了一个N=8的序列对称示意。 序列的共轭对称性(Conjugation Symmetry of Sequences) 任意序列都可写成其共轭对称分量与共轭反对称分量之和； 利用序列与复共轭序列DFT间的关系，可导出序列DFT的对称特性。

复序列共轭对称示意图

离散付氏变换 如果序列x(n)的DFT为X(k)，则x(n)的实部和纯虚部的DFT分别为X(k)的共轭对称分量和共轭反对称分量。即，如果：x(n)=xr(n)+jxi(n)；X(k)＝DFT[x(n)]＝Xep(k)＋Xop(k)，则： DFT[xr(n)]=Xep(k) ； DFT[jxi(n)]=Xop(k) 如果序列x(n)的DFT为X(k)，则x(n)的共轭对称分量和共轭反对称分量的DFT分别为X(k)的实部和纯虚部。即，如果：x(n)=xep(n)+xop(n)；X(k)＝DFT[x(n)]＝XR(k)＋jXI(k)，则： DFT[xep(n)]=Re[X(k)]=XR(k) DFT[xop(n)]=jIm[X(k)]=jXI(k) 由序列DFT的共轭关系，可以推出各类序列DFT的对称关系，它们可总结如下表所示。

序列共轭对称性总结及示例

离散付氏变换 1、若x(n)为实函数，则X(k)是共轭偶对称的；x(n)为共轭偶对称的，则X(k)是实函数，从而有： 实、偶实、偶 实、奇虚、奇 3、因为X(k)=DFT[jxiep(n)]＝jDFT[xiep(n)]，由“1”得DFT[xiep(n)]是实偶函数， 即X(k)为虚偶函数，从而有： 虚、偶虚、偶 4、因为X(k)＝DFT[jxiop(n)]＝jDFT[xiop(n)]，由“2”得DFT[xiop(n)]是虚奇函数，即X(k)为实奇函数，从而有： 虚、奇实、奇

第三章 付里叶分析 频率域采样(Frequency Sampling) 第三章 付里叶分析 利用序列DFT的对称关系可以减少DFT的运算量，一般而言，只需计算大约一半点数的DFT，另一半可由对称性求得。序列对称性是DFT和DFS快速算法（FFT)的重要基础。 频率域采样(Frequency Sampling) 由时域采样定理知：在时域只要满足采样定理（即时域采样点足够多）即可用采样序列无失真地恢复原始信号（用采样序列代表原始连续信号）。由时频域的对称性原理推断，在频域也应存在类似的采样定理。即满足何种条件可以对频域连续函数采样，使得采样序列可以无失真地恢复原始频域函数。

频率域采样 频域采样定理(Frequency Sampling Theorem) ： 对M点有限长序列x(n)，若X(k)为x(n)频域函数的采样序列，只有当采样点数N≥M时，才有： 即可由频域采样序列X(k)恢复原始频域连续函数，进而可恢复原始时域序列x(n)。 若采样点数N<M，时域将发生混叠现象（失真），不能无失真地恢复原始信号； 有限长序列DFT是建立在频域采样定理基础上的，由此可以解释为何DFT用N点对频谱等间隔采样； 由频域采样定理可以推断无限长序列的DFT不存在（无意义），因为此时无论频域采样点数选取多大，时域都将发生混叠。

频率域采样 X(z)的内插公式及内插函数(Interpolation Function and Interpolation Formula of X(z)) 满足频域采样定理后，x(n)的DFT（X(k)）可以无失真地恢复（表示）x(n)，所以它也应能表示它的Z变换X(z)。用X(k)表示X(z)的表达形式称为X(z)的内插公式；在内插公式中描述采样点间轨迹关系的函数称为内插函数。 利用IDFT表达式和有限项级数求和公式容易推导得到X(z)的内插公式为： 式中： 为内插函数。

频率域采样 利用序列z变换与付氏变换的关系，由X(z)的内插公式容易求得 的内插公式和内插函数为： 利用尤拉公式和 ，对内插函数进行恒等变换：

频率域采样 所以， 的内插公式和内插函数又可写作：

第三章 付里叶分析 快速付氏变换(Fast Fourier Transform) 引言(Introduction) 第三章 付里叶分析 此表达方式将在《数字信号处理》介绍的频率采样FIR滤波器设计中得到应用。 快速付氏变换(Fast Fourier Transform) 引言(Introduction) DFT是数字（离散）信号中的一种重要变换，但从DFT定义可以容易得到直接计算一个N点的DFT需要：N2次复数乘法；N(N-1)次复数加法。即其运算量随着N按平方增加，当N较大时，其计算量非常大，直接用DFT进行实时计算或谱分析是不切实际的。

快速付氏变换 基2FFT算法(The Algorithm of Base 2 FFT) 1965年库利(J.W.Cooley)和图基(J.W.Tukey)发现DFT的快速算法后，DFT才得到实际的应用。 自1965年后，DFT的快速计算算法的研究得到空前的发展，除了Cooley-Tukey算法；Sande-Tukey算法外，还有许多其它算法，如：Winograd算法；余弦变换快速算法；Walsh变换；数论变换等。 基2FFT算法(The Algorithm of Base 2 FFT) FFT的基本思想(The Basal Thought of FFT) 长为N的序列x(n)的DFT定义：

快速付氏变换 式中， 为旋转因子，具有如下特性： 周期性： 对称性： 式中， 为旋转因子，具有如下特性： 周期性： 对称性： FFT的基本思想(The Basal Thought of FFT) ： 利用 的周期性和对称性，可使DFT运算中的某些项合并； 因为DFT的运算量与N2成正比，若将DFT运算尽可能地分解成小N点的DFT的组合，这样可以降低运算量。

快速付氏变换 基2时域抽取FFT(Cooley-Tukey算法，DIT-FFT) 基2FFT ：通过补零使N满足：N=2M，M为自然数; 时域抽取原理(Time-Domain Decimation Theory) 按n的奇偶将x(n)分解为两个N/2点的子序列： 则x(n)的DFT可写作：

快速付氏变换 再由 的周期性和对称性可求的DFT的后一半： 由周期性： 得：

快速付氏变换 和 再由对称性： 从而有： 这样，一个N点的DFT被分解成了两个N/2点的DFT线性组合： 将DFT分解M次，最后为2点DFT，完成FFT分解。

快速付氏变换 蝶形运算表示(The Denotation of Butterfly Computation) 上式定义的运算称为蝶形运算(Butterfly Computation)，它可由下图形象表示，利用蝶形运算符号可将FFT运算用流图描述。 一个蝶形运算由一次复乘法；两次复加法实现。向上加；向下减。

快速付氏变换 N=8的Cooley-Tukey法示例 一个N点基2FFT算法可以通过分解M次，每次用N/2个蝶形运算表示。 例3-13：N=8的时域抽取FFT通过3次抽取实现。后面三个图分别给出了8点时域抽取FFT的一、二、三次分解过程。由分解完成的8点时域FFT流图可以看出流图由M=3级构成，每一级由N/2个蝶形组成，每级蝶形的旋转因子均有其规律。

8 点DFT的第一次时域抽取分解图

8 点DFT的第二次时域抽取分解图

N点DIT-FFT运算流图（N=8）

快速付氏变换 Cooley-Tukey算法的规律及特点(Rules and Properties of Cooley-Tukey Algorithm) 规律： 流图结构(The Structure of Flow-Graph) N=2M点基2FFT算法流图结构共有M级，每级有N/2个蝶形； 输入序列的倒序(The Reverse order of Input Sequence) 按M位二进制“码位倒置”规律扰乱输入序列的角标顺序。 例3-14：设N=8，M=3，有：

快速付氏变换 蝶距(The Space of Butterfly Input) 定义：蝶形输入两信号点间的节点数称为蝶距。 式中：N为点数；M为级数；l为级号。 旋转因子 各级蝶形有 组 ；每组有 个 ，而且组中 的幂m按差 由0递增。 由这些规律可以很容易地画出N=2M点的基2FFT运算流图，从而用软件编程或硬件系统实现信号的DFT运算。

快速付氏变换 特点： 运算次数(Number of Computation) 每个蝶形最多需要一次复乘法、二次复加法。这样一个N点基2FFT的运算量最多为： 复乘法： 复加法： 与直接运算比较：

快速付氏变换 原位运算(Original Computation) 在运算中无需中间寄存器。仅需（N+N/2）个存储单元。 复加法： 例如，N=1024＝210，M=10，有： N越大，FFT效率越高。 原位运算(Original Computation) 在运算中无需中间寄存器。仅需（N+N/2）个存储单元。

快速付氏变换 IDFT的运算(Computation of IDFT) 将运算中的旋转因子 改为 ，计算完后再乘1/N。此法需要修改FFT子程序； 由IDFT表达式有： 由上式可以看出，若先将X(k)取共轭，然后直接调用FFT子程序（或用与正变换相同的专用硬件），再将结果取共轭并乘以1/N，即可求出X(k)的IDFT。 此法的特点是无需对软件或硬件做修改，可共用。

快速付氏变换 基2频域抽取FFT(Sande-Tukey算法 ，DIF-FFT) 抽取原理(Decimation Theory) 将x(n)分成前N/2和后N/2两半，即： 这样，DFT可写作：

快速付氏变换 将k分成偶和奇数，即将X(k)分解成奇偶两组，在偶数组中k=2r,则 ；在奇数组中k=2r+1,则 ；有：

快速付氏变换 至此，X(k)已被分解成了两个N/2点的DFT，当然，在计算N/2点DFT之前还需计算如下蝶形运算：

快速付氏变换 频域抽取的蝶形运算(Butterfly Computation in Frequency-Domain) 与时域抽取类似，继续分解M次，直到2点DFT。 频域抽取的蝶形运算(Butterfly Computation in Frequency-Domain) 与时域抽取类似，上式蝶形运算也可用一种蝶形描述，如下图所示，其运算次数与时域蝶形相同，区别在于旋转因子相乘的位置不同。

快速付氏变换 N=8的频域抽取法示例 例3-15：以下二图说明了8点频域抽取FFT第一次抽取和第二次抽取的过程，再后一图为8点频域抽取FFT的完整信号流图。

DIF-FFT一次分解运算流图（N=8）

DIF-FFT二次分解运算流图（N=8）

DIF-FFT运算流图（N=8）