数字信号处理5章节

《数字信号处理5章节》由会员分享，可在线阅读，更多相关《数字信号处理5章节（96页珍藏版）》请在金锄头文库上搜索。

1、第5章 快速傅里叶变换(FFT) Fast Fourier Transforming,快速付里叶变换FFT,有限长序列通过离散傅里叶变换 (DFT)将其频 域离散化成有限长序列.但其计算量太大(与N的平方成正比）, 很难 实时地处理问题 , 因 此 引 出 了 快 速 傅 里 叶 变 换(FFT) . FFT 并 不 是 一 种 新 的 变 换 形 式 ,它 只 是 DFT 的 一 种 快 速 算 法 . 并 且 根 据 对 序 列 分 解 与 选 取 方 法 的 不 同 而 产 生 了 FFT 的 多 种 算 法 . FFT 在 离 散 傅 里 叶 反 变 换 、 线 性 卷 积 和 线 性

2、 相 关 等 方 面 也 有 重 要 应 用.。,二、FFT产生故事,当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基(J.W.Turkey)正在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。1965年库利-图基在、Mathematic of Computation 杂志上发表了著名的“机器计算付里级数的一种算法”文章，提出一种快速计算DFT的方法和计算机程序-揭开了FFT发展史上的第一页

3、，促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件， 使DFT的运算大简化了。,直接计算DFT的问题及改进的基本途径,一、直接计算DFT计算量,问题提出： 设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算，共需多大的运算工作量?,1.比较DFT与IDFT之间的运算量,其中x(n)为复数， 也为复数 所以DFT与IDFT二者计算量相同。,2.以DFT为例，计算DFT复数运算量,计算一个X(k)(一个频率成分)值，运算量为 例k=1则 要进行N次复数乘法 (N-1)次复数加法 所以，要完成整个DFT运算，其计算量为： N*N次复数相

4、乘和N*(N-1)次复数加法,3.一次复数乘法换算成实数运算量,复数运算要比加法运算复杂，需要的运算时间长。 一个复数乘法包括4个实数乘法 和2个实数加法。 (a+jb)(c+jd)=(ac-bd)+j(bc+ad),4次实数乘法,2次实数加法,4.计算DFT需要的实数运算量,每运算一个X(k)的值，需要进行 4N次实数相乘和 2N+2(N-1)=2(2N-1)次实数相加. 整个DFT运算量为： 4N2次实数相乘和2N(2N-1)次实数相加. 由此看出： 直接计算DFT时，乘法次数与加法次数都是和N2成比例的。当N很大时，所需工作量非常可观。,例子,例1:当N=1024点时，直接计算DFT需要

5、： N2=220=1048576次，即一百多万次的复乘运算 这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求迫切需要改进DFT的计算方法，以减少总的运算次数。 例2：石油勘探，24道记录，每道波形记录长度5秒，若每秒抽样500点/秒， 每道总抽样点数=500*5=2500点 24道总抽样点数=24*2500=6万点 DFT运算时间=N2=(60000)2=36*108次,二、改善DFT运算效率的基本途径,利用DFT运算的系数 的固有对称性和周期性，改善DFT的运算效率。 1. 合并法：合并DFT运算中的某些项。 2. 分解法： 将长序列DFT利用对称性和周期性，分解

6、为短序列DFT。,利用DFT运算的系数 的固有对称性 和周期性，改善DFT的运算效率,的对称性：,的周期性：,因为：,由此可得出：,例子,例:,利用以上特性,得到改进DFT直接算法的方法.,合并法：,合并DFT运算中的有些项 对虚实部而言 所以带入DFT中：,分解成虚实部,展开：,代入DFT中,根据：,有：,合并有些项,由此找出其它各项的类似归并方法：乘法次数可以减少一半。 例：,结论,2、将长序列DFT利用对称性和周期性分解为短序列DFT-思路,因为DFT的运算量与N2成正比的 如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。,2、将长序列DFT利

7、用对称性和周期性分解为短序列DFT-方法,把N点数据分成二半：,其运算量为：,再分二半：,+,=,+,+,+,=,这样一直分下去，剩下两点的变换。,2、将长序列DFT利用对称性和周期性分解为短序列DFT-结论,快速付里时变换(FFT)就是在此特性基础上发展起来的，并产生了多种FFT算法，其基本上可分成两大类： 按抽取方法分： 时间抽取法(DIT);频率抽取法(DIF) 按“基数”分：基-2FFT算法；基-4FFT算 法；混合基FFT算法；分裂基FFT算法 其它方法：线性调频Z变换(CZT法),按时间抽取的 基-2 FFT算法 Decimation-in-Time(DIT) (Coolkey-T

8、ukey),一、算法原理,设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。 其中基数2-N=2M，M为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M,例子,设一序列x(n)的长度为L=9,应加零补长为 N=24=16 应补7个零值。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n,x(n),二、算法步骤 1.分组，变量置换,DFT变换：,先将x(n)按n的奇偶分为两 组，作变量置换: 当n=偶数时，令n=2r; 当n=奇数时，

9、令n=2r+1; 得到：x(2r)=x1(r); x(2r+1)=x2(r);r=0N/2-1; 则可得其DFT为两部分： 前半部分： 后半部分：,2.代入DFT中,生成两个子序列,x(0),x(2)x(2r)偶数点 x(1),x(3)x(2r+1)奇数点,代入DFT变换式：,3.求出子序列的DFT,上式得：,4.结论,一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：,再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。,5.求出后半部的表示式,看出：后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的

10、k值所对应的X1(k),X2(k)的值。,6.结论2,频域中的N个点频率成分为：,结论：只要求出（0N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。,7.结论3,由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。,三、蝶形结,即蝶式计算结构也即为蝶式信号流图 上面频域中前/后半部分表示式可以用蝶形信号流图表示。,X1(k),X2(k),作图要素

11、： (1)左边两路为输入 (2)右边两路为输出 (3)中间以一个小圆表示加、减运算（右上路为相加输出、右下路为相减输出),(4)如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。,(5)当支路上没有箭头及系数时，则该支路的传输比为1。,例子：求 N=23=8点FFT变换 （1）先按N=8N/2=4，做4点的DFT：,先将N=8DFT分解成2个4点DFT： 可知：时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)X(3)，由X(k)给出 X(4)X(7),由X(k+N/2)给出,(a)比较

12、N=8点直接DFT与分解2个4点DFT的FFT运算量,N=8点的直接DFT的计算量为：N2次(64次）复数相乘,N(N-1)次(8(8-1)=56次)复数相加.共计120次。,（b)求 一个蝶形结需要的运算量,要运算一个蝶形结，需要一次乘法 ， 两次加法。,（c）分解为两个N/2=4点的DFT的运算量,分解2个N/2点（4点）的DFT：,偶数 其复数相乘为 复数相加为,奇数 其复数相乘为 复数相加为,(d)用2个4点来求N=8点的FFT所需的运算量,再将N/2点（4点）合成N点(8点)DFT时，需要进行N/2个蝶形运算,还需N/2次（4次）乘法 及 次(8次）加法运算。,(e)将N=8点分解成

13、2个4点的DFT的信号流图,4点 DFT,x(0) x(2) x(4) x(6),4点 DFT,x(1) x(3) x(5) x(7),X(0) X(1) X(2) X(3),X(4) X(5) X(6) X(7),X1(0),X1(1),X1(2),X1(3),X2(0),X2(1),X2(2),X2(3),偶数序列,奇数序列,X(4)X(7) 同理,x1(r),x2(r),(2)N/2(4点)N/4(2点)FFT (a)先将4点分解成2点的DFT：,因为4点DFT还是比较麻烦，所以再继续分解。 若将N/2(4点)子序列按奇/偶分解成两个N/4点（2点）子序列。即对将x1(r)和x2(r)分

14、解成奇、偶两个N/4点（2点）点的子序列。,(b)求2点的DFT,（c)一个2点的DFT蝶形流图,2点DFT,2点DFT,x(0) x(4),x(2) x(6),X3(0),X3(1),X4(0),X4(1),X1(0) X1(1),X1(2) X1(3),（d)另一个2点的DFT蝶形流图,2点DFT,2点DFT,x(1) x(5),x(3) x(7),X5(0),X5(1),X6(0),X6(1),X2(0) X2(1),X2(2) X2(3),同理：,(3)将N/4（2点）DFT再分解成2个1点的DFT (a)求2个一点的DFT,最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就

15、等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。,(b)2个1点的DFT蝶形流图,1点DFT,x(0),1点DFT,x(4),X3(0) X3(1),进一步简化为蝶形流图：,X3(0) X3(1),x(0),x(4),(4)一个完整N=8的按时间抽取FFT的运算流图,x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7),X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7),m=0,m=1,m=2,四、FFT算法中一些概念 （1）“级”概念,将N 点DFT先分成两个N/2点DFT，再是四个N/4点DFT直至N/2个两点DFT.每分一次称为“一”级运算。 因为N=2M所以N点DFT可分成M级 如上图所示依次m=0,m=1.M-1共M级,（2）“组”概念,每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的 因子分布，第m级的组数为：,例：N=8=23，分3级。 m=0级,分成四组,每组系数为 m=1级,分成二组,每组系数为 m=2级,分成一组,每组系数为,(3) 因子的分布,结论：每由后