数字信号处理课件作者尹为民15-4.3基2频抽FFT+4.4复合数FFT.pptVIP

review——DIT-FFT § 4.3 按频率抽选(DIF)的基-2FFT算法 一、算法原理 一、算法原理 一、算法原理 二、按频率抽选的FFT算法的特点 § 4.4 N为复合数的FFT算法 下面只说明N＝p·q情况下的算法 尚辅网 / DIT-FFT的输入为倒位序，输出为自然数顺序 原位运算 蝶距 j = k + 2m-1 旋转因子 r = k ? 2L-m 算法原理 按频率抽选的FFT算法的特点 按频率抽选法与按时间抽选法的异同 重点：理解算法原理，掌握计算量比较以及8点流图 分解过程遵循规则：对频率进行奇偶分解 将频率偶奇分解：X(k)=X(2r)+X(2r+1)， r=0,1,…,N/2-1 频率抽取法蝶形运算单元 按频率( k 的奇偶)抽取的第一次分解 (N=8) 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) X (0) X (4) X (2) X (6) X (1) X (5) X (3) X (7) 按频率( k 的奇偶)抽取的第二次分解 (N=8) 按频率抽取的FFT(N=8)运算流图 1. 原位运算（同址运算） 频率抽取法蝶形运算单元 按频率抽取的FFT(N=8)运算流图 实现全部运算只需要一列存储N个复数的寄存器。 2. 倒位序规律 DIF-FFT的输入为自然数顺序，输出为倒位序 3. 蝶形运算两节点的“距离” 2L-m 第 m 级 蝶距(节点距离) 蝶形级数 4. WNr的确定 将地址 k 乘以 2m-1 (左移(m -1)位)。 二、按频率抽选的FFT算法的特点 三、按频率抽选法与按时间抽选法的异同 1. 相同点 (1)运算量相同 (2)都是原位运算 都有L级运算，每级有N/2个蝶形 复乘数 复加数 2. 相异点——蝶形运算结构不同 DIF的复数乘法只出现在减法之后。 DIT是先作复乘后再作加减法； 三、按频率抽选法与按时间抽选法的异同 DIT法与DIF法的基本蝶形互为转置 按时间抽取和按频率抽取的基 -2FFT算法，由于具有程序简单、计算效率高、对存储量要求不很高等优点，因而在实际中得到了最广泛的应用。若不满足N=2L，则有两种方法： (1)用补零的办法将x(n)延长为2L； (2)采用混合基FFT算法。 设N＝pq，则可将N点DFT分解成p 个q点或q个p点DFT来计算。为此，先将x(n)分为p组，每组长为q，即 p组 x(pr) x(pr+1) , r=0,1, … ,q?1 … x(pr+p-1) 例如，N=12=3×4，即p=3，q=4；将x(n)分为3组，每组各有4个序列，即 p=3组 x(0) x(3) x(6) x(9) x(1) x(4) x(7) x(10) x(2) x(5) x(8) x(11) 长为q=4 然后，将N点DFT也分解为p组来计算，即 由于 ，因此 是一个q点DFT，这样X(k)可写成： 可见，一个N=pq点的DFT可用p个q点的DFT来组成。 下面只说明N＝p·q情况下的算法 一个 N=pq 点的DFT分组示意图 在最一般的情况下，设N=r1r2···rL，其中r1～rL是L个素因子。首先把N分解为两个因子，即N=r1q1，其中q1＝r2r3···rL，并用以上讨论的方法将DFT分解为r1个q1点DFT；然后，将q1分解为q1=r2q2，其中q2=r3r4···rL，即将每一个q1点DFT分解为r2个q2点DFT；这样，通过L次分解，最后达到rL点DFT。这种算法可以使DFT的运算获得最高效率。 N为复合数的FFT算法 1式为前一半输入与后一半输入之和的N/2点DFT， 2式为前一半输入与后一半输入之差再与WNn之积的N/2点DFT。 1式为前一半输入与后一半输入之和的N/2点DFT， 2式为前一半输入与后一半输入之差再与WNn之积的N/2点DFT。 此式的蝶形运算也需要一次复乘和两次复加。 DIF的基本蝶形（图3-16）与DIT的基本蝶形（图3-6）则有所不同，这才是实质的不同，DIF的复数乘法只出现在减法之后，DIT则是先作复乘后再作加减法。 这样，我们就把一个N点DFT按k的奇偶分解为两个N/2点的DFT了。 N=8时，上述分解过程如图。