按时间抽取的基2FFT算法分析文档格式.docx
《按时间抽取的基2FFT算法分析文档格式.docx》由会员分享，可在线阅读，更多相关《按时间抽取的基2FFT算法分析文档格式.docx（25页珍藏版）》请在冰点文库上搜索。
[x（0）
=[x（0）
x
（2）]W40[x
（1）x（3）W；
（周期性）
x
（2）]-[x
（1）x（3）]W40（对称性）
通过合并，使乘法次数由
4次减少到1次，运算量减少。
FFT的算法形式有很多种，但基本上可以分为两大类：
按时间抽取
（DIT）和按频率抽取（DIF）。
4.1按时间抽取（DIT）的
FTT
为了将大点数的DFT分解为小点数的
DFT运算，要求序列的长度N为
复合数，最常用的是N2M的情况（M
为正整数）。
该情况下的变换称为
基2FFT。
下面讨论基2情况的算法。
先将序列x（n）按奇偶项分解为两组
x（2r）Xi（r）
x（2r1）x2（r）
r0,1,,N1
2
将DFT运算也相应分为两组
X（k）DFT[x（n）]
N1
x（n）Wn
x（n）WNkn+
n为偶数
x（n）WNkn
n为奇数
N/21
x（2皿rk
r0
x（2r1）wN2r1）k
X1（r）wfk
WNkX2（r）wN^rk
X1（r）WNk/2
WNkX2（r）WNk/2（因为wN2rkWNrk/2）
Xi（k）WNX2（k）
其中Xi（k）、X2（k）分别是xi（n）、X2（n）的N/2点的
DFT
X1（k）=X1（r）wNk/2
x（2r）wN為,0
X2（k）=X2（r）WNrk/2
N/21
x（2r1）WNrk/2
0
至此，一个N点DFT被分解为两个
N/2点的DFT。
上面是否将全部N点的X（k）求解出来了?
分析：
Xi（k）和X2（k）只有N/2个点（k0,1,
k
X（k）X1（k）WNX2（k）只能求出X（k）的前N/2个点的DFT，要求出
全部N点的X（k），需要找出X1（k）>
X2（k）和X（kN/2）的关系，其
中k0,1,
岁1。
由式子X（k）Xi（k）W,X2（k）可得
X（k
N/2）Xi（kN/2）wNkN/2
X2（kN/2）化简得
N/2）=Xi（k）wNkX2（k）,
0,1,,-21
这样N点DFT可全部由下式确定出来:
X（k）Xi（k）WNkX2（k）
X（kN/2）X1（k）WNX2（k）
上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运
算。
WNb
WnId
通过这样的分解以后，每一个N/2点的
DFT只需要（N）2—次复数
24
N2N2乘法，两个N/2点的DFT需要2（—）——次复乘，再加上将两个N/2
22
点DFT合并成为N点DFT时有N/2次与W因子相乘，一共需要
NNN
—————次复乘。
可见，通过这样的分解，运算量节省了近一半。
222
因为N2M,N/2仍然是偶数，因此可以对两个N/2点的DFT再
分别作进一步的分解，将两个N/2点的DFT分解成两个N/4点的DFT。
例如对x1（r），可以在按其偶数部分及奇数部分进行分解:
0,1,，-1
4
xi（2l）X3（l）
xi（2l1）X4（l）
则的运算可相应分为两组:
N/41
X1（k）=X1（2l）wN2l/k2
l0
X1（2l1）wN2l21）k
N/41lk
X3（I）Wn/4
WNk/2
X4（I）Wn/4
X3（k）W,/2X4（k）
k0,1,
41
将系数统一为以N为周期，即W,/2
W点，可得
2k
X1（k）X3（k）WnX4（k）
X1（kN/4）X3（k）WnX4（k）
同样，对X2（k）也可进行类似的分解。
一直分解下去，最后是2点的
DFT,2点DFT的运算也可用碟形符号来表示。
这样，对于一个N2’8
的DFT运算，其按时间抽取的分解过程及完整流图如下图所示。
O»
令O
1^#^—J
卩伍RpXXXX
OQOOOOOb
D
点
FT
■T
DI
1
■C
1护
.^^1^/r^^1012345G7rLrLrLrLnrLrLrLxxxxxxxx
3用
o#
0^0
咗：
1用£
^-3再沪肘「聊一了严m-岂"
/八、
1/WOQOC0
爲二?
oftQoopo二
00e
*b_4卞十o粵o魯萌一更
--ft00
P同罔问⑴冋⑶PXXXXXXXX
XXXXX/e"
ee
这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数
还是奇数来抽取的，故称为“时间抽取法”。
分析上面的流图，N2M，—共要进行M次分解，构成了从x（n）至U
X（k）的M级运算过程。
每一级运算都是由N/2个蝶形运算构成，因此每
级运算都需要N/2次复乘和N次复加，则按时间抽取的M级运算后总共
需要
复数乘法次数：
mF—MNlog2N
F22
复数加法次数：
aFNMNlog2N
根据上面的流图，分析FFT算法的两个特点，它们对FFT的软硬件构成产生很大的影响。
（1）原位运算
也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。
根据运算流图
分析原位运算是如何进行的。
原位运算的结构可以节省存储单元，降低设备成本。
（2）变址分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”的顺序。
见图。
自然顺序
二进制表示
码位倒置
码位倒置顺序
000
1
001
100
010
011
110
6
5
101
7
111
X⑺
在实际运算中，直接将输入数据x（n）按码位倒置的顺序排好输入很不
方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序
的存储换成码位倒置顺序的存储，这样就可以进行
FFT的原位运算。
变质
的功能如图所示。
用软件实现是通用采用雷德（Rader）算法，算出I的倒
序J以后立即将输入数据X（I）和X（J）对换。
尽管变址运算所占运算量的比例
，也可设法用适当
很小，但对某些高要求的应用（尤其在实时信号处理中）
的电路结构直接实现变址。
例如单片数字信号处理器
TMS320C25就有专
用于FFT的二进制码变址模式。
4.2按频率抽取（DIF）的FTT
除时间抽取法外，另外一种普遍使用的FFT结构是频率抽取法。
频率
抽取法将输入序列不是按奇、偶分组，而是将N点
DFT写成前后两部分：
＋x（n）WNkn
nN/2
因为WNN/2
x（n）WNnk
[x（n）n0
1,WN（N/2）k
x（nn0
WN（N/2）kx（n
（1）k，k
N/2）WN（nN/2）k
N/2）]WNnk
为偶数时
（1）k
1，k为奇数时
X（k）DFT[x（n）]x（n）WNkn
（N/2）1x（n）WNknn0
（1）1，由此可将X（k）分解为偶数组和奇数组:
knk
（1）kx（nN/2）]WNnk
X（k）=[x（n）
x（n
nrN/2）]WNnr/2
N/21
X（2r）=[x（n）
[x（n）
x（nN/2）]WN2nr
x1（n）
x2（n）
X（2r
x（n）[x（n）
1）=[x（n）
[x（n）x（nn0
x（nN/2）]WN（2r1）n
N/2）]WNnWNnr/2
x（nN/2）
x（nN/2）]WNnn0,1,,N/2
这两个序列都是N/2点的序列，对应的是两个N/2点的
DFT运算：
N/21
X（2r）=人5）阿石；
X（2r1）=X2（n）wNn/2
这样，同样是将一个N点的DFT分解为两个
N/2点的DFT了。
频率抽选
法对应的碟形运算关系图如下:
对于N=8时频率抽取法的FFT流图如下:
b）WNn
啲m唧]flX[Z）沁]oX[4]^X[51^X[6）^X[7）
x[Oh
x[2k
X阪
X宙b
x[6I»
刈了b
MO）mx[1b刈2“XP]o诃xPIx[G]叩n
►0
4点
X（0]*0X|2]■oxM）”X问
xn1MXl3）*0X|51”xpi
x（01。
X[l]ex（£
]ox[3].
x[5]dx（G]cx[7]<
匹
2点
2占
帀严I才甲
一X161
才5
X[51
巴鼻X171
x|0）oxlDc釁罔口XP）OxMhx[5hX161c
X17）o,
■1
-1
心X|0]
0X（4）
。
X⑵
心X[6]
“X（1J
0X⑸
X（3]
0X|71
这种分组的办法由于每次都是按输出X（k）在频域的顺序上是属于偶数还是
奇数来分组的，称为频率抽取法。
与前面按时间抽取的方法相比，相同点
问题：
如何利用快速算法计算IDFT?
分析IDFT的公式:
x（n）IDFT[X（k）]+
Nk
X（k）WNnk,n
0,1,
N1
比较DFT的公式:
X（k）DFT[x（n）]x（n）WNnk,k0,1,
N
得知可用两种方法来实现IDFT的快速算法：
（1）只要把
运算中的每
nknkI
个系数Wn该为Wn，并且最后再乘以常数—，就可以用时间抽取法
N
或频率抽取的FFT算法来直接计算IDFT。
这种方法需要对
FFT的程序和参
数稍加改动才能实现。
（2
x（n）y^WNY卡DFT[X*（k）]},n0,1,
Nk0N
N1，也就
是说，可先将X（k）取共轭变换，即将X（k）的虚部乘以—1,
就可直接调用
FFT的程序，最后再对运算结果取一次共轭变换并乘以常数
1/N即可得到
x（n）的值。
这种方法中，FFT运算和IFFT
运算都可以共用一个子程序块,
在使用通用计算机或用硬件实现时比较方便。
4.1.3混合基FFT算法
以上讨论的是基2的FFT算法，即
N2M的情况，这种情况实际
上使用得最多，这种FFT运算，程序简单,
效率很高，用起来很方便。
另
外，在实际应用时，有限长序列的长度N
到底是多少在很大程度时是由人
为因素确定的，因此，大多数场合人们可以将
N选定为N2m，从而可
以直接调用以2为基数的FFT运算程序。
如果长度N不能认为确定，而N的数值又不是以2为基数的整数次
方，一般可有以下两种处理方法:
将x（n）用补零的方法延长，使N增长到最邻近的一个
N2M数值。
例如，N=30，可以在序列x（n）中补进x（30）=
x（31）=0两个零值点，使N=32。
如果计算FFT的目的是为了
了解整个频谱，而不是特定频率点，则此法可行。
因为有限长序列补零以后并不影响其频谱X（ejw），只是频谱的采样点数增
加而已。
2）如果要求特定频率点的频谱，则N不能改变。
如果N为复合
数，则可以用以任意数为基数的FFT算法来计算。
快速傅里叶变换的
基本思想就是要将DFT的运算尽量分小。
例如，N=6时，可以按照
N=3X2分解，将6点DFT分解为3组2点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）x（m）h（nm）
m
x（n）
若通过
有限长序列x（n）与h（n）的卷积的结果y（n）也是一个有限长序列。
假设
与h（n）的长度分别为N1和N2，贝Uy（n）的长度为N=N1+N2-1。
补零使x（n）与h（n）都加长到N点，就可以用圆周卷积来计算线性卷积。
样得到用FFT运算来求y（n）值（快速卷积）的步骤如下:
（1）对序列x（n）与h（n）补零至长为N,使N>
N1+N2-1
N2M（M为整数），即
x（n）,n0,1,,N11
x（n）0,nN1,N11,,N1
h（n）h（n）,n0,1,,N21
0,nN2,N21,,N1
（2）用FFT计算x（n）与h（n）的离散傅里叶变换
x（n）（FFT）X（k）
N点）
h（n）（FFT）H（k）
（3）计算Y（k）=X（k）H（k）
（4）用IFFT计算Y（k）的离散傅里叶反变换得:
y（n）=IFFT[Y（k）]
应用于连
4.2.2利用FFT求相关—快速相关
互相关及自相关的运算已广泛的应用于信号分析与统计分析，续时间系统也用于离散事件系统。
用FFT计算相关函数称为快速相关，它与快速卷积完全类似，不同的
是一个应用离散相关定理，
另一个应用离散卷积定理。
同样都要注意到离散
傅里叶变换固有的周期性，
也同样用补零的方法来绕过这个障碍。
设两个离散时间信号
x（n）与y（n）为已知，离散互相关函数记作Rxy（n）,
定义为
Rxy（n）
x（m）y（nm）
如果x（n）与y（n）的序列长度分别为N1和N2，则用FFT求相关的计算步骤
如下：
（1）对序列x（n）与y（n）补零至长为
N，
使N>
N1+N2-1,并且
N2m（M为整数），即
x（n）,n
0,n
0,1,,N1
N1,N11,
y（n）
y（n）,n
0,1,,N2
N2,N21,
（2）用FFT计算
x（n）与y（n）的离散傅里叶变换
y（n）（FFT）Y（k）
（3）将X（k）的虚部lm[X（k）]改变符号,
求得其共轭X*（k）
（4）计算Rxy（k）=X*（k）Y（k）
（5）用IFFT求得相关序列Rxy（n）
Rxy（n）=IFFT[Rxy（k）]
如果x（n）=y（n），则求得的是自相关序列Rxx（n）
4.2.3Chirp－Z变换
采用FFT算法可以很快的计算出全部DFT值，也即Z变换在单位圆
上的全部等间隔采样值。
但是，很多场合下，并非整个单位圆上的频谱都是很有意义的，例如对于窄带信号过程，往往只需要对信号所在的一段频带进行分析，这是，希望采样能密集在这段频带内，而对频带以外的部分，则可以完全不管。
另外，有时也希望采样能不局限于单位圆上，例如，语音信号处理中，往往需要知道其Z变换的极点所在频率，如果极点位置离单位圆较远，，则其单位圆上的频谱就很平滑，如图所示，这是很难从中识别出极点所在的频率。
要是采样不是沿单位圆而是沿一条接近这些极点的弧线进
从而可以较准确
FFT来快
行，则所得的结果将会在极点所在频率上出现明显的尖峰，的测定极点频率。
螺线采样就是一种适用于这种需要的变换，并且可以采用
速计算，这种变换也称为Chirp-Z变换，它是沿Z平面上的一段螺线作等分角的采样，这些采样点可表达为
zkAWk,k0,1,,M1
其中M为采样点的总数，A为起始点位置，这个位置可以进一步用它的半径Ao及相角0来表示
AA0ej0
参数W可表示为
WW0ej0
其中Wo为螺线的伸展率，W0>
1时螺线内缩（反时针方向）;
W0<
1时螺
线外伸。
0为螺线上采样点之间的等分角。
螺线采样点在Z平面上的分布可表示为下图。
面分析这些点上采样值计算的特点。
假定x（n）是长度为N的有限
长信号序列，则其Z变换在采样点上的值为
升级会员 