4快速傅里叶变换.ppt

造成倒位序的原因是输入x(n)按标号n的偶奇的不断分组。 如果n用二进制数表示为(n2n1n0)2（当N=8=23时，二进制为三位）， 第一次分组，由图4-2看出，n为偶数（相当于n的二进制数的最低位n0=0）在上半部分，n为奇数（相当于n的二进制数的最低位 n0=1）在下半部分。 下一次则根据次最低位n1为“0”或是“1”来分偶奇（而不管原来的子序列是偶序列还是奇序列）， 如此继续分下去，直到最后N个长度为1的子序列。 图4-8的树状图描述了这种分成偶数子序列和奇数子序列的过程。 图4-8 描述倒位序的树状图 3.倒位序实现 输入序列先按自然顺序存入存储单元,然后经变址运算来实现倒位序排列。 设输入序列的序号为n,二进制为(n2 n1 n0 )2 , 倒位序顺序用? 表示,其倒位序二进制为(n0 n1 n2 )2 , 例如 ，N=8时如下表： 表4-2 码位的倒位序（N=8） 0 4 2 6 1 5 3 7 000 100 010 110 001 101 011 111 000 001 010 011 100 101 110 111 0 1 2 3 4 5 6 7 倒位序顺序（?） 倒位序二进制数 二进制数 自然顺序（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-9 倒位序的变址处理 (N=8) 变址处理方法 4. 蝶形运算两节点的“距离” 以图4-5的8点FFT为例，其输入是倒位序的，输出是自然顺序的。 其第一级（第一列）每个蝶形的两节点间“距离”为1， 第二级每个蝶形的两节点“距离”为2， 第三级每个蝶形的两节点“距离”为4。 由此类推得，对N=2L点FFT，当输入为倒位序， 输出为正常顺序时，其第m级运算，每个蝶形的两节点“距离”为2m-1。 5. WNr的确定 由于对第m级运算，一个DFT蝶形运算的两节点“距离”为2m-1， 因而式（4-21）可写成: （4-22a） （4-22b） 为了完成上两式运算，还必须知道系数ＷNr的变换规律：  ① 把式（4-22）中蝶形运算两节点中的第一个节点标号值， 即k值，表示成L位（注意N=2L）二进制数； ② 把此二进制数乘上2L-m，即将此L位二进制数左移M-m位（注意m是第m级运算），把右边空出的位置补零， 此数即为所求r的二进制数。  从图4-5看出，WNr因子最后一列有N/2种，顺序为WN0， WN1，…， ， 其余可类推。 6.存储单元 存输入序列 需N个存储单元 存放系数 需N/2个存储单元； 共计需(N+N/2)个存储单元。 四、 按时间抽取的FFT算法的其他形式流图 显然，对于任何流图，只要保持各节点所连的支路及传输系数不变，则不论节点位置怎么排列所得流图总是等效的，所得最后结果都是x(n)的DFT的正确结果，只是数据的提取和存放的次序不同而已。这样就可得到按时间抽取的FFT算法的若干其他形式流图。 将图4-5中和x(4)水平相连的所有节点和x(1)水平相连的所有节点位置对调，再将和x(6)水平相连的所有节点与和x(3)水平相连的所有节点对调，其余诸节点保持不变，可得图4-11的流图。 图4-11与图4-5的蝶形相同，运算量也一样，不同点是： 第4章 快速傅里叶变换(FFT) * 第4章 快速傅里叶变换 4.1 引言 4.2 直接计算DFT的问题及改进的途径 4.3 按时间抽取（DIT）的基2-FFT算法 4.4 按频率抽取（DIF）的基2-FFT算法 4.5 离散傅里叶反变换（IDFT）的快速计算方法 4.10 线性卷积的FFT算法 4.1 引 言 快速傅里叶变换（FFT）并不是一种新的变换， 而是离散傅里叶变换（DFT）的一种快速算法。  由于有限长序列在其频域也可离散化为有限长序列（DFT），因