网络通信与OSI_3b

计算机网络与通信主讲：蔡伟鸿汕头大学工学院计算机系第三章、数据通信概论差错控制编码数据通信基础传输控制电路时钟同步技术第六节差错控制编码纠错编码的基本原理常用的简单编码线性码循环码原理数据通信系统模型1、纠错编码的基本原理例子：“晴”，“雨”的编码分组码:由信息码分组,附加若干监督码组成|k个信息||r个监督|汉明距离:两个码组对应位上数字不同的位娄称码距.码重:每个码中的1个数.(,,,...,)aaaaannn12310(,,...,,,...,)aaaaaannrr12110最小码距的与检错和纠错能力的关系为检测E个错码,要求最小码距:ed≥e+1最小码距的与检错和纠错能力的关系为纠正t个错码,要求最小码距d≥2t+1t最小码距的与检错和纠错能力的关系为纠正t个错码,同时检测e个错误,要求条件：t≤ed≥t+e+11et⒈2、常用的简单编码——奇偶监督码在偶数监督码中,无论信息位有多少,监督位只一位,它使码组中“1”的数目为偶数,即要求偶校验2mod1niiC奇校验2mod11niiC常用的简单编码——二维奇偶监督码奇数个错误数字可检测可能检测偶数个错误不能检测的情况有构成矩形的四个错码常用的简单编码——恒比码在恒比码中,每个码组含有相同数目的1(和0)).检测时,只计算接收码组中1的数目是否对电传机传输汉字钟与口取了的恒比码数字码保护码国际码数字码保护码国际码10101111101610101101012110011100171110011100310110100008011100110041101001010910011000115001110000100110101101常用的简单编码——恒比码检错能力:可检所有奇数个码元的错误及部分偶数个码元的错误,但不能检测同时1变0和0变1的偶个码元的错误.例子常用的简单编码——正反码编码:正反码的监督位数目和信息位数目相同,监督码元信息码元相同或相反,则由信息码中1的个数而定.设码长N=10,R=5,K=511001----1100111001(奇数1)10001----1000101110(偶数1)常用的简单编码——正反码解码:信息位和监督位按位模2相加,得一合成的码组,若信息位有奇个1,为检验码组,若信息位有偶个,则取反码为校验码组,校验规则如下:1.全为0,元错码2.有4个1,1个0信息码中有一位错码,与0位置3.有4个0,1个14.其它错码多于1个常用的简单编码——交织码在原有检错能力条件下,解决连续错误3、线性码1.各种编码依据的原理不同2.奇偶监督码的编码原理利用了代数关系式代数码:建立在代数学基础上的编码,其中有线性码,线性码中信息位和监督位是由一些线性代数方程构成的.汉明码偶数监督码的构成.S=S只有两种情况0--无错1---有错若把监督位设为两位,有四种情况:00---无错,01,10,11表示1位错码的3种不同位置,同理R位监督可指示一位错位的(22-1)个不同位置.niCi汉明码—构造一种能纠正一位错码的编码设码长为n，信息位数为k，则监督位数r＝n－k，要r位监督位数能指示一位错码的几种可能位置，则要求：2r－１＞＝n或2r＞＝k＋r＋１举例：k＝４──＞r≥３即n＝７（７，４）码汉明码—构造一种能纠正一位错码的编码用a6a5a4a3a2a1a0表示这７个码元，用Ｓ１，Ｓ２，Ｓ３表示三个监督关系式的校正子。Ｓ１Ｓ２Ｓ３错码位置Ｓ１Ｓ２Ｓ３错码位置００１a0１０１a4０１０a1１１０a5１００a2１１１a6０１１a3０００无错汉明码—构造一种能纠正一位错码的编码Ｓ１＝a２＋a４＋a５＋a６Ｓ２＝a１＋a３＋a５＋a６Ｓ３＝a０＋a3＋a４＋a６当无错时，Ｓ１＝Ｓ２=Ｓ３=０a２＋a４＋a５＋a６＝０a１＋a３＋a５＋a６＝０a０＋a3＋a４＋a６＝０汉明码—构造一种能纠正一位错码的编码a0=a3＋a4＋a６a1=a3＋a5＋a６监督位的生成式a2=a4＋a5＋a６信息码（１０１０）可得码（１０１００１０）a3１０１１０１０错位──线性码1.A6+1.A5+1.A4+0.A3+1.A2+0.A1+0.A0=01.A6+1.A5+0.A4+1.A3+0.A2+1.A1+0.A0=01.A6+0.A5+1.A4+1.A3+0.A2+0.A1+1.A0=0HAT0┌┐┌┐│A6│┌┐│1110100││A5││0││1101010││A4│=│0││1011001││A3││0│└┘│A2│└┘│A1││A0│└┘线性码记为H.AT=0T或A.HT=0其中H称为监督矩阵,A为一码组.┌┐┌┐│1110100││1110100│H=│1101010│=│1101010│=[PIr]│1011001││1011001│└┘└┘H矩阵的各行是线性无关,即秩为R.线性码由生成式可得:┌┐┌┐┌┐│A2││1110││A6││A1│=│1101││A5││A0││1011││A4│└┘└┘└A3┘┌┐[A2A1A0]=[A6A5A4A3]│111│=[A6A5A4A3].Q│110││101││011│└┘Q=PT线性码┌┐│1000111│令G=[IQ]=│0100110││0010101││0001011│└┘称G为生成矩阵[]=[].G或A=[].GG的各行是线性关系的,由G可构成个码组.推广到一般,N元码组.A=[]aaaaaaa6543210,,,.,,,aaaa6543,,,.aaaa6543,,,.aaaaannn12310,,,...,线性码设B为接收码组.B-A=E为错码行矩阵E[B-A]H=BH-AH=BH=EH=S若B=A,则[B-A]H=0若BA,则S=BHSiEiS1…SnE1..EnSijS为校正子,利用它来指示错码位置.线性码的封闭性:线性码中的任意两个码字之和仍为这种码中的一个码字.（证明）4、循环码原理循环码的性质及特点1、循环码除线性码的一般性质外,还具有循环性2、循环码的编码和解码设备不太复杂,且检(纠)错的能力较强.若xn-1+xn-2+…+x2+x+1是一个循环码字,则xn-2+xn-3+…+x+1+xn-1xn-3+xn-4+…+1+xn-1+xn-2也是在该编码中的码字循环码原理例--(7,3)循环码11001011001011001011101011101011100011100111100100000000用一多项式来表示(xn-1+xn-2+…+x2+x+1)(为体现循环性及数学表达式)T(x)=xn-1+xn-2+…+x2+x+1第1码组可表示为T1(x)=x6+x5+x2+1循环码原理在整数运算中:M/N=Q+P/NPN则按模N运算下,有M=Q*N+PP(模N)类似,对任一多项式F(x)被一N次多项式N(x)除,得到商式Q(x)和一个次数小于N的余式R(x),即F(X)=N(X).Q(X)+R(X)则有F(X)ΞR(X)(模N(X))循环码原理如x3被(x3+1)除,有x3=x3+1+1=1(模x3+1)同理x4+x2+1=x2+x+1(模x3+1)练习：x5+x3+x性质:在循环码中,若xiT(X)是一个长为N的许用码字,则T(X)在按模xn+1运算下,亦是一个许用码字,即若xiT(X)=T’(X)(模+1)则T’(X)也是一个许用码字(证明)循环码原理11001011001011001011101011101011100011100111100100000000例T1(x)=x6+x5+x2+1左循环移位3次T‘(x)=x3（x6+x5+x2+1）=x5+x3+x2+x1(模xn+1)n=7──(0101110)练习：T2(x)=x4+x2+x+1循环码原理构成生成矩阵GG为K行N列,G中每一行都为一码组,且线性无关,则若能找到K个已知码组,就能构成矩阵后,用g(X)(R次方,生成多项式)表示(N,K)码中前(K-1)位皆为“0”的码组,(即若有第一位信息位为“1”),则g(X),xg(X),......Xk-1g(x)都是码组,且这K个码组是线性关系的,可构成G.g(X)的唯一性及存在性,(讨论)循环码原理[a6,a5,a4,a3,a2,a1,a0]=[a6,a5,a4,a3,]G或A=[a6,a5,a4,a3,]G┌┐│g(x)││xg(X)│G(x)=│.....││Xk-2g(x)││Xk-1g(x)│└┘T(X)=H(x)g(x)(结论)循环码原理---编,解码方法设(N,K)码,生成多项式为G(X),M(X)为信息码多项式,次数小于K,则T(X)=Xn-km(x)+r(x)(勘误)r(x)为Xn-km(x)/g(x)的余式(证明)举例:g(x)=x4+x2+x+1m(x)=x2+1举例：110011发送数据比特序列CRC校验码比特序列1001带CRC校验码的发送数据比特序列1100111001110011100111001110010100001110011000011001G(x)1100110000110011001R(x)100001Q(x)f(x).xk练习：（7，4）例子（10，6）例子标准CRC生成多项式G（x）CRC-12G（x）=x12+x11+x3+x2+x+1CRC-16G（x）=x16+x15+x2+1CRC-CCITTG（x）=x16+x12+x5+1CRC-32G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1第七节、数据通信基础一、二进制串行传输在设备体内,一般采用并行传输在设备间,一般采用串行传输二、通信的模式演讲、讲话──单向传输信息对话──双向传输信息1单工数据只在一个方向上传输的模式2半双工两台设备能交替交换数据的模式3全双工两台设备能同时交换数据的模式第七节、通信基础三、传输模式传输中为正确确认每一个比特数据必须知道(1)比特速率(2)每一元素的启始(3)每一元素的末端时钟同步字符同步帧同步通信可分为异步传输同步传输三、传输模式1异步传输当被传输数据的时间间隔是随机时,通常采用异步传输每一符号的起始比特(1──0)每一符号的终止比特1为了可靠接收,时钟必须高于传输BIT率的N倍.每一传输单元包含10个比特1个起始+8个字符+1个结束波特率(BAND)的定义:每秒种传输信号的数量,当传输二进制信号时,1BPS=1BAND当传输多进制信号时,1BPS1BAND三、传输模式1异步传输当被传输数据的时间间隔是随机时,通常采用异步传输每一符号的起始比特(1──0)每一符号的终止比特1为了可靠接收,时钟必须高于传输BIT率的N倍.每一传输单元包含10个比特1个起始+8个字符+1个结束波特率(BAND)的定义:每秒种传输信号的数量,当传输二进制信号时,1BPS=1BAND当传输多进制信号时,1BPS1BAND三、传输模式2、同步传输使用异步传输的缺点:(1)每一个符号必须包含一些多余控制信息(2)可靠传输的最高速率为19200BPS使用同步传输的条件(1)传输比特流需经适当的编码,使接收端保持比特同步.(2)所有帧必须有一个(或多个)字节(或字符)作为帧的同步信号,以使接收端确定每一数据帧的间隔.(3)每帧的内容由一对字符组装.分析同步与异步传输的不同点