《快速傅里叶变换(FFT)第四章》课件.ppt

《《快速傅里叶变换(FFT)第四章》课件.ppt》由会员分享，可在线阅读，更多相关《《快速傅里叶变换(FFT)第四章》课件.ppt（58页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、本章主要内容本章主要内容理解按时间抽选的基理解按时间抽选的基2FFT2FFT算法原理、运算流图、算法原理、运算流图、所需计算量和算法特点；所需计算量和算法特点；理解按频率抽选的基理解按频率抽选的基2FFT2FFT算法原理、运算流图、算法原理、运算流图、所需计算量和算法特点；所需计算量和算法特点；理解理解I IFFTFFT算法；算法；了解混合基、分裂基和基了解混合基、分裂基和基4FFT4FFT算法；算法；理解用理解用DFTDFT的快速算法对信号进行频谱分析的快速算法对信号进行频谱分析第第4 4章章 离散离散傅里叶变换傅里叶变换的计算与应用的计算与应用DFT是是信信号号分分析析与与处处理理中中的的

2、一一种种重重要要变变换换。但但直直接接计计算算DFT的的计计算算量量与与变变换换区区间间长长度度N的的平平方方成成正正比比，当当N较较大大时时，计计算算量量太太大大，直直接接用用DFT算算法法进进行行谱谱分分析和信号的实时处理是不切实际的。析和信号的实时处理是不切实际的。1965年年发发现现了了DFT的的一一种种快快速速算算法法，使使DFT的的运运算算效效率率提提高高12个个数数量量级级，为为数数字字信信号号处处理理技技术术应应用用于于各各种种信信号号的的实实时时处处理理创创造造了了条条件件，推推动动了了数数字字处处理技术的发展。理技术的发展。1984年年，提提出出了了分分裂裂基基快快速速算算

3、法法，使使运运算算效效率率进进一一步提高；步提高；4.1 离散傅里叶变换的高效计算思路离散傅里叶变换的高效计算思路4.1 4.1 离散傅里叶变换的高效计算思路离散傅里叶变换的高效计算思路 直接计算直接计算DFT的运算量的运算量长度为长度为N的有限长序列的有限长序列x(n)的的DFT为：为：考虑考虑x(n)为复数序列的一般情况，对某一个为复数序列的一般情况，对某一个k值，直接按上式计算值，直接按上式计算X(k)值需要值需要N次复数次复数乘法乘法、(N-1)次复数加法次复数加法。4.1 4.1 离散傅里叶变换的高效计算思路离散傅里叶变换的高效计算思路4.1 4.1 离散傅里叶变换的高效计算思路离散

4、傅里叶变换的高效计算思路例例N=1024，N2=1,048,5762 2、减少运算量的思路和方法、减少运算量的思路和方法思思路路：N N点点DFTDFT的的复复乘乘次次数数等等于于N N2 2。把把N N点点DFTDFT分分 解解为为几几个个较较短短的的DFTDFT，可可使使乘乘法法次次数数大大大大减减少少。另外，旋转因子另外，旋转因子W Wm mN N具有周期性和对称性。具有周期性和对称性。4.1 4.1 离散傅里叶变换的高效计算思路离散傅里叶变换的高效计算思路3 3、FFTFFT算法思想算法思想 不断地把不断地把长序列长序列的的DFTDFT分解成分解成几个短序列几个短序列的的DFTDFT，

5、并利用旋转因子的，并利用旋转因子的周期性周期性和和对称性对称性来来减少减少DFTDFT的运算次数。的运算次数。方法：方法：分分解解N为为较较小小值值：把把序序列列分分解解为为几几个个较较短短的的序列，分别计算其序列，分别计算其DFT值；值；利利用用旋旋转转因因子子WNk的的周周期期性性、对对称称性性、可可约约性性进进行行合合并并、归归类类处处理理，以以减减少少DFT的的运运算次数。算次数。周期性周期性：对称性对称性：可约性可约性：4.1 4.1 离散傅里叶变换的高效计算思路离散傅里叶变换的高效计算思路 一、一、时域抽取法基时域抽取法基2FFT基本原理基本原理 FFT算算法法基基本本上上分分为为

6、两两大大类类：时时域域抽抽取取法法FFT(简简 称称 DIT-FFT)和和 频频 域域 抽抽 取取 法法 FFT(简简 称称DIFFFT)。1、时域抽取法、时域抽取法FFT的算法思想：的算法思想：将将序序列列x(n)按按n为为奇奇、偶偶数数分分为为x1(n)、x2(n)两两组组序序列列；用用2个个N/2点点DFT来来完完成成一一个个N点点DFT的计算。的计算。4.2 基基2时间抽选的时间抽选的FFT算法算法 设序列设序列x(n)的长度为的长度为N，且满足：，且满足：(1)按按n的奇偶把的奇偶把x(n)分解为两个分解为两个N/2点的子序列点的子序列4.2 基基2时间抽选的时间抽选的FFT算法算法

7、为自然数为自然数(2)用用N/2点点X1(k)和和X2(k)表示表示N点点 X(k)4.2 基基2时间抽选的时间抽选的FFT算法算法偶数偶数奇数奇数注意：注意：这里这里k的取值范围为的取值范围为0，1，N-1？由由于于X1(k)和和X2(k)均均隐隐含含周周期期为为N/2，且且 ,X(k)又可表示为又可表示为:对上式的运算用下图所示的对上式的运算用下图所示的流图符号流图符号来表示来表示4.2 基基2时间抽选的时间抽选的FFT算法算法这样将这样将N点点DFT分解为两个分解为两个N/2点的点的DFT对上式的运算用下图所示的对上式的运算用下图所示的流图符号流图符号来表示来表示4.2 基基2时间抽选的

8、时间抽选的FFT算法算法X1(k)X2(k)X1(k)+WNkX2(k)X1(k)WNkX2(k)WNk蝶形运算蝶形运算图图-1例例:X(0)=X1(0)+WN0X2(0)，X(1)=X1(1)+WN1X2(1)x(0)x(2)x(4)x(6)WN0X(0)WN1X(1)WN2X(2)WN3X(3)X1(0)X1(1)X1(2)X1(3)N/2点点DFTX2(0)X2(1)X2(2)X2(3)N/2点点DFTx1(0)x1(1)x1(2)x1(3)x(1)x(3)x(5)x(7)x2(0)x2(1)x2(2)x2(3)X(4)-1X(5)-1X(6)-1X(7)-1N=8点的点的DIT-2FF

9、T(时域抽取图时域抽取图)一次分解图一次分解图x1x2(3)第二次分解：第二次分解：将将x1(r)按按r取奇、偶可分解成取奇、偶可分解成2个长度为个长度为N/4的子序列的子序列 x3(l)=x1(2l)、x4(l)=x1(2l+1)，根据上面推导可得：根据上面推导可得：X1(k)=X3(k)+WN/2k X4(k)，k=0,1,N/2-1将将x2(r)按按r取奇、偶可分解成取奇、偶可分解成2个长个长N/4的子序列的子序列 x5(l)=x2(2l)，l=0,1,，N/4 x6(l)=x2(2l+1)；同理得同理得4.2 基基2时间抽选的时间抽选的FFT算法算法l=0,1,，N/4-1；X1(k+

10、N/4)=X3(k)WN/2k X4(k)，k=0,1,N/4-1；X1(k)=X3(k)+WN/2k X4(k)，k=0,1,N/4-1；X2(k)=X5(k)+WN/2k X6(k)，k=0,1,N/4-1 ；X2(k+N/4)=X5(k)WN/2k X6(k),k=0,1,N/4-1；X1(0)W40 x3(0)x3(1)x4(0)x4(1)W80X(0)W81X(1)W82X(2)W83X(3)X(4)-1X(5)-1X(6)-1X3(0)X3(1)N/2点点DFTX1(1)W41X(7)-1X1(2)-1X1(3)-1X4(0)X4(1)N/2点点DFTx1(0)x1(2)x1(1)

11、x1(3)N/2点点DFTX2(0)X2(1)X2(2)X2(3)x5(0)x5(1)x6(0)x6(1)W40W41X5(0)X5(1)X6(0)X6(1)-1-1N/2点点DFTx2(0)x2(2)x2(1)x2(3)x(0)=x(4)=x(2)=x(6)=x(1)=x(5)=x(3)=x(7)=N=8点点DFT的二次时域抽取分解图的二次时域抽取分解图 x3(l)=x1(2l)x4(l)=x1(2l+1)4.2 基基2时间抽选的时间抽选的FFT算法算法l=0,1,，N/4-1；以以N=8为例，将为例，将k=0,1代入得代入得4.2 基基2时间抽选的时间抽选的FFT算法算法N=8点点DIT-

12、FFT运算流图运算流图X(5)x(0)x(4)x(2)x(6)x(1)x(5)x(3)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(6)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/20WN/40 x(7)WN/21L=1级级L=2L=3X(7)X3(0)X1(0)WN/40WN/40WN/40-1-1-1-1-1-1-1-1-1-1-1-1二、二、DITFFT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较1、直接、直接DFT运算运算N点运算

13、点运算：复数乘次数：复数乘次数：NN 复数加次数：复数加次数：N(N-1)2、用用DIT-FFT作作N点运算：点运算：复数乘次数：复数乘次数：MN/2=N/2log2N；复加次数：复加次数：2 N/2M=Nlog2N。可见可见FFT大大减少了运算次数，提高了运算速度。大大减少了运算次数，提高了运算速度。4.2 基基2时间抽选的时间抽选的FFT算法算法整整个个运运算算流流图图中中有有M级级蝶蝶形形，每每 一一 级级 中中 有有N/2个个 蝶蝶 形形，每每个个蝶蝶形形需需一一次次复复乘乘和和两两次次复数加复数加运算。运算。4.2 基基2时间抽选的时间抽选的FFT算法算法1.蝶形运算蝶形运算 序列经

14、过时域抽选后，存入数组中，如果蝶形序列经过时域抽选后，存入数组中，如果蝶形运算的两个输入数据相距运算的两个输入数据相距B个点，应用原位计算，个点，应用原位计算，蝶形运算可表示成如下形式：蝶形运算可表示成如下形式：XL-1(k)X L-1(k+B)WNpp=J2M-L，J=0,1,2,2L-11B=2L-1-1三、三、DITFFT的运算的运算特点特点及编程思想及编程思想2.原位计算原位计算序序列列长长为为N=2M点点的的FFT，有有M级级蝶蝶形形，每每级级有有N/2个个蝶蝶形运算形运算。同同一一级级中中，每每个个蝶蝶形形的的两两个个输输入入数数据据只只对对本本蝶蝶形形有有用用，每每个个蝶蝶形形的

15、的输输入入、输输出出数数据据节节点点在在用用一一条条水水平平线线上上。这这样样，当当计计算算完完一一个个蝶蝶形形后后，所所得得的的输输出出数数据据可可立立即即存存入入原原输输入入数数据据所所占占用用的的存存储储单单元元。经经过过M级级运运算算后后，原原来来存存放放输输入入序序列列数数据据的的N个个存存储储单单元元中中可可依依次存放次存放X(k)的的N个值。个值。原原位位计计算算：利利用用同同一一存存储储单单元元存存储储蝶蝶形形计计算算输输入入、输输出数据的方法。出数据的方法。优点优点：节约存储空间、降低设备成本。：节约存储空间、降低设备成本。4.2 基基2时间抽选的时间抽选的FFT算法算法3.

16、旋转因子和运算级数的关系旋转因子和运算级数的关系N点点DITFFT运运算算流流图图中中，每每个个蝶蝶形形都都要要乘乘以以旋旋转转因因子子WpN，p称为旋转因子的指数。称为旋转因子的指数。N8 23 时各级的旋转因子时各级的旋转因子 第一级：第一级：L=1，有有1个旋转因子：个旋转因子：WNp=WN/4J=W2LJ J=0 第二级：第二级：L=2，有，有2个旋转因子：个旋转因子：WNp=WN/2J=W2LJ J=0,1 第三级：第三级：L=3，有，有4个旋转因子：个旋转因子：WNp=WNJ=W2LJ J=0,1,2,3 对于对于N2M 的的一般情况，一般情况，第第L级级共有共有2L-1个不同的旋

17、转因子：个不同的旋转因子：WNp=W2LJ J=0,1,2,2L-11 2L=2L M 2M=N 2L M 故：故：按照上面两式可以确定第按照上面两式可以确定第L级运算的旋转因子。级运算的旋转因子。4.2 基基2时间抽选的时间抽选的FFT算法算法JJ 2M-LWNp=W2LJ=WN 2L-M=WNp=J2M-L，J=0,1,2,2L-11同一级中，同一旋转因子对应蝶形数目同一级中，同一旋转因子对应蝶形数目 第第L级级FFT运算中，运算中，同一旋转因子同一旋转因子用在用在2M-L个蝶形中；个蝶形中；同一级中，蝶形运算使用相同旋转因子之间相隔的同一级中，蝶形运算使用相同旋转因子之间相隔的“距离距离

18、”第第L级中，蝶距：级中，蝶距：D=2L。4.2 基基2时间抽选的时间抽选的FFT算法算法4.序列的倒序序列的倒序 N=2M，用，用M位二进制数位二进制数(nM-1nM-2n1n0)2表示序列的序号表示序列的序号n.M次次偶偶奇奇时时域域抽抽选选过过程程为为：对对最最低低位位按按0、1分分为为偶偶、奇奇两两组组，次低位也按次低位也按0、1分组，依此类推，分组，依此类推，M次分解后形成次分解后形成倒序图倒序图倒序图倒序图为：为：4.2 基基2时间抽选的时间抽选的FFT算法算法二进制数二进制数(N=8)分解倒序图分解倒序图10041015110611170000001101020113倒序前倒序前

19、00111015011311170000100401021106倒序后倒序后可可见见，只只要要将将顺顺序序数数的的二二进进制制位位倒倒置置可可得得到到对对应应的的二二进进制制倒序值倒序值。10n20101n100010n0111(n2n1n0)2思考题思考题：已知：已知N=16点，在点，在DIT-FFT运算中，序数为运算中，序数为2的二进制的二进制数经倒序后为多少数经倒序后为多少?4.2 基基2时间抽选的时间抽选的FFT算法算法顺顺序序数数增增加加1，是是在在顺顺序序数数的的二二进进制制数数的的最最低低位位加加1，向向左左进进位位到到序序数数是是在在M位位二二进进制制数数的的最最高高位位加加1

20、，向向右右进位进位(0010-0100)顺序和倒序二进制数对照表顺序和倒序二进制数对照表 N=2M，用，用M位二进制数位二进制数表示，则从左至表示，则从左至右的右的十进制权值为：十进制权值为：N/2、N/4、N/8,、2,1 对倒序数对倒序数J，其下一个序，其下一个序数是在该序数数是在该序数J的二进制的二进制首位码加首位码加1，相当于十进，相当于十进制运算制运算J+N/2。计算机上倒序数的实现计算机上倒序数的实现过程为：过程为：4.2 基基2时间抽选的时间抽选的FFT算法算法JN/2？JN/4输入当前倒序数输入当前倒序数十进制数值十进制数值JNYNYJN/2MNY结束结束J=J-N/2倒序数的

21、十进制运算规律倒序数的十进制运算规律倒序程序框图倒序程序框图 为了实现原位运算，以节约存贮空间，提高运算速率。在为了实现原位运算，以节约存贮空间，提高运算速率。在倒序数倒序数 J 形成后，需将原存储器中存放的输入序列重新排列。形成后，需将原存储器中存放的输入序列重新排列。下面先分析下面先分析N=8点的倒序规律。点的倒序规律。4.2 基基2时间抽选的时间抽选的FFT算法算法x(0)A(0)x(1)A(1)x(2)A(2)x(3)A(3)x(4)A(4)x(5)A(5)x(6)A(6)x(7)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)输入序列输入序列数组数组分析上图分

22、析上图N=8点倒序规律，顺序数点倒序规律，顺序数I与倒序数与倒序数J 存在关系：存在关系：I=J时，不交换；时，不交换；I J时，不交换，直接更新序数值；时，不交换，直接更新序数值；IJx(0)x(2)x(4)x(1)x(5)x(6)x(3)x(7)计算倒计算倒序值序值交换数组交换数组中的数据中的数据不交换数据，避免不交换数据，避免再次调换前面调换再次调换前面调换过的一对数据，计过的一对数据，计算下一个倒数值。算下一个倒数值。6.DIT-FFT程序框图程序框图根根据据DIT-FFT原原理理和和过过程程，DIT-FFT的的完完整整程程序序框框图包括以下几部分：图包括以下几部分：(1)倒倒序序:输

23、输入入自自然然顺顺序序序序列列x(n)，根根据据倒倒序序规规律，进行倒序处理；律，进行倒序处理；(2)循循环环层层1:确确 定定 运运 算算 的的 级级 数数，L=1 M(N=2M)；确定一蝶形两输入数据距离；确定一蝶形两输入数据距离B=2L-1(3)循循环环层层2:确确定定L级级的的(B=)2L-1个个旋旋转转因因子子；旋转因子指数旋转因子指数p=2M-LJ，J=0 B-1；(4)循循环环层层3:对对于于同同一一旋旋转转因因子子，用用于于同同一一级级2M-L个个蝶蝶形形运运算算中中：k的的取取值值从从J到到N-1，步步长长为为2L(使用同一旋转因子的蝶形相距的距离使用同一旋转因子的蝶形相距的

24、距离)(5)完成一个蝶形运算完成一个蝶形运算。4.2.4 DIT-FFT的其他形式流图W40W40W40W40W40W40W40W40W40W40W40W40X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)按时间抽选，输入自然序，输出倒位序的按时间抽选，输入自然序，输出倒位序的FFT流图流图DIT-FFT的其他形式流图按时间抽选，输入和按时间抽选，输入和输出都是输出都是自然序的自然序的FFT流图流图W80W81W82W83X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1WN0WN0W

25、N2WN2-1-1-1-1WN0WN0WN0WN0 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1DIT-FFT的其他形式流图按时间抽选按时间抽选,各级具有相同几何形状的各级具有相同几何形状的FFT流图流图WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1WN0WN0WN2WN2-1-1-1-1WN0WN0WN0WN0 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1 在基在基2快速算法中，频域抽取法快速算法中，频域抽取法FFT也是一种常用的快速算法。也是一种常用的快速算法。

26、1、算法思想和运算过程、算法思想和运算过程 设设序序列列x(n)长长度度为为N=2M，将将序序列列x(n)前前后后对对半半分分为为x1(n)、x2(n)两组序列，用两组序列，用2个个N/2点点DFT来完成一个来完成一个N点点DFT的计算。的计算。4.3 按频率抽取的基按频率抽取的基-2FFT算法算法nk=偶数偶数,k=奇数奇数 4.3 按频率抽取的基按频率抽取的基-2FFT算法算法将将X(k)分解成分解成偶数组偶数组与与奇数组奇数组，当，当k取偶数取偶数(k=2r,r=0,1,N/2-1)时时 当当k取奇数取奇数(k=2r+1,r=0,1,N/2-1)时：时：将将x1(n)和和x2(n)分别代

27、入上式，可得分别代入上式，可得x1(n)x2(n)表明表明：X(k)按奇偶按奇偶k值分为两组值分为两组:偶数组偶数组是是x1(n)的的N/2点点DFT 奇数组奇数组是是x2(n)的的N/2点点DFTr=0,1,N/2-1那么对序列那么对序列x1(n)、x2(n)和和x(n)可用蝶形运算符号表示可用蝶形运算符号表示4.3 按频率抽取的基按频率抽取的基-2FFT算法算法x(n)x1(n)=x(n)+x(n+N/2)x2(n)=x(n)x(n+N/2)WNnx(n+N/2)DIF-FFT蝶形运算流图符号蝶形运算流图符号WNk-14.3 按频率抽取的基按频率抽取的基-2FFT算法算法N=8时第时第1次

28、分解的运算流图次分解的运算流图x(0)x(1)x(2)x(3)WN0X(0)WN1X(2)WN2X(4)WN3X(6)N/2点点DFTN/2点点DFTx(4)x(5)x(6)x(7)X(1)-1X(3)-1X(5)-1X(7)-1N=2M，N/2仍是偶数仍是偶数，继续将继续将N/2点进行分解点进行分解。将输入序列。将输入序列x1(n)、x2(n)分别按前、后对半分解成分别按前、后对半分解成4个长个长N/4的子序列的子序列,其其n=0,1,，N/4-14.3 按频率抽取的基按频率抽取的基-2FFT算法算法x3(n)=x1(n)+x1(n+N/4)x4(n)=x1(n)-x1(n+N/4)WN/2

29、n x5(n)=x2(n)+x2(n+N/4)x6(n)=x2(n)-x2(n+N/4)WN/2nDIFFFT二次分解运算流图二次分解运算流图(N=8)X(0)X(4)X(2)X(6)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0N/4点点DFTN/4点点DFTWN0WN1WN2WN3X(1)X(5)X(3)X(7)WN2WN0WN2N/4点点DFTN/4点点DFT-1-1-1-1-1-1-1-1DIFFFT运算流图运算流图(N=8)4.3 按频率抽取的基按频率抽取的基-2FFT算法算法X(0)X(4)X(2)X(6)x(0)x(1)x(2)x(3)x(4)x(5)x(

30、6)x(7)WN0WN0WN1WN2WN3X(1)X(5)X(3)X(7)WN2WN0WN2-1-1-1-1-1-1-1-1-1-1-1-1WN0WN0WN0WN02、DIF-FFT运算规律运算规律 DIF-FFT算算法法也也可可采采用用原原位位计计算算；N=2M时时，共共有有M级级运运算算，每每级级共共有有N/2个蝶形个蝶形，DIT与与DIF算法的算法的运算次数运算次数相同。相同。DIT与与DIF不同的是不同的是：DIF-FFT算法算法输入序列为自然序列输入序列为自然序列，输出为倒序输出为倒序序列。因此，在序列。因此，在M级运级运算完成后，需对输出数据进行倒序才能得到自然顺序的算完成后，需对

31、输出数据进行倒序才能得到自然顺序的X(k)。蝶形运算符号不同蝶形运算符号不同：DIT-FFT蝶形是先相乘，后加蝶形是先相乘，后加/减；而减；而DIF-FFT蝶蝶形是先加形是先加/减，后相乘。减，后相乘。4.3 按频率抽取的按频率抽取的基基-2FFT算法算法x(n)x1(n)=x(n)+x(n+N/2)x2(n)=x(n)x(n+N/2)WNnx(n+N/2)DIF-FFT蝶形运算流图符号蝶形运算流图符号WNk-13、其它形式的、其它形式的DIT-FFT运算流图运算流图 通过改变通过改变输入输入/输出节点输出节点,中间节点中间节点的排列顺序的排列顺序,可以得到不同变形的可以得到不同变形的FFT运

32、运算流图。因此，前面介绍的算流图。因此，前面介绍的DIT-FFT和和DIF-FFT运算流图都不是唯一的运算流图都不是唯一的。4.3 按频率抽取的基按频率抽取的基-2FFT算法算法输出序列输出序列输入序列输入序列DIT-FFT的一种变形运算流图（输入顺序，输出倒序）的一种变形运算流图（输入顺序，输出倒序）X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)X3(0)X5(0)X4(0)X6(0)X3(1)X5(1)X4(1)X6(1)WN0 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN0WN0WN2WN1WN3X1(0)X2(0)X1(2)X2(2)X1

33、(1)X2(1)X1(3)X2(3)WN0WN0WN0WN2WN2 用同样的方法可得用同样的方法可得DIT-FFT的另外一种变形运算流图，的另外一种变形运算流图，输入输入和输出均为顺序排列，但不能采用原位计算。和输出均为顺序排列，但不能采用原位计算。4.3 按频率抽取的基按频率抽取的基-2FFT算法算法DITFFT的一种变形运算流图的一种变形运算流图一、一、IDFT的高效算法的高效算法1 DFT和和IDFT的公式比较的公式比较上述上述FFT算法流图也可以用于离散傅里叶逆变换算法流图也可以用于离散傅里叶逆变换IDFT根根据据运运算算公公式式可可以以看看出出，只只需需将将DFT的的系系数数WNkn

34、变变为为WN-kn，最后结果最后结果乘以乘以1/N，就是，就是IDFT的运算公式。的运算公式。4.4 傅里傅里反反叶变换叶变换（IDFT）的）的快速快速计算方法计算方法X(k)n2 用用FFT流图实现流图实现IDFT快速算法快速算法将将DIT-FFT或或DIF-FFT蝶形运算流图中蝶形运算流图中旋转因子旋转因子WNp改为改为WN-p在在IDFT快快速速算算法法的的最最后后结结果果输输出出前前，乘乘以以1/N常常数数；如如要要防防止止溢溢出出，可可在在每每一一级级运运算算中中，输输出出支支路路分分别别乘乘以以1/2，实实现现系系数数分分级分担。级分担。在在IDFT快速算法中，快速算法中，输入序列

35、为输入序列为X(k)，而，而输出序列为输出序列为x(n)。节点对应关系：节点对应关系：DIT-FFT对应对应DIF-IFFT DIF-FFT对应对应DIT-IFFT4.4 傅里反叶变换（傅里反叶变换（IDFT）的快速计算方法）的快速计算方法4.4 傅里反叶变换（傅里反叶变换（IDFT）的快速计算方法）的快速计算方法DITIFFT运算流图运算流图 4.4 傅里反叶变换（傅里反叶变换（IDFT）的快速计算方法）的快速计算方法DITIFFT运算流图运算流图(防止溢出防止溢出)3、直接调用、直接调用FFT程序实现程序实现IFFT的计算的计算 对对FFT流程作一些修改后，调用流程作一些修改后，调用FFT

36、程序实现程序实现IFFT的快速计算。的快速计算。具体实现方法：具体实现方法：先将先将X(k)取共轭取共轭，得到，得到X*(k)；直接调用直接调用FFT子程序计算出子程序计算出DFTX*(k)的值；的值；对输出序列对输出序列取共轭取共轭，并乘以，并乘以1/N常数。常数。虽虽然然2次次用用了了取取共共轭轭运运算算，但但可可以以和和FFT共共用用一一个个子子程程序序，实实现方便。现方便。4.4 傅里反叶变换（傅里反叶变换（IDFT）的快速计算方法）的快速计算方法*4.8.1 两个长度相同的实序列两个长度相同的实序列 可可以以将将两两个个长长度度相相同同的的实实序序列列组组合合成成一一个个复复序序列列

37、来来进进行行FFT运运算算，从从而而一一次次完完成成这这两两个个实实序序列列的的FFT，减减少少了了总的计算量。总的计算量。4.8 实序列的实序列的FFT算法算法 设设p(n)和和g(n)是两个长度均为是两个长度均为N的实序列，并设：的实序列，并设：又设又设 ，则由则由DFT的线性有：的线性有：利用有限长序列利用有限长序列DFT的对称性，有的对称性，有4.8 实序列的实序列的FFT算法算法上两式中上两式中0kN-1。4.8.2 4.8.2 一个一个2 2N N点的实序列点的实序列 将将一一个个2 2N N点点的的实实序序列列x(n)x(n)按按偶偶数数点点和和奇奇数数点点分分组组形形成成两个两

38、个N N点实序列：点实序列：4.8 实序列的实序列的FFT算法算法则有：则有：k=0,1,N-1 (4.k=0,1,N-1 (4.8.18.1)一、连续时间非周期信号的DFT近似4.10 用DFT的快速算法对信号进行频谱分析4.10 用DFT的快速算法对信号进行频谱分析4.10 用用DFT的快速算法对信号进行频谱分析的快速算法对信号进行频谱分析二、二、连续时间周期信号的连续时间周期信号的DFT近似近似4.10 用用DFT的快速算法对信号进行频谱分析的快速算法对信号进行频谱分析三、利用DFT对连续时间信号频谱的近似过程图解4.10 用用DFT的快速算法对信号进行频谱分析的快速算法对信号进行频谱分

39、析四、用DFT计算连续时间信号的频谱可能造成的误差1.混叠现象4.10 用用DFT的快速算法对信号进行频谱分析的快速算法对信号进行频谱分析4.10 用用DFT的快速算法对信号进行频谱分析的快速算法对信号进行频谱分析2.频谱泄漏4.10 用用DFT的快速算法对信号进行频谱分析的快速算法对信号进行频谱分析0n0nn4.10 用用DFT的快速算法对信号进行频谱分析的快速算法对信号进行频谱分析3.栅栏效应 用DFT计算频谱时，只是知道在频率 的整数倍处的频谱。在两个谱线之间 的情况就不知道,这相当通过一个栅栏观察景象一样，故称作栅栏效应。补零点加大周期 ，可使F0变小来提高分辨力，以减少栅栏效应。4.10 用用DFT的快速算法对信号进行频谱分析的快速算法对信号进行频谱分析