《MATLAB在通信网中的应用.ppt》由会员分享，可在线阅读，更多相关《MATLAB在通信网中的应用.ppt（51页珍藏版）》请在三一办公上搜索。
1、第八讲Matlab在通信网中的应用,信号的时域分析,单边衰减指数信号t=0:0.01:10;A=1;A=-0.4;ft=A*exp(a*t);plot(t,ft)xlabel(t)ylabel(f(t),正弦信号t=0:0.001:8;A=1;w0=2*pi;phi=pi/6;ft=A*sin(w0*t+phi);plot(t,ft)xlabel(t)ylabel(f(t),信号的时域分析,抽样函数信号t=-3*pi:pi/100:3*pi;ft=sinc(t/pi);plot(t,ft)xlabel(t)ylabel(Sa(t),信号的时域分析,矩形脉冲信号t=0:0.001:4T=1;ft
2、=rectpuls(t-2*T,T);plot(t,ft);axis(0,4,-0.5,1.5)xlabel(t)ylabel(rectpuls(t),信号的时域分析,产生单位脉冲序列ks=-4;ke=4;n=2;k=ks:ke;x=(k-n)=0;stem(k,x);xlabel(k);,信号的时域分析,正弦序列k=0:39;fk=sin(pi/6*k);stem(k,fk)xlabel(k)ylabel(sinusoidal signal),信号的时域分析,系统的时域分析,连续时间系统的冲激响应ts=0;te=5;dt=0.01;sys=tf(10,1 2 100);t=ts:dt:te;
3、y=impulse(sys,t);plot(t,y);xlabel(Time(sec)ylabel(h(t),离散系统的单位脉冲响应k=0:10;a=1 3 2;b=1;h=impz(b,a,k);subplot(2,1,1)stem(k,h)title(approximation of h(k);hk=-(-1).k+2*(-2).k;subplot(2,1,2)stem(k,hk)title(h(k)in theory);,系统的时域分析,信号的频域分析,求周期序列的DFSN32；M=4;%定义周期方波序列的参数f=ones(1,M+1)zeros(1,N-2*M-1)ones(1,M);
4、%产生序列Ffft(f);%计算DFS系数m=0:N-1;subplot(2,1,1);stem(m,real(F);title(real of Fm);xlabel(m);subplot(2,1,2);stem(m,imag(F);title(imaginary of Fm);xlabel(m);,连续周期信号的傅立叶级数的计算N=8;%计算n=-N到1的傅立叶系数n1=-N:-1;c1=-4*j*sin(n1*pi/2)/pi2./n1.2;%计算n=0时的傅立叶系数c0=0;%计算n=1到N的傅立叶系数n2=1:N;c2=-4*j*sin(n2*pi/2)/pi2./n2.2;cn=c1
5、 c0 c2;n=-N:N;subplot(2,1,1);stem(n,abs(cn);ylabel(Amplitude of Cn);subplot(2,1,2);stem(n,angle(cn);ylabel(Phase of Cn);xlabel(omega/omega0);,信号的频域分析,系统的频域分析,输入为余弦的连续系统响应RC=0.04;t=linspace(-2,2,1024);w1=5;w2=100;H1=j*w1/(j*w1+1/RC);H2=j*w2/(j*w2+1/RC);f=cos(5*t);y=abs(H1)*cos(w1*t+angle(H1)+abs(H2)*
6、cos(w2*t+angle(H2);subplot(2,1,1);plot(t,f);ylabel(f(t);xlabel(t(sec)subplot(2,1,2);ylabel(y(t);xlabel(t(sec);,产生调制信号（PM）Fm=10;Fc=100;Fs=1000;N=1000;k=0:N-1;t=k/Fs;x=sin(2.0*pi*Fm*t);Xf=abs(fft(x,N);y2=modulate(x,Fc,Fs,pm);subplot(2,1,1);plot(t(1:200),y2(1:200);xlabel(Time(s);axis(0,0.2,-1,1);title(
7、Modulated Signal(PM);Yf2=abs(fft(y2,N);subplot(2,1,2);stem(Yf2(1:200);xlabel(Frequency(Hz);title(Modulated Signal(PM),系统的频域分析,主 页,上一页,下一页,树直观形象的表示工具,类似于自然界中的树,形象地表示家族,主 页,上一页,下一页,连通图：其中任意两点之间都有路径。圈：当一条路径的起点和终点是同一顶点时，称这条路径为环。,提示,一个连通图,树直观形象的表示工具,主 页,上一页,下一页,树：没有环的连通图 树中任意两点间有唯一路径。树的边数恰好为顶点数减1。在树中任意去掉
8、一条边，将会不连通。树中任意两个不相邻顶点间添一边后，就恰好含一个环。,树图直观形象的表示工具,主 页,上一页,下一页,形象地表示家族；表示行政组织机构；用树图来列举排列；用树来分析游戏中的策略；计算机用树来描述运算顺序；用树来组织其拥有的资源以便于查找；在编译程序中，用树来表示源程序语法结构；在数据库系统中，可用树来组织信息。,树直观形象的表示工具,返 回,主 页,上一页,下一页,城市电信局有许多业务如收费，营业，112，114等，希望在全市范围实现计算机联网服务，共享各种资源。一个主要关心的问题是：用数据通讯线把一组站点联结起来，而不允许通讯线在非站点处相交，如何连接可使通讯线的花费最小？
9、,引例：计算机网络的线路设计,主 页,上一页,下一页,假设各站点间可以铺设通讯线路进行连接的情况如图所示，顶点为站点，边为连接两站点之间的通讯线，边的权为其费用。,引例：计算机网络的线路设计,主 页,上一页,下一页,1)左图中哪些边是多余的？2)最经济的网络应具备什么特性？3)如何求出最经济的连接线路图？,引例：计算机网络的线路设计,想,主 页,上一页,下一页,引例：计算机网络的线路设计,最经济的网络不应该有任何封闭的回路。,橡筋圈上剪一刀后，仍然是一个整段。,联想,主 页,上一页,下一页,引例：计算机网络的线路设计,生成树或支撑树(spanning tree)：G的是树的子图，其顶点集等于G
10、的顶点集；,如何简便地得到左图的生成树？它应有几条边？,主 页,上一页,下一页,确定应在哪些站点之间铺设通讯线路，是否可看作是在相应的加权图中构造最小费用的生成树的问题？生成树的权：其上所有边权之和。,引例：计算机网络的线路设计,主 页,上一页,下一页,最小生成树 最大生成树,引例：计算机网络的线路设计,1)一个完全图Kn有多少不同的生成树？2)如何求其最小生成树?,主 页,上一页,下一页,10个顶点的完全图，其不同的生成树就有一亿棵。一般地，n个顶点的完全图，其不同的生成树个数为nn-2。30个顶点的完全图就有3028个生成树，求最小生成树时用穷举法是无效的。,引例：计算机网络的线路设计,返
11、 回,主 页,上一页,下一页,背景聚焦,Prim算法,Kruskal算法,生成树算法及其MATLAB程序实现,返 回,算法的MATLAB程序实现,主 页,上一页,下一页,1,3,2,将所有顶点涂成红色；在黄色边中，挑选一条权最小的边，使其与红色边不形成圈，将该黄色边涂红；重复直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。,Kruskal算法,4,5,8,6,9,1,5,7,10,3,主 页,上一页,下一页,Kruskal算法,计算机如何实现上述非数值计算算法？计算机如何判断一些边是否形成圈?,主 页,上一页,下一页,Kruskal算法,1,2,3,4,5,8,3,9,1,5
12、,7,10,6,红色边和顶点构成三棵子树,一条边与红色边形成圈当且仅当这条边的两个端点属于同一个子树,猜想,主 页,上一页,下一页,Kruskal算法,给每个子树一个不同的编号,返 回,主 页,上一页,下一页,Kruskal算法,例:用Kruskal算法求引例中的加权图的最小生成树。,b=1 1 1 2 2 3 3 4;2 4 5 3 5 4 5 5;8 1 5 6 7 9 10 3;,边权矩阵：,b=1 1 1 2 2 3 3 4;2 4 5 3 5 4 5 5;8 1 5 6 7 9 10 3;B,i=sortrows(b,3);B=B;m=size(b,2);n=5;t=1:n;k=0;
13、T=;c=0;for i=1:m if t(B(1,i)=t(B(2,i)k=k+1;T(k,1:2)=B(1:2,i),c=c+B(3,i)tmin=min(t(B(1,i),t(B(2,i);tmax=max(t(B(1,i),t(B(2,i);for j=1:n if t(j)=tmax t(j)=tmin;end end end,if k=n-1 break;end end T,c,主 页,上一页,下一页,程序运行结果：T=1 4 4 5 2 3 2 5 c=17,Kruskal算法,返 回,主 页,上一页,下一页,最小生成树算法的背景聚焦,1956年，美国AT&T利用最小生成树来计算
14、出对几家商业客户的索价。一张大比例的美国地图铺在地板上，寻找联结所有站点的总长度最小的网络。用手工（并且跪着）操作的方式完成的问题很有限。,历史,手工操作,主 页,上一页,下一页,最小生成树算法的背景聚焦,Kruskal算法刚发表，它的第一步是整理所有站点对间的距离表 500个站点的边数：500*499/2=124750，计算机不具有处理这样大规模数据集的能力 需要另一种算法,大规模问题犯难,主 页,上一页,下一页,最小生成树算法的背景聚焦,1957年，领导贝尔实验室数学研究室的Prim，得到了他的算法。Prim 算法优于Kruskal算法之处是Prim算法一次处理的数据不超过n，Prim算法
15、所需的存储器比Kruskal算法小。,历史,柳暗花明,返 回,主 页,上一页,下一页,Prim算法,任选一个顶点v1，将其涂红；在一个端点为红色，另一个端点为黄色的边中，找一条权最小的边涂红，把该边的白端点也涂成红色；重复2)直到所有顶点都成红色为止。最终的红色边和顶点便是最小生成树.,算法的手工操作,主 页,上一页,下一页,Prim算法,算法的手工操作,1,2,3,4,5,8,6,9,1,5,7,10,3,主 页,上一页,下一页,Kruskal算法和Prim算法都蕴涵了贪婪法的思想；贪婪法的基本思想：把解看成是由若干个部件构成，每一步求出解的一个部件（不是从整体或长远的角度考虑，只是局部或当
16、前的最好选择）。求出的一个个部件组合而作为最终的解。,主 页,上一页,下一页,贪婪法可被用于各种各样问题的处理。贪婪法只是一种试探法，计算上简便，有效，可提供正确解的一个近似。但一般情况下，不能保证输出的解是正确的。其正确性需要证明，这往往比较困难。,返 回,主 页,上一页,下一页,分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽量少，最理想的情况是使每个零件的加工，都在组内完成。假设有13种零件，需在9台机器上加工。在各台机器上加工的零件号在下表中给出。,范例：制造系统的分组技术,主 页,上一页,下一页,范例：制造系统的分组技术,主
17、页,上一页,下一页,设用Mi表示需由机器i加工的零件集，对任意两台机器i,j,定义相异度：,范例：制造系统的分组技术,建模,“”：对称差，分子：在机器i但不在机器j上加工，或在机 器j但不在机器i上加工的零件数。分母：或在机器i，或在机器j上加工的零件数。显然 01,建模,1)(i,j)=0和(i,j)=1分别表示什么？2)表达了什么？,上一页,下一页,主 页,主 页,上一页,下一页,构造加权图 以机器为顶点，作一个完全图，每条边(i,j)被赋予权(i,j)。原问题的转化 加权图的最小生成树是由那些相异度最小的边构成的连通图，如果希望把机器分成k个组，就继续删去最小生成树上权最大的k-1条边。
18、于是得到k个分离的子树，每棵树的顶点集就构成各机器组。,建模,对表1给出的数据，加权图的边权矩阵如下：1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8;2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 4 5 6 7 8 9 5 6 7 8 9 6 7 8 9 7 8 9 8 9 9;0.5 1 0.89 0.14 1 1 1 1 1 1 0.62 1 1 1 1 1 1 1 1 1 0.5 0.87 0.67 0.75 0.75 1 1 1 1 1 1 1 1 0 1 1 用Kruskal
19、算法可求出最小生成树，在前面给出的Kruskal算法的MATLAB程序中，边权矩阵b的值改为此处的边权矩阵，顶点数n改为9即可。,模型求解,上一页,下一页,主 页,T=7 8 1 5 1 2 3 9 4 6 4 7 4 5 1 3 c=4.4300,机器的分组：3，9，1，2，5，4，6，7，8。,上一页,下一页,主 页,主 页,上一页,下一页,你能给出对应于该机器分组的零件分类吗？,机器的分组：3，9，1，2，5，4，6，7，8。,模型结果,返 回,主 页,上一页,下一页,实验内容,2.在一个计算机通讯网络中，某一计算机欲呼叫另一台计算机并进行数据传输，若传输数据量很大，又要求了传输速度，则通常需要沿容量最大的路径进行数据传输。求两台给定计算机之间容量最大的路径。,最大容量路径,主 页,上一页,下一页,假设上图为该通讯网络对应的无向图G,其上每条边的权代表容量（带宽），即通过该边的最大流量。,最大容量路径,
