第九章 错误检测与纠正,Chapter 9 ERROR DETECTION AND CORRECTION,9.1 Types of errors 9.2 Error detection 9.3 Error correction 9.4 Summary,Contents,Introduction,Any time data are transmitted from one node to the next, they can become corrupted in passage. Some applications require that errors be detected and corrected. Error detection and correction are implemented either at the data link layer or the transport layer of the OSI model.,9.1 Types of Errors,Whenever bits flow from one point to another, they are subject to unpredictable changes because of interference.,9.1.1 Single-bit error,A single-bit error is when only one bit in the data unit has changed.,In a single-bit error, a 0 is changed to a 1 or a 1 to a 0.,9.1.2 Multiple-Bit Error,A multiple-bit error is when two or more nonconsecutive(不连续的) bits in the data unit have changed.,9.1.3 Burst error,A burst error means that two or more consecutive (连续的) bits in the data unit have changed.,突发差错大多发生在串行传输时。 通常噪声持续时间比位持续时间长，这就是说当噪声影响数据时就会影响一组比特。 影响的位数依赖于数据速率和噪声持续时间。 例如，如果发送数据速率是1Kbps ,1/100s的噪声将影响10个比特;如果速率是1Mbps，同样的噪声影响10000个比特。,9.1.3 Burst error,9.2 Error Detection(错误检测),In error detection, we are looking only to see if any error has occurred. The answer is a simple yes or no. We are not even interested in the number of errors. A single-bit error is the same for us as a burst error.,9.2.1 Redundancy,The central concept in detecting or correcting errors is redundancy. To be able to detect or correct errors, we need to send some extra bits with our data. These redundant bits are added by the sender and removed by the receiver. Their presence allows the receiver to detect or correct corrupted bits.,Using redundant bits to check the accuracy of a data unit,9.2.1 Redundancy,Four types of redundancy checks are used in data communications.,VRC (Vertical Redundancy Check, 垂直冗余校验) LRC (Longitudinal Redundancy, 纵向冗余校验) CRC (Cyclical Redundancy Check, 循环冗余校验) Checksum(校验和) VRC、LRC、CRC在物理层实现，数据链路层使用；校验和应用于更高的OSI层次。,9.2.1 Redundancy,9.2.2 VRC (Vertical Redundancy Check),VRC(垂直冗余校验)often called parity check (奇偶校验): odd parity or even parity In this technique, a redundant bit, called a parity bit(校验位), is appended to every data unit so that the total number of 1s in the unit become either even or odd. VRC can detect all single-bit errors. It can detect multiple-bit or burst error only if the total number of errors is odd.,Even parity VRC concept,9.2.2 VRC (Vertical Redundancy Check),9.2.3 LRC (Longitudinal Redundancy Check),A better approach is the two-dimensional parity check. In this method, the data word is organized in a table (rows and columns). 在纵向冗余校验中，将一个数据块划分成几行，并将校验位组成的冗余行添加到整个数据块中。,LRC (Longitudinal Redundancy),9.2.3 LRC (Longitudinal Redundancy),9.2.3 LRC (Longitudinal Redundancy),LRC enormously increases the likelihood of detecting multiple-bit and burst errors. However, there is one pattern of errors that remains elusive. If two bits in one data unit are damaged and two bits in exactly the same positions in another data unit are also damaged, the LRC checker will not detect an error. 例如有两个数据单元11110000 以及11000011。如果在每个数据单元的第一个和最后一个位置的比特被改变，将数据单元变成01110001和01000010，那么LRC就无法检测出这些差错。,The third and most powerful of the redundancy checking techniques is the CRC. Unlike VRC and LRC which based on addition, CRC is based on binary division. 在CRC中，在数据单元末尾附加一串冗余比特，称作循环冗余校验码或循环冗余校验余数，使得整个数据单元可以被另一个预定的二进制数所整除。 到达目的地后，用同一个数去除整个数据单元。如果不产生余数，则认为数据单元是完整正确的，从而接受该数据单元；有余数意味着数据单元被破坏，因此拒绝接受该数据单元。,9.2.4 Cyclic Redundancy Check (CRC),9.2.4 Cyclic Redundancy Check (CRC),CRC generator and checker,在循环冗余校验中使用的冗余比特是将数据单元除以一个预定的除数后产生的，余数就是循环冗余校验码(CRC码)。 只有以下两个特性的CRC码才是合法的: 必须比除数至少少一位； 在附加到数据串末尾后必须形成可以被除数整除的比特序列。,9.2.4 Cyclic Redundancy Check (CRC),The process of deriving the CRC: Step 1: a string of n bits 0s is appended to the end of the data unit. (The number n is one less than the number of bits in the predetermined divisor, which is n+1 bits.) Step 2: the newly elongated data unit is divided by the divisor using a process called binary division. (The remainder resulting from this division is CRC.) Step 3: The CRC of n bits derived in step 2 replaces the appended 0s at the end of the data unit.,9.2.4 Cyclic Redundancy Check (CRC),CRC will detect all possible errors except those that change the bit value of a block of code by exactly the value of the divisor. Popular CRC divisors use 13,17, and 33 bits, bringing the likelihood of an undetected error almost to zero.,9.2.4.1 Reliability,A CRC generator uses modlo-2 division.,9.2.4.2 The CRC Generator,9.2.4.3 CRC Checker,9.2.4.4 Polynomials(多项式),The CRC generator (the divisor) is most often represented as an algebraic polynomial(代数多项式). 多项式所需具备的(基本)性质： 1、不被x除尽； 2、可被x+1除尽。 第一个条件保证检测出所有长度等于多项式阶数的突发差错；第二个条件保证检测出所有影响奇数位的突发差错。,9.2.4.4 Polynomials(多项式),高性能多项式所需具备的特性： 1、至少包含两项； 2、x0项的系数应该是1； 3、应该不能整除xt+1(t为2到n-1之间)； 4、应该有因子x+1。,A polynomial representing a divisor,9.2.4.4 Polynomials(多项式),The relationship of a polynomial to its corresponding binary re