快速傅里叶变换(FFT)

第三章快速傅里叶变换FFT:FastFourierTransform1965年，Cooley,Tukey《机器计算傅里叶级数的一种算法》学习目标理解按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点理解按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点理解IFFT算法了解混合基、分裂基和基-4FFT算法了解CZT算法理解线性卷积的FFT算法及分段卷积方法一、直接计算DFT的问题及改进途径运算量复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)FFT算法分类:时间抽选法

DIT:Decimation-In-Time频率抽选法

DIF:Decimation-In-Frequency二、按时间抽选的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。假设不满足，那么补零将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。那么x(n)的N 点DFT:再利用周期性求X(k)的后半局部分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计运算量减少了近一半N/2仍为偶数，进一步分解：N/2N/4同理：其中：这样逐级分解，直到2点DFT当N=8时，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1

2、运算量当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：比较DFT图直接计算DFT与FFT算法所需乘法次数的比较3、算法特点1〕原位计算m表示第m级迭代，k，j表示数据所在的行数2〕倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n2000110110011013〕蝶形运算对N=2L点FFT，输入倒位序，输出自然序，第m级运算每个蝶形的两节点距离为2m–1第m级运算：蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移L–

m位，把右边空出的位置补零，结果为r的二进制数。

4〕存储单元输入序列x(n):N个存储单元系数：N/2个存储单元4、DIT算法的其他形式流图输入倒位序输出自然序输入自然序输出倒位序输入输出均自然序相同几何形状输入倒位序输出自然序输入自然序输出倒位序

三、按频率抽选的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：按k的奇偶将X(k)分成两局部：令那么X(2r)和X(2r+1)分别是x1(n)和x2(n)的N/2点DFT，记为X1(k)和X2(k)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2点DFTN/2点DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)N/2仍为偶数，进一步分解：N/2N/4x3(0)x3(1)-1-1x4(0)x4(1)N/4点DFTN/4点DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)同理：其中：逐级分解，直到2点DFT当N=8时，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,12、算法特点1〕原位计算-1L级蝶形运算，每级N/2个蝶形，每个蝶形结构：

m表示第m级迭代，k，j表示数据所在的行数2〕蝶形运算对N=2L点FFT，输入自然序，输出倒位序，两节点距离：2L-m=N/2m第m级运算：蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移m-1位，把右边空出的位置补零，结果为r的二进制数。3、DIT与DIF的异同根本蝶形不同DIT:先复乘后加减DIF:先减后复乘运算量相同都可原位运算DIT和DIF的根本蝶形互为转置四、线性调频z变换〔CZT)算法FFT不适用于：只研究信号的某一频段，要求对该频段抽样密集，提高分辨率；研究非单位圆上的抽样值；需要准确计算N点DFT，且N为大的素数；等等。CZT算法：对z变换采用螺线抽样，chirp-z变换 线性调频z变换1、算法原理

N点有限长序列，其z变换：沿z平面上的一段螺线作等分角抽样，抽样点zk：其中：M为要分析的复频谱点数则抽样点：：起始抽样点的矢量半径长度：起始抽样点的相角：相邻抽样点的角度差：逆时针：顺时针：螺线的伸展率W0>1：螺线内缩W0<1：螺线外伸当W0=1，那么表示半径为A0的一段圆弧假设又有A0=1，那么表示单位圆上的一段圆弧若又有，M=N，即为序列的DFT。

求抽样点处的z变换：NM次复乘(N-1)M次复加2、CZT的实现步骤及运算量的估算1)选择，且2)形成L点序列g(n)：(3N)求其L点FFT：(L/2*log2L)

3〕形成L点序列h(n):求其L点FFT:(L/2*log2L)(2N)4〕求乘积(M)(L)5〕求L点IFFT的q(k)(L/2*log2L)6〕求得抽样点的z变换:总运算量:3、CZT算法的优点N，M可为任意数，可不等当，，时，CZT=DFT，解决了N为素数的快速算法问题z0任意，从任意频率开始，便于窄带高分辨率分析周线可以是螺线，而不一定是圆弧任意，易调整频率分辨率五、利用DFT(FFT)对模拟信号作频谱分析信号的频谱分析：计算信号的傅里叶变换1、频率响应的混叠失真及参数的选择同时提高信号最高频率和频率分辨率，需增加采样点数N。信号最高频率与频率分