DSP数字信号处理PPT电子课件教案-第三章 离散傅里叶变换(DFT)及其快速算法(FFT).ppt

8点DIT-FFT运算流图 返回 回到本节 2. DIT-FFT的运算效率 DIT-FFT与DFT所需乘法次数比较曲线 返回 回到本节 由8点DIT-FFT运算流图可见，N=2M时，其DIT-FFT运算流图 由M级蝶形构成，每级有N/2个蝶形。因此，每级需要N/2 次复数乘法运算和N次复数加法运算，M级蝶形所需复数乘 法次数CM(2)和复数加法次数CA(2)分别为 直接计算N点DFT的复数乘法次数为N2，复数加法次数为(N- 1)N。当N1时，N2/CM(2) 1，所以N越大，DIT-FFT运算 效率越高。DIT-FFT算法与DFT所需乘法次数与N的关系曲 线见前页图示。 返回 回到本节 例3.3：N=210=1024时，DIT-FFT的运算效率为 而当N =211=2048时有 DFT的乘法次数 DIT-FFT的乘法次数 返回 回到本节 3. DIT-FFT的运算规律及编程思想 运算规律： （1）原位计算 （2）旋转因子的变化规律 （3）蝶形运算规律 （4）序列的倒序 （5）编程思想及程序框图 返回 回到本节 （1）原位计算 观察每个蝶形的两个输入和两个输出 蝶形的输出可存入原输入数据所占存储单元 利用同一组存储单元存储输入、输出数据的方法，称为原位（址）计算。 节约内存 节省寻址的时间 返回 回到本节 （2）旋转因子的变化规律 N点DIT-FFT运算流图中，每级都有N/2个蝶形。每个蝶 形都要乘以因子，称其为旋转因子，p称为旋转因子的 指数。由于各级的旋转因子和循环方式都有所不同。为 了编写计算程序，应先找出旋转因子 与运算级数的 关系。用L表示从左到右的运算级数（L=1,2,…,M）。 返回 回到本节 由8点DIT-FFT运算流图可以发现，第L级共有2L-1个 不同的旋转因子。 N=23=8时的各级旋转因子表示如下: L=1时 L=2时 L=3时 … 对N=2M的一般情况，第L级的旋转因子为 返回 回到本节 由于 所以 这样，就可按上面两个式子确定第L级运算的旋转因子。 实际编程序时， L为最外层循环变量 返回 回到本节 （3）蝶形运算规律 设序列x(n)经时域抽选（倒序）后，存入数组A中。 如果蝶形运算的两个输入数据相距B个点，应用原位计 算，则蝶形运算可表示成如下形式: 式中 下标L表示第L级运算，AL(J)则表示第L级运算后数组元素 A(J)的值（即第L级蝶形的输出数据）。而AL-1(J)表示第 L级运算前A(J)的值（即第L级蝶形的输入数据）。 返回 回到本节 用实数运算完成上述蝶形运算，可按下面的算法进行： 设 式中，下标R表示取实部，I表示取虚部。 则 设 则 返回 回到本节 （4）序列的倒序 DIT-FFT算法的输出X(k)为自然顺序，但为了适应原位计 算，其输入序列不是按x(n)的自然顺序排序，这种经过M-1次 偶奇抽选后的排序称为序列x(n)的倒序（倒位）。 因此，在运算之前应先对序列x(n)进行倒序。 由于N = 2M，因此顺序数可用M位二进制数（nM-1nM-2…n1n0）表 示。M次偶奇时域抽选过程如 右图所示。第一次按最低位 n0的0和1将x(n)分解为偶奇两 组，第二次又按次低位n1的0、 1值分别对偶奇组分解；依次 类推，第M次按nM-1位分解，最 后得到二进制倒序数。 形成例序的树状图(N = 23) 返回 回到本节 不按顺序排列 顺 序 倒 序 十进制数I 二进制数 二进制数 十进制数 J 0 1 2 3 4 5 6 7 1 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 4 2 6 1 5 3 7 按顺序输出 返回 回到本节 （5）编程思想及程序框图 先从输入端（第1级）开始，逐 级进行，共进行M级运算。在进 行第L级运算时，依次求出 B=2L-1个不同的旋转因子，每 求出一个旋转因子，就计算完 它对应的所有2M-L个蝶形。这 样，我们可用三重循环程序实 现DIT-FFT运算，程序框图如右 程序运行后，数组A中 存放的是x(n)的N点DFT，即 X(k)=A(k)。 图所示。 返回 回到本节 4. IDFT的高效算法 上述FFT算法流图也可以用于IDFT。比较DFT和IDFT的运算 公式: 只要将DFT运算式中的因子改为，最后乘以1/N，就是I