dsp-第4章.ppt

第四章 离散傅里叶变换快速算法（FFT） 快速傅里叶变换（FFT）是计算DFT的一种快速有效方法， 并不是新的傅立叶变换式。 从前面的讨论中看到，有限长序列在数字技术中占有很重要的地位。有限长序列的一个重要特点是其频域也可以离散化，即离散傅里叶变换（DFT）。 虽然频谱分析和DFT运算很重要，但在很长一段时间里，由于DFT运算复杂，并没有得到真正的运用，而频谱分析仍大多采用模拟信号滤波的方法解决 直到1965年首次提出DFT运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法——快速傅里叶变换（FFT）算法。FFT的出现，使DFT的运算大大简化，运算时间缩短一～二个数量级，使DFT的运算在实际中得到广泛应用。 1、DFT运算的特点： FFT算法的基本思想 2、按时间抽取的FFT（N点DFT运算的分解）DIT—FFT 信号流图 N=23=8 的例子 时间抽取法FFT的运算特点 （1）蝶形运算 例 N=2048 N2=4194304， (N/2)log2N=11264， 相差N2/ [(N/2) log2N]=392.4倍。 FFT显然要比直接法快得多 （2）原位计算 当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直到最后输出，中间无需其它存储器，这叫原位计算。 每一级运算均可在原位进行，这种原位运算结构可节省存储单元，降低设备成本，还可节省寻址的时间。 （3）序数重排 对按时间抽取FFT的原位运算结构，当运算完毕时，正好顺序存放着 X（0），X（1），X（2），…，X（7），因此可直接按顺序输出，但这种原位运算的输入 x（n）却不能按这种自然顺序存入存储单元中，而是按x(0)，x(4)，x(2)，x(6)，…，x(7)的顺序存入存储单元，这种顺序看起来相当杂乱，然而它也是有规律的。当用二进制表示这个顺序时，它正好是“码位倒置”的顺序。例如，原来的自然顺序应是 x(1)的地方，现在放着 x(4)，用二进制码表示这一规律时， 则是在 x（0 0 1）处放着 x（1 0 0）， x（0 1 1）处放着 x（1 1 0）。 第一次分偶、奇，根据最低位n0的0、1状态来分，若n0=0，则为偶序列；n0=1则为奇序列，得到两组序列： 000 010 100 110 ? 001 011 101 111 第二次对这两个偶、奇序列再分一次偶、奇序列，这就要根据n1的０、１状态。若n1=0，则为偶序列；n1=1则为奇序列，得到四组序列： 000 100 ? 010 110 ? 001 101 ? 011 111 同理，再根据n2的０、１状态来分偶、奇序列，直到不能再分偶、奇时为止。对于N=8, n2已是最高位，最后一次分得结果为 000 ? 100 ? 010 ? 110 ? 001 ? 101 ? 011 ? 111 （4）蝶形类型随迭代次数成倍增加 观察8点FFT的三次迭代运算: 第一级迭代，有一种类型的蝶形运算系数W80，两个数据点间隔为1 第二级迭代，有二种类型的蝶形运算系数W80 、 W82 ，参加 运算的两个数据点间隔为2。 第三级迭代，有四类蝶形运算系数W80 、 W81 、 W82 、 W83 ，参加运算的两个数据点间隔为4。 结论：每迭代一次，蝶形类型增加一倍，数据点间隔也增大一倍。 每一级的取数间隔和蝶形类型种类均为2i-1，i=1,2,…M。 FFT算法流图 3. 频率抽取法FFT (DIF-FFT) FFT的变形运算流图 2.4 FFT应用中的几个问题 通过N点FFT运算可得到： Y(k)=X1(k)+jX2(k) ，N点 根据前面的讨论，得到 3) 线性卷积的FFT算法 线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上,如卷积滤波等。 以前曾讨论了用线性卷积计算线性卷积的方法归纳如下: 将长为N2的序列x(n)延长到L,补L-N2个零， 将长为N1的序列h(n)延长到L,补L-N1个零， 如果L≥N1+N2-1,则循环卷积与线性卷积相等,此时,可用FFT计算线性卷积，方法如下: a.计算X(k)=FFT[x(n)] b. 求H(k)=FFT[h(n)] c. 求Y(k)=H(k)X(k) k=0～L-1 d