《离散傅里叶变换及其快速算法(下)》由会员分享，可在线阅读，更多相关《离散傅里叶变换及其快速算法(下)（91页珍藏版）》请在金锄头文库上搜索。
1、第二章 离散傅里叶变换 及其快速算法2.3 快速傅里叶变换 （FFT）快速傅里叶变换（FFT）是计算DFT的一种 快速有效方法。 从前面的讨论中看到，有 限长序列在数字技术中占有很重要的地位。有 限长序列的一个重要特点是其频域也可以离散 化，即离散傅里叶变换（DFT）。虽然频谱分析和DFT运算很重要，但在很长一 段时间里，由于DFT运算复杂，并没有得到真正 的运用，而频谱分析仍大多采用模拟信号滤波 的方法解决，直到1965年首次提出DFT运算的一 种快速算法以后，情况才发生了根本变化，人 们开始认识到DFT运算的一些内在规律，从而很 快地发展和完善了一套高速有效的运算方法 快速付里变换（FFT
2、）算法。FFT的出现，使 DFT的运算大大简化，运算时间缩短一二个数 量级，使DFT的运算在实际中得到广泛应用。1、DFT运算的特点：一般，x(n)和wnkN都是复数，因此，每计算一个X(k)值，要进 行N次复数相乘，和N-1次复数相加，X(k)一共有N个点，故完成 全部DFT运算，需要N2次复数相乘和N（N-1）次复数相加，在 这些运算中，乘法比加法复杂，需要的运算时间多，尤其是复数 相乘，每个复数相乘包括4个实数相乘和2个实数相加，例首先分析有限长序列 x(n)进行一次DFT运算所需的运算量。又每个复数相加包括2个实数相加，所以，每计算一个 X(k)要进 行4N次实数相乘和2N+2（N-1
3、）=2（2N-1）次实数相加，因此， 整个DFT运算需要4N2实数相乘和2N（2N-1）次实数相加。从上面的分析看到，在DFT计算中，不论是乘法和 加法，运算量均与N2成正比。因此，N较大时，运 算量十分可观。例，计算N=10点的DFT，需要100 次复数相乘，而N=1024点时，需要1048576（一百 多万）次复数乘法，如果要求实时处理，则要求 有很高的计算速度才能完成上述计算量。反变换IDFT与DFT的运算结构相同，只是多乘 一个常数1/N，所以二者的计算量相同。FFT算法的基本思想：考察DFT与IDFT的运算发现，利用以下两个特性可减少运 算量： 1）系数 是一个周期函数，它的周期性和
4、对称 性可用来改进运算，提高计算效率。例利用这些周期性和对称性，使DFT运算中有些项可合并； 2）利用 的周期性和对称性，把长度为N点的大点数的 DFT运算依次分解为若干个小点数的DFT。因为DFT的计算量正 比于N2，N小，计算量也就小。 FFT算法正是基于这样的基本思想发展起来的。它有多种形式， 但基本上可分为两类：时间抽取法和频率抽取法。又如因此 2、按时间抽取的FFT（N点DFT运算的分解）先从一个特殊情况开始，假定N是2的整数次方，N=2M，M：正整数首先将序列x（n）分解为两组，一组为偶数项，一组为奇 数项，将DFT运算也相应分为两组：因为 故其中注意到，H（k），G（k）有N/2
5、个点，即k=0，1， N/2-1，还必须应用系数 wkN 的周期性和对称性表示 X（k）的 N/2 N-1点：由得：可见，一个N点的DFT被分解为两个N/2点的DFT，这 两个N/2点的DFT再合成为一个N点DFT.依此类推，G(k)和H(k)可以继续分下去，这种按时间抽 取算法是在输入序列分成越来越小的子序列上执行DFT 运算，最后再合成为点的DFT。 蝶形信号流图将G(k)和H(k) 合成X(k)运算可归结为： Wa+bWa-bW -W- -1a+bWa-bWWabab蝶形运算 的简化(a)(b)图 (a)为实现这一运算的一般方法，它需 要两次乘法、两次加减法。考虑到-bW和 bW两个乘法
6、仅相差一负号，可将图 (a)简 化成图2.7(b)，此时仅需一次乘法、两次 加减法。图 (b)的运算结构像一蝴蝶通常 称作蝶形运算结构简称蝶形结，采用这 种表示法，就可以将以上所讨论的分解 过程用流图表示。 N=23=8 的例子。N/2点 DFTG(0)G(1)G(2)G(3)X(0)X(1)X(2)X(3)x(0)x(2)x(4)x(6)N/2点 DFTH(0)H(1)H(2)H(3)X(4)X(5)X(6)X(7)x(1)x(3)x(5)x(7)WN1WN2WN3-1-1-1-1两个4点DFT组成8点DFT按照这个办法，继续把N/2用除，由于N=2M ，仍然是偶数，可以被整除，因此可以对两
7、 个N/2点的DFT再分别作进一步的分解。即对 G(k)和H(k)的计算，又可以分别通过计算 两个长度为N/4=2点的DFT，进一步节省计算 量，见图。这样，一个点的DFT就可以分解 为四个点的DFT。 N/4N/4点点N/4N/4点点N/4N/4点点N/4N/4点点由四个由四个2 2点点DFTDFT组成组成8 8点点DFTDFT最后剩下的是2点DFT，它可以用一个蝶形结表示：这样，一个8点的完整的按时间抽取运算的流图由于这种方法每一步分解都是按输入时间序列是属 于偶数还是奇数来抽取的，所以称为“按时间抽取法” 或“时间抽取法”。按时间抽取的8点FFT时间抽取法FFT的运算特点：（1）蝶形运算
8、（2）原位计算 （3）序数重排（4）蝶形类型随迭代次数成倍增加（1）蝶形运算 对于N=2M，总是可以通过M次分解最后成为2点的 DFT运算。这样构成从x(n)到X(k)的M级运算过程。 从上面的流图可看到，每一级运算都由N/2个蝶形运 算构成。因此每一级运算都需要N/2次复乘和N次复加 ，这样，经过时间抽取后M级运算总共需要的运算：复乘 复加 而直接运算时则与N2 成正比。 例N=2048，N2=4194304，(N/2)log2N=11264，N2 / (N/2)log2N=392.4。FFT显然要比直接法快得多。（2）原位计算 当数据输入到存储器中以后，每一级运算 的结果仍然储存在同一组存
9、储器中，直到最 后输出，中间无需其它存储器，这叫原位计 算。 每一级运算均可在原位进行，这种原位运算 结构可节省存储单元，降低设备成本，还可 节省寻址的时间。（3）序数重排对按时间抽取FFT的原位运算结构，当运算完 毕时，正好顺序存放着 X（0），X（1），X（2 ），X（7），因此可直接按顺序输出，但这 种原位运算的输入 x（n）却不能按这种自然顺序 存入存储单元中，而是按x(0)，x(4)，x(2)，x(6) ，x(7)的顺序存入存储单元，这种顺序看起 来相当杂乱，然而它也是有规律的。当用二进制 表示这个顺序时，它正好是“码位倒置”的顺序。 例如，原来的自然顺序应是 x(1)的地方，现在放
10、 着 x(4)，用二进制码表示这一规律时， 则是在 x（0 0 1）处放着 x（1 0 0），x（0 1 1）处放着 x（1 1 0）。表 码位倒置顺序自然顺序二进码表示码位倒置码位倒置顺序0000000010011004201001023011110641000011510110156110010371111117在实际运算中，一般直接将输入数据 x（n）按码位倒置的顺序 排好输入很不方便，总是先按自然顺序输入存储单元，然后再通 过变址运算将自然顺序的存储转换成码位倒置顺序的存储，然后 进行FFT的原位计算。目前有许多通用DSP芯片支持这种码位倒置 的寻址功能。 第一次分偶、奇，根据最低位n
11、0的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的三次迭代运算: 第一级迭
12、代，有一种类型的蝶形运算系数W08， 两个数据点间隔为1 第二级迭代，有二种类型的蝶形运算系数W08、 W28，参加 运算的两个数据点间隔为2。 第三级迭代，有四类蝶形运算系数W08、W18、 W28、W38，参加运算的两个数据点间隔为4。结论：每迭代一次，蝶形类型增加一倍，数据 点间隔也增大一倍。 每一级的取数间隔和蝶形类型种类均为2i-1， i=1,2,M。 3、按频率抽取的FFT（按输出X（k）在频域的顺序上属于 偶数还是奇数分解为两组） 对于N=2M情况下的另外一种普遍使用的FFT结构是 频率抽取法。 对于频率抽取法，输入序列不是按偶奇数，而是按 前后对半分开，这样便将N点DFT写成前
13、后两部分：把X（k）进一步分解为偶数组和奇数组：令 a(n)=x(n)+x(n+N/2)b(n)=x(n)-x(n+N/2wnN 这两个序列都是N/2点的序列，将其代入上两式，得x1(n)+ x2(n)WNnx1(n)x2(n)x1(n)-x2(n) WNn-1这正是两个N/2点的DFT运算，即将一个N点的DFT分解为两 个N/2点的DFT，上式的运算关系可用下图表示. 以N=8的频率抽取为例x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1N/2点 DFTa(0)a(1)a(2)a(3)N/2点 DFTb(0)b(1)b(2)b(3)WN1WN2WN3X(0)X
14、(2)X(4)X(6)X(1)X(3)X(5)X(7)按频率抽取将8点DFT分解成两个4点DFT按频率抽取将8点DFT分解成四个2点 DFT与时间抽取法一样，由于N=2M，N/2仍是一个偶数, 这样，一个N=2M点的DFT通过M次分解后，最后只 剩下全部是2点的DFT，2点DFT实际上只有加减运 算。但为了比较，也为了统一运算的结构，仍用一 个系数为W0N 的蝶形运算来表示。 频率抽取法的流图是时域抽取法流图的左右翻转。 下图是N=8的频率抽取法FFT流图。N=8的按频率抽取FFT运算流图按时间抽取的8点FFTN=8的按频率抽取FFT运算流图频率抽取法FFT的运算特点： （1）蝶形运算对于任何
15、一个2的整数幂N=2M，总是可以通过M 次分解最后完全成为2点的DFT运算。这样的M次分 解，就构成从x(n)到X(k)的M级运算过程。将频率抽 取法的流图反转，并将输入变输出，输出变输入， 得到的便是时间抽取法流图（反映了时域，频域的 对称法）。频率抽取法也共有M级运算（N=2M）， 其运算量与时间抽取法相同。（2）原位计算 类似于时间抽取法，当数据输入到存储器中以后 ，每一级运算的结果仍然储存在同一组存储器中， 直到最后输出，中间无需其它存储器，所以频域抽 取法也可进行原位计算。（3）序数重排它的输入正好是自然顺序。但它的输出却是码位倒置 的顺序。因此运算完毕后，要通过变址运算将码位倒置
16、的顺序转换为自然顺序，然后输出，变址方法同时间抽 取法。（4）蝶形类型随迭代次数成倍减少(与时间抽取法相反)第一级迭代中有N/2种蝶形运算系数，参加蝶形运算 的两个数据相隔N/2，随后每次迭代，蝶形类形比前一 级减少一倍，间距也减少一倍，最后一级迭代，蝶形类 形只有一种W0N，数据间隔为1。 由这几点规律可以看出，频率抽取法与时间抽到法是两 种等价的FFT运算。4. N为组合数的FFT（任意基数的FFT算法）以上讨论的都是以2为基数的FFT算法，即N=2M，这 种情况实际上使用得最多。优点：程序简单，效率高，使用方便。实际应用时，有限长序列的长度N很大程度上由人 为因素确定，因此多数场合可取 N=2M，从而直接使用 以 2 为基数的FFT算法。如N不能人为确定 , N的数值也不是以2为基数的整 数次方,处
