第4章快速傅立叶变换(FFT)精选.ppt

这是由奇偶分组造成的,以N=8为例 说明如下: 0 1 0 1 0 1 0 1 (n2) x(000) 0 x(100) 4 x(010) 2 x(110) 6 x(001) 1 x(101) 5 x(011) 3 x(111) 7 （偶） （奇） * 陈友兴 数字信号处理第四章 3.倒位序实现 输入序列先按自然顺序存入存储单元,然后经变址运算来实现倒位序排列。设输入序列的序号为n,二进制为 (n2 n1 n0 )2 ,倒位序顺序用 表示,其倒位序二进制为(n0 n1 n2)2,例如 ，N=8时如下表： * 陈友兴 数字信号处理第四章 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 自然顺序n 二进制n2n1n0 倒位序二进制 n1n2 倒位顺序n ^ * 陈友兴 数字信号处理第四章 A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) 变址处理方法 存储单元 自然顺序 变址 倒位序 4.蝶形运算两节点的距离:2m-1 其中,m表示第m列,且m =1,… ,L 例如N=8=23 ,第一级(列)距离为21-1=1, 第二级(列)距离为22-1=2， 第三级(列)距离为23-1=4。 FFT流图 * 陈友兴 数字信号处理第四章 5.WNr 的确定(仅给出方法) 考虑蝶形运算两节点的距离为2m-1 ,蝶 形运算可表为 由于N为已知,所以将r的值确定即可。 为此，令k=(n2n1n0)2 ,再将k= (n2n1n0)2 左移(L-m)位,右边位置补零,就可得到 (r)2 的值，即(r)2 =(k)22L-m 。 FFT流图 * 陈友兴 数字信号处理第四章 6.存储单元 存输入序列 计N个单元; 存放系数 需N/2个存储单元； 共计(N+N/2)个存储单元。 按时间抽取其他形式的流图见P154 * 陈友兴 数字信号处理第四章 4-3频率抽取（DIF）的基-2 FFT算法 一、DIF法的原理 （前一半） （后一半） * 陈友兴 数字信号处理第四章 -1 蝶形运算 * 陈友兴 数字信号处理第四章 -1 -1 -1 -1 8点DIF的FFT原理结构 N/2点 DFT N/2点 DFT * 陈友兴 数字信号处理第四章 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 二、DIF的FFT流图 * 陈友兴 数字信号处理第四章