第10章_检错与纠错.ppt

第十章第十章 检错与纠错检错与纠错 Chapter 10 Chapter 10 Error Detection and Error Detection and CorrectionCorrection Computer NetworksComputer Networks P.174 本章主要内容本章主要内容 What’s about What’s about This ChapterThis Chapter？？ 本章学习如何检测和纠正数据传输中“位差错” l本章研究： “位差错”的概念和类型 检错技术基本原理 三种常用的检错技术 l奇偶校验技术 l循环冗余校验技术 l校验和技术 l汉明码纠错技术 l本章仅讲技术原理，数学细节留给大家自己去深入… 本章主要内容本章主要内容 ContentsContents 1 差错类型 Types of Error 2 差错检测 Error Detection 3 差错纠正 Error Detection 概述概述 OverviewOverview l传输中差错是不可避免的所以必须检测和纠正比特流在传 输中出现的“位差错” l所谓“位差错” ，就是指将数据从一个节点传送到下一个节点 的过程中，数据中的一位（比特）或多位发生了改变。

l“位差错”检测的基本原理是“冗余校检技术” l检错技术的基本要求：接收方应在不知道实际发送的数据的 情况下，能发现所接收到的数据是否有错 l在计算机通信中，通常是先检错，发现差错时不是对有错的 数据进行纠错，而是丢弃有差错的数据，并通过“重传”（将 数据重新发送一遍）实现纠错 l无论是检错还是纠错技术，都是数学研究的成果 1 1 差错类型差错类型 Types of ErrorTypes of Error 传输差错的产生传输差错的产生 Error ProductionError Production l信号在物理信道中传输时，线路本身电器特性 造成的随机噪声、信号幅度的衰减、频率和相 位的畸变、电器信号路上产生反射造成的 回音效应、相邻线路间的串扰以及各种外界因 素（如大气中的闪电、开关的跳火、外界强电 流磁场的变化、电源的波动等）都会造成传输 信号的失真 l在数据通信中，以上原因将会使接收端收到的 二进制数位和发送端实际发送的二进制数位不 太一致，从而造成由“0”变成“1”或由“1”变成“0” 的差错 差错产生的原因差错产生的原因 Reasons of Error ProductionReasons of Error Production 信道本身的随机热噪声 随机错误(某位错）,可通过提高信道的信 噪比等方法来抑制 外界原因引起的冲击噪声 突发错误（一 连串码元均出错） 【突发长度】从突发错误发生的第一个码元 到有错的最后一个码元间所有码元的个数 差错类型差错类型 Types of ErrorsTypes of Errors 差错类型示意图差错类型示意图 More about ErrorsMore about Errors 一位差错： 数据单元中仅某一位差错 多位差错： 数据单元中两位或两位以上 差错 突发差错： 数据单元中连续两位或两位 以上差错。

受影响的位数取 决于数据速度和噪声的持续 时间 参见P174-175 图10.1, 图10.2 发生差错的码元数 Pe = ————————— 接收的总码元数 在计算机网络中，误码率一般要求低于10-6 误码率误码率 Undetectd Error RateUndetectd Error Rate 2 2 差错检测差错检测 Error DetectionError Detection 实现差错检测的基本思路 发送方添加一些附加的比特作为差错检测码 l从最简单的做法说起 问题：知道了可能发生的差错类型，如何把它 们检测出来？ 一种可用的方法：将每个数据单元发送两次 Ø如输入密码或告诉对方号码两遍 缺点：这样做将使数据传送速率奇慢 Ø传输时间将要增加一倍， Ø需花费大量时间进行逐个比特的比较 差错检测原理差错检测原理 Error DetectionError Detection：：PrinciplePrinciple 使用“冗余校验技术” 最常用的技术是在每个数据单元中加入一些称为“冗余位 ”的附加比特（即“差错控制编码”） 这种技术之所以被称为“冗余校验技术”,因为一旦传输被 确认无误，那些附加的冗余数位便被自动丢弃。

发送的码字发送的码字= =数据位数据位+ +冗余位冗余位 （第二遍给出的密码或号码即为“冗余位”） 数据位——要发送的数据 冗余位——差错控制编码 码 字——codeword 差错检测技术差错检测技术 Error DetectionError Detection：：TechniqueTechnique 数据字和码字数据字和码字 DatawordsDatawords and and CodewordsCodewords l数据字：报文划成的数据块（假设为k位 ） l码字：数据字＋冗余位 P17７图10.５ 编码器和译码器的结构编码器和译码器的结构 The structure of encoder and decoderThe structure of encoder and decoder P175图10.3 冗余校验示意图冗余校验示意图 RedundancyRedundancy 差错控制编码可分为： ◆ 检错码 用于自动发现传输差错的编码 ◆ 纠错码 能自动发现而且能自动纠正传输差错的编码 编码效率计算: k k R= ——— = ——— k+r n 式中: k - 码字中信息位数 r - 码字中冗余位数 n - 码字总位数 差错控制的两大目标： 尽量降低误码率 尽量提高编码效率 差错控制编码差错控制编码 Redundancy CheckRedundancy Check 模模2 2运算运算 Modulo-2 ArithmeticModulo-2 Arithmetic l又称异或运算(XOR), 计算机编码常用。

l运算法则: l相同是0,不同是1 l或者视为没有进位的1和0的简单加法 P176 图10.4 汉明距离汉明距离 Hamming DistanceHamming Distance l汉明距离 两个码字作XOR运算，运算结果中1的个 数 例 10.4 1. d(000,011)的汉明距离是2 2. d(10101,11110)的汉明距离是3 关于汉明距离关于汉明距离 More about More about Hamming DistanceHamming Distance l在信息论中，两个等长字符串之间的汉明距离 是两个字符串对应位置的不同字符的个数换 句话说，它就是将一个字符串变换成另外一个 字符串所需要替换的字符个数 例如： 1011101 与 1001001 之间的汉明距离是 2 2143896 与 2233796 之间的汉明距离是 3 “toned” 与 “roses” 之间的汉明距离是 3 l汉明距离是以美国数学家理查德·卫斯里·汉明 (Richard Wesley Hamming,1915-1998)的名字 命名的 最小汉明距离最小汉明距离 Minimum Hamming DistanceMinimum Hamming Distance l最小汉明距离 有效码字表中所以码字对的最小汉明距离 。

例10.5 求表10.1的最小汉明距离(dmin=2) 例10.6 求表10.2的最小汉明距离(dmin=3) 编码方案编码方案 Encoding SchemeEncoding Scheme l编码方案三参数 码字长度n， 数据位长度k，最小汉明距离dmin 写法 C(n,k)和dmin=… l检错定理 一个编码方案的最小汉明距离如果是dmin=s+1 ，那么只能检测出不多于s个的差错 l纠错定理 一个编码方案的最小汉明距离如果是dmin=2s+1 ，那么只能纠正不多于s个的差错 差错检测技术分类差错检测技术分类 Types of Redundacy ChecksTypes of Redundacy Checks l奇偶校验 l奇、偶位值的加入，使字符中“1”的个数为偶数（“ 偶校验”）或奇数（“奇校验”） l无法检测整数倍偶数个比特差错 l使用奇偶校验并不是十分安全，因为噪声脉冲持 续的时间经常足以破坏一个以上的比特，特别是 在数据率较高的情况下 l奇偶校验码 通过增加冗余位使码字中“1”的个数保持奇数或偶数 的编码方法简单经济，但漏检率较高 ■ 垂直奇偶校验 (简单奇偶校验，行奇偶校验) ■ 水平奇偶校验（列奇偶校验） ■ 水平垂直奇偶校验(两维奇偶校验) ①① 奇偶校验奇偶校验 Parity CheckParity Check 奇偶校验码的编码与译码奇偶校验码的编码与译码 EncodEncodngng and Decoding for Parity-check Code and Decoding for Parity-check Code P176 图10.4 l垂直奇偶校验( “简单奇偶校验”或“行奇偶校验”) 编码和校验实现最简单。

可以边发送边插入冗余位 最常用而且最经济的检错技术 l偶校验（even-parity check） 使码字中“1”的个数保持偶数 l奇校验（odd-parity check） 使码字中“1”的个数保持奇数 垂直奇偶校验技术垂直奇偶校验技术 Vertical Parity CheckVertical Parity Check 垂直奇偶校验码垂直奇偶校验码 Vertical Parity Check CodeVertical Parity Check Code 偶校验位 p = (d1+d2+…+dn-1) = 奇校验位 p = (d1+d2+…+dn-1+1) = 编码方案编码方案 Encoding SchemeEncoding Scheme l表10.1和表10.3分别是数据位为2和5时的“简单 奇偶校验码” C(3,2)和C(5,4) l可以证明C(3,2)和C(5,4)编码方案的最小汉明距 离都是dmin=2 l根据检错定理，这种编码只能检测出单个位的 差错，且不能纠正任何差错 l实际上，简单奇偶校验码可以检测出发生奇数 个差错出现的问题，但不能检测出发生偶数个 差错的问题。

lP182 例10.12 (数据见下页) 表表10.3 10.3 C(5, 4)简单奇偶校验编码简单奇偶校验编码 Simple parity-check code C(5, 4) l如果接收到的码字不在上表，则被拒收（检错成功） l如果接收到的码字在上表中，则被接收（无出错或漏检） 偶校验示意图偶校验示意图 Even-parity Check ConceptEven-parity Check Concept 奇校验示意图奇校验示意图 Odd-parity Check ConceptOdd-parity Check Concept 垂直奇偶校验可以检测出所有的1位差错，但只能检测差错数为奇数 的多位差错或突发差错差错漏检率≈1/2 【例】原始数据000111011，采用偶校验 则发送端通过线路传输发出的码字为1000111011 若接收端接收到的是 1111111011 或0110111011 或 1100010011，将均被拒收 但若接收端接收到的是1110111011或1100011011或 1000011010，仍会通过验收（漏检） 编码效率 R： (设发送的数据为k位,发送时另加一个奇校验位或偶校验位) 垂直奇偶校验示例垂直奇偶校验示例 Sample of VRC Sample of VRC 水平奇偶校验水平奇偶校验 Longitudinal Redundancy CheckLongitudin。