《计算机通信网 》第3章 数据链路层Part1

1、第第3章章 数据链路层数据链路层3.1 数据链路层概述数据链路层概述3.2 成帧与帧定界成帧与帧定界3.3 差错检测与校正方法差错检测与校正方法3.4 差错与流量控制协议差错与流量控制协议3.5 协议描述与验证协议描述与验证3.6 数据链路层协议案例数据链路层协议案例3.1 数据链路层概述数据链路层概述n链路层模型链路层模型传输系统传输系统G.703G.703传输系统提供透明的传输系统提供透明的bit 传输传输3.1 数据链路层概述数据链路层概述nDL面临的环境面临的环境网络层网络层数据链路层数据链路层物理层物理层SAPSAPSAPSAP网络层网络层数据链路层数据链路层物理层物理层分组分组帧帧

2、装入装入分组分组取出取出1010110110101101帧帧发送方发送方接收方接收方信道有噪声，信道有噪声，bits可能出错可能出错可能装入太快可能装入太快取出跟不上取出跟不上3.1 数据链路层概述数据链路层概述n链路层模型链路层模型链路层链路层网络层网络层物理层物理层010101比特传输比特传输传输信号传输信号Packet物理层物理层实现了把实现了把比特传输比特传输转换成转换成信号信号传输传输、进入信道。、进入信道。网络层网络层需要把一个个分组送到对方网需要把一个个分组送到对方网络层络层链路层链路层组织一个个分组，用比特传输组织一个个分组，用比特传输实现逐个分组的传输和接收实现逐个分组的传输

3、和接收3.1 数据链路层概述数据链路层概述n链路层的基本任务链路层的基本任务物理层物理层DUFraming(帧同步帧同步)发送：转换成特定的发送：转换成特定的bit传输形式，将传输形式，将Frame送出送出接收：界定每个接收：界定每个frame的位置，取出的位置，取出frameDUError Control(差错控制差错控制)发送：组织发送：组织DU (frame)，方便对方检查错误，方便对方检查错误接收：检测接收：检测DU是否出错，是否出错，DU出错的处理出错的处理Link Control(链路控制链路控制)双方通过配合，实现：双方通过配合，实现： 链路的使用规则，流量控制、汇聚分发等链路的

4、使用规则，流量控制、汇聚分发等DUService(服务服务)为上面的实体提供分组传输服务为上面的实体提供分组传输服务3.1 数据链路层概述数据链路层概述n链路层任务模型链路层任务模型DUDU约定成帧方式约定成帧方式约定出错处理手段约定出错处理手段约定控制方法约定控制方法可用的通信功能可用的通信功能DU3.1 数据链路层概述数据链路层概述n链路层效率定义链路层效率定义n链路层链路层n有效数据率有效数据率 r = ni/T （ni：第：第i帧帧bit数，数，T：测量：测量总时间）总时间）n物理层物理层n信道的速率信道的速率 R b/sn链路层效率：链路层效率： = r/R = r/R （ 1）Li

5、nk Layer Servicesn三种服务的示意图三种服务的示意图有确认面向连接有确认面向连接无确认无连接无确认无连接Frameack有确认无连接有确认无连接Frameack连接确认连接确认连接请求连接请求FrameFrameack拆除确认拆除确认拆除请求拆除请求B方方A方方Link Layer Servicesn三种可能的服务三种可能的服务n无确认的无连接服务无确认的无连接服务n无需对方许可，直接向对方发送无需对方许可，直接向对方发送Frame，对方不需要反馈确认信息，对方不需要反馈确认信息n优点：不受等待确认的拖累；缺点：优点：不受等待确认的拖累；缺点：frame传输可靠性不高传输可靠性

6、不高n信道效率：不等待确认，可提高信道效率，但传输出错降低信道效率信道效率：不等待确认，可提高信道效率，但传输出错降低信道效率n协议考虑：协议考虑：PDU中含源中含源/目的地址目的地址n有确认的无连接服务有确认的无连接服务n无需对方许可，直接向对方发送无需对方许可，直接向对方发送Frame，需要对方反馈确认信息，需要对方反馈确认信息n优点：通过重传增加了可靠性；缺点：受等待应答的拖累优点：通过重传增加了可靠性；缺点：受等待应答的拖累n保持发送和确认间的正确对应关系所采取的措施会大大降低信道使用效率保持发送和确认间的正确对应关系所采取的措施会大大降低信道使用效率n协议考虑：协议考虑：PDU编号，

7、编号，PDU中含源中含源/目的地址、单帧确认，差错检目的地址、单帧确认，差错检测与重传测与重传n有确认的面向连接服务有确认的面向连接服务n需事先与对方沟通，双方建立起一套复杂的发送、确认机制来实现恢复差需事先与对方沟通，双方建立起一套复杂的发送、确认机制来实现恢复差错、排除重复、维持顺序的可靠通信错、排除重复、维持顺序的可靠通信n适合于有大量适合于有大量Frame传输的场合传输的场合n协议考虑：协议考虑：PDU编号、确认、差错控制（丢弃错帧和重复帧，请求编号、确认、差错控制（丢弃错帧和重复帧，请求重发错帧）重发错帧）3.2 成帧成帧Framingn成帧成帧(或帧同步或帧同步)：就是确定帧的界限

8、（起与止）：就是确定帧的界限（起与止）n通俗理解：通俗理解：n发送方：在帧的前后各加入事先商定好的标记发送方：在帧的前后各加入事先商定好的标记n接收方：在接收方：在bits中寻找标记来识别帧的起与止中寻找标记来识别帧的起与止n需要特别考虑：需要特别考虑：n若数据与帧的起止标记相同时，发送方必须采取措施若数据与帧的起止标记相同时，发送方必须采取措施n否则可能会引起接收方的误断否则可能会引起接收方的误断n成帧方法：成帧方法：n字符计数法字符计数法n字符填充首尾界定法字符填充首尾界定法n位填充首尾界定法位填充首尾界定法n物理层编码违例法物理层编码违例法110101101001011011001111

9、011110010101011100010101001011010101011011010100100100.如何分离出一个如何分离出一个一个的帧一个的帧？成帧成帧n不同传输方式下的帧同步不同传输方式下的帧同步n同步传输方式同步传输方式(Sync,连续连续bit流流)n连续的连续的bit流传递离散的流传递离散的Framen每个每个Frame都成为连续都成为连续bit流中的一段，接收方识别并取流中的一段，接收方识别并取出出Framen异步传输方式异步传输方式(Async,异步字节序列异步字节序列)n每个每个Frame转换为异步字节序列传送，接收方收集字节转换为异步字节序列传送，接收方收集字节序列

10、，还原序列，还原Framen数据块传输方式数据块传输方式(Block)n每个每个Frame形成一个数据块传送。形成一个数据块传送。Sync信道的帧同步技术信道的帧同步技术n连续的连续的bit流由若干流由若干Frame和它们间的空闲和它们间的空闲bit组成组成n注意：注意：frame中或空闲的中或空闲的bit都只有两种取值：都只有两种取值：0或或1n关键问题：如何正确识别和提取关键问题：如何正确识别和提取bit流中的流中的Frame部分？部分？n思路：假设空闲思路：假设空闲bit用某种特殊的用某种特殊的bit模式模式(pattern)构成，而构成，而Frame中不会出现该中不会出现该patter

11、n，则接收方就能够正确设别和提，则接收方就能够正确设别和提取取Framen但但: 应该允许应该允许Frame包含任意数据，就肯定包含了这种包含任意数据，就肯定包含了这种Pattern。n若能对若能对Frame中出现的中出现的Pattern用某种变换方式消除，接收方提用某种变换方式消除，接收方提取出取出Frame后，再通过反变换，恢复原来的后，再通过反变换，恢复原来的Frame，该假设成，该假设成立立FrameFrameFrameFrame反变换反变换变换变换Frame连续连续bit流流空闲空闲空闲空闲空闲空闲特殊特殊patternSync信道的帧同步技术信道的帧同步技术n发送发送开始开始扫描扫

12、描Frame发现发现PatternPattern变换变换扫描结束扫描结束发送发送Frame否否是是结束结束否否是是n接收接收开始开始否否检测检测pattern发现发现存储数据存储数据否否检测检测pattern发现发现复原复原Frame是是继续继续是是结束结束是是Frame开始开始Frame结束结束否否Pattern选择选择-易于变换易于变换-易于检测易于检测-易于反变换易于反变换Sync信道的帧同步技术信道的帧同步技术n位填充首尾定界法位填充首尾定界法 （0比特插入比特插入/删除技术删除技术)nPattern=01111110称为定界标志称为定界标志F (Flag)nFrame内内F的变换和反

13、变换的变换和反变换(利用利用F中连续中连续6个个1的性的性质质)n变换：变换：nFrame中如果出现连续中如果出现连续5个个1时，插入一个时，插入一个0n提取提取n从第一次出现非从第一次出现非F开始，到重新出现开始，到重新出现F时的所有时的所有bitn反变换反变换nFrame中出现连续中出现连续5个个1时，删除后面的时，删除后面的1个个0n采用采用01111110的特点：的特点：n变换与发送合一：发送连续变换与发送合一：发送连续5个个1，加发一个，加发一个0n接收与复原合一：连续接收接收与复原合一：连续接收5个个1，下一，下一bit若是若是0则则直接去掉，否则，应该出现的就是直接去掉，否则，应

14、该出现的就是01111110结束该结束该帧帧位填充首尾定界法位填充首尾定界法发送：在帧体部分出现连续发送：在帧体部分出现连续5个个1，无条件地插入一个，无条件地插入一个0 接收：在帧体中扫描连续接收：在帧体中扫描连续5个个1，无条件去掉后面的，无条件去掉后面的001111110 001010111101111101111110101011111 1111001000成帧成帧0010101111011111101011111 1111001000位填充首尾定界法位填充首尾定界法n位填充位填充 (实现示意图实现示意图)0 1 1 1 1 1 1 0位填充首尾定界法位填充首尾定界法n软件模拟软件模拟

15、nint Send(char *pF, int Len) n int i,j,c,msk, sn;n sn = 0;n for(i=0;iLen;i+) / 循环帧的字节长度n msk = 1;n for(j=0;j8;j+) / 8bitn c = pFi & msk ? 1:0; 测试第j bitn msk =1; 准备测试下一 bitn Xmitb(c);sn+;n if (c) cnt+; else cnt = 0; / 计算连续1的个数n if (cnt = 5) Xmitb(0); cnt = 0;sn+; n n n return sn; / 回送发送总bit数n 假定函

16、数假定函数Xmitb(c)：向信道发送：向信道发送c (1bit)Async信道的帧同步技术信道的帧同步技术n描述描述n以字节以字节(8bit)为单位的传输方式为单位的传输方式n逐字节传输实现逐字节传输实现Frame传输传输n帧同步讨论帧同步讨论nFrame间留有足够的时间间隔，以区分各个间留有足够的时间间隔，以区分各个Framen对对Frame传输能力有较大的影响传输能力有较大的影响nFrame间的时间间隔不够大，帧与帧区分易出错间的时间间隔不够大，帧与帧区分易出错n两种典型帧同步技术两种典型帧同步技术n字节计数法字节计数法n字符填充首尾定界法字符填充首尾定界法PSTN成帧成帧字符计数法字符

17、计数法n也可称为也可称为字节计数法字节计数法n假设一个字符由假设一个字符由8位二进制数表示位二进制数表示n基本思想基本思想n在帧头的第在帧头的第1个字节指明帧内的字节数个字节指明帧内的字节数n问题问题n字节计数值可能在传输中出错（被篡改）字节计数值可能在传输中出错（被篡改）n简单、不可靠简单、不可靠 11101010 00101110 01010101 010111010 10101011发送发送DATA11101010 00101110 01010101 010111010 10101011错错00000010接收接收 11101010 00101110 01010101 010111010

18、 10101011000001100000001100000110字符填充首尾定界法字符填充首尾定界法n思想思想n与同步方式的位填充类似，不同的是以与同步方式的位填充类似，不同的是以字节为单位为单位n方法：方法：“定界字符定界字符”n在帧体的前后都用某个特定的字节加以在帧体的前后都用某个特定的字节加以“定界定界”n帧体中也可能出现该定界字符，通过变换消除帧体中也可能出现该定界字符，通过变换消除n接收时提取接收时提取Frame后，通过反变换复原后，通过反变换复原n局限性：数据的长度总是以字符或其倍数为单位局限性：数据的长度总是以字符或其倍数为单位n定界字符定界字符: F(Flag) = 0111

19、1110F 1 4 7 6 8 x 3 1 4 5 2 F 6 8 4 3 1 4 F6 8 4 3 1 41 4 7 6 8 F 3 1 4 5 2字符填充首尾定界法字符填充首尾定界法n将将F变换为某个其它字节变换为某个其它字节(x)存在问题：存在问题：n帧体中其它字节也可能出现帧体中其它字节也可能出现x，反变换，反变换xF时就出错时就出错nFrame体中定界字符的变换方法体中定界字符的变换方法n一字节到两字节的变换一字节到两字节的变换,变换后帧体中不出现变换后帧体中不出现Fn帧体中的帧体中的F和和x都需要变换：都需要变换：Fxy; xxzny和和z是另外选取的两个字符，对是另外选取的两个字

20、符，对y、z不再需要变换不再需要变换n分析分析n若帧体中出现若帧体中出现xyn变换：变换：xy(xz)y ；反变换：；反变换：xzyxy,正确复原正确复原n可以验证：对帧体中出现可以验证：对帧体中出现F,x,y,z的任意顺序的组合，只的任意顺序的组合，只对其中的所有对其中的所有F和和x进行变换，反变换时都能正确复原进行变换，反变换时都能正确复原字符填充首尾定界法字符填充首尾定界法n处理帧体内的特殊字符处理帧体内的特殊字符 (RFC1662，异，异步步PPP)nF=01111110 (7e),定界字符定界字符nx=01111101 (7d),称为转义字符称为转义字符ny=01011110 (5e

21、)nz=01011101 (5d)1 4 7 6 F 4 3x5d5 2F 1 4 7 6 x5e4 3 x5d5d52 F发送发送XmitB(F)B=F？结束结束否否是是B=Framei+XmitB(B)B=x？XmitB(x)XmitB(y)XmitB(x)XmitB(z)否否是是iLen是是XmitB(F)否否XmitB：发送字节：发送字节XrcvB：接收字节：接收字节练习练习n分两组：一组成帧，一组提取帧分两组：一组成帧，一组提取帧n分别用位填充法、计数法、字符填充法进行练习分别用位填充法、计数法、字符填充法进行练习n可自定义若干帧来完成该练习可自定义若干帧来完成该练习n思考思考n字符

22、填充法中，仅用字符填充法中，仅用F和和x是否能够实现，如能实是否能够实现，如能实现，给出实现方法，如不能实现，请说明不能实现，给出实现方法，如不能实现，请说明不能实现的理由现的理由字符填充首尾定界法字符填充首尾定界法教材教材PP.159块传输信道的帧同步技术块传输信道的帧同步技术n当用电缆或无线直接通信当用电缆或无线直接通信(不经过传输系统不经过传输系统)时，最简洁的时，最简洁的通信方式是块传输方式，每个块就是一个通信方式是块传输方式，每个块就是一个Framen块传输方式块传输方式n每个每个Frame都带有前导都带有前导bit序列序列(preamble)和后续和后续bit序列序列(postam

23、ble),以确保以确保Frame的头和尾能正确检测和接收的头和尾能正确检测和接收n因此需要确定：因此需要确定：nPreamble结束和结束和Frame开始的比特位置开始的比特位置nFrame结束和结束和postamble开始的开始的bit位置位置n同步技术同步技术n违例编码法：利用信息违例编码法：利用信息bit的码型特性，用非正常码型来进行界定位置的码型特性，用非正常码型来进行界定位置preamblepostamble块传输信道的帧同步技术块传输信道的帧同步技术n例例1：曼切斯特编码：曼切斯特编码(1b/2b, 10M以太网以太网)nBlock = 010101JKFramebodyKJ010

24、101n例例2：4b/5b编码编码(100M以太网以太网)n4bit数据映射成数据映射成5bit码组码组n000011110, 000101001, , 111111101n空闲空闲11111, 定界符定界符111000, 定界符定界符210001nBlock = 010101定界符定界符1FrameBody定界符定界符2 010101n例例3：8b/10b编码编码(1000M以太网以太网)n8bit数据数据映射成映射成10bit码组码组n从从1024个码组中只需选取个码组中只需选取256个来代表个来代表8bit的各个值的各个值n剩余剩余1024-256个码组可作为控制、定界等多种功能个码组可

25、作为控制、定界等多种功能 0 =1 =违例违例和和J=K=块传输信道的帧同步技术块传输信道的帧同步技术校验和法校验和法n利用利用ATM信元固定、且长度较短信元固定、且长度较短(53字节字节)的的特性特性n信元前信元前4字节是头部，第字节是头部，第5字节是校验和，使用循字节是校验和，使用循环冗余校验环冗余校验n设设40位寄存器，计算校验和位寄存器，计算校验和n正确则可能发现了一个信元正确则可能发现了一个信元n不正确则移一位，再次计算，直到得到一个信元不正确则移一位，再次计算，直到得到一个信元成帧成帧10011010001010111111010001101100011110111003.2 成帧

26、成帧讨论与理解讨论与理解n帧定界正确，请问帧一定无错吗？帧定界正确，请问帧一定无错吗？n一个帧定界出错，请问一个帧定界出错，请问n用字符计数法，后续的帧也不能正确识别吗？为什么？用字符计数法，后续的帧也不能正确识别吗？为什么？n用字符填充法和位填充法，情况又如何？用字符填充法和位填充法，情况又如何？n位填充法比字符填充法有哪些优越性？位填充法比字符填充法有哪些优越性？Framing小结小结n不同的成帧技术以适应信道的不同传输体制不同的成帧技术以适应信道的不同传输体制n需求：需求：n接收方易于提取、出错时对后续帧的提取影响小接收方易于提取、出错时对后续帧的提取影响小n较高的信道利用率、较简单的实

27、现较高的信道利用率、较简单的实现n位填充、字符计数、字符填充、违例编码、校验和位填充、字符计数、字符填充、违例编码、校验和n与其它功能的关系与其它功能的关系n实现的是信道上传输和接收帧的功能，不涉及帧的内容实现的是信道上传输和接收帧的功能，不涉及帧的内容n链路层其它功能直接对帧的处理，不受传输体制影响链路层其它功能直接对帧的处理，不受传输体制影响差错处理、链路功能差错处理、链路功能差错处理、链路功能差错处理、链路功能3.3 差错检测与纠正差错检测与纠正n信道传输过程中信道传输过程中 (误码：误码：10; 01)n随机干扰：随机错随机干扰：随机错 (均匀性均匀性)n突发干扰：突发错突发干扰：突发

28、错 (一定的突发长度一定的突发长度)n出错处理出错处理n检错：验证是否出现了误码检错：验证是否出现了误码n纠错：找到误码的位置，纠正之纠错：找到误码的位置，纠正之3.3 差错检测与纠正差错检测与纠正n如何理解数据传输中的差错？如何理解数据传输中的差错？n一位错就等于全帧错一位错就等于全帧错n关于误码率关于误码率Pb与误帧率与误帧率Pen假设假设n帧长度为帧长度为N比特，误码率为比特，误码率为Pb（设每比特出错独立）（设每比特出错独立）n则则n比特正确率为：比特正确率为：1- PbnN比特正确率为比特正确率为 （1- Pb）Nn帧出错率（误帧率）帧出错率（误帧率） （一帧中至少一位错）为一帧中至

29、少一位错）为 Pe= 1-（1- Pb）N NPb （帧出错的概率与帧成近似成正比）（帧出错的概率与帧成近似成正比）3.3 差错检测与纠正差错检测与纠正n差错控制，意味着：差错控制，意味着：n首先检测出差错首先检测出差错n然后是纠正差错然后是纠正差错n检测差错检测差错n采用冗余编码技术进行差错检验编码采用冗余编码技术进行差错检验编码n纠错码：不仅能检测差错，且能知道错在哪儿纠错码：不仅能检测差错，且能知道错在哪儿n检错码：只能检测差错，但不知错在哪检错码：只能检测差错，但不知错在哪n纠正差错纠正差错n前向纠错前向纠错FEC（Forward Error Correction）n用纠错码，收方检错

30、并自动纠错用纠错码，收方检错并自动纠错 n自动请求重发自动请求重发ARQ （ Automatic Request for Repeat） n用检错码，收方检错通知发方重发恢复差错用检错码，收方检错通知发方重发恢复差错n计算机网络中常采用计算机网络中常采用3.3 差错检测与纠正差错检测与纠正n假设假设n待传数据为待传数据为m位位n为检测差错，所需要的冗余位（校验位）为为检测差错，所需要的冗余位（校验位）为r位位n则则n传输码长度传输码长度n=m+rn通常采用纠错码或检错码，即：通常采用纠错码或检错码，即：n按某种算法计算出校验位按某种算法计算出校验位n然后将然后将m位数据和位数据和r位校验码形成

31、传输码位校验码形成传输码n接收方根据相同的算法重新计算校验位，判断是否出错接收方根据相同的算法重新计算校验位，判断是否出错3.3 差错检测与纠正差错检测与纠正n一种直观简单的纠错方法一种直观简单的纠错方法n每个每个bit重传三次：重传三次：1111; 0000n如果如果3bit中有中有1bit错错, 我们可以纠正过来我们可以纠正过来n101、110、011 111 1n001、010、100 000 0n如果如果3bit中有中有2bit或或3bit全错，则无法纠正了全错，则无法纠正了n101 111 ? 000 ? 无法知道是无法知道是1bit还是还是2bit错错n将每个将每个bit重传重传2

32、n+1次，次，n越大，纠错能力越越大，纠错能力越强强(传输效率越低传输效率越低)n不管不管n如何取，我们仍不知道是否真的纠正了错误，如何取，我们仍不知道是否真的纠正了错误，只能认为增大了纠正错误的概率只能认为增大了纠正错误的概率3.3.1 纠错码纠错码海明码海明码n海明距离海明距离 （Hamming Distance）教材教材P162163n两个等长码对应位不同的个数，称作这两个码的海明距两个等长码对应位不同的个数，称作这两个码的海明距离离n例：例：0001111和和0001100的海明距离为的海明距离为2n某种编码的任意两个有效编码之间的距离称为该编某种编码的任意两个有效编码之间的距离称为该

33、编码的海明距离码的海明距离n结论结论1：检出检出d个错误的检错码，海明距离至少为个错误的检错码，海明距离至少为d1n结论结论2：纠正纠正d个错误的纠错码，海明距离至少为个错误的纠错码，海明距离至少为2d1 海明码是一种能纠正一位错的纠错码海明码是一种能纠正一位错的纠错码3.3.1 纠错码纠错码海明码海明码n假设假设n数据为数据为m位位n则纠正一位错的校验码则纠正一位错的校验码 r 满足满足 m+r+12r （证明：（证明：P163）n例如：例如：m=3m=3，3+r+13+r+12r r=3n则海明码码长则海明码码长= = m+r=6位位n海明码的编码为海明码的编码为r r与与m m的混排方式

34、，规则为：的混排方式，规则为：n检验位检验位r的序号为的序号为2的整次幂的整次幂1，2，4，8，n信息位信息位m的序号为的序号为2的非整次幂，的非整次幂，3，5，6，7.nr1r2m3r4m5m63.3.1 纠错码纠错码海明码海明码n假设数据为假设数据为011，该如何确定海明编码？，该如何确定海明编码？n编码应为：编码应为：r1r2m3r4m5m6n现已知：现已知：m3 m5 m6 = 0 1 1n关键是确定关键是确定r1、r2和和r4nr的计算方法的计算方法n首先找出哪些与首先找出哪些与 r1、r2和和r4相关的数据位相关的数据位n将数据位数拆成将数据位数拆成2的整次幂相加的整次幂相加n如如

35、3=1+2 m3与与r1和和r2相关相关n然后将与某然后将与某r相关的数据位模相关的数据位模2加加(异或），结果为该异或），结果为该r值值n与与r1相关的数据位：相关的数据位：m3、m5 则则r1=0 1=1n与与r2相关的数据位：相关的数据位：m3、m6 则则r2=0 1=1n与与 r4相关的数据位：相关的数据位：m5、m6 则则r4=1 1=0n得出：得出：011的海明编码为的海明编码为1100113.3.1 纠错码纠错码海明码海明码n已知：已知：011的海明编码为的海明编码为110011（ r1r2m3r4m5m6）n假设：编码在传输中出了一位错假设：编码在传输中出了一位错 n 1100

36、11 错成错成 110010 n接收方的纠错规则接收方的纠错规则n首先：对于每个首先：对于每个ri，将，将ri和与之相关的数据位进行依次异或和与之相关的数据位进行依次异或n结果为结果为1，则记录，则记录Ai=i（i为为r的序号）的序号）n结果为结果为0，则记录，则记录Ai=0n然后然后累加累加，计算，计算Ai的值，结果等于几就是该对应位出错的值，结果等于几就是该对应位出错n最后，将出错位取反进行纠错最后，将出错位取反进行纠错n计算过程计算过程nr1 m3 m5=1 0 1=0 则则 A1=0 nr2 m3 m6=1 0 0=1 则则 A2=2 nr4 m5 m6=0 1 0=1 则则 A4=4

37、 n出错位：出错位： Ai=A1+A2+A4=6n纠错：纠错： 110010 110011 （差错位取反）（差错位取反）3.3.2 差错检测差错检测n采用冗余编码技术进行差错检验编码采用冗余编码技术进行差错检验编码n基本思想基本思想n发送方：将待发数据按照某种规则加上一定的冗余位后，发送方：将待发数据按照某种规则加上一定的冗余位后，进行传输，进行传输，n接收方：对收到的数据进行判断，是否符合原规则，若接收方：对收到的数据进行判断，是否符合原规则，若符合则无错，不符合则出错。符合则无错，不符合则出错。C(x) = R(x) 无错无错C (x)R(x) 出错出错3.3.2 差错检测差错检测检错码检

38、错码n奇偶校验码奇偶校验码n循环冗余码循环冗余码CRCn校验和编码校验和编码3.3.2 差错检测差错检测奇偶校验码奇偶校验码n增加冗余位使信息码中的增加冗余位使信息码中的“1”的个数为奇数或偶数的编码的个数为奇数或偶数的编码n奇校验：奇校验：“1”的个数为奇数的个数为奇数n偶校验：偶校验：“1”的个数为偶数的个数为偶数n具体实现：信息位逐位进行模具体实现：信息位逐位进行模2加（异或运算）加（异或运算）na1 a2 a3 a4 a5 n 结果为结果为0，偶校验时，偶校验时 校验位为校验位为0，奇校验时，校验位为，奇校验时，校验位为1n结果为结果为1， 偶校验时偶校验时 校验位为校验位为1，奇校验

39、时，校验位为，奇校验时，校验位为0n例例 信息字段信息字段 奇校验码奇校验码 偶校验码偶校验码 011001 011001 0 011001 1 出错为：出错为： 001001 0 001001 1重新计算校验和：重新计算校验和： 10不同则出错不同则出错纠正突发错纠正突发错n数据组织成矩阵，按行编写奇偶效验码数据组织成矩阵，按行编写奇偶效验码n发送时按列发送发送时按列发送n出现突发错误时，可按行纠正出现突发错误时，可按行纠正3.3.2 差错检测差错检测循环冗余码循环冗余码n循环冗余码（循环冗余码（CRC: Cyclic Redundancy Code）教材教材p165167n对任意对任意m位

40、二进制流，补充位二进制流，补充r个个0n用规定的用规定的r+1位除数进行求位除数进行求余计算，得到余计算，得到r位效验码位效验码n数据与数据与r位效验码组成传输位效验码组成传输码组码组n发送出去发送出去3.3.2 差错检测差错检测循环冗余码循环冗余码nCRC校验校验n对收到的完整的数对收到的完整的数据帧用发送方相同据帧用发送方相同的的r+1位除数进行求位除数进行求余计算余计算n余数为余数为0则无错则无错3.3.2 差错检测差错检测循环冗余码循环冗余码n基于任何一个二进制位串组成的代码，都可以与系基于任何一个二进制位串组成的代码，都可以与系数只为数只为0和和1的多项式建立一一对应的关系。的多项式

41、建立一一对应的关系。n一个一个K位的数据可以看成是从位的数据可以看成是从xK-1x0次系数为次系数为0和和1的多项式的多项式 x4 x3 x2 x1 x0 数据：数据： 1 1 0 1 1多项式多项式 x4 + x3 + x + 13.3.2 差错检测差错检测循环冗余码循环冗余码n1）基本思想：）基本思想：n设：数据设：数据m位，对应多项式位，对应多项式M（x），校验码为），校验码为r位，对应多项式位，对应多项式R(x)n 给定：生成多项式给定：生成多项式G（x），阶数为），阶数为r，r+1位，高位和低位系数为位，高位和低位系数为1n发送方：将发送方：将M（x）通过）通过G（x）计算出带校验和

42、的传输多项式）计算出带校验和的传输多项式T（x）n接收方：将收到的带校验和的多项式接收方：将收到的带校验和的多项式T （x）除以）除以G（x），如有余数，），如有余数，出错，能除尽，无错出错，能除尽，无错n2）校验码与传输多项式的计算）校验码与传输多项式的计算nSTEP 1 在在m位数据之后加上位数据之后加上 r个个0，数据位变成，数据位变成m+r位，对应多项式位，对应多项式x r M（x） nSTEP 2 计算校验码多项式：计算校验码多项式：x r M（x）/ G（x）(对应二进制位串模对应二进制位串模2除除)，余数为校验码，对应多项式为，余数为校验码，对应多项式为R（x）nSTEP 3 计

43、算传输多项式：计算传输多项式：T（x）= x r M（x）+ R（x），对应系数），对应系数位串为传输数据位串为传输数据3.3.2 差错检测差错检测循环冗余码循环冗余码n示例：数据：示例：数据： 110110 nG（x）= x4 + x+ 1 对应位串对应位串 10011 （除数）（除数）n在数据后加在数据后加4个个0 形成形成 1101100000 被除数，被除数， 求余数求余数3.3.2 差错检测差错检测冗余循环码冗余循环码n值得注意：值得注意：n多项式变为码字时，首位对应最高次，中间的多项式变为码字时，首位对应最高次，中间的“0”不能丢不能丢掉掉n在计算中涉及的在计算中涉及的“+”和和“-”均为模均为模2运算（加、减结果一样，运算（加、减结果一样，异或运算，相同为异或运算，相同为0，相异为，相异为1）n模模2除商除商1的原则：只要被除数的首位为的原则：只要被除数的首位为1，且位数与除数相，且位数与除数相同则商同