快速傅立叶变换FFT.ppt

4.2.5 频域抽取法FFT（DIF-FFT) 4.2.5 频域抽取法FFT（DIF-FFT) 4.2.6 IDFT的高效算法 4.2.6 IDFT的高效算法 下次课内容: 1. Matlab 语言简介 2. 实验 3. 期中考试. 说明: 学校书库只有少量《数字信号处理实习指导书》，为此，同学们可不必购买，而直接在网上下载电子版的该书。我已经放在学院教案下载处。 开 始 输入x(n),M N=2M 倒序 L=1,M B?2L-1 J=0,B-1 P=2M-L. J k=J,N-1,2L 输出 结束 L表示运算级数 旋转因子个数 对旋转因子计数 计算旋转因子指数 每个旋转因子对应2M-L个蝶形运算。 两个蝶形运算第一个输入点‘距离’是2L 此流程图是针对C写的,MATLAB时要相应修改 4. 倒位序规律 若 是三位二进制数， 则 就是它的倒位序。 按原位计算时，FFT的输出X(k)是按自然顺序存储的，但这时输入序列却不是按自然顺序存储的。 输入序列初看起来，好象没有规律，实际是按倒位序存储的。 DIT-FFT的运算规律及编程思想 DIT-FFT的运算规律及编程思想 倒位序的形成 0 0 1 0 0 0 1 1 0 1 0 1 1 1 x(111)=x(7) x(000)=x(0) x(010)=x(2) x(110)=x(6) x(001)=x(1) x(101)=x(5) x(100)=x(4) 造成倒位序的原因是输入序列x(n)，按标号(序号)n的奇偶不断地分组造成的。 x(011)=x(3) 5. 倒位序的实现 DIT-FFT的运算规律及编程思想 （1）只要将顺序二进制数（n2n1n0）的二进制位倒置，得（ n0n1n2）。根据这种规律，容易用硬件电路和汇编语言产生倒位序数。 （2）用高级语言程序实现时，必须找出产生倒序数的十进制运算规律。 DIT-FFT的运算规律及编程思想 0 000 0 000 1 001 4 100 2 010 2 010 3 011 6 110 4 100 1 001 5 101 5 101 6 110 3 011 7 111 7 111 左边为按自然顺序排列的二进制数，下面的一个数是上面一个数的最低位上加上1，且向高位进位。 右边为倒位序数，下面的一个数是上面一个数的最高位上加上1，且由高位向低位进位。称为反向进位加法 顺序与倒序二进制对照表 可由当前任一倒序值求得下一个倒序值 反向进位加法的实现(十进制情况) 若已知某个倒位序数J，求下一个倒位序数， 判 断 J 的最高位是否为“0”, 让J与N/2比较，因为N/2总是100……, 如果 JN/2 ,则 J 的最高位为零,只需把该位变为 1(J=J+N/2),就得到下一个倒位序数,否则,把最高位变为 0(J=J-N/2) 判 断 J 的次高位是否为“0”, 让J与N/4比较， 如果 J 的次高位为零,只需把该位变为 1(J=J+N/4),其它位不变,就得到下一个倒位序数,否则,还需判断下一位(与 N/8比较),如此依次进行下去,总会碰到某位为 0,将此位改为1即可. DIT-FFT的运算规律及编程思想 JK No 实现倒位序的流程图 DIT-FFT的运算规律及编程思想 上一个倒序数 下一个倒序数 形成倒序数后，把原来按自然顺序存放在存储单元的输入序列x(n)重新按倒序排列。 通过变址运算完成倒位序 时，不必调换。而当 时，需调换。 变址 与DIT相对应，DIF算法是将频域X(k)的序号k按奇偶分开。 推导过程 设 M为自然数 则x(n)的DFT为 式中 分别令k=2r,k=2r+1,r=0.1……,N/2-1 令 则 4.2.5 频域抽取法FFT（DIF-FFT) 4.2.5 频域抽取法FFT（DIF-FFT) 由于N=2M ，N/2仍然是偶数，继续将N/2点的DFT分成偶数组和奇数组。 这样每个N/2点DFT可由两个N/4点DFT形成。 其输入序列分别是x1(n)和x2(n)按上下对半分开形成的四个子序列。 DIF与DIT算法的比较 基本蝶形不同 都有M级运算,每级有N/2个蝶形 都可进行原位计算 运算次数相同 输入为自然顺序,输出为倒位序 4.2.5 频域抽取法FFT（DIF-FFT) 这样将X(k)按k的奇偶把一个N点的DFT分成为两个N/2点的DFT,且可一直分解为直到两点的DFT. 比较两个公式可以看出，只要改变DFT运算中的每个系数符号，最后乘以 1/N ，就是IDFT的运算公式了。 实际中，为