2 离散傅里叶变换（DFT）
2.1 离散傅里叶变换的定义
设x(n)是一个长度为M的有限长序列，则x(n)的N点离散傅立叶变换为：
N?1kn?x(n)WNX(k)=DFT[x(n)]=n?0,k=0,1,...,N-1。 (1)
X(k)的离散傅里叶逆变换为：
1N?1?knx(n) =IDFT[X(k)]= NX(k)Wn??0N,k=0,1,...,N-1 (2)
?j2?式中，
WN?eN，N称为DFT变换区间长度，N≥M。
2.2 离散傅里叶变换的基本性质 2.2.1线性性质
如果x1(n)和x2(n)是两个有限长序列，长度分别为N1和N2，且 y(n)?ax1(n)?bx2(n)。
式中，a、b为常数，取N?max[N1,N2]，则y(n)的N点DFT为：
Y(k)?DFT[y(n)]N?aX1(k)?bX2(k) 0≤k≤N—1 其中，X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT。 2.2.2 循环移位性质
（1）序列的循环移位
设x(n)为有限长序列，长度为M，M≤N，则x(n)的循环移位定义为 y(n)?x((n?m))NRN(n) (4) （2）时域循环移位定理
设x(n)是长度为M（M≤N）的有限长序列，y(n)为x(n)的循环移位，即 y(n)?x((n?m))NRN(n)
则
y(k)?DFT[y(n)]?kmN?WMX(k) 其中 X(k)?DFT[x(n)]N 0≤k≤N—1 （3）频域循环移位定理
3）5）（ （
如果 X(k)?DFT[x(n)]N 0≤k≤N—1 Y(k)?x((k?l))NRN(k)
nly(n)?IDFT[Y(k)]?WNNx(n) （6） 则
2.2.3 循环卷积定理
有限长序列x1(n)和x2(n)的长度分别为N1和N2，N≥max[N1，N2]，x1(n)和x2(n)的N点循环卷积为：
?x(n)?x(n)x(n)21M=0 ○*=
则x(n)的N点DFT为：
N?1x2(m)x1((n?m))NRN(n)
X(k)?DFT[x(n)]N?X1(k)X2(k) （7） 2.2.4 共轭对称性
如果序列x(n)的DFT为X(k)，则x(n)的实部和虚部（包括j）的DFT分别为X(k)的共轭对称分量和共轭反对称分量；而x(n)的共轭对称分量和反共轭对称分量的DFT分别为X(k)的实部和虚部乘以j[3]。
3 快速傅里叶变换（FFT）
3.1 FFT算法基本原理
快速傅里叶变换（FFT）是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅里叶变换的算法进行改进获得的，它对离散傅里叶变换并没有新的发现。
有限长序列x(n)及其频域表示X(k)可由以下离散傅立叶变换得出
nkx(k)=DFT[x(n)]=?x(n)WNn?0N?1 0?k?N?1 （8）
1N?1?nkx(n)=IDFT[X(k)]=?X(k)WNNn?0 0?k?N?1 （9）
其中WnkN?e?j2?nkN。式（8）称为离散傅立叶正变换，式（9）称为离散傅立叶逆变换，x(n)与X(k)
构成了离散傅立叶变换对。
根据上述公式，计算一个X(k)，需要N次复数乘法和N-1次复数加法，而计算全部
20?k?N?1NX(k)( )，共需要次复数乘法和N(N-1)次复数加法。实现一次复数乘法需要四次实
数乘法和两次实数加法，一次复数加法需要两次实数加法，因此直接计算全部X(k)共需要4N次实数乘法和2N(2N-1)次实数加法。当N较大时，对实时信号处理来说，对处理器计算速度有十分苛刻的要求，于是如何减少计算离散傅里叶变换运算量的问题变得至关重要。
为减少运算量，提高运算速度，就必须改进算法。计算DFT过程中需要完成的运算的系数里，存在相当多的对称性。通过研究这种对称性，可以简化计算过程中的运算，从而减少计算DFT所需的时间。
如前所述，N点的DFT的复乘次数等于N。显然，把N点的DFT分解为几个较短的DFT，可是乘
mWN法的次数大大减少。另外，旋转因子具有明显的周期性和对称性，其周期为：
?j2?(m?lN)N?j2?mN22Wm?lNN?e?em?WN
其对称性表现为：
?mN?mN?m*mW?W[W]?WNNNN 或
mWNFFT算法就是不断地把长序列的DFT分解成几个短序列的DFT，并利用的周期性和对称性来
减少DFT的运算次数。
nkWN具有以下固有特性：
nknk(n?N)kn(k?N）WW?W?WNNNN(1)的周期性： nk?nknknn(N?k)WW?（W）?WNNNN(2)的对称性： nknnWW?W,W?WN/nNNn (3)N的可约性：NN/2(k?N/2)kW??1,W??WNNN另外，。
nkWN利用的上述特性，将x(n)或X(k)序列按一定规律分解成短序列进行运算，这样可以避免
大量的重复运算，提高计算DFT的运算速度。算法形式有很多种，但基本上可以分为两大类，即按时间抽取(Decimation In Time，DIT)FFT算法和按频率抽取(Decimation In Frequency，DIF)FFT算法。
3.2 基-2FFT算法
如果序列x(n)的长度N?2，其中M是整数(如果不满足此条件，可以人为地增补零值点来达
M
到)，在时域上按奇偶抽取分解成短序列的DFT，使最小DFT运算单元为2点。通常将FFT运算中最小DFT运算单元称为基(radix)，因而把这种算法称为基-2时间抽取FFT(DIT-FFT)算法[4]。
将x(n)按n为奇偶分解成两个子序列，当n为偶数时，令n=2r；当n为奇数时，令n=2r+l；可得到
x(2r)?x1(r),x(2r?1)?x2(r),r?0,...,N?12 （10）
则其DFT可写成
2rk(2r?1)kX(k)??x(2r)WN??x(2r?1)WNr?0r?0N?12r?0N?12r?0N?12N?12
2rk(2r?1)k??x1(r)WN??x2(r)WNN?12r?0N?12r?0
rkrk??x(2r)WN/2??x(2r?1)WN/2
k?X(k)?WX2(k) （11） 1N
X1(k)和X2(k)均分别是N/2点序列x1(n)和x2(n)的DFT，而且r与k的取值满足0,1,?,N/2-1。
nkW而X(k)是一个N点的DFT，因此式（11）只计算了X(k)的前N/2的值。由DFT和N的性质可得到X(k)
的后N/2的值为：
Nk?NNNX(k?)?X1(k?)?WN2X2(k?)k?X(k)?W2221NX2(k) （12）
式（11）和式（12）表明，只要计算出两个N/2点的DFT x1(k)和x2(k)，经过线性组合，即
MM?1可求出全部N点的X(k)。由于N?2，N/2?2仍为偶数，因而这样的分解可以继续进行下去，
直到最后的单元只需要做2点DFT为止。
nkX(p)X(q)Wm?1m?1N若Xm(p)和Xm(q)为输入数据，和为输出数据，为旋转因子，则对于基
-2DIT-FFT算法，蝶形运算的基本公式为
{
其图形表示如图1所示，称Xm(P)为上结点，Xm(q)为下结点。
kXm?1(p)?Xm(p)?Xm(q)WNkXm?1(q)?Xm(p)?Xm(q)WN
图1 时间抽取蝶形运算单元
对于一个8点的FFT，根据上述算法可以得到一个完整的N=8的基-2DIT-FFT的运算流图，如图2所示。
图2 N=8 DIT-FFT运算流图
根据上述算法原理及运算流图，可以得出基-2DIT-FFT的基本特点，特点如下。
MN?2(1)级数分解：对于。共分了M级，每级包含N/2个蝶形运算单元，总共所需蝶形运算个数为
NN?M??log2N22。
N?log2N2(2)运算量估计：每个蝶形运算需要一次复数乘法和两次复数加(减)法，N点FFT共需要次
复数乘法，N?log2N次复数加(减)法。实际上有些蝶形运算不需要做复乘。
(3)原位运算：当数据输入到存储器以后，每一组蝶形运算后，结果仍然存放在这同一组存储器中的同一位置，不需要另辟存储单元，直到最后输出。
(4)位码倒序：由图2可以看到，FFT输出的X(k)的次序正好是顺序排列的，即X(0)，X(1)，?,X(7)，而输入X(n)是按x(0)，X(4)，?,X(7)的倒序存入存储单元，即为倒序输入，正序输出。这种顺序看起来相当杂乱，然而它是有规律的，即位码倒序规则。