周期信号的频率表示是离散的图形，谱线之间有相等的间隔，这些间隔等于基本频率; 确定波形的形状，基频F􀬴是给定周

来源: marketreflections 于 2010-11-19 18:13:12 [] [博客] [旧帖] [给我悄悄话] 阅读数 : (20593 bytes)

http://read.pudn.com/downloads74/sourcecode/others/266781/%E5%BF%AB%E9%80%9F%E5%82%85%E7%AB%8B%E5%8F%B6%E7%AE%97%E6%B3%95%E7%9A%84%E5%88%86%E6%9E%90%E4%B8%8E%E5%AE%9E%E7%8E%B0.pdf

DSP 2006-2007
快速傅立叶算法分析
The College of Computer Science
Beijing University of Technology
S200607097 杨涛
Email : i_am_ytao@126.com
数字信号处理 S200607097 杨涛
2
目录
一、傅立叶分析理论的提出 ................................................................................................... 3
二、傅立叶分析的类别及其联系 ........................................................................................... 3
（一）连续周期信号的傅立叶级数 ................................................................................... 3
（二）连续非周期信号的傅立叶变换 ............................................................................... 4
（三）离散周期信号的傅立叶级数 ................................................................................... 4
（四）离散非周期信号的傅立叶变换 ............................................................................... 4
（五）离散傅立叶变换 ....................................................................................................... 5
三、快速傅立叶变换的算法分析 ........................................................................................... 5
（一）快速傅立叶变换提出的原因 ................................................................................... 5
（二）快速傅立叶变换的原理 ........................................................................................... 6
（三）基2 快速傅立叶算法分析 ...................................................................................... 6
四、快速傅立叶算法的实现 ................................................................................................... 6
（一）算法设计 ................................................................................................................... 6
（1）计算相位因子Wn .................................................................................................. 7
（2）蝶形运算 ................................................................................................................. 7
（3）重排信号序列 ......................................................................................................... 8
（二）结果分析 ................................................................................................................... 9
五、参考文献 ........................................................................................................................... 9
数字信号处理 S200607097 杨涛
3
一、傅立叶分析理论的提出
在物理学研究中，科学家发现当白光通过玻璃棱镜可被分解为不同颜色的光，每一种颜
色对应一种可见光谱的特定频率，因此由光到颜色的分析就是一种频率分析。将这种思想应
用到对信号性质的研究中，就引出了傅立叶分析理论。
将信号展开成傅立叶级数的基本目的就是要将时间变量t 的函数分解为不同的频率分
量，这些基本的构造分量正弦和余弦函数。数学家已经证明，形如（1）式的三角函数的和
式就足以表示绝大多数曲线。
􀝂􁈺􀝔􁈻 􀵌 􀜽􀬴 􀵅 􀷍􁈺􀜽􀯞 cos 􀝇􀝔 􀵅 􀜾􀯞 sin 􀝇􀝔􁈻
􀮶
􀯞􀭀􀬵
（1）
对周期函数进行这种分解，被称为傅立叶级数；对有限能量信号函数，这种分解被称为
傅立叶变换。三角函数展开起源于18 世纪关于简谐振动以及类似的物理现象的研究。1808
年傅立叶在著作《热的分析理论》中详细地研究了三角函数，并利用三角函数解决了很多热
传导问题。在随后的二百年间，傅立叶分析理论得到不断的发展，并被应用于众多的领域，
例如用来消除信号中的高频噪声或进行数据压缩等等。
二、傅立叶分析的类别及其联系
根据信号的各种分类和相应特点，我们可以将施加其上的傅立叶分析分为诸如连续信号
傅立叶级数和傅立叶变换、离散信号傅立叶级数和傅立叶变换；根据对信号的处理策略上的
改进，又由离散傅立叶变换（DFT）衍生了快速傅立叶变换（FFT）等等。在刚刚接触这些术
语和缩写时常常会感到混乱和迷惑。为了更加清晰地认识其理论脉络，下面将简要介绍它们
各自的应用范围，以及它们之间的联系与区别。
（一）连续周期信号的傅立叶级数
傅立叶级数是周期信号的基本数学表示，它是相关正弦信号或负指数信号的线性加权和。
出于数学上分析和表示的方便，常根据欧拉公式（2）将傅立叶级数表示为复指数信号和的
信号。
e􀵇􀭨􀗎 􀵌 cos 􀗎 􀵇 sin 􀗎 （2）
Dirichlet 条件保证了除不连续时刻外，级数式（3）一定和初始信号x(t)相吻合。
x􁈺t􁈻 􀵌 􀷍 c
􀭩
􀮶
􀭩􀭀􀬿􀮶
e􀭨􀬶􀮠􀭩F􀰬􀭲 􁈺3􁈻
c􀭩 􀵌 􀬵
TP
􀗬 x􁈺t􁈻 TP
e􀬿􀭨􀬶􀮠􀭩F􀰬􀭲dt 􁈺4􁈻
其中系数c􀭩确定波形的形状，基频F􀬴是给定周期TP的倒数，确定基本周期，选取适当
的基频F􀬴和系数c􀭩就可以构造不同类型的周期信号。
数字信号处理 S200607097 杨涛
4
（二）连续非周期信号的傅立叶变换
由上面的公式（3）我们可以知道，周期信号的频率表示是离散的图形，谱线之间有相
等的间隔，这些间隔等于基本频率。如果信号的周期趋近于无限，信号变为非周期的，谱线
间隔将趋近0，因此信号的频率表示变成连续函数。非周期信号通过周期为TP的重复得到周
期信号，我们可以看到傅立叶级数和傅立叶变换之间的本质区别是后者的谱是连续的，因此
在公式（5）中合成非周期信号的过程使用积分运算代替了（3）式中的求和运算。
x􁈺t􁈻 􀵌 􀶱 X􁈺F􁈻
􀮶
􀬿􀮶
e􀭨􀬶􀮠􀭩F􀭲dF 􁈺5􁈻
X􁈺F􁈻 􀵌 􀶱 x􁈺t􁈻
􀮶
􀬿􀮶
e􀬿􀭨􀬶􀮠􀭩F􀭲dt 􁈺6􁈻
（三）离散周期信号的傅立叶级数
从上面的介绍我们可以知道，由于连续周期信号的频率范围是从􀵆∞延伸到∞。然而离
散时间信号的频率范围在（ 􀵆 π，π）或（0，2π），以N 为周期，频率分量间隔2π/N。因
此离散周期信号的傅立叶级数最多包含N 个频率分量，这是连续周期信号与离散周期信号
的傅立叶级数之间的主要差别。
x􁈺t􁈻 􀵌 􀷍 c􀭩
N
􀭩􀭀􀬴
e􀭨􀬶􀮠􀭩􀭬/N 􁈺7􁈻
c􀭩 􀵌
1
N
􀷍 x􁈺t􁈻
N􀬿􀬵
􀭬􀭀􀬴
e􀬿􀭨􀬶􀮠􀭩􀭬/N 􁈺8􁈻
公式（7）称为离散时间傅立叶级数（DTFS）。
（四）离散非周期信号的傅立叶变换
与连续信号的傅立叶分析相似，我们也可以同样从对周期信号的频谱分析推广到非周期
信号的情况。
x􁈺n􁈻 􀵌
1
2π
􀶱 X􁈺ω􁈻e􀭨􀮩􀭬dω
􀬶􀮠
􁈺9􁈻
X􁈺ω􁈻 􀵌 􀷍 x􁈺n􁈻
􀮶
􀭬􀭀􀬿􀮶
e􀬿􀭨􀮩􀭬 􁈺10􁈻
公式（10）中的X􁈺ω􁈻 以2π为周期，因为任何离散时间信号的频率范围限制在
（ 􀵆 π，π）或（0，2π）。信号在时间域是离散的，因此公式（10）用求和号代替了公式
（6）中的积分号，被称为离散时间傅立叶变换（DTFT）。
数字信号处理 S200607097 杨涛
5
（五）离散傅立叶变换
从上文对离散时间傅立叶变换的分析可以看出X􁈺ω􁈻是序列x􁈺n􁈻的频域等效表示，然而
X􁈺ω􁈻是频率的连续函数。由于在计算机中无法表示连续频域，考虑使用X􁈺ω􁈻的等间隔频率
样本X（2πk/N）, k 􀵌 0,1, … , N 􀵆 1,来表示频域信息,就引出了离散傅立叶变换（DFT）。需要
注意的是，DFT 和上小节介绍的DTFT 之间的区别，后者的频率域是连续的。离散傅立叶变
换在频域分析中有着重要的地位，因为它将时域的离散信号转换为离散频率域的表示形式，
使得在计算机以及其他数字系统中应用傅立叶变换成为可能。公式（11）和（12）分别表示
了傅立叶变换和反变换。
X􁈺k􁈻 􀵌 􀷍 x􁈺n􁈻
N􀬿􀬵
􀭬􀭀􀬴
e􀬿􀭨􀬶􀮠􀭩􀭬/N k 􀵌 0,1,2 … , N 􀵆 1 􁈺11􁈻
x􁈺n􁈻 􀵌
1
N
􀷍 X􁈺k􁈻
N􀬿􀬵
􀭬􀭀􀬴
e􀭨􀬶􀮠􀭩􀭬/N k 􀵌 0,1,2 … , N 􀵆 1 􁈺12􁈻
三、快速傅立叶变换的算法分析
快速傅立叶变换是离散傅立叶变换的改进和优化，利用DFT 的相关数学性质，通过使
用各种巧妙的算法提高计算性能。由于在计算机上实现傅立叶变换需要巨大的计算量，正是
快速傅立叶变换的出现才使得这些理论和方法能够在计算机上实现和普及。
（一）快速傅立叶变换提出的原因
由第二章的介绍我们知道离散傅立叶变换能够在计算机上进行实现，在诸如线性滤波、
相关分析和谱分析等众多领域有着广泛的应用。然而在实际解决问题时，DFT 的巨大数据运
算量却使得它难以最大地发挥傅立叶变换的优势。
给定长度为N 的数据序列x􁈺n􁈻，将它的DFT 定义为：
X􁈺k􁈻 􀵌 􀷍 x􁈺n􁈻
N􀬿􀬵
􀭬􀭀􀬴
WN
􀭩􀭬 0 􀵑 k 􀵑 N 􀵆 1 􁈺13􁈻
其中 WN 􀵌 e􀬿􀭨􀬶􀮠/N （14）
通过对公式（13）的计算过程进行分析可以发现，公式首先进行了N 次的复数乘法
x􁈺n􁈻WN
􀭩􀭬，每次复数乘法可以分解为4 次实数乘法；随后公式进行了N

请您先登陆，再发跟帖！