快速傅立叶变换(FFT)算法实验结果分析

快速傅立叶变换(FFT)算法实验

摘要：FFT（Fast Fourier Transformation），即为快速傅里叶变换，是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。这种算法大大减少了变换中的运算量，使得其在数字信号处理中有了广泛的运用。本实验主要要求掌握在CCS环境下用窗函数法设计FFT快速傅里叶的原理和方法；并且熟悉FFT快速傅里叶特性；以及通过本次试验了解各种窗函数对快速傅里叶特性的影响等。 引言：

快速傅里叶变换FFT是离散傅里叶变换DFT的一种快速算法。起初DFT的计算在数字信号处理中就非常有用，但由于计算量太大，即使采用计算机也很难对问题进行实时处理，所以并没有得到真正的运用。1965年J.W.库利和T.W.图基提出快速傅里叶变换，采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FF

实验一 快速傅立叶变换

( 信息工程专业 )

一 实验目的

1 在理论学习的基础上，通过本实验加深对快速傅立叶变换的理解； 2 熟悉并掌握按时间抽取FFT算法的程序；

3 了解应用FFT进行信号频谱分析过程中可能出现的问题，例如混淆、泄漏、栅栏效应等，以便在实际中正确应用FFT。

二 实验内容

1 仔细分析教材第六章‘时间抽取法FFT ’的算法结构，编制出相应的用FFT

进行信号分析的C语言（或MATLAB 语言）程序；

2 用FFT程序计算有限长度正弦信号

y(t)?sin(2?ft),0?t?N*T

分别在以下情况下所得的DFT结果并进行分析和讨论：

a） 信号频率f＝50Hz，采样点数N=32,采样间隔T=0.000625s

b） 信号频率f＝50Hz，采样点数N=32,采样间隔T=0.005s

c） 信号频率f＝50Hz，采样点数N=32,采样间隔T=0.0046875s

d） 信号频率f＝50Hz，采样点数N=32,采样间隔T=0.004s

e） 信号频率f＝50Hz，采样点数N=64,采样间隔T=0.000625s

f） 信号频率f＝250Hz，采样点数N=32,采样间隔T=0.005s

g）

第四章 快速傅立叶变换

4.1 引言：

DFT 的运算量

1

0()(),0,1,,1N kn N n X k x n W

k N -===???-∑

计算一个N 点的DFT ，所需要的复数乘法和加法的次数分别为

()()()()a jb c jd ac bd j bc ad ++=-++

*,(1)N N N N N N ==-复乘复加

实数乘法和加法的次数分别为

4*,4(1)N N N N N N ==-实乘实加

直接用DFT 算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT 的发生了根本的变化。

4.2 基2FFT 算法

1、改进的途径：利用旋转因子的性质

（1）旋转因子m N W 的周期性：

22()j m lN j m m lN

m

N N N N W e e W ππ-+-+=== （2）旋转因子m N W 的对称性：

2[]N m m

N m N m m m

N N N N N N W W W W W W +---*===-，， （3）可约性

//m nk nk nk nk m

m N N N N m W W W W ==， /21N N W =-，(/2)k N k

N N W W +=- 利用上述特性,可以将有些项合并,并将DFT 分解为短序

快速傅里叶变换（FFT）的DSP实现

（天津大学电子信息工程学院）

摘要：本文介绍了快速傅里叶变换（FFT）的快速高效的原理及实现方法，对快速傅立叶变换（FFT）的特点进行了研究和总结。对于快速傅立叶变换（FFT） 在TMS320C54X系列数字信号处理器（DSP）实现中出现的计算溢出等问题进行了分析并提出了解决方法，同时据此使用DSP实现了快速傅立叶变换（FFT）。 关键词：数字信号处理；快速傅立叶变换；反序；计算溢出

1 引言：

傅里叶变换是一种将信号从时域变换到频域的变换方式，在语音处理、图像处理、信号处理领域中都发挥了极大的作用，是一种重要的分析工具。离散傅里叶变换（DFT）是连续傅里叶变换在离散系统中的表现形式，具有非常广泛的应用。但是由于DFT的计算量很大，因此在很长一段时间里其应用受到限制。快速傅里叶变换（FFT）是实现普通离散傅里叶变换的一种高效方法，快速傅里叶变换（FFT）的出现使得傅里叶变换在实际中得到了广泛的应用。

快速傅里叶变换并不是一种新的变换，它是离散傅里叶变换的一种快速算法。它是DSP领域中的一项重大突破。由于考虑了计算机和数字硬件实现的约束条件，研究了有利于机器操作的运算结构，使DSP的计算时间缩短了一到两个

一、傅立叶变换的由来

关于傅立叶变换，无论是书本还是在网上可以很容易找到关于傅立叶变换的描述，但是大都是些故弄玄虚的文章，太过抽象，尽是一些让人看了就望而生畏的公式的罗列，让人很难能够从感性上得到理解，最近，我偶尔从网上看到一个关于数字信号处理的电子书籍，是一个叫Steven W. Smith, Ph.D.外国人写的，写得非常浅显，里面有七章由浅入深地专门讲述关于离散信号的傅立叶变换，虽然是英文文档，我还是硬着头皮看完了有关傅立叶变换的有关内容，看了有茅塞顿开的感觉，在此把我从中得到的理解拿出来跟大家分享，希望很多被傅立叶变换迷惑的朋友能够得到一点启发，这电子书籍是免费的，有兴趣的朋友也可以从网上下载下来看一下，URL地址是：http://www.dspguide.com/pdfbook.htm

要理解傅立叶变换，确实需要一定的耐心，别一下子想着傅立叶变换是怎么变换的，当然，也需要一定的高等数学基础，最基本的是级数变换，其中傅立叶级数变换是傅立叶变换的基础公式。

二、傅立叶变换的提出

让我们先看看为什么会有傅立叶变换？傅立叶是一位法国数学家和物理学家的名字，英语原名是Jean Baptiste Joseph Fourier (1768-183

第4章 快速傅里叶变换

第四章 快速傅里叶变换

第4章 快速傅里叶变换

4.1 4.2

引言 直接计算DFT的问题及改进的途径

4.34.4 4.5 4.6 4.7

按时间抽取(DIT)的基2-FFT算法按频率抽取(DIF)的基2-FFT算法 离散傅里叶反变换(IDFT)的快速计算方法 线性卷积的FFT算法——快速卷积 FFT的其他应用

第4章 快速傅里叶变换

本章学习目标理解按时间抽选的基-2FFT算法的算法原理、运算 流图、所需计算量和算法特点

理解按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点 了解IFFT算法 理解线性卷积的FFT算法及分段卷积算法

第4章 快速傅里叶变换

4.1 引 言快速傅里叶变换(FFT)并不是一种新的变换， 而是 离散傅里叶变换(DFT)的一种快速算法。  由于有限长序列在其频域也可离散化为有限长序列， 因此离散傅里叶变换(DFT)在数字信号处理中是非常有 用的。例如，在信号的频谱分析、 系统的分析、 设计和 实现中都会用到DFT的计算。 但是，在相当长的时间里， 由于DFT的计算量太大，即使采用计算机也很难对问题进 行实时处理，所以并没有得到真正的运用。 直到1965年

首次发现了DFT运算的一种快速算法以

实验一 离散时间系统的时域分析

一、实验目的

１. 运用MATLAB仿真一些简单的离散时间系统，并研究它们的时域特性。

２. 运用MATLAB中的卷积运算计算系统的输出序列，加深对离散系统的差分方程、冲激响应和卷积分析方法的理解。

二、实验原理

离散时间系统其输入、输出关系可用以下差分方程描述：

当输入信号为冲激信号时，系统的输出记为系统单位冲激响应

N?dkk?0y[n?k]?M?k?0pkx[n?k]?[n]?h[n]，则系统响应为如下的卷积计算式：

y[n]?x[n]?h[n]?m????x[m]h[n?m]

? 当h[n]是有限长度的（n：[0，M]）时，称系统为FIR系统；反之，称系统为IIR系统。在MATLAB中，可以用函数y=Filter(p,d,x) 求解差分方程，也可以用函数 y=Conv(x,h)计算卷积。 例1

clf; n=0:40; a=1;b=2; x1= 0.1*n;

x2=sin(2*pi*n); x=a*x1+b*x2; num=[1, 0.5,3]; den=[2 -3 0.1];

ic=[0 0]; %设置零初始条件

y1=filter(num,den,x1,ic); %计算输入为x1(n

实验七快速傅里叶变换实验

2011010541 机14林志杭

一、实验目的

1 ?加深对几个特殊概念的理解：“采样”……“混叠”；“窗函数”(截断)……“泄漏”;

“非整周期截取”……“栅栏”。

2 ?加深理解如何才能避免“混叠”，减少“泄漏”，防止“栅栏”的方法和措施以及估计这些因素对频谱的影响。

3 ?对利用通用微型计算机及相应的FFT软件，实现频谱分析有一个初步的了解。

二、实验原理

为了实现信号的数字化处理，利用计算机进行频谱分析一一计算信号的频谱。由于

计算机只能进行有限的离散计算(即DFT),因此就要对连续的模拟信号进行采样和截断。

而这两个处理过程可能引起信号频谱的畸变，从而使DFT的计算结果与信号的实际

频谱有误差。有时由于采样和截断的处理不当，使计算出来的频谱完全失真。因此在时域处理信号时要格外小心。

时域采样频率过低，将引起频域的“混叠”。为了避免产生“混叠”，要求时域采样时必须满

足采样定理，即：采样频率fs必须大于信号中最高频率fc的2倍(fs> 2fc)。因此在信号

数字处理中，为避免混叠，依不同的信号选择合适的采样频率将是十分重要的。

频域的“泄漏”是由时域的截断引起的。时域的截断使频域中本来集中的能量向它的邻域扩

散(如由一个3( f)变成一个

实验三 FFT算法的应用

一、实验目的

1. 2. 3.

通过实验加深对快速傅立叶变换（FFT）基本原理的理解。 掌握FFT的用于信号的谱分析； 掌握利用FFT计算卷积。

二、实验仪器设备

PC机 MATLAB软件

三、实验原理

离散傅里叶变换（DFT）和卷积是信号处理中两个最基本也是最常用的运算，它们涉及到信号、系统的分析与综合这一广泛的信号处理领域。实际上卷积与DFT之间有着互通的联系：卷积可化为DFT来实现，其它的许多算法，如相关、滤波和谱估计等都可化为DFT来实现，DFT也可化为卷积来实现。 1.MATLAB中DFT的FFT实现

对N点序列x(n)，其DFT变换对定义为：

N?1?nk?X(k)??x(n)WN?n?0?N?11?nk?x(n)?X(k)WN??Nk?0?k?0,1,...,N?1,WN?n?0,1,...,N?1e?j2?/N

显然，求出N点X(k)需要N次复数乘法，N(N-1)次复数加法。众所周知，实现一次复

数乘需要四次实数乘和两次实数加，实现一次复数加则需要两次实数加。当N很大时，其计算量是相当可观的。例如，若N=1024，则需要1,048,576次复数乘法，即4,194,304次实数乘法。所需时间过长

实验三 FFT算法的应用

一、实验目的

1. 2. 3.

通过实验加深对快速傅立叶变换（FFT）基本原理的理解。 掌握FFT的用于信号的谱分析； 掌握利用FFT计算卷积。

二、实验仪器设备

PC机 MATLAB软件

三、实验原理

离散傅里叶变换（DFT）和卷积是信号处理中两个最基本也是最常用的运算，它们涉及到信号、系统的分析与综合这一广泛的信号处理领域。实际上卷积与DFT之间有着互通的联系：卷积可化为DFT来实现，其它的许多算法，如相关、滤波和谱估计等都可化为DFT来实现，DFT也可化为卷积来实现。 1.MATLAB中DFT的FFT实现

对N点序列x(n)，其DFT变换对定义为：

N?1?nk?X(k)??x(n)WN?n?0?N?11?nk?x(n)?X(k)WN??Nk?0?k?0,1,...,N?1,WN?n?0,1,...,N?1e?j2?/N

显然，求出N点X(k)需要N次复数乘法，N(N-1)次复数加法。众所周知，实现一次复

数乘需要四次实数乘和两次实数加，实现一次复数加则需要两次实数加。当N很大时，其计算量是相当可观的。例如，若N=1024，则需要1,048,576次复数乘法，即4,194,304次实数乘法。所需时间过长