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