数字信号处理课件快速傅里叶变换.pptx

《数字信号处理课件快速傅里叶变换.pptx》由会员分享，可在线阅读，更多相关《数字信号处理课件快速傅里叶变换.pptx（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、14.1 引言 DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。第1页/共89页24.2 基2FFT算法 4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为 考虑x(n)为复数序列的一般情况，对某一个k值，直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。(4.2.1)第2页/共89页3

2、如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为(4.2.2)其对称性表现为或者第3页/共89页4 4.2.2 时域抽取法基2FFT基本原理 FFT算法基本上分为两大类：时域抽取法FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation In Frequency FFT,简称DIFFFT)。下面先介绍DIFFFT算法。设序列x(n)的长度为N，且满足为自然数按n的奇偶把x(n)分解为两个N/2点的子序列第4页/共89页5

3、则x(n)的DFT为由于所以第5页/共89页6 其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即(4.2.5)(4.2.6)由于X1(k)和X2(k)均以N/2为周期，且，所以X(k)又可表示为(4.2.7)(4.2.8)第6页/共89页7图4.2.1蝶形运算符号第7页/共89页8图4.2.2N点DFT的一次时域抽取分解图(N=8)第8页/共89页9 与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为(4.2.9)第9页/共89页10式中同理，由X3(k)和X4(k)的周期性和WmN/2的对称性Wk+N/

4、4N/2=-WkN/2最后得到：(4.2.10)第10页/共89页11 用同样的方法可计算出(4.2.11)其中第11页/共89页12图4.2.3N点DFT的第二次时域抽取分解图(N=8)第12页/共89页13图4.2.4N点DITFFT运算流图(N=8)第13页/共89页14 4.2.3 DITFFT算法与直接计算DFT运算量的比较 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为复数加次数为例如，N=210=1024时第14页/共89页15图4.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线第15页/共89页16 4.2.

5、4 DITFFT的运算规律及编程思想 1.原位计算 由图4.2.4可以看出，DITFFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。2.旋转因子的变化规律 如上所述，N点DITFFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转因子，p称为旋转因子的指数。第16页/共89页17 观 察 图 4.2.4不 难 发 现，第 L级 共 有 2 L-1个 不 同 的 旋 转 因 子。N=23=8时的各级旋转因子表示如下：L=1时，WpN=WJ N/4=WJ2L，J=0 L=2时，WpN=WJ N/2=WJ2L，J=0，1 L=3时，WpN

6、=WJN=WJ2L，J=0，1，2，3 对N=2M的一般情况，第L级的旋转因子为(4.2.12)(4.2.13)第17页/共89页18 3.蝶形运算规律 设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：X(J)XL-1(J)+X L-1(J+B)WpN XL(J+B)XL-1(J)-X L-1(J+B)WpN式中 p=J2 M-L；J=0,1,，2 L-1-1；L=1,2,，M第18页/共89页19 下标L表示第L级运算，XL(J)则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算，可按下面

7、的算法进行。设 T=X L-1(J+B)WpN=TR+jTI X L-1(J)=XR(J)+jXI(J)式中下标R表示取实部，I表示取虚部，第19页/共89页20则第20页/共89页21 4.编程思想及程序框图图4.2.6DITFFT运算和程序框图第21页/共89页22 5.序列的倒序 DITFFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。图4.2.7形成倒序的树状图(N=23)第22页/共89页23表4.2.1顺序和倒序二进制数对照表第23页/共89页24图4.2.8倒序规律第24页/

8、共89页25图4.2.9倒序程序框图第25页/共89页26 4.2.5 频域抽取法FFT(DIFFFT)在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIFFFT。设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：第26页/共89页27偶数奇数将X(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,N/2-1)时(4.2.14)第27页/共89页28当k取奇数(k=2r+1,r=0,1,N/2-1)时(4.2.15)将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得(4.2.16)第28页/共8

9、9页29图4.2.10DIFFFT蝶形运算流图符号第29页/共89页30图4.2.11DIFFFT一次分解运算流图(N=8)第30页/共89页31图4.2.12DIFFFT二次分解运算流图(N=8)第31页/共89页32图4.2.13DIFFFT运算流图(N=8)第32页/共89页33图4.2.14DITFFT的一种变形运算流图第33页/共89页34图4.2.15DITFFT的一种变形运算流图第34页/共89页35 4.2.6 IDFT的高效算法 上 述 FFT算 法 流 图 也 可 以 用 于 离 散 傅 里 叶 逆 变 换(Inverse Discrete Fourier Transfor

10、m，简称IDFT)。比较DFT和IDFT的运算公式：第35页/共89页36图4.2.16DITIFFT运算流图第36页/共89页37图4.2.17DITIFFT运算流图(防止溢出)第37页/共89页38 如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：由于 对上式两边同时取共轭，得第38页/共89页394.3 进一步减少运算量的措施 4.3.1 多类蝶形单元运算 由DITFFT运算流图已得出结论，N=2M点FFT共需要MN/2次复数乘法。由(4.2.12)式，当L=1时，只有一种旋转因子W0N=1，所以，第一级不需要乘法运算。第39页/共89页40 综上所述，先除去第一、二两级后，

11、所需复数乘法次数应是 从L=3至L=M共减少复数乘法次数为(4.3.1)(4.3.2)因此，DITFFT的复乘次数降至(4.3.3)第40页/共89页41第41页/共89页42 从实数运算考虑，计算N=2M点DITFFT所需实数乘法次数为(4.3.4)第42页/共89页43 4.3.2 旋转因子的生成 在FFT运算中，旋转因子WmN=cos(2m/N)-jsin(2m/N)，求正弦和余弦函数值的计算量是很大的。第43页/共89页44 4.3.3 实序列的FFT算法 设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即对y(n)进行N/2点FFT，输出Y(

12、k)，则根据DITFFT的思想及式(4.2.7)和(4.2.8)，可得到第44页/共89页45 由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为 第45页/共89页464.4 分裂基FFT算法 4.4.1 分裂基FFT算法原理 当n=pq，且p=N/4，q=4时，n可表示为并有第46页/共89页47再将上式中的k表示为第47页/共89页48可得对k0=0，1,2,3,并用k表示k1，用n表示n0，可以写出第48页/共89页49(4.4.1)第49页/共89页50(4.4.2)第50页/共89页51(4.4.3)令第51页/共89页52 则(4.4.2)式可写成如下

13、更简明的形式：(4.4.4)第52页/共89页53图4.4.1分裂基第一次分解L形流图第53页/共89页54例如，N=16，第一次抽选分解时，由式(4.4.3)得x2(n)=x(n)+x(n+8),0n7x14(n)=x(n)-x(n+8)-jx(n+4)-x(n+12)Wn16,0n3x24(n)=x(n)-x(n+8)+jx(n+4)-x(n+12)W3n16,0n3把上式代入式(4.4.4)，可得 X(2k)=DFTx2(n),0k7 X(4k+1)=DFTx14(n),0k3 X(4k+3)=DFTx24(n),0k3 第54页/共89页55图4.4.2分裂基FFT算法L形排列示意图与

14、结构示意图(a)分裂基FFT算法L形排列示意图；(b)分裂基FFT算法运算流图结构示意图第55页/共89页56图4.4.316点分裂基第一次分解L形流图(图中省去箭头)第56页/共89页57 第二次分解：先对图4.4.3中N/2点DFT进行分解。令X1(l)=X(2l)，则有 X1(2l)=DFTy2(n),0l3 X1(4l+1)=DFTy14(n),0l1 X1(4l+3)=DFTy24(n),0l1 第57页/共89页58 其中y2(n)=x2(n)+x2(n+4),0n3y14(n)=x2(n)-x2(n+4)-x2(n+2)x(n+6)Wn8,n=0,1y24(n)=x2(n)-x2

15、(n+4)+jx2(n+2)x2(n+6)W3n8,n=0,1第58页/共89页59图4.4.4图4.4.4中N/2点DFT的分解L形流图第59页/共89页60图4.4.54点分裂基L形运算流图第60页/共89页61图4.4.616点分裂基FFT运算流图第61页/共89页62 4.4.2 分裂基FFT算法的运算量 设第j级有lj个L形，j=1,2,M-1,M=log2N，则有l1=N/4。由图4.4.2(b)可见，第j-1列中的L形包含了第j列中的一部分结点的计算，即空白部分，所占结点数刚好等于第j-1列中所有L形对应结点的一半，所以第j列L形个数就减少l j-1/2个，即 第62页/共89页

16、63第63页/共89页64由于每个L形有两次复(数)乘运算，所以全部复乘次数为(4.4.5)第64页/共89页654.5 离散哈特莱变换(DHT)4.5.1 离散哈特莱变换定义 设x(n),n=0,1,N-1，为一实序列，其DHT定义为式中，cas()=cos+sin。其逆变换(IDHT)为(4.5.3)第65页/共89页66 逆变换证明如下：(4.5.4)第66页/共89页67 将式(4.5.2)代入式(4.5.3)得第67页/共89页68 4.5.2 DHT与DFT之间的关系 为了便于比较，重写DFT如下：(4.5.5)(4.5.6)容易看出，DHT的核函数DFT的核函数的实部与虚部之和。

17、第68页/共89页69 将XH(k)分解为奇对称分量XHo(k)与偶对称分量XHe(k)之和(4.5.7)(4.5.8)(4.5.9)由DHT定义有(4.5.10a)(4.5.10b)第69页/共89页70 所以，x(n)的DFT可表示为同理，x(n)的DHT可表示为因此，已知x(n)的DHT，则DFT可用下式求得：(4.5.11)(4.5.12)(4.5.13)第70页/共89页71 4.5.3 DHT的主要优点 (1)DHT是实值变换，在对实信号或实数据进行谱分析时避免了复数运算，从而提高了运算效率，相应的硬件也更简单、更经济；(2)DHT的正、反变换(除因子1/N外)具有相同的形式，因而

18、，实现DHT的硬件或软件既能进行DHT，也能进行IDHT；(3)DHT与DFT间的关系简单，容易实现两种谱之间的相互转换。第71页/共89页72 4.5.4 DHT的性质 1.线性性质(4.5.14)2.x(N-n)的DHT(4.5.15)其中，当k=0时，XH(N-k)=XH(N)=XH(0)。第72页/共89页73 证明 由DHT定义 而第73页/共89页74 3.循环移位性质(4.5.16)(4.5.17)证明由DHT定义有第74页/共89页75第75页/共89页76 4.奇偶性 奇对称序列和偶对称序列的DHT仍然是奇对称序列或偶对称序列，即DHT不改变序列的奇偶性。5.循环卷积定理(4

19、.5.18)(4.5.19)第76页/共89页77 证明 下面利用DFT的循环卷积定理和DHT与DFT之间的关系来证明 其中，X1(k)=DFTx1(n),X2(k)=DFTx2(n),根据DHT与DFT之间的关系，则有第77页/共89页78 将上面两式代入式(4.5.20)并整理后，得所以式(4.5.18)成立。同理可证明式(4.5.19)亦成立。当x1(n)或x2(n)是偶对称序列时，则由DHT的奇偶性有(4.5.21)第78页/共89页79 4.5.5 DHT的快速算法(FHT)1.基2DITFHT算法及运算流图 仿照快速DFT的分解方法，可通过时域抽取或频域抽取的方式实现快速DHT。x

20、(n)的N=2M点DHT如下式：对x(n)进行奇偶抽取(4.5.22)(4.5.23)第79页/共89页80 与DFT的时域抽取分解比较，不是 一个指数函数，所以处理要比W(2r+1)kN麻烦一些。根据三角公式有(4.5.24)(4.5.25)第80页/共89页81 令X0H(k)=DHTx0(n),X1H(k)=DHTx1(n)，并考虑DHT的周期性，(4.5.25)式可写成为了使以下推导中公式简明，记C(k)=cos(2/N)k，S(k)=sin(2/N)/k。将式(4.5.26)中的k分别取k，N/2+k,N/2-k和N-k四个值，并考虑X0H(k)和X1H(k)以N/2为周期，得到第8

21、1页/共89页82(4.5.27)第82页/共89页83 当k=0时，式(4.5.27)中有重复，可单独写成(4.5.28)同理，在k=N/4时有(4.5.29)第83页/共89页84图4.5.1基2DIT-FHT原理和哈特莱碟形第84页/共89页85图4.5.24点DFHT蝶形图第85页/共89页86图4.5.316点基2DITFHT流图第86页/共89页87 2.基2DITFHT的运算量 观察图4.5.3可知，运算流图中都是实数运算。N=2M点FHT流图 共 分 为 M级。用 L表 示 流 图 自 右 向 左 的 蝶 形 级 数。第 L级 乘 法 次 数 为2L(N/2L-2)，但最后二级无乘法运算，所以，总的乘法次数MH为(4.5.30)(4.5.31)同理可求得总的加法次数AH为第87页/共89页88 4.5.6 实信号的快速循环卷积 用DITFFT计算两个实信号x1(n)和x2(n)的循环卷积时，最直接的方法是将信号的虚部都置为零，再按复序列用FFT计算。显然这样做是很浪费的。现在我们可用基2DITFHT直接进行实正交变换来处理实信号的循环卷积问题。计算式(4.5.18)第88页/共89页课件89感谢您的观看。第89页/共89页