FFT 算法详解

《FFT 算法详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.3快速傅立叶变换问题1)问题背景在数值电路的传输中，为了避免信号干扰，需要把一个连续信号x(t)先通过取样离散化为一列数值脉冲信号x(0),x(1),……,然后再通过编码送到传输电路中。如果取样间隔很小，而连续信号的时间段又很长，则所得到的数值脉冲序列将非常庞大。因此，传输这个编码信号就需要长时间的占用传输电路，相应地也需要付出昂贵的电路费用。那么能否经过适当处理是使上述的数值脉冲序列变短，而同时又不会丧失有用的信息？的经过研究，人们发现，如果对上述数值脉冲序列作如下的变换处理：(1)则所得到的新序列X(0),X(1),……将非常

2、有序，其值比较大的点往往集中在某一很狭窄的序列段内，这将非常有利于编码和存储，从而达到压缩信息的目的。公式（1）就是所谓的离散傅立叶变换，简称DFT。现在我们来分析一下计算DFT所需要的工作量。如果我们不考虑公式（7.1）中指数项的运算，那么计算其每一个点X(n)需要N次复数乘法和N-1次的复数加法。显然当N很大时，这个工作量也非常巨大。正是由于这个原因，使得DFT的应用范围在过去很长的时间里受到了严格的限制。注意到公式（1）是非常有规律性的，那么能否利用这种规律性来降低DFT的计算时间？1965年，凯莱和塔柯的提出了一种用于计算DF

3、T的数学方法，大大减少了DFT的计算时间，同时又特别适用于硬件处理，这就是所谓的快速傅里叶变换，简称FFT。鉴于DFT的数据结构可以通过傅立叶变换的离散化获得，亦可通过三角插值得到，而本质上又同连续傅里叶分析有着极为密切的关系。下面我们从傅立叶级数级数和傅立叶积分入手，导出DFT结构的来源和FFT的工作原理。2）傅立叶变换如果x(t)是定义在整个实轴上的实值或复值函数，则其傅立叶变换可由下式给出：（2）若对任意参数f，上述积分都存在，则（2）式确定了一个函数X(f)，称为x(t)的傅立叶变换。如果已知X(f)则利用如下的傅立叶逆变换，

4、还可复原x(t)：（3）若x(t)和X(f)同时满足（2）、（3）式，则称他们是一个傅立叶变换对，记为。。通常X(f)是一个复函数，因此可以写成如下两部分：，（4）式子中R(f)，I(f)分别是X(f)的实部和虚部。将上式表示为指数形式：（5）其中（6）工程技术中，常将x(t)看成一时间信号，相应的空间，称为时间域和空域；将其傅立叶变换X(f)看成频率函数，相应的空间称为频域。称为x(t)的傅立叶谱，而称为其相角，这在物理上是有良好背景的。的譬如此频率的的含义可以这样来理解：应用欧拉公式可将指数项表示成正弦-余弦的形式，如果把（2）式

5、解释成离散项和的极限，则显然X(f)是包含了无限项正弦-余弦的和，而且f的每一个值确定了所对应的正弦-余弦的频率。在以后的叙述中，我们不妨用t表示时间，用f表示频率；同时用小写字母表示时间函数，并用相应的大写字母表示其傅立叶变换。傅立叶变换可很容易地推广到二维情形。假设x(t,s)是连续的和可积的，且X(f,g)是可积的，则相应的傅立叶变换对如下：（7）（8）3）离散傅立叶变换尽管傅立叶级数和傅立叶变换具有非常优美的数学结构，但并不实用，并为他们都无法用有限字长的计算机作逻辑上的运算。为此，我们必须建立傅立叶变换的数值方法，并由此导出

6、DFT数据结构的来源。a.傅立叶积分的离散化由于傅立叶变换无法用数字计算机进行逻辑运算，工程分析中，通常采用抽样的方法，观测x(t)的一些离散值，然后利用数值积分将傅立叶变换离散化。函数抽样是函数插值的逆过程，假定用取2N+1个互相间隔为的节点的方法，当一个连续函数x(t)离散化为的一个序列：于是当N充分大时，有：（9）现在我们把（9）式中的求积函数当成周期为的函数，以为节点，对（9）式用复化梯形公式做数值积分得（10）对f进行离散化，取，则上式可改写：（11）这就是一维傅立叶积分的离散表达式。b离散傅立叶变换在上面，我们普便的遇到了

7、带有复指数乘积项的和式。实际上，这种特殊的数据结构可利用以下更为一般的方式定义。给定N个实或复的数列{x(0),x(1),……x(N-1)}，定义（12）为{x(k)}的离散傅立叶变换，简称DFT。我们指出，（11）式可以转化成上述一般形式。这说明（12）式与傅立叶变换之间存在内在的联系，渴望获得与连续傅立叶变换相类似的性质，事实上确实如此。下面我们就来做这件事。首先说明，由（12）式确定的序列{X(n)}可以恢复为原序列{x(k)}。事实上，在（12）式两边同乘以，并对n从0到n-1求和得：（13）注意到（13）式的和式中分子部分为

8、0，从而（14）今后我们称（14）式是（12）式的逆变换，并称{x(k)}和{X(n)}为离散傅立叶变换对，简记为离散傅立叶变换的这种可恢复性质，在工程技术中有着极为重要的应用。因为，可以通过抽样获得一组的离散值，并利用