第3章 傅里叶分析
3.1 傅里叶变换概述
一、 时间连续、频率连续的傅里叶变换（FT）
其傅里叶变换公式为： 正变换 X(jΩ)=
⎰
∞
-∞∞
x(t)e-jΩtdt
X(jΩ)ejΩtdΩ
1
反变换 x(t)=
2π
⎰
-∞
时域函数的连续性造成频域函数的非周期性，而时域的非周期性造成频谱的连续性。 二、 时间连续、频率离散的傅里叶变换——傅里叶级数（FS）
周期为T的周期性连续时间函数x(t)可展开成傅里叶级数，其系数为X(jkΩ0)，X(jkΩ0)是离散频率的非周期函数。x(t)和X(jkΩ0)组成变换对，其变换公式为： 正变换 X(jkΩ0)=
∞
1T
⎰
T/2
-T/2
x(t)e-jkΩ0tdt
反变换 x(t)=
k=-∞
∑X(jkΩ
)ejkΩ0t
式中，k——谐波序号；
Ω0=2π/T——两条相邻的离散谱线之间角频率的间隔；
时域函数的连续性造成频域函数的非周期性，而时域函数的周期性造成频域函数的离散化。 三、 时间离散、频率连续的傅里叶变换——序列的傅里叶变换（DTFT） 1. DTFT的定义
序列的傅里叶变换公式为： 正变换 X(e
jω
)=12π
n=-∞
∑x(n)e⎰π
-
∞
-jωn
反变换 x(n)=
π
X(ejω)ejωndω
注意：序列只有当为整数时才有意义，否则没有定义。 ．．x(n)．．．．．．．n．．．．．．．．．．．．．．．．．
由于存在关系
DTFT[x(n)]=X(ejω)=X(z)z=ejω
因此，序列的傅里叶变换也就是单位圆上的Z变换。
时域的离散化造成频谱函数的周期性延拓，而时域的非周期性造成频域的连续性。 2. DTFT的性质 （1） 线性定理
DTFT[ax1(n)+bx2(n)]=aX1(ejω)+bX2(ejω)
（2） 时移定理
DTFT[x(n-n0)]=e-jωn0X(ejω)
（3） 频移定理
DTFT[x(n)ejω0n]=X(ej(ω-ω0))
（4） 卷积定理
注意：此处的卷积又称为线性卷积。 ．．．．．．．．．．．．．
I. 时域卷积定理
若y(n)=x(n)*h(n)，则Y(ejω)=X(ejω)H(ejω)
序列的运算包括翻褶、移位、和、积等。 （a） 翻褶
如果序列为x(n)，则x(-n)是以n=0的纵轴为对称轴将序列x(n)加以翻褶。 （b） 移位
如果序列为x(n)，当m为正时，则序列x(n+m)是指将序列x(n)依次逐项左移m位；当m为负时，则右移m位。 （c） 和
两序列的和是指同序号（n）的序列值逐项对应相加。 （d） 积
两序列的积是指同序号（n）的序列值逐项对应相乘。 线性卷积的几何意义： ．．．．．．．．．
若两序列x(n)和h(n)的卷积和定义为
∞
y(n)=x(n)*h(n)=
m=-∞
∑x(m)h(n-m)
则卷积的运算过程包含以下四步：
1翻褶：先在坐标系上作出h(m)，将h(m)以m=0的纵轴为对称轴翻褶成h(-m)； ○
2移位：将h(-m)移位n，即得h(n-m)； ○
注意： h(．-m) 与(m)的移位规律恰好相反，当为正时，则右移位；当为负时，则左．．．．．h．．．．．．．．．．．．．．．n．．．．．．．．n．．．．n．．．．．．．移位。 ．n．．．
3相乘：再将相同m值所对应的h(n-m)和x(m)值相乘； ○
4相加：将上述所有对应点的乘积叠加，即得y(n)值； ○
依次取n=„，-2，-1，0，1，2，„，即可得到全部的y(n)值。
II. 频域卷积定理
若y(n)=x(n)h(n)，则
11
Y(e)=X(ejω)*H(ejω)=
2π2π
jω
⎰πX(e
-
π
jθ
)H(ej(ω-θ))dθ
上述两个定理表明：离散时间序列的时域卷积对应频域相乘，而时域相乘则对应其频域卷积。
（5） Parseval（帕塞瓦）定理
n=-∞
∑x(n)=
∞
2
12π
⎰π
-
π
X(ejω)dω
2
Parseval定理表明：信号在时域的总能量就等于其频域的总能量。 四、 时间离散、频率离散的傅里叶变换——离散傅里叶变换（DFT）
结论：一个域（时域或频域）的离散化必然造成另一个域的周期延拓。 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
3.2 周期序列的离散傅里叶级数（DFS）
一、 DFS的定义 1. 周期序列的概念
x(n)是周期为N的一个周期序列，即 设~
~x(n)=~x(n+rN)， r为任意整数
因为在任何z值下，周期序列z变换的和式都不收敛，也就是说，周期序列不是绝对可
和的，所以不能用z变换表示。
但是，和连续时间周期信号一样，周期序列可以用离散傅里叶级数来表示，也就是用周期为N的复指数序列来表示。
2. 周期序列的离散傅里叶级数变换对
（1） 数学推导（略，参见教材P98~99） （2） 结论
x(n)与其离散傅里叶级数的系数X(k)组成一个变换对，且通过推导可见，周期序列~
~
~
X(k)也是一个周期为N的周期序列。
一般，采用符号
2πN
2πknN
WN=e
-j
，W
knN
=e
-j
则周期序列的离散傅里叶级数变换公式为：
N-1
~kn~正变换 X(k)=DFS[x(n)]=∑~ x(n)WN
n=0
1N-1~~-kn~反变换 x(n)=IDFS[X(k)]= X(k)W∑N
Nk=0
kn
3. WN的性质
（1） 周期性
kn(k+N)nk(n+N)
WN=WN=WN
（2） 对称性
-knkn*(N-k)nk(N-n)
WN=(WN)=WN=WN
（3） 正交性（重点强调）
⎧1，1N-1kn
W=δ(k-mN)=⎨∑N
Nn=0⎩0，
二、 DFS的性质
k=mN，m为任意整数
k为其他值
x(n)和~y(n)均是周期为N的周期序列，且有 设~
~~
X(k)=DFS[~x(n)]，Y(k)=DFS[~y(n)]
1. 线性性质
~~DFS[a~x(n)+b~y(n)]=aX(k)+bY(k)
2. 移位性质
-mk~DFS[~x(n+m)]=WNX(k) （时移）
~nl~DFS[WNx(n)]=X(k+l) （频移，又称调制特性）
3. 周期卷积
（1） 时域卷积
N-1
~△~~*x(n)=若f(n)=y(n)○x(m)~y(n-m)∑~
m=0
换元
令n-m=km=0
~~y(m)x(n-m)，则 ∑=
N-1
~~~~
F(k)=DFS[f(n)]=X(k)⋅Y(k)
1注意：此处的卷积为周期卷积。它和前面所介绍的非周期序列的线性卷积的区别在于：○．参．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
与周期卷积运算的两个序列都是周期为结果仍是一个以．．．．．．．．．．．．．．．．．N．的周期序列，则其卷积．．．．．．．．．．．．．．．．．N．为周期．．．
2的周期序列；○m=0~N-1）的范围内进行。 ．求和运算只在一个周期（．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．周期卷积的运算过程（参见图3.2.2）：
运算在m=0~N-1区间内进行，先计算出n=0，1，„，N-1的卷积结果，然后将所得的结果进行周期延拓，即可得到所求的整个周期序列。
注意：计算过程中，一个周期的某一序列值移出计算区间时，相邻的一个周期的同一位置．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．的序列值就移入计算区间。 ．．．．．．．．．．．．
（2） 频域卷积
由于DFS和IDFS的对称性，同样可以证明：时域周期序列的乘积对应频域周期序列的周期卷积，即：
若f(n)=~x(n)~y(n)，则
~
1N-1~~~~~
*Y(K)=F(k)=X(K)○∑X(l)Y(k-l)
Nl=01
=
N
∑Y(l)X(k-l)
l=0
N-1
~~
3.3 离散傅里叶变换（DFT）
一、 DFT的定义
1. 有限长序列和周期序列的关系
x(n)之间的关系可表示为 有限长序列x(n)和周期序列~
x(n)，0≤n≤N-1⎧~
x(n)=⎨
0，其他n⎩
x(n)的第一个周期（n=0~N-1）定义为“主值区间”x(n)通常，我们将周期序列~，故x(n)是~
的“主值序列”，且上述关系式可简写为
⎛对有限长序列进行⎫周期~ x(n)=x((n))N 延拓，可得到周期⎪⎪序
列⎝⎭
式中，((n))N表示“n对N求余数”，或称“n对N取模值”；
利用长度为N的矩形序列符号RN(n)，即
⎧1，
RN(n)=⎨
⎩0，
则（3.3.1）式又可写成
0≤n≤N-1
其他n
⎛对周期序列进行截⎫取，~ x(n)=x(n)RN(n) 可得到有限长序列⎪⎪序⎝⎭列
同理，频域周期序列X(k)也可看成是对有限长序列X(k)的周期延拓，而有限长序列X(k)则可看成是周期序列X(k)的主值序列，即
~
~
~
X(k)=X((k))N
或X(k)=X(k)RN(k)
~
2. 有限长序列的离散傅里叶变换对
有限长序列的离散傅里叶变换公式为： 正变换 X(k)=DFT[x(n)]=
∑x(n)W
n=0
N-1
knN
，0≤k≤N-1
1N-1-kn
反变换 x(n)=IDFT[X(k)]=X(k)WN，∑Nk=0
二、 DFT的性质 1. 线性性质
设x1(n)和x2(n)均是长度为N的有限长序列，且有
0≤n≤N-1
X1(k)=DFT[x1(n)]，X2(k)=DFT[x2(n)]
则 DFT[ax1(n)+bx2(n)]=aX1(k)+bX2(k)
说明：
（1） 若x1(n)和x2(n)的长度均为N，则ax1(n)+bx2(n)的长度也为N；
（2） 若x1(n)和x2(n)的长度不等，设分别为N1和N2，则ax1(n)+bx2(n)的长度应为二者中的最大值，即N = max[N1, N2]；
例如，当N1
有限长序列x(n)左移m（m为正整数）位的循环移位定义为
xm(n)=x((n+m))NRN(n)
可见，上式的循环移位表示将序列x(n)周期延拓成周期序列~x(n)=x((n))N后，再左移m位并取其主值序列而得到的。注意：序列的循环移位始终限定在主值区间内进行。 ．．．．．．．．．．．．．．．．．．．．如图所示，有限长序列循环移位的过程中，在主值区间（n=0~N-1）内，当某序列值从区间的一端移出时，与它同值的序列值又从区间的另一端移入，因而，此过程可以看成是将序列x(n)按逆时针方向排列在一个N等分的圆周上，则序列循环左移m位就相当于将该序列在圆周上顺时针旋转m位。
（2） 时域移位特性
-mk
Xm(k)=DFT[xm(n)]=DFT[x((n+m))NRN(n)]=WNX(k)
（3） 频域移位特性
nl
IDFT[X((k+l))NRN(k)]=WNx(n)
3. 循环卷积（又称圆周卷积）
（1） 循环卷积的定义
长度均为N的有限长序列x(n)和h(n)的循环卷积定义为
Nh(n)=[x((n))○*h((n))]R(n) y(n)=x(n)○NNN
⎡N-1⎤
=⎢∑x(m)h((n-m))N⎥RN(n)⎣m=0⎦⎡⎤
=⎢∑h(m)x((n-m))N⎥RN(n)⎣m=0⎦
N-1
（3.3.5）
可见，循环卷积就是周期卷积在主值区间（n=0~N-1）内的值
（2） 循环卷积的运算方法
1利用求和定义式（3.3.5）直接求解； ○
2利用与周期卷积的关系求解； ○
3根据循环卷积的特点，利用图解法求解，其步骤如下： ○
I. 将序列x(n)按逆时针方向均匀地（N等分）分布在一个圆周（内圆）上，而将序
列h(n)按顺时针方向均匀地（N等分）分布在另一个圆周（外圆）上，如图（a）所示；
II. 求两个圆上相应序列的乘积，并叠加N项乘积作为n=0时循环卷积值y(0)； III. 若求n=1时循环卷积值y(1)，则将外圆h(n)固定，把内圆上的序列x(n)顺时针旋
转一个单位（或将内圆x(n)固定，把外圆上的序列h(n)逆时针旋转一个单位，即内、外圆相对旋转一个单位），并将对应项的乘积叠加，即为所求的y(1) 值，如图（b）所示；
IV. 类似地，依次取n=2~N-1，重复步骤Ⅲ，直到将内圆序列循环移位一周，便可以
求得所有的y(n)值；
（3） 时域和频域循环卷积定理
I. 时域循环卷积定理
Nh(n)，则Y(k)=X(k)H(k) 若y(n)=x(n)○
这表明：两序列循环卷积的离散傅里叶变换等于其傅里叶变换的乘积。
II. 频域循环卷积定理
若y(n)=x(n)h(n)，则Y(k)=
1
NH(k) X(k)○
N
这表明：两序列乘积的离散傅里叶变换等于其傅里叶变换的循环卷积乘以1/N。 （4） 循环卷积、周期卷积和线性卷积的关系
1利用周期卷积计算循环卷积 ○
先计算两序列的周期卷积（列表法，参见例3.2.3），再对卷积结果取其主值区间（n=0~N-1）内的值即可。
2利用循环卷积计算线性卷积 ○
I. 用循环卷积代替线性卷积的条件
设两个有限长序列x(n)、h(n)的点数分别为N和M，其循环卷积的长度为L，则要用循环卷积代替线性卷积的条件是：循环卷积的长度必须不小于线性卷积的长度+M-1，．．．．．．．．．．．．．．．．．．．．．．．L．．．．．．．．．．．．．N．．．．．
即
L≥N+M-1
否则，在循环卷积周期延拓时会产生混叠。
II. 用循环卷积实现线性卷积的具体步骤
i) 根据上述条件，取L=N+M-1，分别将序列x(n)、h(n)补零扩展为L点序列，即
⎧x(n)，0≤n≤N-1⎧h(n)，0≤n≤M-1
，h(n)=⎨ x(n)=⎨
0，N≤n≤L-10，M≤n≤L-1⎩⎩
ii) 分别计算序列x(n)、h(n)的L点离散傅里叶变换，即
X(k)=DFT[x(n)]，H(k)=DFT[h(n)]
iii) 利用时域循环卷积定理计算序列x(n)、h(n)的L点循环卷积，且它就等于其线
性卷积，即
Lh(n)=IDFT[X(k)H(k)] y(n)=x(n)*h(n)=x(n)○
4. Parseval（帕塞瓦）定理
N-1
*
1N-1
x(n)y(n)=∑X(k)Y*(k) ∑Nk=0n=0
证： 由DFT的逆变换和正变换的定义，可得
⎡1N-1-kn⎤x(n)y(n)=x(n)Y(k)W∑∑N⎥⎢N∑n=0n=0⎣k=0⎦
1N-1*N-1kn=∑Y(k)∑x(n)WN Nk=0n=0
*
N-1N-1
*
1=N
如果令y(n) = x(n)，则上式变为
N-1
∑Y
k=0
N-1
*
(k)X(k)
1N-1
x(n)x(n)=∑X(k)X*(k) ∑Nk=0n=0
*
即
1N-12
x(n)=X(k)∑∑Nn=0k=0
2
N-1
这表明：序列在时域的能量与在频域的能量是相等的。
三、 DFT与DTFT及Z变换的关系
1. Z变换与DTFT的关系
DTFT与Z变换之间存在关系
DTFT[x(n)]=X(ejω)=X(z)z=ejω
即：若Z变换的收敛域包含单位圆，则序列的DTFT也就是单位圆上的Z变换。 2. Z变换与DFT的关系
有限长序列x(n)的DFT为
kn
X(k)=∑x(n)WN，k=0，1， ，N-1
n=0N-1
其Z变换为
X(z)=
对照上述公式，可知
n=-∞
∑x(n)z
∞
-n
X(k)=X(z)z=W-k=X(z)z=ej2Nπk，k=0，1， ，N-1
N
这表明：序列的DFT也就是其Z变换在单位圆上的等间隔采样，其角度间隔为ω=2π/N，
即将单位圆N等分，各序列的DFT值均匀分布在单位圆上。 3. DTFT与DFT的关系
ω
由于Z变换在单位圆上的取值就等于序列的傅里叶变换 X(ej)，则
X(k)=X(z)
2πjkz=eN
=X(e
j
2πkN
)
ω=
2πkN
=X(e)
jω
，k=0，1， ，N-1
这表明：序列的DFT也就是其DTFT的等间距采样，其采样间距为ω=2π/N。
序列的Z变换、DFT以及DTFT 的关系如图所示（P68图3.2.5）。
四、 频域采样
频域采样定理： ．．．．．．．
对于长度为频域采样不失真的条件是：频域采样点数N．．．．．M．的有限长序列，．．．．．．．．．．．．．．．．．．．．．．．．．．不小于序列．．．．．长度，即 ．．M．．．
N≥M
五、 DFT在实际应用中的问题 1. 混叠失真现象 2. 栅栏效应
因为DFT计算信号频谱，只给出了基频整数倍处的离散谱，而不是连续频谱，这就象通过一个“栅栏”观看景象一样，只能在离散点上看到真实景象，这种现象称为“栅栏效应”。 ．．．．减小栅栏效应的一个方法就是要使频域采样更密，即增加频域采样点数，这样必然使各谱线间的距离更近，从而使原来被“栅栏”挡住的频谱分量显露出来，为此，我们可以在不改变原有数据记录的基础上，采用在时域数据的末尾补零的方法来实现。补零的好处在于：．．．．．．．○1使频域采样更密，减小栅栏效应；○2使采样点数的整数次幂，便于利用计算机．．．．．．．．．．．．．．．．．．．．．．N．变为．．2．．．．．．．．．．．．．．实现快速傅里叶变换（FFT）。（P209） ．．．．．．．．．．．．．．．．．．．．．3. 频谱泄漏
在进行谱分析时，通常需要用矩形窗将长序列信号截取成若干段有限长序列信号，这种过程相当于原序列与矩形窗函数相乘，而时域相乘则对应于频域中的原序列频谱与矩形窗函数频谱的卷积过程，从而造成卷积后的频谱拓宽，即：在频谱图中的主瓣以外，又出现了多个旁瓣，这种失真现象就称为“频谱泄漏”现象。 ．．．．
为了减少泄漏带来的影响，截取信号时应根据具体情况，选择合适的窗函数，如哈明窗．．．．．．．．或汉宁窗等。那么，窗函数的选择依据如下： 1. 窗函数的评价指标（P207~208）
（1） 最大旁瓣用最大旁瓣值与主瓣峰值之比的对数来表示，即20lg(A旁max/A峰)； （2） 旁瓣衰减率以10个相邻旁瓣峰值的衰减比的对数来表示，即20lg(A旁10/A旁1)；
⎡G读⎤
-1⎥⨯100%； （3） 主瓣峰值可能最大误差ε=⎢G⎣峰⎦
（4） 主瓣宽
主瓣的宽窄对频率分辨率有影响，若主瓣宽越窄，则分辨率越高。 2. 窗函数的长度
窗的长度越长，其分辨率越高。 3. 窗函数的位置
对于周期信号尽量保证整周期采样。
3.4 快速傅里叶变换（FFT）
1965年，库利（J.W.Cooley）和图基（J.W.Tukey）在《计算数学》杂志上发表了著名的“机器计算傅里叶级数的一种算法”的文章，提出了DFT的一种快速算法。 一、 直接计算DFT的问题及改进途径
N点有限长序列x(n)的离散傅里叶变换公式为：
正变换 X(k)=DFT[x(n)]=
∑x(n)W
n=0
N-1
knN
，k=0，1， ，N-1
1N-1-kn
反变换 x(n)=IDFT[X(k)]=X(k)WN，n=0，1， ，N-1 ∑Nk=0
实现整个DFT运算需要进行N 2次复数乘法和N(N-1)次复数加法。由此可见，直接计算DFT时，其乘法次数和加法次数都与N 2成正比。
kn
解决途径：利用系数WN所固有的周期性、对称性等特性，可以将长序列的DFT分解．．．．．
为短序列的DFT，这样就可以大大减少DFT的运算量。正是基于这种基本思路而形成了快速傅里叶变换算法（Fast Fourier Transform，缩写为FFT），这种算法基本上可分为两大类：按时间抽取法（Decimation-In-Time，缩写为DIT）和按频率抽取法（Decimation-In-Frequency，缩写为DIF）。
注意：快速傅里叶变换（FFT）并不是一种新的变换，而是离散傅里叶变换（DFT）的一种．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．快速算法。 ．．．．．
二、 按时间抽取（DIT）的基-2FFT算法（库利-图基算法） 1. 算法的原理
先假设序列x(n)的长度N=2M（M为整数）。如果不满足这个条件，可以人为地在序列末尾补上若干个零值点，使其达到这一要求。这种N为2的整数幂的FFT也称基-2FFT。
将长度为N=2M的序列按n的奇偶分为两组，则通过公式推导可知，一个N点DFT可分解成两个N/2点DFT。
如果采用蝶形信号流图来表示上述分解过程，则该分解过程为
由于N=2M，则N/2仍是偶数。因此，若进一步将每个N/2点子序列再按奇偶部分分解
k2k
成两个N/4点的子序列，且将系数统一为WN/2=WN，则一个N=8点DFT就可以分解为
四个N/4=2点DFT（无需再分解），如图所示。
由此可见，这种方法的每一步分解都是按输入序列在时间上的奇偶次序来分解为两个更短的子序列，所以称为“时间抽取算法”。
上述N=8点时间抽取法FFT的流图如下所示。
2. 运算量
由上图可见，当N=2M时，共有M级（列）蝶形，每级都由N/2个蝶形运算组成，而每个蝶形运算都需要一次复数乘法和两次复数加法，因此每级运算都需N/2次复乘和N次复加，这样M级运算总共需要
复乘次数 mF=
NN
M=log2N 22
复加次数 aF=NM=Nlog2N
以乘法为例，由FFT算法、直接DFT算法的运算量与点数N的关系曲线图（P90图3.4.5）
可以直观地看出FFT算法的优越性，尤其是当点数N越大时，FFT的优点更突出，如图所示。
3. 算法的特点
由上面介绍的N=8点时间抽取法FFT流图，我们可以总结出N=2M点的时间抽取法的运算规律和特点。 （1） 蝶形运算
由8点FFT流图可见，FFT运算中的每一级（列）计算都是由N/2个蝶形运算组成，而N=2M时，共有M级（列）蝶形，因此N运算共需要/2·M个蝶形运算来完成。．点．FFT．．．．．．．．N．．．．．．．．．．．．其中，每个蝶形结构完成如下基本的迭代运算：
r
Xm(k)=Xm-1(k)+Xm-1(j)WN
Xm(j)=Xm-1(k)-Xm-1(j)W
rN
（3.4.8）
式中，m表示第m级（列）迭代，k，j为数据所在行数。其一般形式如图所示，它包括一
次复乘和两次复加。
在8点FFT流图中，第一级（列）每个蝶形的两节点间距为1=2，第二级每个蝶形的
M．两节点间距为2=21，第三级每个蝶形的两节点间距为4=22，由此类推得，对于N=2．．．．．点．FFT．．．
m-1．．．运算，其第m级每个蝶形的两节点间距为2．．．．．．．．．．．．．．．．．．．。
r
另外，由推导可得，每一级（列）不同的WN因子分布情况为：
第1级，W2r，r=0第2级，W4r，r=0,1第3级，W8r，r=0,1,2,3
(1种)(2种)(3种) (N/2种)
r
第M级，WN，r=0,1, ,N/2-1
r
因此我们不难总结出WN因子分布的一般规律为： ．．．．．．．．．．
rN/2
第m级，W2rm=WN，r=0,1, ,2m-1-1(2m-1种)
m
（2） 同址运算
在计算机编程时，将蝶形的两个输出值仍放回到两个输入所在的存储器中，这种运算就称为“同址运算”。 ．．．．（3） 倒位序规律及实现
I. 倒位序的规律
这种顺序看似混乱无序，但实际上是有规律的，我们将其称为“倒位序”。 ．．．
倒位序的原因是输入(n)按时域变量的奇偶不断进行分组而造成的。 ．．．．．．．．．x．．．．．．．．．n．．．．．．．．．．．．．．．
II. 倒位序的实现
一般在实际运算中，我们总是先按自然顺序将输入序列存入存储单元中，再通过变址运算来实现倒位序的排列。其具体方法如下：
如果输入序列x(n)的序号n用二进制数（例如n2 n1 n0）表示，则其倒位序二进制数n就是（n0 n1 n2
^
^
由此可知，只要在原来存放自然顺序序列x(n)的单元中，存入倒位序序列x(n)，即可实现倒位序的排列。这个变址过程如图所示。
由图可见，当n=n时，不必调换；只有当n≠n时，才需要将原来存放x(n)和x(n)的存储单元中的内容互换。为了节省调换时间，避免重复调换（保证只调换一次，否则又回到原状），我们只需检查n和n的相对大小，若n>n，则表明此x(n)在前面已经和x(n)调换过了，不必再
^
^
^
^
^
^
调换；否则，就必须进行互换。
综上所述，实现倒位序排列的具体方法为：若≥n时，不必调换；若
三、 按频率抽取（DIF）的基-2FFT算法（桑德-图基算法）
前面讨论的FFT算法是将输入序列x(n)按时间变量n的奇偶分解为越来越短的序列。类似地，如果我们将输出序列X(k)按频域变量k的奇偶分解为越来越短的序列，这种FFT算法就称为“频域抽取法”。 四、 IDFT的快速算法（IFFT）
利用FFT算法来计算IFFT的具体方法有以下两种： 1. 方法一
首先，比较IDFT公式
^
^
^
1N-1-kn
x(n)=IDFT[X(k)]=∑X(k)WN
Nk=0
和DFT 公式
kn X(k)=DFT[x(n)]=∑x(n)WN
n=0N-1
kn-kn
可见，只要将DFT运算中的每一个系数WN换成WN，最后再乘以常数1/N，则前面所介
绍的按时间或按频率抽取的FFT算法都可用来计算IDFT。
kn-kn
例如，我们可直接由8点频率抽取FFT流图出发，把WN换成WN，并在每级（列）MM．．
运算中都乘以1/2（注意：因为乘以1/N就等效于1/N =1/2=(1/2)．．．．．．．．．．．．．．．．．．．．．．．．，所以相当于每级都乘．．．．．．．．．．
以）
IFFT流图，如图所示。 ．1/2．．．
2. 方法二
首先，对IDFT公式取共轭，得
1
x(n)=
N
*
∑X
k=0
N-1
*
kn (k)WN
然后对上式两边再取共轭，得
1⎡N-1*1kn⎤**
x(n)=⎢∑X(k)WN={DFT[X(k)]}⎥N⎣k=0N⎦
由此可见，只要先将X(k)取共轭，就可以直接利用FFT运算，最后将运算结果再取共轭，
并乘以1/N，即可得到x(n)值。这样，FFT运算和IFFT运算可以共用一个子程序，便于编*
程实现。
第3章 傅里叶分析
3.1 傅里叶变换概述
一、 时间连续、频率连续的傅里叶变换（FT）
其傅里叶变换公式为： 正变换 X(jΩ)=
⎰
∞
-∞∞
x(t)e-jΩtdt
X(jΩ)ejΩtdΩ
1
反变换 x(t)=
2π
⎰
-∞
时域函数的连续性造成频域函数的非周期性，而时域的非周期性造成频谱的连续性。 二、 时间连续、频率离散的傅里叶变换——傅里叶级数（FS）
周期为T的周期性连续时间函数x(t)可展开成傅里叶级数，其系数为X(jkΩ0)，X(jkΩ0)是离散频率的非周期函数。x(t)和X(jkΩ0)组成变换对，其变换公式为： 正变换 X(jkΩ0)=
∞
1T
⎰
T/2
-T/2
x(t)e-jkΩ0tdt
反变换 x(t)=
k=-∞
∑X(jkΩ
)ejkΩ0t
式中，k——谐波序号；
Ω0=2π/T——两条相邻的离散谱线之间角频率的间隔；
时域函数的连续性造成频域函数的非周期性，而时域函数的周期性造成频域函数的离散化。 三、 时间离散、频率连续的傅里叶变换——序列的傅里叶变换（DTFT） 1. DTFT的定义
序列的傅里叶变换公式为： 正变换 X(e
jω
)=12π
n=-∞
∑x(n)e⎰π
-
∞
-jωn
反变换 x(n)=
π
X(ejω)ejωndω
注意：序列只有当为整数时才有意义，否则没有定义。 ．．x(n)．．．．．．．n．．．．．．．．．．．．．．．．．
由于存在关系
DTFT[x(n)]=X(ejω)=X(z)z=ejω
因此，序列的傅里叶变换也就是单位圆上的Z变换。
时域的离散化造成频谱函数的周期性延拓，而时域的非周期性造成频域的连续性。 2. DTFT的性质 （1） 线性定理
DTFT[ax1(n)+bx2(n)]=aX1(ejω)+bX2(ejω)
（2） 时移定理
DTFT[x(n-n0)]=e-jωn0X(ejω)
（3） 频移定理
DTFT[x(n)ejω0n]=X(ej(ω-ω0))
（4） 卷积定理
注意：此处的卷积又称为线性卷积。 ．．．．．．．．．．．．．
I. 时域卷积定理
若y(n)=x(n)*h(n)，则Y(ejω)=X(ejω)H(ejω)
序列的运算包括翻褶、移位、和、积等。 （a） 翻褶
如果序列为x(n)，则x(-n)是以n=0的纵轴为对称轴将序列x(n)加以翻褶。 （b） 移位
如果序列为x(n)，当m为正时，则序列x(n+m)是指将序列x(n)依次逐项左移m位；当m为负时，则右移m位。 （c） 和
两序列的和是指同序号（n）的序列值逐项对应相加。 （d） 积
两序列的积是指同序号（n）的序列值逐项对应相乘。 线性卷积的几何意义： ．．．．．．．．．
若两序列x(n)和h(n)的卷积和定义为
∞
y(n)=x(n)*h(n)=
m=-∞
∑x(m)h(n-m)
则卷积的运算过程包含以下四步：
1翻褶：先在坐标系上作出h(m)，将h(m)以m=0的纵轴为对称轴翻褶成h(-m)； ○
2移位：将h(-m)移位n，即得h(n-m)； ○
注意： h(．-m) 与(m)的移位规律恰好相反，当为正时，则右移位；当为负时，则左．．．．．h．．．．．．．．．．．．．．．n．．．．．．．．n．．．．n．．．．．．．移位。 ．n．．．
3相乘：再将相同m值所对应的h(n-m)和x(m)值相乘； ○
4相加：将上述所有对应点的乘积叠加，即得y(n)值； ○
依次取n=„，-2，-1，0，1，2，„，即可得到全部的y(n)值。
II. 频域卷积定理
若y(n)=x(n)h(n)，则
11
Y(e)=X(ejω)*H(ejω)=
2π2π
jω
⎰πX(e
-
π
jθ
)H(ej(ω-θ))dθ
上述两个定理表明：离散时间序列的时域卷积对应频域相乘，而时域相乘则对应其频域卷积。
（5） Parseval（帕塞瓦）定理
n=-∞
∑x(n)=
∞
2
12π
⎰π
-
π
X(ejω)dω
2
Parseval定理表明：信号在时域的总能量就等于其频域的总能量。 四、 时间离散、频率离散的傅里叶变换——离散傅里叶变换（DFT）
结论：一个域（时域或频域）的离散化必然造成另一个域的周期延拓。 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
3.2 周期序列的离散傅里叶级数（DFS）
一、 DFS的定义 1. 周期序列的概念
x(n)是周期为N的一个周期序列，即 设~
~x(n)=~x(n+rN)， r为任意整数
因为在任何z值下，周期序列z变换的和式都不收敛，也就是说，周期序列不是绝对可
和的，所以不能用z变换表示。
但是，和连续时间周期信号一样，周期序列可以用离散傅里叶级数来表示，也就是用周期为N的复指数序列来表示。
2. 周期序列的离散傅里叶级数变换对
（1） 数学推导（略，参见教材P98~99） （2） 结论
x(n)与其离散傅里叶级数的系数X(k)组成一个变换对，且通过推导可见，周期序列~
~
~
X(k)也是一个周期为N的周期序列。
一般，采用符号
2πN
2πknN
WN=e
-j
，W
knN
=e
-j
则周期序列的离散傅里叶级数变换公式为：
N-1
~kn~正变换 X(k)=DFS[x(n)]=∑~ x(n)WN
n=0
1N-1~~-kn~反变换 x(n)=IDFS[X(k)]= X(k)W∑N
Nk=0
kn
3. WN的性质
（1） 周期性
kn(k+N)nk(n+N)
WN=WN=WN
（2） 对称性
-knkn*(N-k)nk(N-n)
WN=(WN)=WN=WN
（3） 正交性（重点强调）
⎧1，1N-1kn
W=δ(k-mN)=⎨∑N
Nn=0⎩0，
二、 DFS的性质
k=mN，m为任意整数
k为其他值
x(n)和~y(n)均是周期为N的周期序列，且有 设~
~~
X(k)=DFS[~x(n)]，Y(k)=DFS[~y(n)]
1. 线性性质
~~DFS[a~x(n)+b~y(n)]=aX(k)+bY(k)
2. 移位性质
-mk~DFS[~x(n+m)]=WNX(k) （时移）
~nl~DFS[WNx(n)]=X(k+l) （频移，又称调制特性）
3. 周期卷积
（1） 时域卷积
N-1
~△~~*x(n)=若f(n)=y(n)○x(m)~y(n-m)∑~
m=0
换元
令n-m=km=0
~~y(m)x(n-m)，则 ∑=
N-1
~~~~
F(k)=DFS[f(n)]=X(k)⋅Y(k)
1注意：此处的卷积为周期卷积。它和前面所介绍的非周期序列的线性卷积的区别在于：○．参．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
与周期卷积运算的两个序列都是周期为结果仍是一个以．．．．．．．．．．．．．．．．．N．的周期序列，则其卷积．．．．．．．．．．．．．．．．．N．为周期．．．
2的周期序列；○m=0~N-1）的范围内进行。 ．求和运算只在一个周期（．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．周期卷积的运算过程（参见图3.2.2）：
运算在m=0~N-1区间内进行，先计算出n=0，1，„，N-1的卷积结果，然后将所得的结果进行周期延拓，即可得到所求的整个周期序列。
注意：计算过程中，一个周期的某一序列值移出计算区间时，相邻的一个周期的同一位置．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．的序列值就移入计算区间。 ．．．．．．．．．．．．
（2） 频域卷积
由于DFS和IDFS的对称性，同样可以证明：时域周期序列的乘积对应频域周期序列的周期卷积，即：
若f(n)=~x(n)~y(n)，则
~
1N-1~~~~~
*Y(K)=F(k)=X(K)○∑X(l)Y(k-l)
Nl=01
=
N
∑Y(l)X(k-l)
l=0
N-1
~~
3.3 离散傅里叶变换（DFT）
一、 DFT的定义
1. 有限长序列和周期序列的关系
x(n)之间的关系可表示为 有限长序列x(n)和周期序列~
x(n)，0≤n≤N-1⎧~
x(n)=⎨
0，其他n⎩
x(n)的第一个周期（n=0~N-1）定义为“主值区间”x(n)通常，我们将周期序列~，故x(n)是~
的“主值序列”，且上述关系式可简写为
⎛对有限长序列进行⎫周期~ x(n)=x((n))N 延拓，可得到周期⎪⎪序
列⎝⎭
式中，((n))N表示“n对N求余数”，或称“n对N取模值”；
利用长度为N的矩形序列符号RN(n)，即
⎧1，
RN(n)=⎨
⎩0，
则（3.3.1）式又可写成
0≤n≤N-1
其他n
⎛对周期序列进行截⎫取，~ x(n)=x(n)RN(n) 可得到有限长序列⎪⎪序⎝⎭列
同理，频域周期序列X(k)也可看成是对有限长序列X(k)的周期延拓，而有限长序列X(k)则可看成是周期序列X(k)的主值序列，即
~
~
~
X(k)=X((k))N
或X(k)=X(k)RN(k)
~
2. 有限长序列的离散傅里叶变换对
有限长序列的离散傅里叶变换公式为： 正变换 X(k)=DFT[x(n)]=
∑x(n)W
n=0
N-1
knN
，0≤k≤N-1
1N-1-kn
反变换 x(n)=IDFT[X(k)]=X(k)WN，∑Nk=0
二、 DFT的性质 1. 线性性质
设x1(n)和x2(n)均是长度为N的有限长序列，且有
0≤n≤N-1
X1(k)=DFT[x1(n)]，X2(k)=DFT[x2(n)]
则 DFT[ax1(n)+bx2(n)]=aX1(k)+bX2(k)
说明：
（1） 若x1(n)和x2(n)的长度均为N，则ax1(n)+bx2(n)的长度也为N；
（2） 若x1(n)和x2(n)的长度不等，设分别为N1和N2，则ax1(n)+bx2(n)的长度应为二者中的最大值，即N = max[N1, N2]；
例如，当N1
有限长序列x(n)左移m（m为正整数）位的循环移位定义为
xm(n)=x((n+m))NRN(n)
可见，上式的循环移位表示将序列x(n)周期延拓成周期序列~x(n)=x((n))N后，再左移m位并取其主值序列而得到的。注意：序列的循环移位始终限定在主值区间内进行。 ．．．．．．．．．．．．．．．．．．．．如图所示，有限长序列循环移位的过程中，在主值区间（n=0~N-1）内，当某序列值从区间的一端移出时，与它同值的序列值又从区间的另一端移入，因而，此过程可以看成是将序列x(n)按逆时针方向排列在一个N等分的圆周上，则序列循环左移m位就相当于将该序列在圆周上顺时针旋转m位。
（2） 时域移位特性
-mk
Xm(k)=DFT[xm(n)]=DFT[x((n+m))NRN(n)]=WNX(k)
（3） 频域移位特性
nl
IDFT[X((k+l))NRN(k)]=WNx(n)
3. 循环卷积（又称圆周卷积）
（1） 循环卷积的定义
长度均为N的有限长序列x(n)和h(n)的循环卷积定义为
Nh(n)=[x((n))○*h((n))]R(n) y(n)=x(n)○NNN
⎡N-1⎤
=⎢∑x(m)h((n-m))N⎥RN(n)⎣m=0⎦⎡⎤
=⎢∑h(m)x((n-m))N⎥RN(n)⎣m=0⎦
N-1
（3.3.5）
可见，循环卷积就是周期卷积在主值区间（n=0~N-1）内的值
（2） 循环卷积的运算方法
1利用求和定义式（3.3.5）直接求解； ○
2利用与周期卷积的关系求解； ○
3根据循环卷积的特点，利用图解法求解，其步骤如下： ○
I. 将序列x(n)按逆时针方向均匀地（N等分）分布在一个圆周（内圆）上，而将序
列h(n)按顺时针方向均匀地（N等分）分布在另一个圆周（外圆）上，如图（a）所示；
II. 求两个圆上相应序列的乘积，并叠加N项乘积作为n=0时循环卷积值y(0)； III. 若求n=1时循环卷积值y(1)，则将外圆h(n)固定，把内圆上的序列x(n)顺时针旋
转一个单位（或将内圆x(n)固定，把外圆上的序列h(n)逆时针旋转一个单位，即内、外圆相对旋转一个单位），并将对应项的乘积叠加，即为所求的y(1) 值，如图（b）所示；
IV. 类似地，依次取n=2~N-1，重复步骤Ⅲ，直到将内圆序列循环移位一周，便可以
求得所有的y(n)值；
（3） 时域和频域循环卷积定理
I. 时域循环卷积定理
Nh(n)，则Y(k)=X(k)H(k) 若y(n)=x(n)○
这表明：两序列循环卷积的离散傅里叶变换等于其傅里叶变换的乘积。
II. 频域循环卷积定理
若y(n)=x(n)h(n)，则Y(k)=
1
NH(k) X(k)○
N
这表明：两序列乘积的离散傅里叶变换等于其傅里叶变换的循环卷积乘以1/N。 （4） 循环卷积、周期卷积和线性卷积的关系
1利用周期卷积计算循环卷积 ○
先计算两序列的周期卷积（列表法，参见例3.2.3），再对卷积结果取其主值区间（n=0~N-1）内的值即可。
2利用循环卷积计算线性卷积 ○
I. 用循环卷积代替线性卷积的条件
设两个有限长序列x(n)、h(n)的点数分别为N和M，其循环卷积的长度为L，则要用循环卷积代替线性卷积的条件是：循环卷积的长度必须不小于线性卷积的长度+M-1，．．．．．．．．．．．．．．．．．．．．．．．L．．．．．．．．．．．．．N．．．．．
即
L≥N+M-1
否则，在循环卷积周期延拓时会产生混叠。
II. 用循环卷积实现线性卷积的具体步骤
i) 根据上述条件，取L=N+M-1，分别将序列x(n)、h(n)补零扩展为L点序列，即
⎧x(n)，0≤n≤N-1⎧h(n)，0≤n≤M-1
，h(n)=⎨ x(n)=⎨
0，N≤n≤L-10，M≤n≤L-1⎩⎩
ii) 分别计算序列x(n)、h(n)的L点离散傅里叶变换，即
X(k)=DFT[x(n)]，H(k)=DFT[h(n)]
iii) 利用时域循环卷积定理计算序列x(n)、h(n)的L点循环卷积，且它就等于其线
性卷积，即
Lh(n)=IDFT[X(k)H(k)] y(n)=x(n)*h(n)=x(n)○
4. Parseval（帕塞瓦）定理
N-1
*
1N-1
x(n)y(n)=∑X(k)Y*(k) ∑Nk=0n=0
证： 由DFT的逆变换和正变换的定义，可得
⎡1N-1-kn⎤x(n)y(n)=x(n)Y(k)W∑∑N⎥⎢N∑n=0n=0⎣k=0⎦
1N-1*N-1kn=∑Y(k)∑x(n)WN Nk=0n=0
*
N-1N-1
*
1=N
如果令y(n) = x(n)，则上式变为
N-1
∑Y
k=0
N-1
*
(k)X(k)
1N-1
x(n)x(n)=∑X(k)X*(k) ∑Nk=0n=0
*
即
1N-12
x(n)=X(k)∑∑Nn=0k=0
2
N-1
这表明：序列在时域的能量与在频域的能量是相等的。
三、 DFT与DTFT及Z变换的关系
1. Z变换与DTFT的关系
DTFT与Z变换之间存在关系
DTFT[x(n)]=X(ejω)=X(z)z=ejω
即：若Z变换的收敛域包含单位圆，则序列的DTFT也就是单位圆上的Z变换。 2. Z变换与DFT的关系
有限长序列x(n)的DFT为
kn
X(k)=∑x(n)WN，k=0，1， ，N-1
n=0N-1
其Z变换为
X(z)=
对照上述公式，可知
n=-∞
∑x(n)z
∞
-n
X(k)=X(z)z=W-k=X(z)z=ej2Nπk，k=0，1， ，N-1
N
这表明：序列的DFT也就是其Z变换在单位圆上的等间隔采样，其角度间隔为ω=2π/N，
即将单位圆N等分，各序列的DFT值均匀分布在单位圆上。 3. DTFT与DFT的关系
ω
由于Z变换在单位圆上的取值就等于序列的傅里叶变换 X(ej)，则
X(k)=X(z)
2πjkz=eN
=X(e
j
2πkN
)
ω=
2πkN
=X(e)
jω
，k=0，1， ，N-1
这表明：序列的DFT也就是其DTFT的等间距采样，其采样间距为ω=2π/N。
序列的Z变换、DFT以及DTFT 的关系如图所示（P68图3.2.5）。
四、 频域采样
频域采样定理： ．．．．．．．
对于长度为频域采样不失真的条件是：频域采样点数N．．．．．M．的有限长序列，．．．．．．．．．．．．．．．．．．．．．．．．．．不小于序列．．．．．长度，即 ．．M．．．
N≥M
五、 DFT在实际应用中的问题 1. 混叠失真现象 2. 栅栏效应
因为DFT计算信号频谱，只给出了基频整数倍处的离散谱，而不是连续频谱，这就象通过一个“栅栏”观看景象一样，只能在离散点上看到真实景象，这种现象称为“栅栏效应”。 ．．．．减小栅栏效应的一个方法就是要使频域采样更密，即增加频域采样点数，这样必然使各谱线间的距离更近，从而使原来被“栅栏”挡住的频谱分量显露出来，为此，我们可以在不改变原有数据记录的基础上，采用在时域数据的末尾补零的方法来实现。补零的好处在于：．．．．．．．○1使频域采样更密，减小栅栏效应；○2使采样点数的整数次幂，便于利用计算机．．．．．．．．．．．．．．．．．．．．．．N．变为．．2．．．．．．．．．．．．．．实现快速傅里叶变换（FFT）。（P209） ．．．．．．．．．．．．．．．．．．．．．3. 频谱泄漏
在进行谱分析时，通常需要用矩形窗将长序列信号截取成若干段有限长序列信号，这种过程相当于原序列与矩形窗函数相乘，而时域相乘则对应于频域中的原序列频谱与矩形窗函数频谱的卷积过程，从而造成卷积后的频谱拓宽，即：在频谱图中的主瓣以外，又出现了多个旁瓣，这种失真现象就称为“频谱泄漏”现象。 ．．．．
为了减少泄漏带来的影响，截取信号时应根据具体情况，选择合适的窗函数，如哈明窗．．．．．．．．或汉宁窗等。那么，窗函数的选择依据如下： 1. 窗函数的评价指标（P207~208）
（1） 最大旁瓣用最大旁瓣值与主瓣峰值之比的对数来表示，即20lg(A旁max/A峰)； （2） 旁瓣衰减率以10个相邻旁瓣峰值的衰减比的对数来表示，即20lg(A旁10/A旁1)；
⎡G读⎤
-1⎥⨯100%； （3） 主瓣峰值可能最大误差ε=⎢G⎣峰⎦
（4） 主瓣宽
主瓣的宽窄对频率分辨率有影响，若主瓣宽越窄，则分辨率越高。 2. 窗函数的长度
窗的长度越长，其分辨率越高。 3. 窗函数的位置
对于周期信号尽量保证整周期采样。
3.4 快速傅里叶变换（FFT）
1965年，库利（J.W.Cooley）和图基（J.W.Tukey）在《计算数学》杂志上发表了著名的“机器计算傅里叶级数的一种算法”的文章，提出了DFT的一种快速算法。 一、 直接计算DFT的问题及改进途径
N点有限长序列x(n)的离散傅里叶变换公式为：
正变换 X(k)=DFT[x(n)]=
∑x(n)W
n=0
N-1
knN
，k=0，1， ，N-1
1N-1-kn
反变换 x(n)=IDFT[X(k)]=X(k)WN，n=0，1， ，N-1 ∑Nk=0
实现整个DFT运算需要进行N 2次复数乘法和N(N-1)次复数加法。由此可见，直接计算DFT时，其乘法次数和加法次数都与N 2成正比。
kn
解决途径：利用系数WN所固有的周期性、对称性等特性，可以将长序列的DFT分解．．．．．
为短序列的DFT，这样就可以大大减少DFT的运算量。正是基于这种基本思路而形成了快速傅里叶变换算法（Fast Fourier Transform，缩写为FFT），这种算法基本上可分为两大类：按时间抽取法（Decimation-In-Time，缩写为DIT）和按频率抽取法（Decimation-In-Frequency，缩写为DIF）。
注意：快速傅里叶变换（FFT）并不是一种新的变换，而是离散傅里叶变换（DFT）的一种．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．快速算法。 ．．．．．
二、 按时间抽取（DIT）的基-2FFT算法（库利-图基算法） 1. 算法的原理
先假设序列x(n)的长度N=2M（M为整数）。如果不满足这个条件，可以人为地在序列末尾补上若干个零值点，使其达到这一要求。这种N为2的整数幂的FFT也称基-2FFT。
将长度为N=2M的序列按n的奇偶分为两组，则通过公式推导可知，一个N点DFT可分解成两个N/2点DFT。
如果采用蝶形信号流图来表示上述分解过程，则该分解过程为
由于N=2M，则N/2仍是偶数。因此，若进一步将每个N/2点子序列再按奇偶部分分解
k2k
成两个N/4点的子序列，且将系数统一为WN/2=WN，则一个N=8点DFT就可以分解为
四个N/4=2点DFT（无需再分解），如图所示。
由此可见，这种方法的每一步分解都是按输入序列在时间上的奇偶次序来分解为两个更短的子序列，所以称为“时间抽取算法”。
上述N=8点时间抽取法FFT的流图如下所示。
2. 运算量
由上图可见，当N=2M时，共有M级（列）蝶形，每级都由N/2个蝶形运算组成，而每个蝶形运算都需要一次复数乘法和两次复数加法，因此每级运算都需N/2次复乘和N次复加，这样M级运算总共需要
复乘次数 mF=
NN
M=log2N 22
复加次数 aF=NM=Nlog2N
以乘法为例，由FFT算法、直接DFT算法的运算量与点数N的关系曲线图（P90图3.4.5）
可以直观地看出FFT算法的优越性，尤其是当点数N越大时，FFT的优点更突出，如图所示。
3. 算法的特点
由上面介绍的N=8点时间抽取法FFT流图，我们可以总结出N=2M点的时间抽取法的运算规律和特点。 （1） 蝶形运算
由8点FFT流图可见，FFT运算中的每一级（列）计算都是由N/2个蝶形运算组成，而N=2M时，共有M级（列）蝶形，因此N运算共需要/2·M个蝶形运算来完成。．点．FFT．．．．．．．．N．．．．．．．．．．．．其中，每个蝶形结构完成如下基本的迭代运算：
r
Xm(k)=Xm-1(k)+Xm-1(j)WN
Xm(j)=Xm-1(k)-Xm-1(j)W
rN
（3.4.8）
式中，m表示第m级（列）迭代，k，j为数据所在行数。其一般形式如图所示，它包括一
次复乘和两次复加。
在8点FFT流图中，第一级（列）每个蝶形的两节点间距为1=2，第二级每个蝶形的
M．两节点间距为2=21，第三级每个蝶形的两节点间距为4=22，由此类推得，对于N=2．．．．．点．FFT．．．
m-1．．．运算，其第m级每个蝶形的两节点间距为2．．．．．．．．．．．．．．．．．．．。
r
另外，由推导可得，每一级（列）不同的WN因子分布情况为：
第1级，W2r，r=0第2级，W4r，r=0,1第3级，W8r，r=0,1,2,3
(1种)(2种)(3种) (N/2种)
r
第M级，WN，r=0,1, ,N/2-1
r
因此我们不难总结出WN因子分布的一般规律为： ．．．．．．．．．．
rN/2
第m级，W2rm=WN，r=0,1, ,2m-1-1(2m-1种)
m
（2） 同址运算
在计算机编程时，将蝶形的两个输出值仍放回到两个输入所在的存储器中，这种运算就称为“同址运算”。 ．．．．（3） 倒位序规律及实现
I. 倒位序的规律
这种顺序看似混乱无序，但实际上是有规律的，我们将其称为“倒位序”。 ．．．
倒位序的原因是输入(n)按时域变量的奇偶不断进行分组而造成的。 ．．．．．．．．．x．．．．．．．．．n．．．．．．．．．．．．．．．
II. 倒位序的实现
一般在实际运算中，我们总是先按自然顺序将输入序列存入存储单元中，再通过变址运算来实现倒位序的排列。其具体方法如下：
如果输入序列x(n)的序号n用二进制数（例如n2 n1 n0）表示，则其倒位序二进制数n就是（n0 n1 n2
^
^
由此可知，只要在原来存放自然顺序序列x(n)的单元中，存入倒位序序列x(n)，即可实现倒位序的排列。这个变址过程如图所示。
由图可见，当n=n时，不必调换；只有当n≠n时，才需要将原来存放x(n)和x(n)的存储单元中的内容互换。为了节省调换时间，避免重复调换（保证只调换一次，否则又回到原状），我们只需检查n和n的相对大小，若n>n，则表明此x(n)在前面已经和x(n)调换过了，不必再
^
^
^
^
^
^
调换；否则，就必须进行互换。
综上所述，实现倒位序排列的具体方法为：若≥n时，不必调换；若
三、 按频率抽取（DIF）的基-2FFT算法（桑德-图基算法）
前面讨论的FFT算法是将输入序列x(n)按时间变量n的奇偶分解为越来越短的序列。类似地，如果我们将输出序列X(k)按频域变量k的奇偶分解为越来越短的序列，这种FFT算法就称为“频域抽取法”。 四、 IDFT的快速算法（IFFT）
利用FFT算法来计算IFFT的具体方法有以下两种： 1. 方法一
首先，比较IDFT公式
^
^
^
1N-1-kn
x(n)=IDFT[X(k)]=∑X(k)WN
Nk=0
和DFT 公式
kn X(k)=DFT[x(n)]=∑x(n)WN
n=0N-1
kn-kn
可见，只要将DFT运算中的每一个系数WN换成WN，最后再乘以常数1/N，则前面所介
绍的按时间或按频率抽取的FFT算法都可用来计算IDFT。
kn-kn
例如，我们可直接由8点频率抽取FFT流图出发，把WN换成WN，并在每级（列）MM．．
运算中都乘以1/2（注意：因为乘以1/N就等效于1/N =1/2=(1/2)．．．．．．．．．．．．．．．．．．．．．．．．，所以相当于每级都乘．．．．．．．．．．
以）
IFFT流图，如图所示。 ．1/2．．．
2. 方法二
首先，对IDFT公式取共轭，得
1
x(n)=
N
*
∑X
k=0
N-1
*
kn (k)WN
然后对上式两边再取共轭，得
1⎡N-1*1kn⎤**
x(n)=⎢∑X(k)WN={DFT[X(k)]}⎥N⎣k=0N⎦
由此可见，只要先将X(k)取共轭，就可以直接利用FFT运算，最后将运算结果再取共轭，
并乘以1/N，即可得到x(n)值。这样，FFT运算和IFFT运算可以共用一个子程序，便于编*
程实现。