FFT原理

快速傅里叶变换（FFT）快速傅里叶变换（FFT）快速傅里叶变换（FFT）是计算DFT的一种快速高效的算法。有限长序列在数字技术中占有很重要的地位，主要原因是由于其频谱可以离散化。有限长序列的DFT本身可以完全表达序列的频谱，所以DFT也可以直接对信号进行频谱分析。谱分析在通信技术、图象传输、语音压缩、生物医学等领域都得到应用。虽然频谱分析和DFT运算很重要，但在很长一段时间里，由于DFT运算量太大，因此它并没有得到真正的运用，频谱分析也大多采用模拟信号滤波的方法解决。直到1965年美国IBM公司的库利和图基这两位科学家首次提出DFT运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法—快速付里叶变换(FFT)算法。FFT的出现，使DFT的运算大大简化，运算时间缩短1-2个数量级，FFT的问世使得DFT在实际中得到广泛应用。§6.1DFT运算的特点：有限长序列x(n)进行一次DFT运算所需的运算量:1010,1,,()[]()()NnnkNNXkDFTkxnxnw一.DFT的运算量：000001121(1)101(1)2(1)(1)(1)(1)(1)(0)(0)(1)(1)NNNNNNNNNNNNNNNNNNNXXXx一般x(n)和都是复数，X(k)也是复数，所以计算一次DFT的运算量是：nkNw在这些运算中，乘法比加法运算复杂，尤其是复数相乘，每个复数相乘包括4个实数相乘和2个实数相加，例：又因每个复数相加包括2个实数相加,所以,每计算一个X(k)要进行4N次实数相乘和2N+2(N-1)=2(2N-1)次实数相加，因此，整个DFT运算需要4N2实数相乘和2N(2N-1)次实数相加。计算一个X(k)值需：N次复数相乘和(N-1)次复数相加计算N点X(k)值需：次复数相乘和N(N-1)次复数相加2N10(){[()][()][][()][()]}NnknkeeNmmNnnknkemNmeNXkRxnRwIxnIwjRxnIwIxnRw从上面的分析看到，在DFT计算中，不论是乘法和加法，运算量均与N2成正比。因此，N较大时，运算量十分可观。例：计算N=10点的DFT，需要100次复数相乘，而N=1024点时，需要1048576（一百多万）次复数乘法，如果要求实时处理，则要求有很高的计算速度才能完成上述计算量。反变换IDFT与DFT的运算结构相同，只是多乘一个常数1/N，所以二者的计算量相同。考察DFT的运算特点发现,利用以下两个特性可减少运算量：1）系数是一个周期函数，利用它的周期性和对称性可改进运算，提高计算效率。2jnknkNNwe()()nknNkkNnNNN/21NNw(/2)nkNnkNNwwnkNw二.DFT的运算特点周期性对称性我们利用系数的周期性和对称性，考察它是如何简化DFT运算的过程。以N＝4为例，的矩阵形式为：4nkw000000000000444444444444012301014444444444440200444444423012003460244444030044444069244414414104周期性性对称DFT的矩阵运算4()()nkXkwxn4()nkabbaNNwxnww运说相乘中有重复算。明0000444401014444000044440101444401230(0)(1)(2)(3)(0)(1)(2)(3)(0)(1)(2)(3)(0)(1)(2)(3)kkkkXxwxwxwxwXxwxwxwxwXxwxwxwxwXxwxwxwxw（）＝（1）＝（2）＝（3）＝2)因为DFT的计算量正比于N2，N小计算量也就小。因此可以把长度为N点的大点数的DFT运算依次分解为若干个小点数的DFT来运算。FFT算法正是基于以上两点基本思想来提高DFT的运算速度。FFT算法基本上可分为两大类：按时间抽取FFT算法和按频率抽取FFT算法。结论：1)利用系数的周期性和对称性可以提高DFT的运算速度。上例中作一次DFT需N2=16次乘法运算，而FFT只需6次乘法运算。nkNw§6.2按时间抽取的FFT为了保证N点DFT的运算分解，首先假设N是2的整幂次方，即N=2M，M是正整数。一.算法原理(1)将序列按序号n的奇、偶分解为两个点子序列1221(2)()0,1,....,(21)()Nxrxrrxrxr数项组奇数项组偶1010,1,,()[]()()NnnkNNXkDFTkxnxnw2N()nxDFT运算也相应分为两组：2011)()(NnNnnkNnkNwnxwnx偶数奇数10()()()NnkNnkDFTxnxnwx/21/2)10021(2((2)1)2NNkNrrrkNrrwrwxx/21/210220(2)(21)NNNNrrrkkrkNrWrWwxx222222NjrkjrkNNrkrkNweew故：21/21/2100222212()()12()()NNNNNNkNrDFTDFrkNTrkrkrrxxXk的点的点显然，和都只含有N/2点DFT,所以X(k)也只包含k=0,1,…,N/2-1点的DFT，还必须利用系数的周期性和对称性，求出X(k)的后N/2点的DFT。1Xk2XknkNw(2)求：12()2NNXkk＝0，1,？＝...,/2110212()()NNrrkNXkWkkrx=令/21/21112200/2112()()()()NNNkNNrkrrrNkXkwwXrrxx()2NkkNNWW可见，一个N点的DFT被分解为前后两个N/2点的DFT，这两个N/2点的DFT再合成为一个N点DFT。同理：222()()NkXkX再利用W系数的对称性：12122()0,1,NkNNXkXkWXkk120,1,Nk12122()()NNkkNXkXkWXkXkXkWXk1Xk2Xk以上两个表达式说明：只要我们计算出N/2个点的所有和的值，就等于求出N点的X(k)值,这使得DFT的运算量减少了约一半。上述两个公式的运算过程可用专用蝶形图表示：图(a)需要两次乘法、两次加减法,将图(a)简化成图(b)，此时仅需一次乘法、两次加减法。12122()()NNkkNXkXkWXkXkXkWXk按时间抽取的蝶形运算流图：(3)和可以继续分解下去，可将N/2点的子序列再按奇、偶项分解，一直到最后分解成两两点的DFT为止。1Xk2Xk偶序列中的偶序列偶序列中的奇序列奇序列中的偶序列奇序列中的奇序列210,1,....Nl13(2)()llxx14(21)()llxx25(2)()llxx26(21)()llxx四个点DFT4N例：N=23=8按时间抽取的DFT分解过程由于N/2仍是偶数，可以被２整除，因此可以对两个N/2点的DFT再分别作进一步的分解。将一个８点的DFT可以分解成四个２点的DFT,直到最后得到两两点的DFT为止。由于这种方法每一步分解都是按输入序列是属于偶数还是奇数来抽取的，所以称为“按时间抽取的FFT算法”。N＝8点按时间抽取的FFT运算流图第一级蝶形第二级蝶形第三级蝶形时间抽取法FFT的运算特点：（1）蝶形运算（2）原位运算结构（3）码位倒置变换（4）蝶形类型随迭代次数成倍增加（1）蝶形运算对于N=2M，总可以通过M次分解最后分解成2点的DFT运算。这构成从x(n)到X(k)的M级运算过程。从上面流图可看到，每一级运算都由N/2个蝶形运算构成。因此每一级运算都需要N/2次复乘和N次复加，经过M级运算后总共需要的运算量为：复乘：复加：而直接进行DFT运算时则与N2成正比。222logNNMN2logNMNN算法的运算速度222logNNNG运数运数直接DFT算次FFT算次例:N=2048，N2=4194304，，显然,FFT要比直接DFT运算快得多。22log11264NN222372.4logNNN（2）原位运算结构（同址运算）FFT运算结构很有规律，它具有强烈的对称性，它的所有运算都可以由左下图所示的基本运算构成。由于运算结构规律，所以硬件实现起来简单，软件编程方便。FFT的蝶形运算结构很经济，它可以采用原位运算。原位运算——指当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直到最后输出，中间无需其它任何存储器，称为原位运算。例如：输入数据A、B相应的存放在寄存器A(1)和A(2)中，当进行完蝶形运算后，输出和存放在A(1)中，输出差存放在A(2)中。下一级蝶形运算的输入数据又分别存放在A(1)和A(2)中，而把前一级输出的结果覆盖掉，直到最后输出，中间无需任何其它存储器。原位运算结构节省存储单元，可以降低设备成本，还可节省寻址的时间。（3）码位倒置变换对按时间抽取FFT的原位运算结构，如果输出按顺序输出,即顺序存放x(0),x(1),x(2),…,x(7),但它的输入x(n)却不是按自然顺序输入的,而是按x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)存入，这种顺序看起来很杂乱，实际上它很有规律。当用二进制表示这个顺序时，它正好是“码位倒置”的顺序。例如：顺序输出码位倒置——指序号用二进制码形式表示，然后将二进制码的首尾颠倒。210012(001)(1)(100)(4)dddAxdddAx输入在实际运算中，输入数据总是按自然顺序输入到存储单元，再通过变址运算将自然顺序转换成码位倒置顺序存储，然后再进行FFT的原位计算。目前有许多通用DSP芯片支持这种码位倒置的寻址功能。下表中以N=8为例给出码位倒置顺序IJ码位倒置的规律(1)当I=J时，A(I)中存储的数不变，A(I)=A(J);(2)当IJ时，A(I)和A(J)的内容互换。即：T=A(J)；A(J)=A(I)；A(I)=T(3)当IJ时，意味着A(I)和A(J)的内容已经互换过了，为了避免将已互换过的数据再次调换，所以A(I)和A(J)的内容不变。N＝8点按时间抽取的FFT运算流图第一级蝶形第二级蝶形第三级蝶形观察N=23=8点FFT的蝶形系数：第一级：有一种类型的蝶形运算系数第二级:有二种类型的蝶形运算系数、第三级:有四种类型的蝶形运算系数、、、第L级:有种蝶形运算系数（4）蝶形图的系数08W08W28W08W28W18W38WnkNwnkNw21012....NNNNN、、、、12L将x(n)按n的顺序前后对半分开：§6.3按频率抽取的FFT频率抽取法是N=2M情况下的另外一种FFT算法按时间抽取FFT算法的基本思路按频率抽取FFT算法的基本思路x(n)按奇、偶一级级分开，X(k)按前一半、后一半一级级分开。X(k)按奇、偶一级级分开，x(n)按前后对半一次次分开。一.按频率抽取法的FFT算法原理10()()NnkNnXkxnW/2110/2/21/21()02(/2)0/210/22()()()()()[()()]NNnknkNNnnNkNNNnnkNNnnNnkNNknNNNXkxnWxnWWxnWxnWxnxnW