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