第七讲快速傅里叶变换fft

第七讲快速傅里叶变换fft内容摘要：

2(7) X3(7)=X(7) W W W W N 0 N 0 N 0 N 0 1 1 1 1 W W W WN 0 N 2 N 0 N 2 1 1 1 1 W W W W N N N N 0 1 2 3 . . . . . . . . . . . xxxxxxxx输入数据、中间运算结果和最后输出均用同一存储器。 (2)旋转因子的变化规律 在每个蝶形的运算过程中，都要乘以因子 ，称其为旋转因子， p称为旋转因子指数。 但各级的旋转因子和循环方式都有所不同。 旋转因子与运算级数有一定的关系 ， 若用 L表示运算级数 ， 对于 N＝ 2M的一般情况 ， 第 L级的旋转因子为： 从运算流图可以看出 ， 原位计算时 ， FFT的输出 X(k)是按正常顺序排列在存储单元中 ， 即按X(0)， X(1),， X(7)的顺序排列 ， 但是这时输入x(n)都不是按自然顺序存储的 ， 这看起来好象是“ 混乱无序 ” 的 ， 实际上是有规律的 ， 我们称之为倒位序。 造成倒位序的原因是输入 x(n)按标号 n的偶奇的不断分组而造成。 (3)倒位序规律 倒位序实现 输入序列先按自然顺序存入存储单元 ,然后经变址运算来实现 倒位序排列 ， 设输入 序列的序号为 n,二进制为 (n2 n1 n0 )2 ,倒位序 顺序用 表示 ,其 倒位序 二进制为 (n0 n1 n2 )2。 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) 变址处理方法 存储单元 自然顺序 变址 倒位序 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 二进制 n n n 倒位序二进制 n n n 倒位顺序 n ^ 2 1 0 0 1 2 例如 ， N=8时如下表： :2m1 其中 ,m表示第 m列 ,且 m =1,… ,L 例如 N=8=23 ,第一级 (列 )距离为 211=1, 第二级 (列 )距离为 221=2， 第三级 (列 )距离为 231=4。 五、按频率抽取 (DIF)的 FFT－－桑德 图基算法 库利图基法是将输入序列按其顺序是奇数还是偶数来分解为越来越短的序列；桑德图基法是把输出序列 X(k)按其顺序的偶奇来分解为越来越短的序列。 设序列 x(n)长度为 N＝ 2M， 首先将 x(n)前后对半分开 ， 得到两个子序列 ， 其 DFT可表示为： 10)()(NnnkNWnxkX10)(。