《数字信号处理第4章汇编》由会员分享，可在线阅读，更多相关《数字信号处理第4章汇编（56页珍藏版）》请在金锄头文库上搜索。
1、第4章 快速傅里叶变换(FFT),4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 其他快速算法简介 习题与上机题,4.1 引 言 DFT是数字信号分析与处理中的一种重要变换 直接计算N点DFT：与变换区间长度N的平方成正比 N较大时，计算量太大难以进行实时处理 快速傅里叶变换FFT(Fast Fourier Transform) 高效计算DFT的算法 使DFT运算效率提高12个数量级,4.2 基2FFT算法 4.2.1 直接计算DFT的特点及减少运算量基本途径 一、直接计算DFT 有限长序列x(n)的N点DFT为 x(n)为复数序列的一般情况： 计算X(k)的1个
2、值： 需要 次复数乘法和 次复数加法； 计算X(k)的所有N个值： 共需N2次复数乘法和N(N1)次复数加法运算 （N1时， N(N1)= N2 ）。,(4.2.1),N,(N1),N较大时，运算量很大： 例如N=1024时，N2=1 048 576 实时处理信号难以实现，对运算速度要求高 二、减少运算量的基本途径： 1、N较大，运算量大 减小N，把N点DFT分解为几个较短的DFT 2、旋转因子具有周期性和对称性 周期性： 对称性：,（4.2.2）,或者,(4.2.3a),(4.2.3b),2：利用 的周期性和对称性来减少DFT的运算次数,减少运算量的基本途径： 1：不断地把长序列的DFT分解
3、成几个短序列的DFT,4.2.2 时域抽取法基2FFT基本原理 基2FFT算法： 频域抽取法FFT (DIFFFT) 时域抽取法： 设序列x(n)的长度为N，且满足N=2M，M为自然数。 （若不满足可补零） 按n的奇偶分解x(n) 为两个N/2点的子序列如下：,时域抽取法FFT(DITFFT ),则x(n)的N点DFT为,而,(4.2.4),其中1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT：,(4.2.5),(4.2.6),所以,由于X1(k)和X2(k)均以N/2为周期，且,(4.2.7),(4.2.8),1、X1(k)和X2(k)两个N/2点DFT 2、上式的运算,图4
4、.2.1 蝶形运算符号,因此X(k)又可表示为:,计算N点DFT分解为：,可用蝶形运算符号表示,图4.2.2 8点DFT一次时域抽取分解运算流图,要完成一个蝶形运算，需要 和 运算 经过一次分解后，计算1个N点DFT共需要计算： 两个N/2点DFT； 计算N点DFT时： 总共需要的复数乘法次数为,复数加法次数为,结论：经过一次分解，运算量减少近一半,一次复数乘法,两次复数加法,N/2个蝶形运算,因为N=2M，N/2仍然是偶数，可对N/2点DFT再作进一步分解。 同上，将x1(r)按奇偶分解成两个N/4点的子序列x3(l)和x4(l)：,X1(k)又可表示为,(4.2.9),同理，X3(k)和X
5、4(k)以N/4为周期， ，可得：,(4.2.10),用同样的方法可计算出,(4.2.11),式中：,其中：,经过第二次分解，N/2点DFT分解为： 2个N/4点DFT和N/4个蝶形运算，如图4.2.3,依此类推，经过M次分解，N点DFT分解成： N个1点DFT和M级蝶形运算，而1点DFT就是时域序列本身,完整的8点DITFFT运算流图如图4.2.4所示,图4.2.3 8点DFT二次时域抽取分解运算流图,图中：1、用到关系式： 2、输入序列不是顺序排列，但有排列规律 3、数组A用于存放输入序列和每级运算结果,图4.2.4 8点DIT-FFT运算流图,4.2.3 DIT-FFT算法与直接计算DF
6、T运算量的比较 由DIT-FFT算法的分解过程及图4.2.4可见，N=2M 时，其运算流图应有M级蝶形，每一级都由N/2个蝶形运算构成。因此，每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为,复数加次数为,而直接计算DFT的复数乘为N2次，复数加为N(N1)次。当N1时，N2(N/2) lbN，所以，DIT-FFT算法比直接计算DFT的运算次数大大减少。例如，N=210=1024时， 这样，就使运算效率提高200多倍。图4.2.5为FFT算法和直接计算DFT所需复数乘法次数CM与变换点数N的关系曲线。由此图更加直观地看出FFT算法的优
7、越性，显然，N越大时，优越性就越明显。,图4.2.5 DIT-FFT算法与直接计算DFT所需复数乘法次数的比较曲线,4.2.4 DIT-FFT的运算规律及编程思想 1 原位计算 DIT-FFT的运算规律： (1) N=2M，共进行M级运算，每级由N/2个蝶形运算组成； (2) 同一级中，每个蝶形的两个输入数据只对该蝶形有用， 每个蝶形的输入、输出数据在一条水平线上 输入、输出可用同一存储单元 即：第一级：N个存储单元存储N个序列值x(n) M级蝶形运算后，该N个存储单元中依次存放X(k)的N个值 原位计算：利用同一存储单元存储蝶形计算输入、输出数据 可节省大量内存，从而使设备成本降低。,2 旋
8、转因子的变化规律 旋转因子：N点DIT-FFT运算流图中，每个蝶形都要乘以因子 ，称其为旋转因子，p为旋转因子的指数。 各级旋转因子和循环方式都有所不同，需找出旋转因子 与运算级数的关系。 用L表示从左到右的运算级数(L=1，2，M)。,第L级共有2L1个不同的旋转因子。N=23=8时的各级旋转因子：,因为 所以 (4.2.12) (4.2.13) 按(4.2.12)和(4.2.13)式可确定第L级运算的旋转因子(实际编程序时，L为最外层循环变量)。,一般的，N=2M时，第L级的旋转因子为,3 蝶形运算规律 设序列x(n)经时域抽选(倒序)后，按图4.2.4所示的次序(倒序)存入数组A中。如果
9、蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式： 式中 下标L：第L级运算 AL(J)：第L级运算后A(J)的值（第L级蝶形输出） AL1(J)：第L级运算前A(J)的值（第L级蝶形输入）,4. 编程思想及程序框图 归纳运算规律： 第L级中，每个蝶形的两个输入数据相距B=2L1个点； 每级有B个不同的旋转因子； 同一旋转因子对应着间隔为2L点的2ML个蝶形。 总结上述运算规律，可采用下述运算方法: (1) 从输入端(第1级)开始，逐级进行，共进行M级运算; (2) 进行第L级运算时，依次求出B个不同的旋转因子，同时计算其对应的2ML个蝶形。,图4.2.6 DIT-F
10、FT运算和程序框图,L为最外层循环变量,求B个不同的旋转因子,计算每个旋转因子所对应的2ML个蝶形,DIT-FFT算法运算流图：输出X(k)为自然顺序，但输入序列不是按x(n)的自然顺序排列。 这种经过M次偶奇抽选后的排序称为序列x(n)的倒序(倒位)。因此，在运算M级蝶形之前应先对序列x(n)进行倒序。 5 序列的倒序 DIT-FFT算法输入序列的排序：倒序的规律： N=2M，顺序数可用M位二进制数(nM1nM2n1n0)表示。 例如N=8，用n2n1n0表示x(0)-x(7)：000-111 M次偶奇时域抽选过程如图4.2.7所示。,图4.2.7 形成例序的树状图（N=23）,(1) 第一
11、次按最低位n0的0和1将x(n)分解为偶奇两组；,(2) 第二次按次低位n1的0、1值分别对偶奇组分组； (3) 依次类推，第M次按nM1位分解，最后所得二进制倒 序数如图4.2.7所示。,表4.2.1 顺序和倒序二进制数对照表,表4.2.1列出了N=8时以二进制数表示的顺序数和倒序数，由表可见，只要将顺序数(n2n1n0)的二进制位倒置，则得对应的二进制倒序值(n0n1n2)。 硬件电路和汇编语言程序容易实现,(1) 自然顺序数I增加1，二进制数最低位加1； (2) 相应的倒序数J则在M位二进制数最高位加1。 例如，自然顺序数0：000最低位加1：001 对应的倒序数0：000最高位加1：1
12、00 自然顺序数1：001最低位加1：010 对应的倒序数4：100最高位为1：010 最高位加1要向次高位进位，其实质是将最高位变为0，再在次高位加1。 用这种算法，可以从当前任一倒序值求得下一个倒序值,但用有些高级语言程序实现倒序时，直接倒置二进制数位是不行的，因此必须找出产生倒序数的十进制运算规律。由表4.2.1可见：,若用J表示当前倒序数的十进制数值，对于N=2M，M位二进制数的权值从左向右依次为N/2，N/4，N/8，2，1。 二进制最高位加1： 十进制：J+N/2最高位是0(JN/2)，则直接加1(J J+N/2)； 最高位是1(JN/2), 先将最高位变成0(J JN/2) 然后
13、次高位加1(J+N/4)， (次高位加1时，同样要判断0、1值) J+N/4次高位为0(JN/4)，则直接加1(J J+N/4); 次高位为1(JN/4),先将次高位变成0(J JN/4) 然后下一位加1(J+N/8)， 再判断下一位的0或1值，依此类推，直到完成最高位加1，逢2向右进位的运算。(图4.2.9所示的虚线框为倒序的程序框图),形成倒序J后，将原数组A中存放的输入序列重新按倒序排列。 (1) 原输入序列x(I)先按自然顺序存入数组A中。 对N=8，A(0)，A(1)，A(7)中依次存放着x(0)，x(1)，x(2)，x(7) (2) 对x(n)重新排序(倒序)：规律如图4.2.8所
14、示： 第一个序列值x(0)和最后一个序列值x(N1)不需要重排； 每计算出一个倒序值J，便与循环语句自动生成的顺序I 比较：当I=J时，不需要交换数据； 当IJ时, A(I)与A(J)交换数据。 为了避免再次调换前面已调换过的一对数据，只对IJ的 情况调换A(I)和A(J)的内容。,图4.2.8 倒序规律,图4.2.9 倒序程序框图,4.2.5 频域抽取法FFT(DIF-FFT) 设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT如下：,式中 将X(k)分解成偶数组与奇数组： 当k取偶数(k=2m, m=0, 1, , N/21)时,(4.2.14),当k取奇数
15、(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。 x1(n)、x2(n)和x(n)之间的关系也可用蝶形运算流图符号表示,图4.2.11 DIF-FFT第一次分解运算流图（N=8）,由于N=2M，N/2仍然是偶数，继续将N/2点DFT分成偶数组合奇数组，这样每个N/2点DFT又可由两个N/4点DFT形成，其输入序列分别是x1(n)和x2(n)按上下对半分开形成的四个子序列。图4.2.12示出
16、了N=8时第二次分解运算流图。 这样继续分解下去，经过M1次分解，最后分解为2M1个两点DFT，两点DFT就是一个基本蝶形运算流图。当N=8，经两次分解，便分解为四个两点DFT。N = 8的完整DIF-FFT运算流图如图4.2.13所示。,图4.2.12 DIF-FFT第二次分解运算流图（N = 8）,图4.2.13 DIF-FFT运算流图（N =8）,这种算法是对X(k)进行奇偶抽取分解的结果，所以称之为频域抽取法FFT。观察图4.2.13可知： DIF-FFT算法与DIT-TTF算法类似，可以原位计算； DIF-FFT算法共有M级运算，每级共有N/2个蝶形运算，所以两种算法的运算次数亦相同； 不同的是DIF-FFT算法输入序列为自然顺序，而输出为倒序排列； M级运算完后，要对输出数据进行倒序才能得到自然顺序的X(k)； 蝶形运算略有不同，DIT-F
