文档介绍：第4章快速傅里叶变换(FFT)
引言
基2FFT算法
进一步减少运算量的措施
§ 引言
FFT: Fast Fourier Transform
1965年,Cooley-Turky 发表文章《机器计算傅里叶级数的一种算法》,提出FFT算法,解决DFT运算量太大,在实际使用中受限制的问题。
FFT的应用
频谱分析、滤波器实现、实时信号处理等。
DSP芯片实现
TI公司的TMS 320c30,10MHz时钟,基2-FFT1024点
FFT时间15ms。
基2FFT算法
一般情况下,x(n)为复数序列,对某一个k值,直接按()式计算一个系数X(k)值需要:
复数乘法:N次复数加法:(N-1)次
计算全部X(k)值需要: N2次 N(N-1)次
当N>>1时,N(N-1)N2 ;
随着N增大复乘、复加次数非线性增大。
()
直接计算DFT的特点及减少运算量的基本途径
一、直接计算DFT的运算量
长度为N的有限长序列x(n)的DFT为:
二、减少运算量的基本途径
在DFT定义式中只有两种运算:x(n)与WmN的乘和加, WmN的特性对运算量必有影响。
(1)根据旋转因子WmN的周期性、对称性和特殊值减少乘法运算次数。
WmN的可约性为:
WmN的对称性表现为:
WmN的周期性表现为:
()
或者
()
WmN的特殊值为:
(2)把N点DFT分解为几个较短DFT的组合,可使乘法次数大大减少。
FFT算法就是不断地把长序列的DFT分解成几个短序列的DFT,并利用旋转因子的周期性和对称性来减少DFT的运算次数。
因为,DFT的运算次数 N2
若序列长度N,则运算次数。
最常用的算法是基2-FFT(N=2M)。
时域抽取法(DIT)基2-FFT基本原理
根据减少运算量的途径,巧妙地在时域或频域进行不同的抽取分解与组合,可得到不同的快速算法。
FFT算法基本上分为两大类:
时域抽取法FFT (Decimation In Time-FFT,DIT-FFT)
频域抽取法FFT (Decimation In Frequency-FFT,DIF-FFT)
我们介绍基2DIT-FFT算法。
所谓基2是序列x(n)的长度N满足:
为自然数
(1)算法思想:进行时域 M 级奇偶抽取,并利用:
将N点DFT变成 M 级蝶形运算。
(2)特点:运算流程图结构规则,可原位计算,程序简单。
设序列x(n)的长度为N,且满足:
为自然数
按n的奇偶把x(n)分解为两个N/2点的子序列:
则x(n)的DFT为:
所以
由于
其中X1(k)和X2(k)分别为x1(r)和x2(r)的 N/2 点DFT
k=0,1,…,N-1
由于X1(k)和X2(k)均以N/2为周期,则由复指数序列的周期性可得:
虽然k=0,1,…,N-1,但从此式只能方便地得到N/2个DFT系数,那么,还有N/2个DFT系数如何方便地得到呢?
所以:
另外由旋转因子WmN的对称性:
()
()
这样将N点DFT分解为两个N/2点的DFT运算,用如图所示的流图符号(蝶形)表示。
要完成一个蝶形运算,
需一次复数乘和两次复数加法运算。
仅经过一次分解,就使
运算量减少近一半:
N2(N2 /4)+ (N2 /4) +N/2
N点DFT的一次时域抽取分解图(N=8)