快速傅立叶变换（FFT）VIP

引言四种不同傅立叶变换对傅里叶级数(FS)：连续时间,离散频率的傅里叶变换。连续傅里叶变换(FT)：连续时间,连续频率的傅里叶变换。序列的傅里叶变换(DTFT):离散时间,连续频率的傅里叶变换.离散傅里叶变换(DFT):离散时间,离散频率的傅里叶变换傅立叶变换离散时间傅立叶变换傅立叶级数离散傅立叶变换时间

连续离散连续离散非周期周期非周期周期

频率1.连续傅里叶变换(FT)非周期连续时间信号通过连续付里叶变换(FT)得到非周期连续频谱密度函数。例子这以下变换对可以看出时域连续函数造成频域是非周期的谱,而是时域的非周期造成频域是连续的谱.2.傅里叶级数(FS)周期连续时间信号非周期离散频谱密度函数。周期为Tp的周期性连续时间函数x(t)可展成傅里叶级数X(jkΩ0),是离散非周期性频谱,表示为:FS例子通过以下变换对可以看出时域的连续函数造成频域是非周期的频谱函数,而频域的离散频谱就与时域的周期时间函数对应.(频域采样，时域周期延拓)3.序列的傅里叶变换(DTFT)非周期离散的时间信号(经过单位园上的Z变换(DTFT))得到周期性连续的频率函数。例子同样可看出,时域的离散造成频域的周期延拓

,而时域的非周期对应于频域的连续

.4.离散傅里叶变换(DFT)上面讨论的三种傅里叶变换对,都不适用在计算机上运算,因为至少在一个域(时域或频域)中,函数是连续的.因为从数字计算角度,我们感兴趣的是时域及频域都是离散的情况,这就是我们这里要谈到的离散傅里叶变换.周期性离散时间信号从上可以推断：周期性时间信号可以产生频谱是离散的离散时间信号可以产生频谱是周期性的。得出其频谱为周期性离散的。也即我们所希望的。二、四种付里叶变换形式的归纳DFS和DFT的导出出发点：如何利用离散频谱表示离散时间信号以便用于计算机进行数字信号处理计算机处理的基本要求：离散值(序列)有限长(存储容量有限)DFT的变换总之，一个域的离散必然造成另一个域的周期延拓。数字计算机N足够大计算机处理信号的流程

模拟信号的频谱分析1.1离散傅立叶变换的定义1.1.1DFT的定义设x（n)是一个长度为M的有限长序列，则定义的N点离散傅立叶变换为其逆变换为：式中N为DFT变换区间长度。用DFT对信号进行谱分析

1．DFT是连续傅里叶变换的近似

分析连续时间信号的频谱,即求其傅里叶变换：

借助计算机分析其频谱时，需要在时域和频域离散化，即对的采样序列求DFT

，这时，求出的X(k)是否能代表原信号的频谱？精度如何保证？N点DFT时域频域（1）采样（离散化）→周期化（2）截取（有限长）↓

↓

→波皱↓

采样←↓

（3）周期化可见，DFT是对连续傅里叶变换的近似，误差主要由采样引起的频谱混叠及信号截取引起的频谱波皱所造成。（1）时域采样间隔(T)应足够小；（2）频域采样间隔(F)应足够小；（3）截取长度(T0)应足够大。∴DFT的点数应足够大。或采取加权技术以提高近似程度。为提高近似精度：1.1.2计算机处理DFT的运算量

k=0,1,2,…,N–1计算机运算时：运算式中有复数因子：N项

N个

∴计算一个N点DFT，共需次复乘。以做一次复乘1μs计，若N=4096，所需时间为由于计算量大，且要求相当大的内存，难以实现实时处理，限制了DFT的应用。

长期以来，人们一直在寻求一种能提高DFT运算速度的方法。FFT便是Cooley&Tukey

在1965年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。1.1.3FFT算法的设计思想

1．利用的特点∴具有

1）周期性2）共轭性3）对称性4）5）2．把N点DFT化为几组点数较少的DFT运算N点DFT运算的复乘次数为次，若将N点DFT化为2组，则复乘次数约为次。1.2

基２FFT按时间抽取算法（Cooley-Tukey算法）1.2.1.算法的推导

设，将x(n)按n的奇偶分为两组：根据这组表达式，可画出X(k)与之间的运算关系流图。X(k)为N点DFT运算，而与为当时，可利用的周期性。这样，可以写出N点的关系式：X(k)与减少运算量化简蝶形运算流图经以上分解，各为、，即分次复乘，而将别进行了与合成为X(k)时，需进行次复乘：显然，这样的分解是有效的。由于,可继续照此办法分解，即将按r

的奇、偶各分为两组，于是，仿照X(k)，可写出如此分解下去,直到分解为两点,以N=8为例。∴复乘次数

1.2.2.序列的逆序排列

由于x(n)被反复地按奇、偶分组，所以流图输入端的的排列不再是顺序的，但仍有规律可循：对于任意n

可以用M个二进制码表示为：当n反复按奇、偶分解时，即按二进制码的“0”，“1”分解。n001n10101n201010101…01010101010101010101010101010101逆序（码位倒置）比较顺序BINDEC00010001011000110101111104261537BINDEC01234567000001010011100101110111运算前运算后1.2.3.同址运算对于算法流图中的任意一个蝶形运算。

1.2.4.FFT的运算量

∴可进行M次分解，即N点FFT可经过M次迭代运算得到，每次迭代中的蝶形运算为个,每个蝶形运算中有一次复乘，∴复乘次数

例如FFT：复乘次数DFT：复乘次数相差1260倍！

1.3基２ＦＦＴ按频率抽取算法（sande-Tukey算法）

频域抽取基－2FFT算法（DIF-FFT）算法的推导频域抽取算法是把时间序列前后对半分解为两个长为N/2点的序列，则：当k取偶数时（k=2r，r=0,1,...,N/2－1）∴的N点DFT按k的奇偶分组可分为两个N/2的DFT当k取奇数时（k=2r＋1，r=0,1,...,N/2－1）这一结论表明：求的N点DFT再次分解成

求两个N/2

点DFT

DIF-FFT的蝶式运算流图DIF-FFT的一次分解运算流图先蝶式运算，后DFT。例如：N=8时DIF-FFT1.3.1.算法的推导将x(n)按前后分为两组：1.3.2.流图的转置频域中的第l点与时域中的第r点的关系为频域中的第r点与时域中的第l点的关系为从流图中也可看到：流图转置：X(•)改写为x(•)，序号不变；x(•)改写为X(•)，序号不变；所有箭头反向，系数不变。DIT-FFTDIF-FFT时间抽取频率抽取1.3.3.两种蝶形运算流图的区别1.4FFT算法的软件实现(下页)（框图）1.4.1.算法的特点

1．基本算法为蝶形运算；

2．运算分为次迭代进行；3．运算可原址进行；

4．输入数据需进行逆序重排；

5．迭代过程中，基本蝶形运算的两个点之间的间距及系数的变化有规律可循。在第L

轮迭代中（1）有种蝶形运算系数（2）系数分别为

（3）每种系数对应的蝶形运算有个，相距点（4）参加同一蝶形运算的两个点之间的间距为点（返回）1.4.2.算法的程序框图开始逆序重排蝶形运算结束L=1,M输出J=0,B-1蝶形运算三层循环：N1为相同系数的蝶形运算的间距（N1=2L

）2）中间层为蝶形运算组次J（J=1，2，…，3）最内层为基本蝶形运算1）最外层为迭代轮次L（L=1，2，…，M）2E-E1-1）