数据通信基础：第10章 检错与纠错

《数据通信基础：第10章 检错与纠错》由会员分享，可在线阅读，更多相关《数据通信基础：第10章 检错与纠错（54页珍藏版）》请在装配图网上搜索。

1、数据通信基础数据通信基础第第10章章(检错与纠错检错与纠错)Error Detection&Correction20111028第第10章内容概要章内容概要10.1 Types of Errors 错误种类10.2 Error Detection 检错Simple Parity Check 简单奇偶校验Two-Dimensional Parity Check 二维奇偶校验Cyclic Redundancy Check(CRC)循环冗余校验Checksum 校验和10.3 Error Correction 纠错20111028Chapter BriefFrom this chapter on,w

2、e will start to discuss the contents for the Data Link Layer in the OSI seven-layer model.First in this chapter,the error detection and correction technique(also called Error Control差错控制)used in the data link layer is discussed.There are many techniques for this purpose,we will limit our discussion

3、on the Parity Check,CRC and Checksum.20111028Single-Bit Error单比特错误单比特错误Burst Error突发错误突发错误20111028Data can be corrupted during transmission.For reliable communication,errors must be detected and corrected.What causes ErrorError can be classified into two main kinds,single-bit error and burst error.2

4、0111028In a single-bit error,only one bit in the data unit has changed.Single-bit ErrorThere are two forms of single-bit error:0 changed to 1;1 changed to 020111028A burst error means that 2 or more bits in the data unit have changed.Burst Error20111028Influence of Burst ErrorBurst error can be a ve

5、ry serious problem to high speed data transmission.The number of bits affected depends on the data rate and duration of noise.For data rate of 1 kbps,a noise of 1/100 seconds can affect 10 bits;while the same noise can affect 10000 bits for the data rate of 1 Mbps.20111028Redundancy 冗余冗余Parity Check

6、Cyclic Redundancy Check(CRC)Checksum20111028Error Detection vs CorrectionError detection is the basis for error correction.The receiver should recognize the transmission errors before it can correct them.Generally speaking,error detection is easier than error correction.Error detection and correctio

7、n are implemented by the addition of REDUNDANCY bits to the original data.20111028Error detection uses the concept of redundancy,which means adding extra bits for detecting errors at the destination.Redundancy20111028Process to check error20111028Categories of Error DetectionThere are four kinds of

8、error detectionSimple Parity CheckAlso called Even or Odd Parity CheckTwo-Dimensional Parity CheckNot in use nowCyclic Redundancy Check(CRC)Checksum20111028Simple Parity Check is also called Parity Check.A redundancy bit(parity bit)is added to every data unit,so that the total number of 1s in the un

9、it(including the parity bit)becomes EVEN.Note that there is another possibility to use ODD-parity check,where the number of 1s should be odd.Furthermore,you can also count the number of 0s instead of 1s.20111028Process of Even-parity Check20111028In parity check,a parity bit is added to every data u

10、nit so that the total number of 1s is even(or odd for odd-parity).20111028Suppose the sender wants to send the word world.In ASCII the five characters are coded as 1110111 1101111 1110010 1101100 1100100The following shows the actual bits sent 11101110 11011110 11100100 11011000 11001001Note:The und

11、erlined bit in each byte represents the parity bit.Example 10.120111028Now suppose the word world in Example 10.1 is received by the receiver without being corrupted in transmission.11101110 11011110 11100100 11011000 11001001The receiver counts the 1s in each character and comes up with even number

12、s(6,6,4,4,4).The data are accepted.Example 10.220111028Now suppose the word world in Example 10.1 is corrupted during transmission.11111110 11011110 11101100 11011000 11001001The receiver counts the 1s in each character and comes up with even and odd numbers(7,6,5,4,4).The receiver knows that the da

13、ta are corrupted,discards them,and asks for retransmission.Example 10.320111028Performance of Parity Check20111028Another form of Parity Check is called Two-dimensional Parity Check.Instead of only one redundancy bit,a group of bits is used for the checking.This group of bits consists of several Par

14、ity Bits,which are formed from the corresponding bit in each data unit.20111028Formation of 2D Parity Check20111028In two-dimensional parity check,a block of bits is divided into rows and a redundant row of bits is added to the whole block.20111028Suppose the following block is sent:10101001 0011100

15、1 11011101 11100111 10101010 However,it is hit by a burst noise of length 8,and some bits are corrupted.10100011 10001001 11011101 11100111 10101010 When the receiver checks the parity bits,some of the bits do not follow the even-parity rule and the whole block is discarded.10100011 10001001 1101110

16、1 11100111 10101010 Example 10.420111028Performance of 2D Parity Check2D PC of n bits can easily detect a burst error of length n bits.A burst error of more than n bits is also detected by 2D PC with a very high probability 概率.2D PC can not detect the error when TWO bits in separate data unit in the

17、 exactly same positions.20111028CRC Generator 产生器产生器CRC Checker 检验器检验器Polynomials 多项式多项式Performance20111028CRC PrincipleUnlike VRC and LRC,CRC is based on binary division.The original data sequence plus n 0 bits(forms the Dividend被除数)is divided by a n+1 bits long fixed Divisor除数,resulting a n bits l

18、ong Remainder余数.The Quotient商 is not used for transmission.The Remainder is called CRC and is sent to the receiver together with the data sequence.20111028CRC Generator and Checker20111028CRC GeneratorNote here:Use binary addition without carry.20111028CRC Checker20111028PolynomialsThe CRC generator

19、(divisor)is often represented as a polynomial.A polynomial form uses the exponential of x to represent the position of binary“1”in the Divisor.NOTE the lowest exponent is 0.20111028NamePolynomialApplicationx8+x2+x+1ATM headerx10+x9+x5+x4+x 2+1ATM AALx16+x12+x5+1HDLCx32+x26+x23+x22+x16+x12+x11+x10+x8

20、+x7+x5+x4+x2+x+1LANsCommonly-used PolynomialsIn data communication,CRC is used for many popular protocols in upper-layer of OSI model.Most of them are standardized by ITU-T.20111028Performance of CRCCRC is very effective.CRC can detect all burst errors that affect an odd number of bits.CRC can detec

21、t all burst errors of length less than or equal to the degree of the polynomial.CRC can detect with a very high probability burst errors of length greater than the degree of the polynomial.20111028The CRC-12 x12+x11+x3+x+1which has a degree of 12,will detect all burst errors affecting an odd number

22、of bits,will detect all burst errors with a length less than or equal to 12,and will detect,99.97 percent of the time,burst errors with a length of 12 or more.Example 10.620111028Checksum GeneratorChecksum CheckerPerformance20111028ChecksumChecksum is another error detection method often used for hi

23、gher-layer protocols.Checksum is based on summation and ONEs Complement 补码arithmetic.The checksum is sent to the receiver and the same calculation is performed at the receiver.If the result is zero,this means no error has occurred during transmission.20111028Checksum at Sender&Receiver20111028ONEs C

24、omplementSee page 881 in appendix E of the book for more detail.To find the complement of a number,invert all of its digits.Adding a number to its complement equals ZERO.+0=(00000000)2-0=(11111111)220111028Data Unit&ChecksumIf the sum of the data segment is T,the checksum will be T.Data and Checksum

25、 are sent to receiver.Their sum is 0 and the resulting complement is 0.20111028Checksum Sender20111028Checksum Receiver20111028Suppose the following block of 16 bits is to be sent using a checksum of 8 bits.10101001 00111001 The numbers are added using ones complement 10101001 00111001 -Sum 11100010

26、Checksum 00011101The pattern sent is 10101001 00111001 00011101Example 10.720111028Now suppose the receiver receives the pattern sent in Example 10.7 and there is no error.10101001 00111001 00011101When the receiver adds the three sections,it will get all 1s,which,after complementing,is all 0s and s

27、hows that there is no error.1010100100111001 00011101 Sum11111111 Complement 00000000 means that the pattern is OK.Example 10.820111028Now suppose there is a burst error of length 5 that affects 4 bits.10101111 11111001 00011101When the receiver adds the three sections,it gets 1010111111111001 00011

28、101 Partial Sum 1 11000101Carry 1Sum11000110 Complement 00111001 the pattern is corrupted.Example 10.920111028Single-bit Error CorrectionHamming CodeBurst Error Correction20111028Error CorrectionSo far we have discussed error detection.After the error is recognized,several methods can be used to cor

29、rect the error.In Retransmission(Automatic Retransmission reQuest,ARQ自动重传请求),receiver will request sender to resend the entire data unit.In Forward Error Correction(FEC前向纠错),errors will be automatically corrected using the error-correcting code.20111028Redundancy BitsFor m data bits,r redundancy bit

30、s are added,forming a total m+r bits.There are m+r+1 states of error positions,all of them should be indicated by the r redundancy bits.Therefore we have the equation:12rmr20111028Number ofdata bitsmNumber of redundancy bitsrTotal bitsm+r2335363749410411Required redundancy bits20111028Hamming CodeR.

31、W.Hamming developed a technique of how to form the correction code.Positions of redundancy bits in Hamming code is shown in the figure below.Four redundancy bits are added to seven data bits(ASCII).After calculation at the receiver,the position of error can be found.Thus,error can be corrected.20111028Redundancy bit calculation20111028Example of redundancy bit calculation20111028Error Correction using Hamming Code20111028Summary for Chapter 10错误可以分为单比特错误和突发错误。检错的四种方法包括：奇偶校验、二维奇偶校验、CRC以及校验和。奇偶校验又分为奇校验和偶校验。CRC是一种基于长除法的有效的检错法。校验和用于高层协议的错误检测。汉明码是一种可以纠单比特错误的纠错码。20111028ExercisesPage 261-26643349