第3章5-8 离散傅里叶变换及其快速算法

1、Discrete Fourier Transform and Fast Algorithm 离散傅里叶变换在实际应用中是非常重要的，利用它可以计算信号的频谱、功率谱和线性卷积等。但是，如果使用定义式(3.20)来直接计算DFT，当N很大时，即使使用高速计算机，所花的时间也太多。因此，如何提高计算DFT的速度，便成了重要的研究课题。1965年库利 (Cooley)和图基(Tukey)在前人的研究成果的基础上提出了快速计算DFT的算法，之后，又出现了各种各样快速计算DFT的方法，这些方法统称为快速傅里叶变换(Fast Fourier Transform)，简称为FFT。FFT的出现，使计算DFT的

2、计算量减少了两个数量级，从而成为数字信号处理强有力的工具。 快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快速算法。它是DSP领域中的一项重大突破，它考虑了计算机和数字硬件实现的约束条件、研究了有利于机器操作的运算结构，使DFT的计算时间缩短了12个数量级，还有效地减少了计算所需的存储容量，FFT技术的应用极大地推动了DSP的理论和技术的发展。DFT的定义在导出FFT算法之前，首先来估计一下直接计算DFT所需的计算量。其中将DFT定义式展开成方程组将方程组写成矩阵形式用向量表示 从矩阵形式表示可以看出，由于计算一个X(k)值需要N次复乘法和(N-1)次复数加法，因而计算N个X(k)值，共

3、需N2次复乘法和N(N-1)次复加法。每次复乘法包括4次实数乘法和2次实数加法，每次复加法包括2次实数加法，因此计算N点的DFT共需要4N2次实数乘法和(2N2+2N(N-1)次实数加法。当N很大时，这是一个非常大的计算量。 FFT算法主要利用了WNk的两个性质：(1)对称性，即(2)周期性，即用复数表示：r为任意整数。 FFT算法是基于可以将一个长度为N的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算这一基本原理的。这一原理产生了许多不同的算法，但它们在计算速度上均取得了大致相当的改善。 在本章中我们集中讨论两类基本的FFT算法。 第一类 称为按时间抽取(Decimation-in

4、-Time)的基2FFT算法，它的命名来自如下事实：在把原计算安排成较短变换的过程中，序列x(n)(通常看作是一个时间序列)可逐次分解为较短的子序列。 第二类称为按频率抽取(Decimation-in-Frequency)的基2FFT算法，在这类算法中是将离散傅里叶变换系数序列X(k)分解为较短的子序列。 前面两种算法特别适用于N等于2的幂的情况。 对于N为合数的情况，本章也将介绍两种处理方法。 这种算法简称为时间抽选FFT算法，其基本出发点是，利用旋转因子WNk的对称性和周期性，将一个大的DFT分解成一些逐次变小的DFT来计算。 分解过程遵循两条规则：对时间进行偶奇分解；对频率进行前后分解。

5、 设N2M，M为正整数。为了推导方便，取N238，即离散时间信号为 按照规则(1)，将序列x(n)分为奇偶两组，一组序号为偶数，另一组序号为奇数，即分别表示为：根据DFT的定义 因为 WN2=WN/21，所以上式变为上式中的G(k)和H(k)都是N/2点的DFT。(3.64)按照规则(2)，将X(k)分成前后两组，即由(3.64)表示的是N/2点DFT，前4个k值的DFT可表示为后4个k值的X(k)表示为：因为所以(3.66)(3.65)按照式(3.65)和式(3.66)可画出图315所示的信号流程图。 式(3.65)和式(3.66)把原来N点DFT的计算分解成两个N/2点DFT的计算。照此可

6、进一 步把每个N/2点DFT的计算再各分解成两个N/4点DFT的计算。具体说来，是把x(0)，x(2)，x(4)，x(6)和x(1)，x(3)，x(5)，x(7)分为x(0)，x(4) | x(2)，x(6)和x(1)，x(5) | x(3)，x(7)。这样，原信号序列被分成x(0)，x(4) | x(2)，x(6) I x(1)，x(5) I x(3)，x(7)4个2项信号。G(k)和H(k)分别计算如下:(3.67)(3.68)(3.69)(3.70) 这样，用式(3.67)(3.70)4个公式就可计算图3.15中的两组N/2点DFT。图3.16所示的是其中一组G(k)的计算。 将图3.1

7、6与图3.15所示的信号流程图合并，便得到图3.17所示的信号流程图。因为N=8，所以上图中N/4点的DFT就是2点的DFT，不能再分解了。 将2点DFT的信号流程图移入图3.17，得到图3.19所示的8点时间抽选的完整的FFT流程图。从图3.19中可看出几个特点：(1)流程图的每一级的基本计算单元都是一个蝶形； (2)输入x(n)不按自然顺序排列，称为“混序”排列，而输出 X(k)按自然顺序排列，称为“正序”排列，因而要对输入进行“变址”；(3)由于流程图的基本运算单元为蝶形，所以可以进行“同址”或“原位”计算。 任何一个N为2的整数幂(即N=2M)的DFT，都可以通过M次分解，最后成为2点

8、的 DFT来计算。M次分解构成了从x(n)到X(k)的M级迭代计算，每级由N/2个蝶形组成。图3.20表示了蝶形的一般形式表示。其输入和输出之间满足下列关系： 从上式可以看出完成一个蝶形计算需一次复数乘法和两次复数加法。因此，完成N点的时间抽选FFT计算的总运算量为 大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计算次数为例来与直接计算进行比较。直接计算DFT需要的乘法次数为D=N2，于是有例如，当N=1024时，则： 205，即直接计算DFT所需复数乘法次数约为FFT的205倍。显然，N越大，FFT的速度优势越大。 表3. 2列出了不同N值所对应的两种计算方法的复数乘法次数和它们

9、的比值。 图3. 19包含log2N级迭代运算，每级由N/2个蝶形计算构成。蝶形计算的优点是可以进行所谓同址或原位计算。 现在来考察第一级的计算规律。设将输入x(0)，x(4)，x(2)，x(6)， x(1)，x(5)，x(3)，x(7)分别存入计算机的存储单元M(1), M(2), M(3),，M(7)和M(8)中。首先，存储单元M(1)和M(2)中的数据x(0)和x(4)进入运算器并进行蝶形运算，流图中各蝶形的输入量或输出量是互不相重的，任何一个蝶形的二个输入量经蝶形运算后，便失去了利用价值，不再需要保存。这样，蝶形运算后的结果便可以送到M(1)和M(2)存储起来。类似地，M(3)和M(4

10、)中的x(2)和x(6)进入运算器进行蝶形运算后的结果也被送回 到M(3)和M(4)保存，等等。第二级运算与第一级类似，不过，M(1)和M(3)存储单元中的数 据进行蝶形运算后的结果被送回M(1)和M(3)保存，M(2)和M(4)中的数据进行蝶形运算 后送回M(2)和M(4)保存，等等。这样一直到最后一级的最后一个蝶形运算完成。 可以看出， 每一级的蝶形的输入与输出在运算前后可以存储在同一地址(原来位置上)的存储单元中，这种同址运算的优点是可以节省存储单元，从而降低对计算机存储量的要求或降低硬件实现的成本。 蝶形运算的特点是，首先每一个蝶形运算都需要两个输入数据，计算结果也是两个数据，与其它结

11、点的数据无关，其它蝶形运算也与这两结点的数据无关、因此，一个蝶形 运算一旦计算完毕，原输入数据便失效了。这就意味着输出数据可以立即使用原输 人数据结点所占用的内存。原来的数据也就消失了。输出、输人数据利用同一内存单 元的这种蝶形计算称为同位(址)计算。 从图3. 19所示的流程图看出，同址计算要求输入x(n)是“混序”排列的。所谓输入为“混 序”，并不是说输入是杂乱无章的，实际上它是有规律的。如果输入x(n)的序号用二进制码来 表示，就可以发现输入的顺序恰好是正序输入的“码位倒置”，表3. 3列出了这种规律。 在实际运算中，按码位倒置顺序输入数据x(n)，特别当N较大时，是很不方便的。因此，数

12、据总是按自然顺序输入存储，然后通过“变址”运算将自然顺序转换成码位倒置顺序存储。实现这种转换的程序可用图3. 21来说明。 图中用n表示自然顺序的标号，用l表示码位倒置的标号。当l=n时，x(n)和x(l)不必互相调换。当ln时， 必须将x(l)和x(n)互相调换，但只能调换一次，为此必须规定每当ln时，要将x(l)和x(n)相互调换，即把原来存放x(n)的存储单元中的数据调入存储x(l)的存储单元中，而把原来存储x(l)的存储单元中的数据调入到存储x(n)的存储单元中。 这样，按自然序输入的数据x(n)经过变址计算后变成了码位倒置的排列顺序，便可进入第一级的蝶形运算。 最后介绍一下时间抽选F

13、FT算法的另外一些形式的流程图。对于任何流程图，只要保持 各节点所连支路及其传输系数不变，则不论节点位置怎样排列，所得到的流程图总是等效的，因而都能得到DFT的正确结果，只是数据的提取和存储次序不同而已。 把图3. 19中与x(4)水平相邻的所有节点和与x(1)水平相邻的所有节点交换，把与x(6)水平相邻的所有节点和与 x(3)水平相邻的所有节点交换，而与x(2)、x(5)和x(7)水平相邻各节点位置不变，就可以从图3. 19得到图3.22。图3.22与图3.19的区别只是节点的排列不同，而支路传输比，即WN的 各次幂保持不变。显然图3.22所示流程图的输入是正序(自然顺序)排列的，输出是码位

14、倒置 排列的，所以输出要进行变址计算。图3. 22所示的流程图相当于最初由库利和图基给出的时 间抽选算法。 另一种形式的流程图是将节点排列成输入 和输出两者都是正序排列，但这类流程图不能进行同址计算，因而需要两列 长度为N的复数存储器。 频率抽选基2FFT算法简称为频率抽选，它的推导过程遵循两个规则：对时间前后分；对频率偶奇分。 设N2M，M为正整数。为推导方便，取N=238。首先，根据规则(1)，将x(n)分成前一半和后一半，即 x(n)x(0), x(1), x(2), x(3), I x(4), x(5), x(6), x(7) 这样 (3. 72) 式(3. 72)虽然包含两个N/2点

15、求和公式，但是在每个求和公式中出现的是WNkn，而不是WN/2kn，因此这两个求和公式都不是N/2点的DFT。如果合并这两个求和公式，并利用则得：其次，按规则(2)，将频率偶奇分，即X(k)=X(0), X(2), X(4), X(6), | X(1), X(3), X(5), X(7)如果用X(2r)和X(2r+1)分别表示频率的偶数项和奇数项，则有令得到上面两式所表示的是N/2的DFT。在实际计算中，首先形成序列g(n)和h(n)，然后计算h(n)WNn，最后分别计算g(n) 和h(n)WNn的N/2点DFT，便得到偶数输出点和奇数输出点的DFT。计算流程图如图3. 24所示。 由于N是2

16、的整数幂，所以N/2仍然是偶数。这样，可以将N/2点DFT的输出再分为偶数组和奇数组，也就是将N/2点的DFT计算进一步分解为两个N/4点的DFT计算，其推导过程如下。 将g(n)分为前后两组，得到因为所以对频率再进行偶奇分，则得频率的偶数项为频率的奇数项为 通过类似的推导可得 上面4式所表示的计算都是N/4点的DFT计算，从而得到图3.25所示的形式。 与时间抽选的FFT算法一样，图3.27所示的流程图的基本运算也是蝶形运算，但是与时间抽选中的蝶形单元(图3.20)有所不同。图3. 28所示的是频率抽选FFT算法的蝶形单元的一般化的流程图 显然，一个蝶形的计算包括1次复数乘法和2次复数加法。

17、图3. 27所示的整个流程图共有log2N级迭代运算，每级有N/2个蝶形。因此，总计算量为频率抽选的FFT算法的计算量与时间抽选FFT算法的计算量是一样。 与时间抽选算法一样，频率抽选FFT算法也具有同址(原位)计算的优点。但是，与时间抽选不同的是，频率抽选FFT算法的信号输入为正序排列，输出为码位倒置排列，因此输出要进行变址计算。 FFT算法同样可以应用于IDFT的计算，称为快速傅里叶反变换，简写为IFFT。前述DFT和IDFT公式为 比较上面两式，可以看出，只要把DFT公式中的系数 改为 ，并乘以系数1/N，就可用FFT算法来计算IDFT，这就得到了IFFT的算法。 当把时间抽选FFT算法

18、用于 IFFT计算时，由于原来输入的时间序列x(n)现在变为频率序列X(k)，原来是将x(n)偶奇分的，而现在变成对X(k)进行偶奇分了，因此这种算法改称为频率抽选IFFT算法。类似地，当把频率抽选FFT算法用于计算IFFT时，应该称为时间抽选IFFT算法。 在IFFT计算中经常把常量1/N分解成M个1/2连乘，即1/N(1/2)M，并且在M级的迭代运算中，每级的运算都分别乘 上一个1/2因子。图3.29表示的是时间抽选IFFT流程图。 上面讨论的以2为基(即N2M)的时间抽选和频率抽选FFT算法，由于具有程序简单、 计算效率高、对存储量要求不很高等优点，因而在实际中得到了最广泛的应用。如果N

19、不等于 2的幂2M，通常有两种处理办法：(1)用补零的办法将x(n)延长为2M。例如N=60，可在序列x(n)的末尾填补4个0，即 令x(60)=x(61) =x(62)=x(63)=0，使N达到2664，这样就可使用基2FFT算法。有限长序列补零以后，只是频谱的取样点有所增加而不会影响它的频谱X(ej)的形状。 (2)采用以任意数为基数的FFT算法。 设N等于两个整数p和q 的乘积，即N=pq，则可将N点DFT分解成p个q点DFT或q个p点DFT来计算。为此，首先将x(n) 分为p组，每组长为q，即 例如，N=18=36，即p=3，q=6；将x(n)分成3组，每组各有6个序列值，即然后，将N

20、点DFT也分解为p组来计算，即 由于WNprk=WN/prk=Wqrk，因此是一个q点DFT，这样上式可写成从而说明：一个N=pq点的DFT可以用p个q点DFT来组成，如下图所示。 在最一般的情况下，设 N=p1p2pm，其中p1pm是m个素因子。首先把N分解为两个因子，即N=p1q1，其中q1p2p3pm，并用以上讨论的方法将DFT分解为p1个q1点DFT； 然后，将q1分解为q1=p2q2，其中q2=p3p4pm，即将每一个q1点DFT分解为p2个q2 点DFT；这样，通过m次分解，最后达到pm点 DFT。这种算法可以使DFT的运算获得最高效率。快速傅里叶变换在数字信号处理中有着广泛的应用

21、。下面简要地介绍它在谱分析和线性卷积计算中的应用。所谓谱分析就是计算信号的频谱，包括振幅谱、相位谱和功率谱。1. 谱分析中参数的选择假设所处理的离散时间信号x(n)是从连续时间信号xa(t)中取样得到的。下面的讨论采用如下符号：T(取样周期)，单位为s；fs(取样频率)，单位为Hz，fs=1/T；f0(连续时间信号xa(t)的最高频率)，单位为Hz；F(xa(t)的频率分辨率)，单位为Hz。所谓频率分辨率是指频域取样中两相邻点间的频率间隔。tp(信号xa(t)的最小记录长度)，tp=1/F，单位为s；N(一个记录长度中的取样数)。基带信号的频谱主要集中在低频段。根据取样定理，为了避免混叠失真，

22、要求最小记录长度必须按所需的频率分辨率来选择，即(3.91)(3.92)在保持分辨率不变的情况下，若希望增加所分析的信号的最高频率，或在保持信号最高频率不变的情况下，提高分辨率，唯一的办法是增加在记录长度内的取样取样点数N。如果f0和F都给定，那么N必须满足条件(3.93)(1) 数据准备设待分析的信号为任意长的连续时间信号xa(t) (t0)。若已知信号的最高频率为f0，频率分辨率为F，那么根据式(3.91)、式(3.92)和式(3.93)可分别求出取样周期T、最小记录长度tp和取样点数N。如果由式(3.93)计算得到的N不是2的整数幂，则应补充零取样值，使N等于2的整数幂，以便利用基2FF

23、T算法。 在记录长度中对xa(t)进行N点取样，得到(2)用FFT计算信号的频谱。用FFT计算x(n)的频谱，X(k)一般是由实部XR(k)和虚部XI(k)组成的复数，即X(k) = XR(k) + jXI(k) (3.95)(3)由X(k)求振幅、相位谱和功率谱。由式(3. 95)可求出振幅谱|X(k)|、相位谱(k)和功率谱S(k)，它们分别为解: 由频率分辨率确定最小记录长度为由信号最高频率计算取样周期记录长度内的取样点数为取N=16，即在使用FFT计算e-nT的频谱时，T不是一个重要参量，因而可令T=1，于是得运行Matlab程序，便可计算出信号x(n)=e-n (0n15)的频谱X(

24、k)，得到X(k)的实部、虚部、振幅谱和相位谱。频谱=1.5820 1.4490-0.3090i 1.2029-0.4229i 1.0064-0.3981i 0.8808-0.3240i 0.8051-0.2399i 0.7611-0.1571i 0.7382-0.0776i 0.7311+0.0000i 0.7382+0.0776i 0.7611+0.1571i 0.8051+0.2399i 0.8808+0.3240i 1.0064+0.3981i 1.2029+0.4229i 1.4490+0.3090i振幅谱=1.5820 1.4816 1.2751 1.0823 0.9385 0.8

25、401 0.7772 0.7423 0.7311 0.7423 0.7772 0.8401 0.9385 1.0823 1.2751 1.4816相位谱=0 -0.2101 -0.3381 -0.3767 -0.3525 -0.2896 -0.2036 -0.1047 0 0.1047 0.2036 0.2896 0.3525 0.3767 0.3381 0.2101信号x(n)通过FIR数字滤波器得到的输出等于x(n)与h(n)的线性卷积，即设信号x(n)的长度为N1，FIR数字滤波器的单位取样响应h(n)的长度为N2，即它们的线性卷积其线性卷积的结果y(n)是一个有限长序列，其非零值长度为

26、N1+N2-1。如果直接计算线性卷积，根据线性卷积的计算方法，其计算量为乘法次数：PDN1N2加法次数：QD(N1-1)(N2-1)两个有限长序列的线性卷积可以用循环卷积来代替，而循环卷积可使用FFT来计算。为了使循环卷积与线性卷积计算结果相等，必须把x(n)和h(n)都延长到N点(NNl+N2-1)，延长的部分均为零取样值。这样，y(n)的计算由以下5步来完成。(1)将x(n)和h(n)都延长到N点，NN1+N2-1；(2)计算x(n)的N点FFT，即X(k)FFTx(n)；(3)计算h(n)的N点FFT，即H(k)FFTh(n)；(4)计算Y(k)X(k)H(k)；(5)计算Y(k)的反变

27、换，即y(n)IFFTX(k)H(k) 。实际中常使用基2FFT算法，因此，当NN1+N2-1不为2的整数幂时，应该用补零取样值的方法将序列x(n)和h(n)都延长到最邻近的2的整数幂的值。第2、第3和第5步各需要做一次FFT，第4步要做N次乘法，因此总计算量为现以乘法运算次数为例，对线性卷积的直接计算方法和FFT计算方法进行比较。令r表示PD与PF的比值，考虑到N=N1+N2-1，有首先讨论x(n)和h(n)的长度相等的情况，这时N=2N1-12N1，于是对于不同的N1值，按上式计算得到的r值如下：由此可见，N1越大，用FFT或循环卷积计算线性卷积的优越性就越大。因此，通常把循环卷积成为快速

28、卷积，而把直接（线性）卷积称为慢速卷积。其次，讨论信号x(n)相对于单位取样响应很长，即N1N2的情况，这时NN1，于是显然，r值将下降，从而使循环卷积算法的优点不能发挥。此时可采用分段卷积来实现即将x(n)分成许多小段，每段长度与h(n)的长度相近，然后用FFT算法进行分段计算。具体见下一节。例3.3 设x(n)和h(n)分别为用循环卷积计算它们的线性卷积。解：(1)用补充零取样值的方法将x(n)和h(n)都延长到16点，即(2)分别计算x(n)和h(n)的N=16点的FFT, 得X(k)=FFTx(n)和H(k)=FFTh(n)。(3)计算Y(k)=X(k)H(k)。(4)计算Y(k)的1

29、6点反变换，得y(n)=IFFTX(k)H(k)。从上面的讨论知道，当信号x(n)的长度和滤波器的单位取样响应h(n)的长度相差不大时，用循环卷积计算线性卷积比直接计算线性卷积的速度要快。但是，当x(n)是一个很长的序列时，由于h(n)必须补很多零，因而循环卷积计算方法的效率将降低。同时，如果一次输入点数太多，则要求计算时占用很大的存储量。为了克服这些困难，可采用分段卷积的方法。分段卷积方法的计算过程是：首先把x(n)分成长度为L的若干段，这里L比h(n)的长度M略长，如左图所示；然后用循环卷积方法计算每段与h(n)的卷积；最后把各段的卷积结果以适当的方式拟合在一起。分段卷积方法有重叠相加法和

30、重叠保留法两种。将x(n)分成长为L的段，每段表示为x(n)可表示为xk(n)之和，即于是其中，yk(n)的长度为L+M-1。对h(n)和xk(n)都增添零取样值，使它们的长度都为N=L+M-1。计算h(n)与xk(n)的N点循环卷积，得到由于yk(n)的长度为L+M-1，而xk(n)长度为L，所以相邻两段yk(n)序列必然有M-1个点发生重叠，如图3.35(b)所示。这些重叠部分应该相加起来才能构成最后的输出序列，这就是“重叠相加法”这一名称的由来。重叠相加法用FFT处理的步骤归纳如下：(1)计算h(n)的N点DFT H(k)，N=L+M-1；(2)计算xk(n)的N点DFT X(k)，N=

31、L+M-1；(3)计算Yk(k)=X(k)H(k)；(4)求Yk(k)的N点反变换，即yk(n)IFFTXk(k)H(k)；(5)将yk(n)的重叠部分相加起来，最后输出为如果将重叠相加法中分段序列中补零的部分改为保留原来输入序列的值，如图3.36(b)中的虚线间的部分所示，且用yk(n)表示每段与h(n)的循环卷积，那么yk(n)将出现混叠，即每一段开始的M-1个点的序列样本是前一段最后M-1个点的序列样本。长度混叠发生在yk(n)的起始部分，因此，yk(n)的开始部分有M-1个点是不正确的，yk(n)可表示为现在，来分析图3.36中yk(n)的局部混叠是怎样产生的。由于h(n)长为M，当0

32、nM-2时，h(n-m)NRN(n)在xk(n)的尾部出现非零值，所以yk(n)中混有xk(n)与h(n-m)NRN(n)的卷积值，于是如图3.36(c)和(d)所示。当M-1nN-1时，h(n-m)NRN(n)在xk(n)尾部无非零值，这样，如图3.36(e)所示。因此，yk(n)的前M-1个点，即图3.36(f)打叉部分不是xk(n)与h(n)的真正卷积值，应把它去掉，yk(n)中只有后面L个点才是正确的。理解为什么产生混叠：1.由于将补零的部分改为保留原来输入序列的值，导致此部分值在相邻两段中计算了两次与h(n)的卷积，这两次计算就会导致混叠。2.图c为h(n)折叠后移位前的情况。每次移

33、位就循环右移一位，可以看出，如果在移位次数n小于M-1时，均会导致xk(m)与h(n-m)NRN(n)的乘积相加在L-1与N-1之间出现两次，从而出现混叠。现将x(n)分解为用FFT计算循环卷积令因此在实际应用中，有时只对信号的某一频段感兴趣，或只需计算单位圆上某一段的频谱值。例如，在对窄带信号进行分析时，常希望在窄频带内对频率的取样很密集，以便提高频率分辨率，而在窄频带外不予以考虑。对于这种情况，如果采用DFT方法，则需要在窄频带内外都增加频域取样点，而窄频带外的计算量是浪费的。此外，有时对非单位圆上的取样感兴趣，例如在语音信号处理中，常常需要知道其Z变换的极点所在处的复频率，这时就需要在这些极点附近的曲线上进行频域取样，这样，就要沿着螺旋线对Z变换取样。这种沿螺旋线上取样点计算的Z变换，称为线性调频Z变换(Chirp Z Transform，简称CZT)。下面就来讨论这种变换的原理及其计算方法。一个长度为N的序列x(n)，其Z变换为(3.110)为了使z可以沿着z平面更一般的路径(不只是单位圆)取值，可以沿一段螺旋线对z作等分角取样，这些取样点上的zk表示为(3.111)其中M为所要分析的复频谱的点数，不一定等于N。W和A为任意复数，可表示为(3.112)得到(3.114)取样点zk所在的路径如图3.38所示，图中：(1)A0表示起始取样点z0的矢量长度，通常A01，否