数字信号处理---第四章 快速傅立叶变换（FFT）.pptVIP

第4章 快速傅立叶变换（FFT） 4.2 基2FFT算法 4.2.1 直接计算DFT的特点及减少运算量的基本途径 计算一个X(k)的值： N次复数乘法运算 N-1 次复数加法运算. 2 改进的途径 的对称性、周期性、可约性 4.2.2 时域抽取法基2FFT基本原理 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） (1) X1 (k),X2 (k)均为N/2点的DFT。 (2) X(k)=X1 (k)+WNk X2 (k)只能确定出X(k)的k= 0.1….N/2-1 个，即前一半的结果。 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） 用同样的方法可计算出 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） 4.2.3 DIT―FFT算法与直接计算DFT运算量的比较 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为 第4章 快速傅立叶变换（FFT） 3. 蝶形运算规律 设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式： AL (J) AL-1(J)+A L-1(J+B)WpN AL(J+B) AL-1(J)-A L-1(J+B)WpN 式中 p=J·2 M-L；J=0,1,…，2 L-1-1；L=1,2,…，M 4. 编程思想及程序框图 DIT―FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2…n1n0)表示。 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） 利用FFT计算IFFT的思路1 把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k)，原来按x(n)的奇、偶次序分组的时间抽取法FFT，现在就变成了按X(k)的奇偶次序抽取了。 频率抽取的FFT运算用于IDFT运算时，也应改变为时间抽取的IFFT。 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） 利用FFT计算IFFT的思路2 第4章 快速傅立叶变换（FFT） 第4章 快速傅立叶变换（FFT） IDFT过程： -1 -1 -1 -1 1/4 1/4 1/4 1/4 -1 -1 -1 -1 -1 -1 -1 -1 -1 点 DFT 点 DFT 点 DFT 点 DFT -1 -1 -1 图4.2.4 N点DIT―FFT运算流图(N=8) 复数加次数为 例如，N=210=1024时 第4章 快速傅立叶变换（FFT） 图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线 1.原位计算 由图4.2.4可以看出，DIT―FFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。 　　在N点DIT-FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子　　，称其为旋转因子，p为旋转因子的指数。但各级的旋转因子和循环方式都有所不同。为了编写计算程序，应先找出旋转因子　　与运算级数的关系。用L表示从左到右的运算级数(L=1，2，…，M)。观察图4.2.4不难发现，第L级共有2L－1个不同的旋转因子。N=23=8时的各级旋转因子表示如下： 4.2.4 DIT―FFT的运算规律及编程思想 2．旋转因子的变化规律 对N=2M的一般情况，第L级的旋转因子为 下标L表示第L级运算，AL(J)则表示第L级运算后数组元素A(J)的值。而AL－1(J)表示第L级运算前A(J)的值（即第L级蝶形的输入数据） 图4.2.6 DIT―FFT运算和程序框图 图4.2.7 形成倒序的树状图(N=23) 5. 序列的倒序 表4.2.1 顺序和倒序二进制数对照表 图4.2.8 倒序规律 图4.2.9 倒序程序框图 4.2.5 频域抽取法FFT（DIT_FFT) 算法原理 (一)N/2点DFT 第4章 快速傅立叶变换（FFT） 第