1、Weihong ChenDepartment of Computer ScienceHunan City UniversitySep 2010Advanced Computer Networks计算机网络Sep10 CNReview Data link layer design issuesService Provided to the network layerFramingError-Correcting CodesError-Detecting CodesSep10 CNThe Data Link LayerChapter 3 Sep10 CNTopicsError detection
2、and correction Hamming code CRC(Cyclic Redundancy Check)Sep10 CN2.1 Error-Correcting Codes2.Error Detection and Correction1010110101011110000100101010110010101111100010100100010100Even check?A single parity bit appended to the data,the parity bit is chosen so that the number of 1 bits in the codewor
3、d is even(or odd)E.g.,1011010 10110100 2D parity check code:Form the data to be transmitted into a matrix.Add a parity bit to each row and each column of the matrix.Sep10 CNHamming distance Rule:To determine how many bits differ,just exclusive OR the two codewords and count the number of 1 bits in t
4、he result,for example:Definition:The number of bit positions in which two codewords differ is called the Hamming distance.Significance:if two codewords are a Hamming distance d apart,it will require d single-bit errors to convert one into the other.Sep10 CN The bits that are powers of 2(1,2,4,8,16,e
5、tc.)are check bits.The rest(3,5,6,7,9,etc.)are filled up with the m data bits.Each check bit forces the parity of some collection of bits,including itself,to be even(or odd).Hamming codeCorrect single errors!Sep10 CNExercise 1.An 8-bit byte with binary value 10101111 is to be encoded using an even-p
6、arity Hamming code.What is the binary value after encoding?2.A 12-bit Hamming code whose hexadecimal value is 0 xE4F arrives at a receiver.What was the original value in hexadecimal?Assume that not more than 1 bit is in error.101001001111The original 8-bit data value was 0 xAF.Sep10 CNGoal:detect“er
7、rors”(e.g.,flipped bits)in transmitted frame(note:used at transport layer only)SenderReceive2.2 Error-Detecting CodesSep10 CNModulo 2 arithmetic No carries for addition or borrows for subtraction Both addition and subtraction are identical to exclusive OR Long division is carried out the same way as
8、 it is in binary except that the subtraction is done modulo 2,as above.Sep10 CNGenerator Polynomial-G(x)The sender and receiver must agree upon a generator polynomial in advance Both the high-and low-order bits of G(x)must be 1 To compute the checksum for some frame with m bits,corresponding to the
9、polynomial M(x),the frame must be longer than G(x)Sep10 CNThe idea of CRC The idea is to append a checksum to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by G(x).When the receiver gets the checksummed frame,it tries dividing it by G(x).If
10、there is a remainder,there has been a transmission error.Sep10 CNview data bits,D,as a binary numberchoose r+1 bit pattern(generator),G goal:choose r CRC bits,R,such that exactly divisible by G(modulo 2)receiver knows G,divides by G.If non-zero remainder:error detected!can detect all burst errors le
11、ss than r+1 bitswidely used in practice(ATM,HDLC)Cyclic Redundancy CheckSep10 CNR=remainder D.2rGExample1Data Frame:101110000Generator G(x)=x3+1The transmitted Frame:101110000011Sep10 CNFig.2 Calculation of the polynomial code checksum Fig.2 illustrates the calculation for a frame 1101011011 using t
12、he generator G(x)=x4+x+1.Example2The transmitted Frame:Sep10 CN Transmitting T(x),receiving T(x)Receiver computes E(x)=T(x)/G(x)Those errors that happen to correspond to polynomials containing G(x)as a factor will slip by;all other error will be caught.Sep10 CNWhat is the remainder obtained by divid
13、ing x7+x5+1 by the generator polynomial x3+x+1?在数据传输过程中，若接收方收到发送方送来的信息为在数据传输过程中，若接收方收到发送方送来的信息为10110011，生成多项式为，生成多项式为G(x)=x3+x2+1，接收方收到的，接收方收到的数据是否正确？若想发送的一段信息为数据是否正确？若想发送的一段信息为10110011，则在，则在线路上传输的码字是怎样的？线路上传输的码字是怎样的？Exercise010不正确不正确10110011100Sep10 CNThe popular G(x)CRC-4 X4+X+1 CRC-8 X8+X5+X4+1 C
14、RC-12 X12+X11+X3+X+1 CRC-16 X16+X15+X2+1 CRC-16-CCITT X16+X12+X5+1 CRC32 X32+X26+X23+X22+X16+X12+X11+X10 +X8+X7+X5+X4+X2+X+1 Sep10 CN冗余码的计算举例冗余码的计算举例 现在现在 k=6,M=101001。设设 n=3,除数除数 P=1101，被除数是被除数是 2nM=101001000。模模 2 运算的结果是：运算的结果是：商商 Q=110101，余数余数 R=001。把余数把余数 R 作为作为冗余码冗余码添加在数据添加在数据 M 的后面发送出去。发送的数据的后面
15、发送出去。发送的数据是：是：2nM+R 即：即：101001001，共，共(k+n)位。位。Sep10 CN接收端对收到的每一帧进行接收端对收到的每一帧进行 CRC 检验检验 (1)若得出的余数若得出的余数 R=0，则判定这个帧没有差错，就，则判定这个帧没有差错，就接接受受(accept)。(2)若余数若余数 R 0，则判定这个帧有差错，就，则判定这个帧有差错，就丢弃丢弃。但这种检测方法并不能确定究竟是哪一个或哪几个比特但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。出现了差错。只要经过严格的挑选，并使用位数足够多的除数只要经过严格的挑选，并使用位数足够多的除数 P，那，那么出现检
16、测不到的差错的概率就很小很小。么出现检测不到的差错的概率就很小很小。Sep10 CNSummarize Design issues Service Provided to the network layer Framing Error-Correcting Codes Error-Detecting CodesSep10 CNHomework Page243 2,3,5,14,15Sep10 CNPreparation Elementary data link protocolsSep10 CN差错的检测与控制差错的检测与控制（1）差错检测 衡量通信线路传输质量的技术指标是误码率误码率。Pe=
17、错误接收的码元数/接收的总码元数（2）几种冗余校验方法 垂直冗余校验水平冗余校验水平垂直冗余校验循环冗余校验Sep10 CN垂直奇偶校验垂直奇偶校验 垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错，如下图所示，因而对有奇数个错，但检测不出偶数个的错，如下图所示，因而对差错的漏检率接近差错的漏检率接近1/21/2。位位数字数字0 1 2 3 4 5 6 7 8 9C10 1 0 1 0 1 0 1 0 1C20 0 1 1 0 0 1 1 0 0C30 0 0 0 1 1 1 1 0 0C40 0 0 0 0 0
18、0 0 1 1C51 1 1 1 1 1 1 1 1 1C61 1 1 1 1 1 1 1 1 1C70 0 0 0 0 0 0 0 0 0 偶偶C00 1 1 0 1 0 0 1 1 0奇奇1 0 0 1 0 1 1 0 0 1垂直奇偶校验方式Sep10 CN水平奇偶校验水平奇偶校验 水平奇偶校验又称横向奇偶校验，它不但能检测出各段水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度同一位上的奇数个错，而且还能检测出突发长度=p=p的所有突的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校
19、验时，一定要使用数据缓冲器。偶校验时，一定要使用数据缓冲器。位位数字数字0 1 2 3 4 5 6 7 8 9偶校验偶校验C10 1 0 1 0 1 0 1 0 11C20 0 1 1 0 0 1 1 0 00C30 0 0 0 1 1 1 1 0 00C40 0 0 0 0 0 0 0 1 10C51 1 1 1 1 1 1 1 1 11C61 1 1 1 1 1 1 1 1 11C70 0 0 0 0 0 0 0 0 00水平奇偶校验方式 Sep10 CN水平垂直校验水平垂直校验 水平垂直校验水平垂直校验(LRC)(LRC)又叫报文校验、方块校验。又叫报文校验、方块校验。将若干水平奇偶校验
20、码排成若干行，然后对每列进行奇偶校将若干水平奇偶校验码排成若干行，然后对每列进行奇偶校验，放在最后一行，该检验字符的编码方法是使每一位纵向代码验，放在最后一行，该检验字符的编码方法是使每一位纵向代码中中1 1的个数成为奇数的个数成为奇数(或偶数或偶数)。传输时按照列顺序进行传输，在。传输时按照列顺序进行传输，在一批字符传送之后，另外增加一个检验字符，在接收端又按照行一批字符传送之后，另外增加一个检验字符，在接收端又按照行的顺序检验是否存在差错。的顺序检验是否存在差错。图2-25 水平垂直奇偶校验方式BackSep10 CNSep10 CNSep10 CNSep10 CNSep10 CNBackSep10 CN
