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

第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(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为：,由于,所以,其中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)，即,那么，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,-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个蝶形运算， 每一级运算都需要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，称其为旋转因子，p称为旋转因子的指数。,图4.2.4 8点DITFFT运算流图,观察图4.2.4不难发现，第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运算和程序框图,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(J JN/2)，然后次高位加1(J+N/4)。 次高位加1时，同样要判断0、1值， 如果为0(JN/4)，则直接加1(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 值分为两组： 偶数组是 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.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时 有两种旋转因子：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) 与其相乘时，,只需要两次实数乘，两次实数加即可实现。,从实数运算考虑，计算N=2M点基2DITFFT所需实数乘法次数为,(4.3.4),对应的每个蝶形节省两次实数乘。 在DIT-FFT运算流图中，从L=3至L=M级，每级都包含旋转因子 ，第L级中， 对应N/2L个蝶形运算。 因此从第三级至最后一级，旋转因子 节省的实数乘次数,在基2FFT程序中， （1）若包含了所有旋转因子， 称为一类碟形单元运算； （2）若去掉 的旋转因子，称为二类碟形单元运算； （3）若再去掉 的旋转因子，称为三类碟形单元运算； （4）若再判断处理 ，称为四类碟形运算。 后三种运算称为多类碟形单元运算。 碟形单元类型越多，编程就越复杂，但当N较大时，乘法运算的减少量是相当可观的。例如，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)分别得到两个实序列的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)，则,根据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，以及进一步减少运算量的途径等内容，对研究新的快速算法都是很有用的。本节简要介绍其他几种快速算法的运算量及其主要特点。,其中未计入乘以j和1的计算。比较基2FFT的复数乘法次数 ，基4FFT的复数乘法次数减少25%。 1984年，法国的杜梅尔（P.Dohamel）和霍尔曼（H. Hollmann）将基2分解和基4分解糅合，提出了分裂基FFT算法，其复数乘法次数接近FFT理论最小值，但其运算流图却与基2FFT很相似，编程简单，运算程序也很短，是一种很实用的高效算法。分裂基FFT算法复数乘法次数为 CM(分裂基)= （4.4.2）,只考虑（4.4.2）式的第一项，分裂基FFT算法的复数乘法次数就比基2FFT减少33%，比基4FFT减少11%。应当说明，在比较时，未考虑（4.4.2）式后2项减少的运算量，所以分裂基FFT算法的效率更高。 由以上比较可见，分裂基FFT算法的效率最高，所以得到广泛应用。但是，对实序列x(n)，上述各种FFT算法仍将其看成虚部为零的复序列存储和计算。而一次复数乘法需要四次实数乘法和二次实数加法。所以，必然浪费存储资源和增加多余的运算量。我们知道，实序列的N点DFT具有共轭对称性，即,所以，只要计算出X（k）的前面N/2个值，则其后面的N/2个值可以由对称性求得。因此，FFT算法得到的N个X（k）值有一半是多余的。由以上分析可见，对实序列一定存在更高效的快速算法。 离散哈特莱变换（DHT）就是针对实序列的一