《数字信号处理 教学课件 ppt 作者 尹为民 15-4.3基2频抽FFT+4.4复合数FFT》由会员分享，可在线阅读，更多相关《数字信号处理 教学课件 ppt 作者 尹为民 15-4.3基2频抽FFT+4.4复合数FFT（18页珍藏版）》请在金锄头文库上搜索。
1、1,reviewDIT-FFT,DIT-FFT的输入为倒位序，输出为自然数顺序 原位运算 蝶距 j = k + 2m-1 旋转因子 r = k 2L-m,2, 4.3 按频率抽选(DIF)的基-2FFT算法,算法原理 按频率抽选的FFT算法的特点 按频率抽选法与按时间抽选法的异同,重点：理解算法原理，掌握计算量比较以及8点流图,3,一、算法原理,分解过程遵循规则：对频率进行奇偶分解,4,一、算法原理,将频率偶奇分解：X(k)=X(2r)+X(2r+1)， r=0,1,N/2-1,5,一、算法原理,频率抽取法蝶形运算单元,2019/5/26,6,按频率( k 的奇偶)抽取的第一次分解 (N=8)
2、,X (1) X (3) X (5) X (7),k=0, 2, 4, 6,k=1, 3, 5, 7,X (0) X (2) X (4) X (6),2019/5/26,7,X (0) X (4),X (2) X (6),X (1) X (5),X (3) X (7),按频率( k 的奇偶)抽取的第二次分解 (N=8),2019/5/26,8,按频率抽取的FFT(N=8)运算流图,9,二、按频率抽选的FFT算法的特点,1. 原位运算（同址运算）,频率抽取法蝶形运算单元,10,按频率抽取的FFT(N=8)运算流图,实现全部运算只需要一列存储N个复数的寄存器。,11,2. 倒位序规律,DIF-FF
3、T的输入为自然数顺序，输出为倒位序,3. 蝶形运算两节点的“距离”,4. WNr的确定,将地址 k 乘以 2m-1 (左移(m -1)位)。,二、按频率抽选的FFT算法的特点,12,三、按频率抽选法与按时间抽选法的异同,1. 相同点,(1)运算量相同,(2)都是原位运算,都有L级运算，每级有N/2个蝶形,13,2. 相异点蝶形运算结构不同,DIF的复数乘法只出现在减法之后。,DIT是先作复乘后再作加减法；,三、按频率抽选法与按时间抽选法的异同,DIT法与DIF法的基本蝶形互为转置,14, 4.4 N为复合数的FFT算法,按时间抽取和按频率抽取的基 -2FFT算法，由于具有程序简单、计算效率高、
4、对存储量要求不很高等优点，因而在实际中得到了最广泛的应用。若不满足N=2L，则有两种方法： (1)用补零的办法将x(n)延长为2L； (2)采用混合基FFT算法。,15,下面只说明Npq情况下的算法,设Npq，则可将N点DFT分解成p 个q点或q个p点DFT来计算。为此，先将x(n)分为p组，每组长为q，即,例如，N=12=34，即p=3，q=4；将x(n)分为3组，每组各有4个序列，即,然后，将N点DFT也分解为p组来计算，即,16,由于 ，因此,是一个q点DFT，这样X(k)可写成：,可见，一个N=pq点的DFT可用p个q点的DFT来组成。,下面只说明Npq情况下的算法,17,一个 N=pq 点的DFT分组示意图,18,在最一般的情况下，设N=r1r2rL，其中r1rL是L个素因子。首先把N分解为两个因子，即N=r1q1，其中q1r2r3rL，并用以上讨论的方法将DFT分解为r1个q1点DFT；然后，将q1分解为q1=r2q2，其中q2=r3r4rL，即将每一个q1点DFT分解为r2个q2点DFT；这样，通过L次分解，最后达到rL点DFT。这种算法可以使DFT的运算获得最高效率。,N为复合数的FFT算法,
