小波分析 快速傅里叶变换.ppt

快速傅里叶变换 快速傅里叶变换(FFT)并不是一种新的变换，而是离散博里叶变换(DFT)的一种快速算法。因此，为了很好地理解和掌握快速傅里叶变换，必须对离散傅里叶变换有充分的理解与掌握 。 由于DFT的计算量太大．即使采用计算机也很难对问题进行实时处理，所以并没有得到真正的运用。直到1965年库利(J. W. Coo1ey)和图基(J. W. Tukey)在《计算数学》上发表了著名的“机器计算傅里叶级数的一种算法”的文章．提出了DFT的一种快速算法．后来又有桑德(G. Sande)和图基的快速算法相继出现，情况才发生了根本的改变。经过人们对算法的改进，发展和完善了一套高速有效的运算方法，使DFT的计算大大简化，运算时间—般可缩短一、二个数量级，从而使DFT的运算在实际中真正得到了广泛的加用。 1 直接计算DFT的问题及改进途径 DFT的运算量分析 一次复数乘法需用四次实数乘法和二次实数加法： 一次复数加法则需两次实数加法。 改进途径 FFT算法的基本思想 使DFT运算中有些项可以合并； 可以将长序列的DFT分解为短序列的DFT FFT算法分类: 时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency 2 按时间抽选(DIT)的基-2 FFT算法(库利·图基算法) 算法原理 先没序列点数为 , 为整数。如果不满足这个条件，可以人为地加上若干零值点，使之达到这一要求。这种 为2的整数幂的FFT也称基-2 FFT。 计算量分析： 计算量减少一半 可以进一步把每一个N／2点子序列再按其奇偶部分分解为两个N／4点的子序列 讨论 按偶数与奇数的分解过程中序列标号的变化。 对于一个N＝8点的DFT的例子，输入序列按偶数点与奇数点第一次分解为两个N／2点序列： 运算量分析： 由按时间抽选法FFT的流图可见，当 时，共有L级蝶形，每级都由N/2个蝶形运算组成，每个蝶形有一次复乘、二次复加．因而每级运算都需N/2次复乘和N次复加，这样L级运算总共需要: 算法特点 1 同址运算 2 到位序规律 3蝶形运算两节点的“距离” 4 的确定 4按频率抽选(DIF)的基-2 FFT算法(桑德·图基算法) 这里讨论另一种FFT算法，称为按频率抽选(DIF)的FFT算法，它是把输出序列 (也是N点序列)按其顺序的奇偶分解为越来越短的序列。 算法原理 仍设序列点数为 ，L为整数。在把输出 按k的奇偶分组之前，先把输入按n的顺序分成前后两半(注意，这不是频率抽选)； 算法特点 1 同址运算 2蝶形运算两节点的“距离” 3 的确定 按频率抽选法与按时间抽选法的异同 DIF的基本蝶形与DIT的基本蝶形运算顺序有所不问，这才是实质的不同，DIF的复数乘法只出现在减法之后，DIT则是先作复乘后作加减法。 DIF与DIT就运算量来说则是相同的，即都有L级(列)运算，每级运算需N／2个蝶形运算来完成，总共需要 次复乘与 次复加 DIF法与DIT法都可进行同址运算。 离散傅里叶反变换(IDFT)的快速计算方法 基-4FFT算法 时就是基-4FFT算法 可以把一个DFT分成4个N/4点的DFT 实序列的FFT算法 实际工作中序列一般都是实序列，如果直接按照FFT的算法计算，就是把序列看成是虚部为零的复序列计算，这增加了存储量和运算时间。 解决方法一： 一个N点的FFT计算两个N点的实序列FFT,一个序列作实部，另一个序列作虚部，计算完FFT后,有DFT的共轭对称性，由输出X(k)得到两个实序列的N点DFT 方法二 设x(n)为N点序列，取x(n)的偶数点和奇数点作为新序列的实部和虚部： 对y(n)进行N/2点的FFT，输出Y(k) 则： 出于计算机上乘法运算所用时间比加法运算所需时间多得多、故以乘法为例，在直接计算DFT与FFT算法的计算量之比为： 372.4 11264 4194304 2048 204.8 5120 1048576 1024 113.8 2304 262114 512 64.0 1024 65536 256 36.6 448 16394 128 21.4 192 4096 64 12.8 80 1024 32 8.0 32 256 16 5.4 12 64 8 4.0 4 16 4 4.0 1 4 2 p, q是参与本碟形单元运算的上下节点的序号。第m级序号为p, q的两点只参与这一个碟形单元的运算