快速傅氏变换之旅(一) 概念简介 2-白红宇

快速傅氏变换之旅(一) 概念简介 2

阅读量：2398 次

发布时间：2019-05-10

本文共 2414 字，大约阅读时间需要 8 分钟。

快速傅里叶变换

定义：离散傅里叶变换的一种快速算法，能克服时间域与频率域之间相互转换的计算障碍，在光谱、大气波谱分析、数字信号处理等方面有广泛应用。

有限长序列可以通过(DFT)将其频域也离散化成有限长序列。但其计算量太大，很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。

快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说中应用离散傅立叶变换，可以说是进了一大步。

计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频率抽取的FFT算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点：一是的周期性；另一是的对称性，这里符号*代表其共轭。这样,便可以把离散傅里叶变换的计算分成若干步进行，计算效率大为提高。

时间抽取算法 　令信号序列的长度为

N=2,其中

M是正整数，可以将时域信号序列

n)分解成两部分，一是偶数部分

x（2

n），另一是奇数部分

x（2

n+1），其中。于是信号序列

n)的离散傅里叶变换可以用两个

N/2抽样点的离散傅里叶变换来表示和计算。考虑到和离散傅里叶变换的周期性，式(1)可以写成

　　(3)其中(4a)(4b)由此可见，式(4)是两个只含有

N/2个点的离散傅里叶变换，

k)仅包括原信号序列中的偶数点序列，

k)则仅包括它的奇数点序列。虽然

k=0，1，2，…，

N-1，但是

k)和

k)的周期都是

N/2,它们的数值以

N/2周期重复。

　　因为于是由式(3)和式(4)得到(5a)(5b)

　　因此，一个抽样点数为

N 的信号序列

n)的离散傅里叶变换，可以由两个

N/2抽样点序列的离散傅里叶变换求出。依此类推，这种按时间抽取算法是将输入信号序列分成越来越小的子序列进行离散傅里叶变换计算，最后合成为N点的离散傅里叶变换。

　　通常用图1中蝶形算法的信号流图来表示式(5)的离散傅里叶变换运算。例如，

N=8=2的抽样点的信号序列

n)的离散傅里叶变换,可用如图2所示的FET算法的信号流图来计算。

　　①　

N=2点的离散傅里叶变换的计算全由蝶形运算组成，需要

M级运算，每级包括

N/2个蝶形运算，总共有个蝶形运算。所以，总的计算量为次复数乘法运算和

N log2

N次复数加法运算。

　　②　FFT算法按级迭代进行，计算公式可以写成

　　(6)

N抽样点的输入信号具有

N个原始数据

x0(

n),经第一级运算后，得出新的

N个数据

x1(

n)，再经过第二级迭代运算，又得到另外

N个数据

x2(

n)，依此类推，直至最后的结果

k)=

xM(

k)=

k)在逐级迭代计算中，每个蝶形运算的输出数据存放在原来存贮输入数据的单元中，实行所谓“即位计算”，这样可以节省大量存放中间数据的寄存器。

　　③　蝶形运算中加权系数随迭代级数成倍增加。由图2可以看出系数的变化规律。对于

N=8,

M=3情况，需进行三级迭代运算。在第一级迭代中，只用到一种加权系数；蝶形运算的跨度间隔等于1。在第二级迭代中，用到两种加权系数即、；蝶形运算的跨度间隔等于2。在第三级迭代中，用到4种不同的加权系数即、、、；蝶形运算的跨度间隔等于4。可见,每级迭代的不同加权系数的数目比前一级迭代增加一倍；跨度间隔也增大一倍。

　　④　输入数据序列

n)需重新排列为

x(0)、

x(4)、

x(2)、

x(6)、

x(1)、

x(5)、

x(3)、

x(7),这是按照二进制数的码位倒置所得到的反序数，例如

N=8中数“1”的二进制数为“001”，将其码位倒转变为“100”，即为十进制数“4”。

频率抽取算法　按频率抽取的 FFT算法是将频域信号序列