《数字信号处理》课程论文
离散傅里叶变换(DFT)
算法简介及其应用举例
姓名：安昱
学号：12011243986
专业：通信工程
班级：2011级（1）班
指导老师：武永峰
学院：物理电气信息学院
完成日期：2013年11月11 日
离散傅里叶变换(DFT)算法简介及其应用举例
（安昱12011243986 2011级1班）
[摘要]：离散傅立叶变换（DFT）实现了信号首次在频域表示的离散化，使得频域也能够用
计算机进行处理。并且这种DFT变换可以有多种实用的快速算法。使信号处理在时、频域的处理和转换均可离散化和快速化。最后就该项目做了总结。
[关键词]DFT算法Matlab语言频域采样DFT应用
一、DFT算法原理
快速傅氏变换（FFT）是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。
设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2（N/2）2=N+N2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。
二、FFT的算法原理
FFT算法的输出X(K)为自然顺序，但为了适应原位计算，其输入序列不是按x(n)的自然顺序排序，这种经过M-1次奇偶抽选后的排序为序列的倒序。因此，在运算之前应先对序列x(n)进行倒序。倒序的规律就是把顺序数的二进制位倒置，即可得到倒序值。倒序数是在M位二进制数最高位加一，逢2向右进位。M 位二进制数最高位的权值为N/2，且从左到右二进制位的权值依次为你N/4，
N/8，…，2，1。因此，最高位加一相当于十进制运算J+N/2。（J 表示当前倒序数的十进制数值）
三、DFT 的定义
设序列x(n)长度为M ，定义x(n)的N 点DFT 为 1,...,1,0,)()]([)(210-===--=∑N k e
n x n x DFT k X kn N j N n N ρ
式中，N 称为离散傅里叶变换区间长度，要求N ≥ M 。为 书写简单，令N j N e W π
2-=，因此通常将N 点DFT 表示为
∑-=-===1
01,...,1,0,)()]([)(N n kn N N N k W n x n x DFT k X
定义X(k)的N 点离散傅里叶逆变换(IDFT)为
∑-=--===101,...,1,0,)(1)]([)(N n kn N N N n W
k x N k X IDFT n x
四、DFT 算法举例
1、用DFT(FFT)对时域离散信号进行频谱分析
给定参考信号如下：
)()(41n R n x =
??
???≤≤-≤≤+=其它0748301)(2n n n n n x
??
???≤≤≤≤=其它－－0743304)(3n n n n n x
n n x 4
c o s )(4π
= :)(5n x 用)()(41n R n x =以8为周期进行周期性延托形成的周期序列
（1） 分别以变换区间N=8,16,32 对)()(41n R n x =进行DFT(FFT),画出相应的
幅频特性曲线
（2） 分别以变换区间N=8,16 对)( ),(32n x n x 分别进行DFT(FFT),画出相应的
幅频特性曲线
（3） 分别以变换区间N=4,8,16对)(4n x 分别进行DFT(FFT),画出相应的幅频
特性曲线
（4） 对)(5n x 进行频谱分析, 请自己选择变换区间,要求画出幅频特性曲线
2、MATLAB 函数简介
MATLAB 是一门计算机编程语言，取名来源于Matrix Laboratory ，本意是专门以矩阵的方式来处理计算机数据，它把数值计算和可视化环境集成到一起，非常直观，而且提供了大量的函数，使其越来越受到人们的喜爱，工具箱越来越多，应用范围也越来越广泛。本题要用到一维快速傅里叶变换函数fft 、取模（实数取绝对值）函数abs 和求相位函角函数angle 、绘图函数plot 和stem 。这些函数都属于MATLAB 基本函数
● fft 和ifft ：一维快速傅里叶变换和一维快速傅里叶逆变换函数。调用各式如下：
Xk=fft(xn , N) 采用FFT 算法计算时域序列向量xn 的N 点DFT 。缺省N 时fft 函数自动按x 的长度计算x 的DFT ，返回xn 的N 点DFT 向量Xk 。当N 为2的整数次幂时，fft 按基2FFT 算法计算，否则用混合基算法。
ifft 的调用格式与fft 相同。
● abs ：求绝对值（复数求摸）。
y=abs(x) 计算实数x 的绝对值。当x 为复数时得到x 的摸（幅度值）。当x 为向量时，计算其每个元素的摸。
● angle ：求相角。
ph=angle(x) 计算复向量x的每个元素的相角（rad），返回相位向量ph。Ph 值介于–π和+π之间。
下面的简单程序就可以实现计算矩形序列x1(n)的32点FFT,并画出幅频特性和相频特性曲线。
%ex1.m:几个函数调用举例
x1n=[1 1 1 1 1 1 1 1];
x1k=fft(x1n,32); %计算32点fft
x1m=abs(x1k); %计算32点fft的模
ph1=angle(x1k); %计算32点fft的相位
k=0:31; %以下为绘图部分
subplot(2,1,1);stem(k,x1m,'.');grid on
xlabel('k');ylabel('幅度')
subplot(2,1,2);stem(k,ph1,'.');grid on
xlabel('k');ylabel('相位')
运行结果如图所示。
矩形序列的32点DFT
五、实验总结
快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法。它是数字信号处理领域中的一项重大突破。它考虑了计算机和数字硬件实现的约束条件，研究了有利于机器操作的运算结构，使DFT的计算时间缩短了1-2个数量级有效地减少了计算所需的存储容量。我们只有熟练DFT的理论算法才能更好的运用MATLAB来计算。
[参考文献]
[1] 刘智敏. 误差与数据处理[M].北京：原子能出版社，1981.
[2] Hanse man D,Littefield B,李人厚.张平安等校译.精通MATLAB5综合辅导与指
南[M].西安：交通大学出版社，2001.
[3] 高西全.数字信号处理[M]西安电子科技大学出版社，2000
蚁群算法简述及实现 1 蚁群算法的原理分析 蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而发展起来的一种基于群体的模拟进化算法,属于随机搜索算法,所以它更恰当的名字应该叫“人工蚁群算法”,我们一般简称为蚁群算法。M.Dorigo等人充分的利用了蚁群搜索食物的过程与著名的TSP问题的相似性,通过人工模拟蚁群搜索食物的行为来求解TSP问题。 蚂蚁这种社会性动物,虽然个体行为及其简单,但是由这些简单个体所组成的群体却表现出及其复杂的行为特征。这是因为蚂蚁在寻找食物时,能在其经过的路径上释放一种叫做信息素的物质,使得一定范围内的其他蚂蚁能够感觉到这种物质,且倾向于朝着该物质强度高的方向移动。蚁群的集体行为表现为一种正反馈现象,蚁群这种选择路径的行为过程称之为自催化行为。由于其原理是一种正反馈机制,因此也可以把蚁群的行为理解成所谓的增强型学习系统(Reinforcement Learning System)。 引用M.Dorigo所举的例子来说明蚁群发现最短路径的原理和机制,见图1所示。假设D 和H之间、B和H之间以及B和D之间(通过C)的距离为1,C位于D和B的中央(见图1(a))。现在我们考虑在等间隔等离散世界时间点(t=0,1,2……)的蚁群系统情况。假设每单位时间有30只蚂蚁从A到B,另三十只蚂蚁从E到D,其行走速度都为1(一个单位时间所走距离为1),在行走时,一只蚂蚁可在时刻t留下浓度为1的信息素。为简单起见,设信息素在时间区间(t+1，t+2)的中点(t+1.5)时刻瞬时完全挥发。在t=0时刻无任何信息素,但分别有30只蚂蚁在B、30只蚂蚁在D等待出发。它们选择走哪一条路径是完全随机的,因此在两个节点上蚁群可各自一分为二,走两个方向。但在t=1时刻,从A到B的30只蚂蚁在通向H的路径上(见图1(b))发现一条浓度为15的信息素,这是由15只从B走向H的先行蚂蚁留下来的;而在通向C的路径上它们可以发现一条浓度为30的信息素路径,这是由15只走向BC的路径的蚂蚁所留下的气息与15只从D经C到达B留下的气息之和(图1(c))。这时,选择路径的概率就有了偏差,向C走的蚂蚁数将是向H走的蚂蚁数的2倍。对于从E到D来的蚂蚁也是如此。 （a）（b）（c） 图1 蚁群路径搜索实例 这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。 这样,我们就可以理解蚁群算法的基本思想:如果在给定点,一只蚂蚁要在不同的路径中选择,那么,那些被先行蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就更大,较多的信息素意味着较短的路径,也就意味着较好的问题回答。
班级：学号：姓名 实验二FFT算法的MATLAB实现 （一）实验目的： （1）掌握用matlab进行FFT在数字信号处理中的高效率应用。 （2）学习用FFT对连续信号和时域离散信号进行谱分析。 （二）实验内容及运行结果： 题1：若x(n)=cos(nπ/6)是一个N=12的有限序列，利用MATLAB计算它的DFT 并进行IDFT变换同时将原图与IDFT变换后的图形进行对比。当求解IFFT变换中，采样点数少于12时，会产生什么问题。 程序代码： N=12; n=0:11; Xn=cos(n*pi/6); k=0:11; nk=n'*k; WN=exp(-j*2*pi/N) WNnk=WN.^nk XK=Xn*WNnk; figure(1) stem(Xn) figure(2) stem(abs(XK)) 运行结果：
IFFT变换中，当采样点数少于12时图像如下图显示：
分析：由图像可以看出，当采样点数小于12时，x(n)的频谱不变，周期为6，而XK 的频谱图发生改变。 题2：对以下序列进行谱分析 132()()103()8470x n R n n n x n n n =+≤≤?? =-≤≤??? 其他n 选择FFT 的变换区间N 为8和16点两种情况进行频谱分析，分别打印其幅频特 性曲线并进行对比、分析和讨论。 ㈠ 程序代码： x=ones(1,3);nx=0:2; x1k8=fft(x,8); F=(0:length(x1k8)-1)'*2/length(x1k8); %进行对应的频率转换 stem(f,abs(x1k8));%8点FFT title('8点FFTx_1(n)'); xlabel('w/pi'); ylabel('幅度'); N=8时：
按时间抽取的基2FFT 算法分析及MATLAB 实现 一、DIT-FFT 算法的基本原理 基2FFT 算法的基本思想是把原始的N 点序列依次分解成一系列短序列，充分利用旋转因子的周期性和对称性，分别求出这些短序列对应的DFT ，再进行适当的组合，得到原N 点序列的DFT ，最终达到减少运算次数，提高运算速度的目的。 按时间抽取的基2FFT 算法，先是将N 点输入序列x(n)在时域按奇偶次序分解成2个N/2点序列x1(n)和x2(n)，再分别进行DFT 运算，求出与之对应的X1(k)和X2(k)，然后利用图1所示的运算流程进行蝶形运算，得到原N 点序列的DFT 。只要N 是2的整数次幂，这种分解就可一直进行下去，直到其DFT 就是本身的1点时域序列。 图1 DIT-FFT 蝶形运算流图 二、DIT-FFT 算法的运算规律及编程思想 1.原位计算 [ 对N=M 2点的FFT 共进行M 级运算，每级由N/2个蝶形运算组成。在同一级中，每个蝶的输入数据只对本蝶有用，且输出节点与输入节点在同一水平线上，这就意味着每算完一个蝶后，所得数据可立即存入原输入数据所占用的数组元素(存储单元)，经过M 级运算后，原来存放输入序列数据的N 个存储单元中可依次存放X(k)的N 个值，这种原位(址)计算的方法可节省大量内存。 2.旋转因子的变化规律 N 点DIT ―FFT 运算流图中，每个蝶形都要乘以旋转因子p W N ，p 称为旋转因子的指数。例如N ＝8 ＝3 2 时各级的旋转因子： 第一级：L=1， 有1个旋转因子：p W N =J /4W N =J 2L W J=0
第二级：L=2，有2个旋转因子：p W N =J /2W N =J 2L W J=0,1 第三级：L=3，有4个旋转因子：p W N =J W N =J 2L W J=0,1,2,3 对于N ＝M 2的一般情况，第L 级共有1-L 2个不同的旋转因子： p W N =J 2L W J=0,1,2,… ,1-L 2 －1 L 2=M 2×M -L 2= N ·M -L 2 故： 按照上面两式可以确定第L 级运算的旋转因子 \ 3、同一级中，同一旋转因子对应蝶形数目 第L 级FFT 运算中，同一旋转因子用在L -M 2 个蝶形中； 4、同一级中，蝶形运算使用相同旋转因子之间相隔的“距离” 第L 级中，蝶距：D=L 2； 5、同一蝶形运算两输入数据的距离 在输入倒序，输出原序的FFT 变换中，第L 级的每一个蝶形的2个输入数据相距：B=1 -L 2。 6、码位颠倒 输入序列x(n)经过M 级时域奇、偶抽选后，输出序列X(k)的顺序和输入序列的顺序关系为倒位关系。 '
1 引言 CCS(Code Composer Studio)是TI公司的DSP集成开发环境。它提供了环境配置、源文件编辑、程序调试、跟踪和分析等工具,帮助用户在一个软件环境下完成编辑、编译链接、调试和数据分析等工作。与TI提供的早期软件开发工具相比,利用CCS能够加快软件开发进程,提高工作效率。CCS一般工作在两种模式下:软件仿真器和与硬件开发板相结合的在线编程。前者可以脱离DSP芯片,在PC机上模拟DSP指令集与工作机制,主要用于前期算法实现和调试。后者实时运行在DSP芯片上,可以在线编制和调试应用程序。 2 C语言和汇编语言的混合编程 TMS320 C5000系列的软件设计通常有三种方法: (1) 用C语言开发; (2) 用汇编语言开发; (3) C和汇编的混合开发。 其中用C语言开发具有兼容性和可移植的优点,有利于缩短开发周期和减少开发难度,但是在运算量较大的情况下,C代码的效率还是无法和手工编写的汇编代码的效率相比,比如FFT运算,用汇编语言开发的效率高,程序执行速度快,而且可以合理利用芯片的硬件资源,但是开发难度较大,开发周期长,而且可读性和可移植性差。C和汇编的混合编程则可以充分利用前两者的优点,以达到最佳利用DSP资源的目的。但是,采用C和汇编语言混合编程必须遵循相关函数调用规则和寄存器调用规则,否则会给程序的开发带来意想不到的问题。 2.1 C语言和汇编语言混合编程的四种方法 (1) 独立编写汇编程序和C程序,分开编译或汇编成各自的目标代码模块,再用链接器将二者链接起来。这种方法比较灵活,但是设计者必须自己维护各汇编模块的入口和出口代码,自己计算传递的参数在堆栈中的偏移量,工作量较大,但是能做到对程序的绝对控制。 (2) 在C程序中使用汇编程序中定义的变量和常数。 (3) 在C程序中内嵌汇编语句。这种方法可以实现C语言无法实现的一些硬件控制功能,如修改中断控制寄存器。 (4) 将C语言编译生成相应的汇编代码,手工修改和优化C编译器生成的汇编代码。采用这种方法可以控制C编译器,从而产生具有交叉列表的汇编程序,而设计者可以对其中的汇编语句进行修改,然后对汇编程序进行编译,产生目标文件。
蚁群算法浅析 摘要：介绍了什么是蚁群算法，蚁群算法的种类，对四种不同的蚁群算法进行了分析对比。详细阐述了蚁群算法的基本原理，将其应用于旅行商问题，有效地解决了问题。通过对旅行商问题C++模拟仿真程序的详细分析，更加深刻地理解与掌握了蚁群算法。 关键词：蚁群算法；旅行商问题；信息素；轮盘选择 一、引言 蚁群算法（Ant Colony Optimization, ACO），是一种用来在图中寻找优化路径的算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。 蚁群算法成功解决了旅行商问题（Traveling Salesman Problem, TSP）：一个商人要到若干城市推销物品，从一个城市出发要到达其他各城市一次而且最多一次最后又回到第一个城市。寻找一条最短路径，使他从起点的城市到达所有城市一遍，最后回到起点的总路程最短。若把每个城市看成是图上的节点，那么旅行商问题就是在N个节点的完全图上寻找一条花费最少的回路。 最基本的蚁群算法见第二节。目前典型的蚁群算法有随机蚁群算法、排序蚁群算法和最大最小蚁群算法，其中后两种蚁群算法是对前一种的优化。本文将终点介绍随机蚁群算法。 二、基本蚁群算法 （一）算法思想 各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就找到了。 蚁群算法的基本思想如下图表示：
快速傅立叶变换（FFT）的C++实现收藏 标准的离散傅立叶DFT 变换形式如： y k=Σj=0n-1a jωn-kj = A (ωn-k). （ωn k为复数1 的第k 个n 次方根，且定义多项式A (x)=Σj=0n-1a j x j） 而离散傅立叶逆变换IDFT (Inverse DFT)形式如：a j=(Σk=0n-1y kωn kj)/n . yk=Σj=0n-1 ajωn-kj = A (ωn-k). （ωnk 为复数1 的第k 个n 次方根，且定义多项式 A (x) = Σj=0n-1 ajxj ） 而离散傅立叶逆变换IDFT (Inverse DFT)形式如：aj=(Σk=0n-1 ykωnkj)/n . 以下不同颜色内容为引用并加以修正： 快速傅立叶变换（Fast Fourier Transform，FFT）是离散傅立叶变换（Discrete Fourier transform，DFT）的快速算法，它是根据离散傅立叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅立叶变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。 设Xn 为N 项的复数序列，由DFT 变换，任一Xi 的计算都需要N 次复数乘法和N -1 次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N 项复数序列的Xi ，即N 点DFT 变换大约就需要N2 次运算。当N =1024 点甚至更多的时候，需要N2 = 1048576 次运算，在FFT 中，利用ωn 的周期性和对称性，把一个N 项序列（设N 为偶数），分为两个N / 2 项的子序列，每个N / 2点DFT 变换需要(N / 2)2 次运算，再用N 次运算把两个N / 2点的DFT 变换组合成一个N 点的DFT 变换。这样变换以后，总的运算次数就变成N + 2 * (N / 2)2 = N + N2 / 2。继续上面的例子，N =1024 时，总的运算次数就变成了525312 次，节省了大约50% 的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT 运算单元，那么N 点的DFT 变换就只需要N * log2N 次的运算，N = 1024 点时，运算量仅有10240 次，是先前的直接算法的1% ，点数越多，运算量的节约就越大，这就是FFT 的优越性。 FFT 的实现可以自顶而下，采用递归，但是对于硬件实现成本高，对于软件实现都不够高效，改用迭代较好，自底而上地解决问题。感觉和归并排序的迭代版很类似，不过先要采用“位反转置换”的方法把Xi 放到合适的位置，设i 和j 互为s = log2N 位二进制的回文数，假设s = 3, i = (110)2 = 6, j = (011)2 = 3, 如果i ≠j , 那么Xi 和Xj 应该互换位置。（关于这个回文数的生成，是很有趣而且是很基本的操作，想当初偶初学C++ 的时候就有这样的习题。）当“位反转置换”完成后，先将每一个Xi 看作是独立的多项式，然后两个两个地将它们合并成一个多项式（每个多项式有2 项），合并实际上是“蝶形运算”（Butterfly Operation, 参考《算法导论》吧^_^），继续合并（第二次的每个多项式有4 项），直到只剩
A1=str2double(get(handles.edit8,'String')); A2=str2double(get(handles.edit9,'String')); F1=str2double(get(handles.edit10,'String')); F2=str2double(get(handles.edit11,'String')); Fs=str2double(get(handles.edit12,'String')); N=str2double(get(handles.edit13,'String')); t=[0:1/Fs:(N-1)/Fs]; x=A1*sin(2*pi*F1*t)+A2*sin(2*pi*F2*t); %信号x的离散值 axes(handles.axes1) %在axes1中作原始信号图 plot(x); grid on m=nextpow2(x);N=2^m; % 求x的长度对应的2的最低幂次m if length(x) 蚁群算法的改进与应用 摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。 关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法; 1 前言 蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特征，解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人于 1991 年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者们称为信息素。这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。在蚂蚁寻觅食物的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选择最短路径。该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。 尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。虽然 ACO 的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。 由于依靠经验来选择蚁群参数存在复杂性和随机性,因此本文最后讨论如何利用遗传算法选取蚁群算法的参数。遗传算法得到的蚁群参数减少了人工选参的不确定性以及盲目性。 2 基本蚁群算法 2.1 蚁群算法基本原理 根据仿生学家的研究结果表明,单只蚂蚁不能找到从巢穴到食物源的最短路 径,而大量蚂蚁之间通过相互适应与协作组成的群体则可以,蚂蚁是没有视觉的,但是是通过蚂蚁在它经过的路径上留下一种彼此可以识别的物质,叫信息素,来相互传递信息,达到协作的。蚂蚁在搜索食物源的过程中,在所经过的路径上留下信息素,同时又可以感知并根据信息素的浓度来选择下一条路径,一条路径上的浓度越浓,蚂蚁选择该条路径的概率越大,并留下信息素使这条路径上的浓度加强,这样会有更多的蚂蚁选择次路径。相反,信息素浓度少的路 实验2 FFT 算法实现 2.1 实验目的 1、 加深对快速傅里叶变换的理解。 2、 掌握FFT 算法及其程序的编写。 3、 掌握算法性能评测的方法。 2.2 实验原理 一个连续信号)(t x a 的频谱可以用它的傅立叶变换表示为 dt e t x j X t j a a Ω-+∞ ∞-?= Ω)()( （2-1） 如果对该信号进行理想采样，可以得到采样序列 )()(nT x n x a = （2-2） 同样可以对该序列进行z 变换，其中T 为采样周期 ∑+∞∞--=n z n x z X )()( （2-3） 当ωj e z =的时候，我们就得到了序列的傅立叶变换 ∑+∞∞-=n j j e n x e X ωω)()( （2-4） 其中ω称为数字频率，它和模拟域频率的关系为 s f T /Ω=Ω=ω （2-5） 式中的s f 是采样频率。上式说明数字频率是模拟频率对采样率s f 的归一化。同模拟域的情况相似，数字频率代表了序列值变化的速率，而序列的傅立叶变换称为序列的频谱。序列的傅立叶变换和对应的采样信号频谱具有下式的对应关系。 ∑+∞∞--=)2(1)(T m j X T e X a j πωω （2-6） 即序列的频谱是采样信号频谱的周期延拓。从式（2-6）可以看出，只要分析采样序列的频谱，就可以得到相应的连续信号的频谱。注意：这里的信号必须是带限信号，采样也必须满 足Nyquist 定理。 在各种信号序列中，有限长序列在数字信号处理中占有很重要的地位。无限长的序列也往往可以用有限长序列来逼近。对于有限长的序列我们可以使用离散傅立叶变换（DFT ），这一变换可以很好地反应序列的频域特性，并且容易利用快速算法在计算机上实现当序列的长度是N 时，我们定义离散傅立叶变换为： ∑-===10)()]([)(N n kn N W n x n x DFT k X （2-7） 其中N j N e W π 2-=，它的反变换定义为： ∑-=-==10)(1)]([)(N k kn N W k X N k X IDFT n x （2-8） 根据式（2-3）和（2-7）令k N W z -=，则有 ∑-====-10)]([)(|)(N n nk N W z n x DFT W n x z X k N （2-9） 可以得到k N j k N e W z z X k X π2|)()(===-,k N W -是z 平面单位圆上幅角为k N πω2=的点，就是将单位圆进行N 等分以后第k 个点。所以，X(k)是z 变换在单位圆上的等距采样，或者说是序列傅立叶变换的等距采样。时域采样在满足Nyquist 定理时，就不会发生频谱混淆；同样地，在频率域进行采样的时候，只要采样间隔足够小，也不会发生时域序列的混淆。 DFT 是对序列傅立叶变换的等距采样，因此可以用于序列的频谱分析。在运用DFT 进行频谱分析的时候可能有三种误差，分析如下： （1）混淆现象 从式（2-6）中可以看出，序列的频谱是采样信号频谱的周期延拓，周期是2π/T ，因此当采样速率不满足Nyquist 定理，即采样频率T f s /1=小于两倍的信号（这里指的是实信号）频率时，经过采样就会发生频谱混淆。这导致采样后的信号序列频谱不能真实地反映原信号的频谱。所以，在利用DFT 分析连续信号频谱的时候，必须注意这一问题。避免混淆现象的唯一方法是保证采样的速率足够高，使频谱交叠的现象不出现。这就告诉我们，在确定信号的采样频率之前，需要对频谱的性质有所了解。在一般的情况下，为了保证高于折叠频率的分量不会出现，在采样之前，先用低通模拟滤波器对信号进行滤波。 （2）泄漏现象 实际中的信号序列往往很长，甚至是无限长序列。为了方便，我们往往用截短的序列来近似它们。这样可以使用较短的DFT 来对信号进行频谱分析。这种截短等价于给原信号序列乘以一个矩形窗函数。而矩形窗函数的频谱不是有限带宽的，从而它和原信号的频谱进行卷积以后会扩展原信号的频谱。值得一提的是，泄漏是不能和混淆完全分离开的，因为泄露导致频谱的扩展，从而造成混淆。为了减小泄漏的影响，可以选择适当的窗函数使频谱的扩散减到最小。 （3）栅栏效应 因为DFT 是对单位圆上z 变换的均匀采样，所以它不可能将频谱视为一个连续函数。 STM32F103 12-15元左右 本文将以一个实例来介绍如何使用STM32提供的DSP库函数进行FFT。 1.FFT运算效率 使用STM32官方提供的DSP库进行FFT，虽然在使用上有些不灵活（因为它是基4的FFT，所以FFT的点数必须是4^n），但其执行效率确实非常高效，看图1所示的FFT运算效率测试数据便可见一斑。该数据来自STM32 DSP库使用文档。 图1 FFT运算效率测试数据 由图1可见，在STM32F10x系列处理器上，如果使用72M的系统主频，进行64点的FFT运算，仅仅需要0.078ms而已。如果是进行1024点的FFT运算，也才需要2.138ms。 2.如何使用STM32提供的DSP库函数 2.1下载STM32的DSP库 大家可以从网上搜索下载得到STM32的DSP库，这里提供一个下载的地址：https://https://www.doczj.com/doc/da2878852.html,/public/STe2ecommunities/mcu/Lists/cortex_ mx_stm32/DispForm.aspx?ID=30831&RootFolder=%2fpublic%2fST e2ecommunities%2fmcu%2fLists%2fcortex%5fmx%5fstm32%2fST M32F10x%20DSP%20library%2c%20where%20is%20it 2.2添加DSP库到自己的工程项目中 下载得到STM32的DSP库之后，就可以将其添加到自己的工程项目中了。 其中，inc文件夹下的stm32_dsp.h和table_fft.h两个文件是必须添加的。stm32_dsp.h是STM32的DSP库的头文件。 src文件夹下的文件可以有选择的添加（用到那个添加那个即可）。因为我只用到了256点的FFT，所以这里我只添加了cr4_fft_256_stm32.s文件。添加完成后的项目框架如图2所示。 图2 项目框架 2.3模拟采样数据 根据采样定理，采样频率必须是被采样信号最高频率的2倍。这里，我要采集的是音频信号，音频信号的频率范围是20Hz到20KHz，所以我使用的采用频率是44800Hz。那么在进行256点FFT时，将得到44800Hz / 256 = 175Hz的频率分辨率。 为了验证FFT运算结果的正确性，这里我模拟了一组采样数据，并将该采样数据存放到了long类型的lBufInArray数组中，且该数组中每个元素的高16 位存储采样数据的实部，低16位存储采样数据的虚部(总是为0)。 为什么要这样做呢？是因为后面要调用STM32的DSP库函数，需要传入的参数规定了必须是这样的数据格式。 下面是具体的实现代码： 1 /****************************************************************** 2函数名称:InitBufInArray() 3函数功能:模拟采样数据，采样数据中包含3种频率正弦波(350Hz，8400Hz，18725Hz) 4参数说明: 5备注:在lBufInArray数组中，每个数据的高16位存储采样数据的实部， 6低16位存储采样数据的虚部(总是为0) 7作者:博客园依旧淡然（https://www.doczj.com/doc/da2878852.html,/menlsh/） 8 *******************************************************************/ 128点FFT 算法设计方法 X(k)=127 n 0x n =∑（）w nk 128, X （k ）=63n 0x n =∑（2）w 1282nk +63n 0x n =∑（2+1） w 128(2n+1)k =63n 0x n =∑（2）w 64nk +(63n 0x n =∑（2+1） w 64nk )w 1281k =H(k)+G(k) w 1281k , H(k)= 63 n 0h n =∑（）w 64nk ,h(n)=x(2n) G(k)= 63 n 0g n =∑（） w 64nk ,g(n)=x(2n+1) H(k) = 63n 0h n =∑（） w 64nk =7a 0=∑(7b 0h a b =∑（+8）)w 64(a+8b)k H(k)=H(k 0+8k 1)= 7a 0=∑(7b 0 h a b =∑（+8）)w 64(a+8b)(k0+8k1) =7a 0=∑(7b 0 h a b =∑（+8）w 648bk0)w 64a(k0+8k1)w 6464bk1 =7a 0 =∑(7b 0h a b =∑（+8）w 648bk0)w 64a(k0+8k1) =7a 0 =∑(7b 0h a b =∑（+8）w 8bk0)w 64a(k0+8k1), [w 6464bk1=1] =7a 0 =∑(7b 0f b =∑（）w 8bk0)w 64a(k0+8k1) =7a 0=∑(7b 0 f b =∑（）w 8bk0w 64ak0 )w 648ak1) =7a 0=∑(7 b 0f b =∑（）w 8bk0w 64ak0 )w 8ak1) w 8bk0旋转因子是1、-1、 等，可以用加减等运算实现，只有w 64ak0要乘旋转因子。 7b 0f b =∑（） w 8bk0用一个蝶8运算。 F(k0)= 7 b 0f b =∑（）w 8bk0,f(b)=h(a+2b), 红色旋转因子还未找到处理方法，使第二级也变为pe8运算 18W =134689222222 ------＝＋＋＋＋＋ 汇编下的FFT算法实现 ;----------------------------------------------------------- ; 快速付里叶变换子程序 ; ; 入口 : 一维四字节浮点数数组的首地址 ; ; ; 以 2 为基β的值,信号抽样的点数 = 2^β; ; ; 出口 : 在原数组的位置保存结果的值; ; ; 补充说明 : ; ; 1. 该子程序所需 RAM 的容量为 2^β*12 字节,另外需要 ; ; 少量的堆栈作为临时变量的存储空间; ; ; 2. 所需 RAM 空间以输入的首地址为基址,向增加的方向 ; ; 扩展; ; ; 应用举例 : ; ; PUSH #0A000H ; 数组首地址压栈 ; PUSH #6 ; β值压栈 ; CALL FFT ; ;----------------------------------------------------------- PROC FFT FFT: LD FFT_CX,2[SP] LD FFT_AX,#0001H ; SHL FFT_AX,FFT_CL ; 计算采样点数 PUSH FFT_AX ; 将采样点数压栈 SHL FFT_AX,#1 ; LD FFT_BX,6[SP] ; 根据采样点数, ADD FFT_BX,FFT_AX ; 计算出其余 PUSH FFT_BX ; 三个被占用 ADD FFT_BX,FFT_AX ; 空间的首地址; PUSH FFT_BX ; 并依次将首地址 SHL FFT_AX,#1 ; ADD FFT_BX,FFT_AX ; 压栈; PUSH FFT_BX ; LD FFT_CX,6[SP] LD FFT_FX,#2 LOOP1: CLR FFT_AX SUB FFT_EX,FFT_CX,#1 LD FFT_BX,FFT_EX LD FFT_DX,10[SP] LOOP2: FFT算法实现实验报告 辛旸 PB10210006 实验目的 1、加深对快速傅里叶变换的理解。 2、掌握FFT 算法及其程序的编写。 3、掌握算法性能评测的方法。 实验内容 1.编写自己的FFT算法： 代码如下： function [ X ] = Sampling( x,N ) %myFFT实现FFT时域取样算法 % 输出：生成FFT序列X(k),输入：欲变换序列x（n），FFT变换长度N（可缺省）（1） if ~exist('N','var'); %检查是否有变换长度N输入 （2） N=length(x); %若无，则令N等于序列长度 （3） end （4） if N （18） w=zeros(1,N); （19） for m=0:1:N-1; %确定反序序列k1和正序序列k的关系 （20） k=m; （21） for n=i-1:-1:0; %从高位开始依次将各位移至反序位 （22） k1(m+1)=k1(m+1)+fix(k/(2^n))*(2^(i-1-n)); （23） k=rem(k,2^n); （24） end; （25） end （26） for l=1:1:N; （27）X(k1(l)+1)=x(l); %生成反序序列 （28） w(l)=exp(-1i*2*pi/N*(l-1)); %生成旋转因子 （29） end （30） for l=0:1:i-1; %控制FFT运算级数 （31） for m=1:1:N; %每一级中有N/2个蝶形运算 （32） if rem((m-1),2^(l+1))<2^l; %找到蝶形运算的上半部分（33） b=X(m)+X(m+2^l)*w(2^(i-1-l)*rem((m-1),2^l)+1); %将结果暂存至b （34）X(m+2^l)=a(m)-X(m+2^l)*w(2^(i-1-l)*rem((m-1),2^l)+1); （35）X(m)=b; %实现原位运算 （36） end （37） end （38） end 2.选择实验1中的典型信号序列验证算法的有效性： 为方便比较两个算法，编写了myCompare函数计算两种算法的运行时间，并绘制频谱曲线 代码如下： function [ t1,t2,e ] = myCompare( x,N ) %myCompare函数：比较自己编写的算法与系统自带算法的差异 % 输入：与变换信号序列x（n）和欲变换长度N % 输出：自己编写的函数的执行时间t1，系统自带函数的执行时间t2，两者计算序列的差异平方和e tic; X1=myFFT(x,N); t1=toc; tic; X2=fft(x,N); 蚁群算法原理及在TSP 中的应用 1 蚁群算法（ACA ）原理 1.1 基本蚁群算法的数学模型 以求解平面上一个n 阶旅行商问题(Traveling Salesman Problem ，TSP)为例来说明蚁群算法ACA （Ant Colony Algorithm ）的基本原理。对于其他问题，可以对此模型稍作修改便可应用。TSP 问题就是给定一组城市，求一条遍历所有城市的最短回路问题。 设()i b t 表示t 时刻位于元素i 的蚂蚁数目，()ij t τ为t 时刻路径(,)i j 上的信息量，n 表示TSP 规模，m 为蚁群的总数目，则1()n i i m b t ==∑；{(),}ij i i t c c C τΓ=?是t 时刻集合C 中元素(城市)两两连接ij t 上残留信息量的集合。在初始时刻各条路径上信息量相等，并设 (0)ij const τ=，基本蚁群算法的寻优是通过有向图 (,,)g C L =Γ实现的。 蚂蚁(1,2,...,)k k m =在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表(1,2,...,)k tabu k m =来记录蚂蚁k 当前所走过的城市，集合随着 k tabu 进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路 径的启发信息来计算状态转移概率。()k ij p t 表示在t 时刻蚂蚁k 由元素(城市)i 转移 到元素(城市)j 的状态转移概率。 ()*()()*()()0k ij ij k k ij ij ij s allowed t t j allowed t t p t αβ αβτητη??????????? ∈?????=????? ??? ∑若否则 (1) 式中，{}k k allowed C tabuk =-表示蚂蚁k 下一步允许选择的城市；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强；β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的重视程度，其值越大，则该状态转移概率越接近于贪心规则；()ij t η为启发函数，其表达式如下： 1 ()ij ij t d η= (2) 基2的DIT蝶形算法源代码及注释如下： /************FFT***********/ //整个程序输入和输出利用同一个空间x[N]，节约空间 #include DSP课程设计报告 设计题目：256点FFT 院系：计算机科学学院 专业：自动化 年级：2008级 姓名： 学号： 指导教师： 页脚内容0 2011年11 月28日 256点FFT的实现 一、设计目的 1、加深对DFT算法原理和基本性质的理解； 2、熟悉FFT的算法原理和FFT子程序的算法流程和应用； 3、学习用FFT对连续信号和时域信号进行频谱分析的方法； 4、学习DSP中FFT的设计和编程思想； 5、学习使用CCS的波形观察器观察波形和频谱情况； 二、设计内容 给定256 采样点,求频谱,统计运行时间并在PC 上显示。 三、设计原理 快速傅里叶变换（FFT）是一种高效实现离散傅里叶变换（DFT）的快速算法，是数字信号处理中最为重要的工具之一，它在声学，语音，电信和信号处理等领域有着广泛的应用。 页脚内容1 快速傅里叶变换FFT 旋转因子WN 有如下的特性。 对称性：WNk+N/2=-WNk 周期性：WNn(N-k)=WNk(N-n)=WN-nk 利用这些特性，既可以使DFT中有些项合并，减少了乘法积项，又可以将长序列的DFT分解成几个短序列的DFT。FFT就是利用了旋转因子的对称性和周期性来减少运算量的。 FFT的算法是将长序列的DFT分解成短序列的DFT。例如：N为偶数时，先将N点的DFT分解为两个N/2点的DFT，使复数乘法减少一半：再将每个N/2点的DFT分解成N/4点的DFT，使复数乘又减少一半，继续进行分解可以大大减少计算量。最小变换的点数称为基数，对于基数为2的FFT算法，它的最小变换是2点DFT。 一般而言，FFT算法分为按时间抽取的FFT（DITＦＦＴ）和按频率抽取的ＦＦＴ（DIF FFT）两大类。ＤIF FFT算法是在时域内将每一级输入序列依次按奇／偶分成２个短序列进行计算。而DIF FFT算法是在频域内将每一级输入序列依次奇／偶分成２个短序列进行计算。两者的区别是旋转因子出现的位置不同，得算法是一样的。在DIF FFT算法中，旋转因子出现在输入端，而在DIF FFT算法中它出现在输入端。假定序列x(n)的点数N是2的幂，按照DIF FFT算法可将其分为偶序列和奇序列。 偶序列：x(2r)=x1(r) 奇序列：x(2r+1)=x2(r) 其中：r=0,1,2,…,N/2-1 则x(n)的DFT表示为 页脚内容2蚁群算法
实验2FFT算法实现
(完整word版)stm32F103进行FFT算法教程
128点FFT算法设计方法
汇编语言实现的FFT算法
FFT算法实现实验报告
蚁群算法原理及在TSP中的应用(附程序)
fft算法代码注释及流程框图
DSP课程设计报告(256点FFT的实现)
相关主题
文本预览