《按时间抽取的基2FFT算法分析报告》由会员分享，可在线阅读，更多相关《按时间抽取的基2FFT算法分析报告（14页珍藏版）》请在金锄头文库上搜索。
1、. . . 第四章 快速傅里叶变换 有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基DIT和基DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。快速傅里叶变换（FFT）是计算离散傅里叶
2、变换（DFT）的快速算法。 DFT的定义式为=在所有复指数值的值全部已算好的情况下，要计算一个需要N次复数乘法和N1次复数加法。算出全部N点共需次复数乘法和次复数加法。即计算量是与成正比的。FFT的基本思想：将大点数的DFT分解为若干个小点数DFT的组合，从而减少运算量。因子具有以下两个特性，可使DFT运算量尽量分解为小点数的DFT运算：（1） 周期性：（2） 对称性：利用这两个性质，可以使DFT运算中有些项合并，以减少乘法次数。例子：求当N4时，X(2)的值 通过合并，使乘法次数由4次减少到1次，运算量减少。FFT的算法形式有很多种，但基本上可以分为两大类：按时间抽取（DIT）和按频率抽取（
3、DIF）。4.1 按时间抽取（DIT）的FTT 为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为复合数，最常用的是的情况（M为正整数）。该情况下的变换称为基2FFT。下面讨论基2情况的算法。 先将序列x(n)按奇偶项分解为两组 将DFT运算也相应分为两组 （因为）其中、分别是的N/2点的DFT至此，一个N点DFT被分解为两个N/2点的DFT。 上面是否将全部N点的求解出来了？分析：和只有N/2个点（），则由只能求出的前N/2个点的DFT，要求出全部N点的，需要找出、和的关系，其中。由式子可得化简得，这样N点DFT可全部由下式确定出来： （）上式可用一个专用的碟形符号来表示，这个
4、符号对应一次复乘和两次复加运算。图蝶形运算符号通过这样的分解以后，每一个N2点的DFT只需要次复数乘法，两个N/2点的DFT需要次复乘，再加上将两个N2点DFT合并成为N点DFT时有N2次与W因子相乘，一共需要次复乘。可见，通过这样的分解，运算量节省了近一半。因为，N/2仍然是偶数，因此可以对两个N/2点的DFT再分别作进一步的分解，将两个N/2点的DFT分解成两个N/4点的DFT。例如对，可以在按其偶数部分及奇数部分进行分解： 则的运算可相应分为两组： 将系数统一为以为周期，即，可得 同样，对也可进行类似的分解。一直分解下去，最后是点的DFT，点DFT的运算也可用碟形符号来表示。这样，对于一
5、个的DFT运算，其按时间抽取的分解过程及完整流图如下图所示。这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，故称为“时间抽取法”。分析上面的流图，一共要进行M次分解，构成了从x(n)到X(k)的M级运算过程。每一级运算都是由N/2个蝶形运算构成，因此每一级运算都需要N/2次复乘和N次复加，则按时间抽取的M级运算后总共需要复数乘法次数：复数加法次数：根据上面的流图，分析算法的两个特点，它们对的软硬件构成产生很大的影响。（） 原位运算也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图分
6、析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备成本。（） 变址分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”的顺序。见图。自然顺序二进制表示码位倒置码位倒置顺序0000000010011004201001023011110641000011510110156110011371111117码位倒置顺序在实际运算中，直接将输入数据x(n)按码位倒置的顺序排好输入很不方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序的存储换成码位倒置顺序的存储，这样就可以进行FFT的原位运算。变质的功能如图所示。用软件实现是通用采用雷德（Rader）算法，算出I
7、的倒序以后立即将输入数据X(I)和X(J)对换。尽管变址运算所占运算量的比例很小，但对某些高要求的应用（尤其在实时信号处理中），也可设法用适当的电路结构直接实现变址。例如单片数字信号处理器TMS320C25就有专用于FFT的二进制码变址模式。4. 按频率抽取（DIF）的FTT除时间抽取法外，另外一种普遍使用的FFT结构是频率抽取法。频率抽取法将输入序列不是按奇、偶分组，而是将点DFT写成前后两部分： 因为，k为偶数时，k为奇数时，由此可将X(k)分解为偶数组和奇数组：令这两个序列都是N/2点的序列，对应的是两个N/2点的DFT运算：这样，同样是将一个N点的DFT分解为两个N/2点的DFT了。频
8、率抽选法对应的碟形运算关系图如下：对于N=8时频率抽取法的FFT流图如下：这种分组的办法由于每次都是按输出X(k)在频域的顺序上是属于偶数还是奇数来分组的，称为频率抽取法。与前面按时间抽取的方法相比，相同点问题：如何利用快速算法计算IDFT？分析IDFT的公式：比较DFT的公式：得知可用两种方法来实现IDFT的快速算法：（）只要把DFT运算中的每一个系数该为，并且最后再乘以常数，就可以用时间抽取法或频率抽取的FFT算法来直接计算IDFT。这种方法需要对FFT的程序和参数稍加改动才能实现。（）因为，也就是说，可先将X(k)取共轭变换，即将X(k)的虚部乘以，就可直接调用FFT的程序，最后再对运算
9、结果取一次共轭变换并乘以常数1/N即可得到x(n)的值。这种方法中，FFT运算和IFFT运算都可以共用一个子程序块，在使用通用计算机或用硬件实现时比较方便。4.1.3 混合基FFT算法以上讨论的是基2的FFT算法，即的情况，这种情况实际上使用得最多，这种FFT运算，程序简单，效率很高，用起来很方便。另外，在实际应用时，有限长序列的长度N到底是多少在很大程度时是由人为因素确定的，因此，大多数场合人们可以将N选定为，从而可以直接调用以为基数的FFT运算程序。如果长度N不能认为确定，而N的数值又不是以2为基数的整数次方，一般可有以下两种处理方法：（） 将x(n)用补零的方法延长，使N增长到最邻近的一
10、个数值。例如，N=30，可以在序列x(n)中补进x(30)x(31)两个零值点，使N=32。如果计算FFT的目的是为了了解整个频谱，而不是特定频率点，则此法可行。因为有限长序列补零以后并不影响其频谱，只是频谱的采样点数增加而已。（） 如果要求特定频率点的频谱，则N不能改变。如果N为复合数，则可以用以任意数为基数的FFT算法来计算。快速傅里叶变换的基本思想就是要将DFT的运算尽量分小。例如，N=6时，可以按照N=3分解，将点DFT分解为组点DFT。举例：N=9时的快速算法。4.2 快速傅里叶变换的应用凡是可以利用傅里叶变换来进行分析、综合、变换的地方，都可以利用FFT算法及运用数字计算技术加以实
11、现。FFT在数字通信、语音信号处理、图像处理、匹配滤波以及功率谱估计、仿真、系统分析等各个领域都得到了广泛的应用。但不管FFT在哪里应用，一般都以卷积积分或相关积分的具体处理为依据，或者以用FFT作为连续傅里叶变换的近似为基础。4.2.1 利用FFT求线性卷积快速卷积在实际中常常遇到要求两个序列的线性卷积。如一个信号序列x(n)通过FIR滤波器时，其输出y(n)应是x(n)与h(n)的卷积：有限长序列x(n)与h(n)的卷积的结果y(n)也是一个有限长序列。假设x(n)与h(n)的长度分别为N1和N2，则y(n)的长度为N=N1+N2-1。若通过补零使x(n)与h(n)都加长到N点，就可以用圆
12、周卷积来计算线性卷积。这样得到用FFT运算来求y(n)值（快速卷积）的步骤如下：（） 对序列x(n)与h(n)补零至长为N，使NN1+N2-1，并且，即（） 用FFT计算x(n)与h(n)的离散傅里叶变换（N点）（N点）（） 计算Y(k)=X(k)H(k)（） 用IFFT计算Y(k)的离散傅里叶反变换得：y(n)=IFFTY(k)（N点）4.2.2 利用FFT求相关快速相关互相关及自相关的运算已广泛的应用于信号分析与统计分析，应用于连续时间系统也用于离散事件系统。用FFT计算相关函数称为快速相关，它与快速卷积完全类似，不同的是一个应用离散相关定理，另一个应用离散卷积定理。同样都要注意到离散傅里
13、叶变换固有的周期性，也同样用补零的方法来绕过这个障碍。设两个离散时间信号x(n)与y(n)为已知，离散互相关函数记作，定义为如果x(n)与y(n)的序列长度分别为N1和N2，则用FFT求相关的计算步骤如下：（）对序列x(n)与y(n)补零至长为N，使NN1+N2-1，并且，即（）用FFT计算x(n)与y(n)的离散傅里叶变换（N点）（N点）（）将X(k)的虚部ImX(k)改变符号，求得其共轭X*(k)（）计算=X*(k)Y(k)（） 用IFFT求得相关序列IFFT（N点）如果x(n)y(n)，则求得的是自相关序列4.2.3 ChirpZ变换采用FFT算法可以很快的计算出全部DFT值，也即Z变换
14、在单位圆上的全部等间隔采样值。但是，很多场合下，并非整个单位圆上的频谱都是很有意义的，例如对于窄带信号过程，往往只需要对信号所在的一段频带进行分析，这是，希望采样能密集在这段频带，而对频带以外的部分，则可以完全不管。另外，有时也希望采样能不局限于单位圆上，例如，语音信号处理中，往往需要知道其Z变换的极点所在频率，如果极点位置离单位圆较远，则其单位圆上的频谱就很平滑，如图所示，这是很难从中识别出极点所在的频率。要是采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则所得的结果将会在极点所在频率上出现明显的尖峰，从而可以较准确的测定极点频率。螺线采样就是一种适用于这种需要的变换，并且可以采用FFT来快速计算，这种变换也称为Chirp-Z变换，它是沿Z平面上的一段螺线作等分角的采样，这些采样点可表达为其中M为采样点的总数，A为起始点位置，这个位置可以进一步用它的半径A0及相角来表示参数W可表示为其中为螺线的伸展率，时螺线缩（反时针方向）；时螺线外伸。为螺线上采样点之间的等分角。螺线采样点在Z平面上的分布可表示为下图。下面分析这些点上采样值计算的特点。假定x(
