1N?1*1nk*x(n)?[?X(k)WN]?{DFT[X*(k)]},n?0,1,?,N?1，也就
Nk?0N是说，可先将X(k)取共轭变换，即将X(k)的虚部乘以－１，就可直接调用FFT的程序，最后再对运算结果取一次共轭变换并乘以常数1/N即可得到x(n)的值。这种方法中，FFT运算和IFFT运算都可以共用一个子程序块，在使用通用计算机或用硬件实现时比较方便。
4.1.3 混合基FFT算法
以上讨论的是基2的FFT算法，即N?2的情况，这种情况实际上使用得最多，这种FFT运算，程序简单，效率很高，用起来很方便。另外，在实际应用时，有限长序列的长度N到底是多少在很大程度时是由人为因素确定的，因此，大多数场合人们可以将N选定为N?2，从而可以直接调用以２为基数的FFT运算程序。
如果长度N不能认为确定，而N的数值又不是以2为基数的整数次方，一般可有以下两种处理方法：
（１）
将x(n)用补零的方法延长，使N增长到最邻近的一个
MMN?2M数值。例如，N=30，可以在序列x(n)中补进x(30)＝x(31)
＝０两个零值点，使N=32。如果计算FFT的目的是为了了解整个频谱，而不是特定频率点，则此法可行。因为有限长序列补零以后并不影响其频谱X(e已。
（２） 如果要求特定频率点的频谱，则N不能改变。如果N为复合数，则可以用以任意数为基数的FFT算法来计算。快速傅里叶变换的
jw)，只是频谱的采样点数增加而
67
基本思想就是要将DFT的运算尽量分小。例如，N=6时，可以按照N=3×２分解，将６点DFT分解为３组２点DFT。 举例：N=9时的快速算法。
4.2 快速傅里叶变换的应用
凡是可以利用傅里叶变换来进行分析、综合、变换的地方，都可以利
用FFT算法及运用数字计算技术加以实现。FFT在数字通信、语音信号处理、图像处理、匹配滤波以及功率谱估计、仿真、系统分析等各个领域都得到了广泛的应用。但不管FFT在哪里应用，一般都以卷积积分或相关积分的具体处理为依据，或者以用FFT作为连续傅里叶变换的近似为基础。
4.2.1 利用FFT求线性卷积—快速卷积
在实际中常常遇到要求两个序列的线性卷积。如一个信号序列x(n)通过FIR滤波器时，其输出y(n)应是x(n)与h(n)的卷积： y(n)?x(n)?h(n)?m????x(m)h(n?m)
?有限长序列x(n)与h(n)的卷积的结果y(n)也是一个有限长序列。假设x(n)与h(n)的长度分别为N1和N2，则y(n)的长度为N=N1+N2-1。若通过补零使x(n)与h(n)都加长到N点，就可以用圆周卷积来计算线性卷积。这样得到用FFT运算来求y(n)值（快速卷积）的步骤如下：
（１） 对序列x(n)与h(n)补零至长为N，使N≥N1+N2-1，并且
N?2M(M为整数)，即
x(n)???x(n),n?0,1,?,N1?1
?0,n?N1,N1?1,?,N?168
?h(n),n?0,1,?,N2?1 h(n)???0,n?N2,N2?1,?,N?1（２） 用FFT计算x(n)与h(n)的离散傅里叶变换
x(n)?(FFT)?X(k) （N点） h(n)?(FFT)?H(k) （N点）
（３） 计算Y(k)=X(k)H(k)
（４） 用IFFT计算Y(k)的离散傅里叶反变换得：y(n)=IFFT[Y(k)] （N点）
4.2.2 利用FFT求相关—快速相关
互相关及自相关的运算已广泛的应用于信号分析与统计分析，应用于连续时间系统也用于离散事件系统。
用FFT计算相关函数称为快速相关，它与快速卷积完全类似，不同的是一个应用离散相关定理，另一个应用离散卷积定理。同样都要注意到离散傅里叶变换固有的周期性，也同样用补零的方法来绕过这个障碍。
设两个离散时间信号x(n)与y(n)为已知，离散互相关函数记作Rxy(n)，定义为
Rxy(n)?m????x(m)y(n?m)
?如果x(n)与y(n)的序列长度分别为N1和N2，则用FFT求相关的计算步骤如下：
（１）对序列x(n)与y(n)补零至长为N，使N≥N1+N2-1，并且
N?2M(M为整数)，即
69
x(n)???x(n),n?0,1,?,N1?1
?0,n?N1,N1?1,?,N?1?y(n),n?0,1,?,N2?1 y(n)???0,n?N2,N2?1,?,N?1（２）用FFT计算x(n)与y(n)的离散傅里叶变换
x(n)?(FFT)?X(k) （N点） y(n)?(FFT)?Y(k) （N点）
（３）将X(k)的虚部Im[X(k)]改变符号，求得其共轭X*(k) （４）计算Rxy(k)=X*(k)Y(k) （５） 用IFFT求得相关序列Rxy(n)
Rxy(n)＝IFFT[Rxy(k)] （N点）
如果x(n)＝y(n)，则求得的是自相关序列Rxx(n)
4.2.3 Chirp－Z变换
采用FFT算法可以很快的计算出全部DFT值，也即Z变换在单位圆上的全部等间隔采样值。但是，很多场合下，并非整个单位圆上的频谱都是很有意义的，例如对于窄带信号过程，往往只需要对信号所在的一段频带进行分析，这是，希望采样能密集在这段频带内，而对频带以外的部分，则可以完全不管。另外，有时也希望采样能不局限于单位圆上，例如，语音信号处理中，往往需要知道其Z变换的极点所在频率，如果极点位置离单位圆较远，，则其单位圆上的频谱就很平滑，如图所示，这是很难从中识别出极点所在的频率。要是采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则所得的结果将会在极点所在频率上出现明显的尖峰，从而可以较准确
70
的测定极点频率。
螺线采样就是一种适用于这种需要的变换，并且可以采用FFT来快速计算，这种变换也称为Chirp-Z变换，它是沿Z平面上的一段螺线作等分角的采样，这些采样点可表达为
zk?AW?k,k?0,1,?,M?1
其中M为采样点的总数，A为起始点位置，这个位置可以进一步用它的半径A0及相角?0来表示 A?A0e参数W可表示为
W?W0ej?0j?0
其中W0为螺线的伸展率，W0>１时螺线内缩（反时针方向）；W0<１时螺线外伸。?0为螺线上采样点之间的等分角。螺线采样点在Z平面上的分布可表示为下图。
下面分析这些点上采样值计算的特点。假定x(n)是长度为N的有限长信号序列，则其Z变换在采样点上的值为
71