4 快速傅里叶变换幻灯片.ppt

2. 倒位序规律 FFT的输出X(k)按正常顺序排列在存储单元中，即按X(0)，X(1)，…，X(7)的顺序排列，但是这时输入x(n)却不是按自然顺序存储的，而是按x(0)，x(4)， …， x(7)的顺序存入存储单元，看起来好像是“混乱无序”的，实际上是有规律的，我们称之为倒位序。 这是由奇偶分组造成的,以N=8为例 说明如下: 造成倒位序的原因是输入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） 图 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位二进制数左移L-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-10的流图。 图4-10与图4-5的蝶形相同，运算量也一样，不同点是： * 第4章 快速傅里叶变换(FFT) * 第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）并不是一种新的变换， 而是离散傅