快速傅里叶变换(FFT).ppt

《快速傅里叶变换(FFT).ppt》由会员分享，可在线阅读，更多相关《快速傅里叶变换(FFT).ppt（67页珍藏版）》请在三一办公上搜索。

1、第4章 快速傅里叶变换(FFT),4.1 引言4.2 基2FFT算法4.3 进一步减少运算量的措施4.4 其它快速算法简介,4.1 引言,DFT是信号分析与处理中的一种重要变换。直接计算DFT的计算量 N2 无法直接用DFT算法进行谱分析和信号的实时处理 直到1965年：DFT的一种快速算法出现FFT更快、更灵活的好算法,4.2 基2FFT算法,4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列 x(n)的DFT为：若 x(n)为复数序列，则对一个 k 值，直接按上式计算 X(k)值需要：N次复数乘法、(N-1)次复数加法对N个 k 值，共需要：N2 次复数乘法和 N

2、(N-1)次复数加法,(4.2.1),（1）把N点DFT分解为几个较短的DFT N点DFT的复乘次数、复加次数都 N2。（2）利用旋转因子WmN的周期性和对称性。周期性：,(4.2.2),对称性：,或者,减少运算量的途径：,4.2.2 时域抽取法基2FFT基本原理 FFT算法基本上分为两大类：时域抽取法FFT（DIT-FFT：Decimation In Time FFT）频域抽取法FFT（DIF-FFT：Decimation In Frequency FFT）DITFFT算法：设序列x(n)的长度为N，且满足,为自然数,按 n 的奇偶把 x(n)分解为两个N/2点的子序列：,则x(n)的DFT

3、为：,由于,所以,其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即,由于X1(k)和X2(k)均以N/2为周期，且，所以X(k)又可表示为,图4.2.1 蝶形运算符号,图4.2.2 8点DFT的一次时域抽取分解运算流图,运算量分析：完成一个蝶形运算需要：一次复数乘法运算、两次复数加法运算。经过一次分解后，计算1个N点DFT共需要：计算两个N/2点DFT、N/2个蝶形运算，即总共需要的复数乘法次数为：复数加法次数为：,由于N=2M,N/2仍然是偶数，故可以对N/2点DFT再作进一步分解。与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)

4、，即,那么，X1(k)又可表示为,式中,同理，由X3(k)和X4(k)的周期性和Wm N/2的对称性 Wk+N/4 N/2=-Wk N/2 最后得到：,用同样的方法可计算出：,其中,经过第二次分解，又将N/2点DFT分解为2个N/4点DFT和N/4个蝶形运算。,图4.2.3 8点DFT第二次时域抽取分解运算流图,依次类推，经过M次分解，最后将N点DFT分解成N个1点DFT和M级蝶形运算，而1点DFT就是时域序列本身。,图4.2.4 8点DITFFT运算流图,基2时间抽取FFT算法流图,N=2,xk=x0,x1,4点基2时间抽取FFT算法流图,X10,X11,X20,X21,-1,-1,-1,-

5、1,X 0,X 1,X 2,X 3,4点基2时间抽取FFT算法流图,8点基2时间抽取FFT算法流图,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,8点基2时间抽取FFT算法流图,基2时间抽取FFT算法,第一级,第二级,第三级,4.2.3 DITFFT算法与直接计算DFT运算量的比较 N=2M 运算流图有M级蝶形，每一级都有N/2个蝶形运算，

6、每一级运算都需要N/2次复数乘和N次复数加。所以，M级运算总共需要的复数乘次数为：,复数加次数为：,例如，N=210=1024 时,图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线,4.2.4 DITFFT的运算规律及编程思想 1.原位计算 N=2M点FFT共进行M级运算，每级有N/2个蝶形运算。同一级中，每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入输出数据结点又同在一条水平线上。这意味着计算完一个蝶形后，所得输出数据可立即存入原输入数据所占用的存储单元。2.旋转因子的变化规律 N点DITFFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋

7、转因子，p称为旋转因子的指数。,图4.2.4 8点DITFFT运算流图,观察图不难发现，第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：,对N=2M的一般情况，第L级的旋转因子为：,因为：,所以：,3.蝶形运算规律 设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：式中：下标L表示第L级运算，AL(J)则表示第L级运算后的数组元素A(J)的值（即第L级蝶形的输出数据）。而AL1(J)表示第L级运算前A(J)的值（即第L级蝶形的输入数据）。,4.编程思想及程序框图,图4.2.6 DITFFT

8、运算和程序框图,5.序列的倒序 DITFFT算法输入序列的排序称为倒序：N=2M，顺序数可用M位二进制数(nM-1nM-2n1n0)表示。,图4.2.7 形成倒序的树状图(N=23),表4.2.1 顺序和倒序二进制数对照表,用J表示当前倒序数的十进制数值。对于N=2M，M位二进制数从左向右二进制位的权值依次为：N/2，N/4，N/8，2，1。最高位加1相当于十进制运算J+N/2。如果最高位是0(JN/2)，则直接由J+N/2得下一个倒序值；如最高位是1(JN/2),则先将最高位变成0(JJN/2)，然后次高位加1(J+N/4)。次高位加1时，同样要判断0、1值，如果为0(JN/4)，则直接加1

9、(JJ+N/4)，如果为1(JN/4)，则将次高位变成0(JJN/4)，再判断下一位；依此类推，直到完成最高位加1，逢2向右进位的运算。,图4.2.8 倒序规律,图4.2.9 倒序程序框图,4.2.5 频域抽取法FFT(DIFFFT)设序列x(n)长度为N=2M，将x(n)前后对半分开，得到两个子序列，其DFT为：,偶数,奇数,将X(k)分解成偶数组与奇数组:当k取偶数(k=2m，m=0,1,N/2-1)时,当k取奇数(k=2m+1，m=0,1,N/21)时:,令,将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得(4.2.16)上式表明，X(k)按奇偶 k 值分为两组

10、：偶数组是 x1(n)的 N/2 点DFT，奇数组是 x2(n)的 N/2 点DFT。,图4.2.10 DIFFFT蝶形运算流图符号,图4.2.10 DITFFT与DIFFFT蝶形运算流图对比,图4.2.11 DIFFFT一次分解运算流图(N=8),图4.2.2 8点DFT的一次时域抽取分解运算流图,图4.2.12 DIFFFT二次分解运算流图(N=8),图4.2.13 DIFFFT运算流图(N=8),8点DITFFT,8点DIFFFT,相同：可原位计算、M级运算、每级N/2个蝶形运算、运算次数不同：输入输出数据的顺序、乘法和加法的先后顺序,图4.2.14 DITFFT的一种变形运算流图,图4

11、.2.15 DITFFT的一种变形运算流图,4.2.6 IDFT的高效算法 FFT算法流图也可以用于离散傅里叶逆变换(Inverse Discrete Fourier Transform，简称IDFT)。比较DFT和IDFT的运算公式：,图4.2.16 DITIFFT运算流图,图4.2.17 DITIFFT运算流图(防止溢出),若想直接调用FFT子程序计算IFFT，可用下法：由于,对上式两边同时取共轭，得,4.3 进一步减少运算量的措施,4.3.1 多类蝶形单元运算 N=2M点FFT共需要 次复数乘法,（1）L=1时 只有一种旋转因子W0N=1，第一级不需要乘法运算。（2）L=2时 有两种旋转

12、因子：W0N=1和WN/4N=-j，也不需乘法运算。,所以，除去第一、二两级后，所需复数乘法次数为：,(4.3.1),（3）L=3时 有两个无关紧要的旋转因子、同一旋转因子对应着 2ML=N/2L 个碟形运算，所以第三级共有2N/23=N/4 个碟形不需要复数乘法运算。（4）L3时 第L级的2个无关紧要的旋转因子减少复数乘法的次数为2N/2L=N/2L1。综上，从L=3至L=M共减少复数乘法次数为：,因此，DITFFT的复乘次数降至：,(4.3.3),（5）FFT中特殊的复数运算：一般实现一次复数乘法运算需要四次实数乘，两次实数加。有些特殊复数：,任一复数(x+jy)与其相乘时，,只需要两次实

13、数乘，两次实数加即可实现。,从实数运算考虑，计算N=2M点基2DITFFT所需实数乘法次数为,(4.3.4),对应的每个蝶形节省两次实数乘。在DIT-FFT运算流图中，从L=3至L=M级，每级都包含旋转因子，第L级中，对应N/2L个蝶形运算。因此从第三级至最后一级，旋转因子 节省的实数乘次数,在基2FFT程序中，（1）若包含了所有旋转因子，称为一类碟形单元运算；（2）若去掉的旋转因子，称为二类碟形单元运算；（3）若再去掉 的旋转因子，称为三类碟形单元运算；（4）若再判断处理，称为四类碟形运算。后三种运算称为多类碟形单元运算。碟形单元类型越多，编程就越复杂，但当N较大时，乘法运算的减少量是相当可

14、观的。例如，N=4096时，三类碟形单元运算的乘法次数为一类碟形单元运算的75%。,4.3.2 旋转因子的生成 旋转因子 求正弦和余弦函数值的计算量是很大的。方法一：直接计算 节省内存 方法二：预先计算 速度提高，内存增多,4.3.3 实序列的FFT算法 在实际工作中，数据x(n)常常是实数序列。如果直接按FFT运算流图计算，就是把x(n)看成一个虚部为零的复序列进行计算，这就增加了存储量和运算时间。三种处方法：（1）用一个N点FFT计算两个N点实序列的FFT，一个实序列作为x(n)的实部，另一个作为虚部，计算完FFT后，根据DFT的共轭对称性，用例3.2.2 所述的方法由输出X(k)分别得到

15、两个实序列的N点DFT。（2）用N/2点FFT计算一个N点实序列的DFT。（3）用离散哈特莱变换（DHT）,所以，由X(k)可以求得两个实序列x1(n)和x2(n)的N点DFT：,【例3.2.2】利用DFT的共轭对称性设计一种算法，通过计算一个N点DFT，就可计算出两个实序列x1(n)和x2(n)的N点DFT解:构造新序列x(n)=x1(n)+jx2(n)，对x(n)进行DFT，得到：,由(3.2.17)、(3.2.18)和(3.2.19)式得到：,设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即,对y(n)进行N/2点FFT，输出Y(k)，则,根据

16、DITFFT的思想及式(4.2.7)和(4.2.8)，可得到,由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为,4.4 其他快速算法简介快速傅里叶变换算法是信号处理领域重要的研究课题。本章仅介绍算法最简单、编程最容易的基2FFT算法原理及其编程思想，使读者建立快速傅里叶变换的基本概念，了解研究FFT算法的主要途径和编程思路。其他高效快速算法有：分裂基FFT算法、离散哈特莱变换(DHT)、基4FFT、基8FFT、基rFFT、混合基FFT，以及进一步减少运算量的途径等内容，对研究新的快速算法都是很有用的。本节简要介绍其他几种快速算法的运算量及其主要特点。,其中未计入乘

17、以j和1的计算。比较基2FFT的复数乘法次数，基4FFT的复数乘法次数减少25%。1984年，法国的杜梅尔（P.Dohamel）和霍尔曼（H.Hollmann）将基2分解和基4分解糅合，提出了分裂基FFT算法，其复数乘法次数接近FFT理论最小值，但其运算流图却与基2FFT很相似，编程简单，运算程序也很短，是一种很实用的高效算法。分裂基FFT算法复数乘法次数为 CM(分裂基)=（）,只考虑（4.4.2）式的第一项，分裂基FFT算法的复数乘法次数就比基2FFT减少33%，比基4FFT减少11%。应当说明，在比较时，未考虑（4.4.2）式后2项减少的运算量，所以分裂基FFT算法的效率更高。由以上比较

18、可见，分裂基FFT算法的效率最高，所以得到广泛应用。但是，对实序列x(n)，上述各种FFT算法仍将其看成虚部为零的复序列存储和计算。而一次复数乘法需要四次实数乘法和二次实数加法。所以，必然浪费存储资源和增加多余的运算量。我们知道，实序列的N点DFT具有共轭对称性，即,所以，只要计算出X（k）的前面N/2个值，则其后面的N/2个值可以由对称性求得。因此，FFT算法得到的N个X（k）值有一半是多余的。由以上分析可见，对实序列一定存在更高效的快速算法。离散哈特莱变换（DHT）就是针对实序列的一种高效变换算法，相对一般的FFT算法，DHT的快速算法FHT可以减少近一半的计算量。N点基2时域抽取快速DH

19、T（基2DIT-FHT）算法的实数乘法次数为（4.4.3）,N点基2DIT-FHT算法的实数加法次数为（4.4.4）由式（4.4.3）可见，基2DIT-FHT算法的实数乘法次数约为基2DIT-FFT算法的一半。与前面三种FFT算法比较，对实序列，基2DIT-FHT算法的实数乘法次数最少。应当说明，DHT是与DFT不同的变换，所以要想得到实序列DFT，还要根据二者的关系式进行转换。下面会看到该关系非常简单。,DHT具有以下主要优点：(1)DHT是实数变换，在对实信号进行处理时避免了复数运算，运算效率高，且实现硬件简单经济。(2)DHT的正、逆变换（除了因子1/N外）具有相同的形式，所以实现硬件或程序亦相同。N点DHT定义如下：（）,N点逆DHT变换定义为（4.4.6）(3)DHT满足循环卷积定理，所以，可以直接用FHT实现实序列的快速卷积，大大提高处理速度，并使处理硬件简化。,(4)DHT与DFT之间的关系非常简单，容易实现二者之间的转换，关系式如下：（4.4.7）所以对实信号x(n)进行谱分析时，可以先对x(n)进行FHT,得到XH(k)=DHTx(n)N，然后再将H(k)转换成X(k)=DFTx(n)N，这样可以提高分析速度，减少存储空间。,