1、Advanced Computer Networks計算機網絡ReviewData link layer design issuesService Provided to the network layerFramingError-Correcting CodesError-Detecting Codes2The Data Link LayerChapter 3 3TopicsError detection and correction Hamming code CRC (Cyclic Redundancy Check)42.1 Error-Correcting Codes2. Error D

2、etection 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 codeword is even (or odd)E.g., 1011010 10110100 2D parity check code: Form the data to be transmitted in

3、to a matrix. Add a parity bit to each row and each column of the matrix.5Hamming distance Rule: To determine how many bits differ, just exclusive OR the two codewords and count the number of 1 bits in the result, for example:Definition: The number of bit positions in which two codewords differ is ca

4、lled 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.6 The bits that are powers of 2 (1, 2, 4, 8, 16, etc.) are check bits.The rest (3, 5, 6, 7, 9, etc.) are filled up with the m data bits. Each ch

5、eck bit forces the parity of some collection of bits, including itself, to be even (or odd). Hamming codeCorrect single errors!7Exercise1. An 8-bit byte with binary value 10101111 is to be encoded using an even-parity Hamming code. What is the binary value after encoding? 2. A 12-bit Hamming code wh

6、ose 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.1The original 8-bit data value was 0 xAF.8Goal: detect “errors” (e.g., flipped bits) in transmitted frame (note: used at transport layer only)SenderReceive2.

7、2 Error-Detecting Codes9Modulo 2 arithmeticNo carries for addition or borrows for subtractionBoth addition and subtraction are identical to exclusive OR Long division is carried out the same way as it is in binary except that the subtraction is done modulo 2, as above.10Generator Polynomial - G(x)Th

8、e sender and receiver must agree upon a generator polynomial in advanceBoth the high- and low- order bits of G(x) must be 1To compute the checksum for some frame with m bits, corresponding to the polynomial M(x), the frame must be longer than G(x)11The idea of CRC The idea is to append a checksum to

9、 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 there is a remainder, there has been a transmission error.12view data bits, D, as a binary numberchoose r+

10、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 less than r+1 bitswidely used in practice (ATM, HDLC)Cyclic Redundancy Check13R = remainder D.2rGExam

11、ple1Data Frame: 101110000Generator G(x) = x3 + 1The transmitted Frame: 10111000001114Fig.2 Calculation of the polynomial code checksum Fig.2 illustrates the calculation for a frame 1101011011 using the generator G(x) = x4 + x + 1.Example2The transmitted Frame:15Transmitting T(x), receiving T(x)Recei

12、ver 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.16What is the remainder obtained by dividing x7+x5+1 by the generator polynomial x3+x+1? 在數據傳輸過程中，若接收方收到發送方送來的信息為，生成多項式為G(x)=x3+x2+1，接收方收到的數據是否正確

13、？若想發送的一段信息為，則在線路上傳輸的碼字是怎樣的？ Exercise010不正確10017The popular G(x)CRC-4 X4+X+1CRC-8 X8+X5+X4+1CRC-12 X12+X11+X3+X+1CRC-16 X16+X15+X2+1CRC-16-CCITT X16+X12+X5+1CRC32 X32+X26+X23+X22+X16+X12+X11+X10 +X8+X7+X5+X4+X2+X+1 18冗余碼的計算舉例 現在 k = 6, M = 101001。設 n = 3, 除數 P = 1101，被除數是 2nM = 101001000。 模 2 運算的結果是：

14、商 Q = 110101， 余數 R = 001。把余數 R 作為冗余碼添加在數據 M 的后面發送出去。發送的數據是：2nM + R 即：101001001，共 (k + n) 位。 19接收端對收到的每一幀進行 CRC 檢驗 (1) 若得出的余數 R = 0，則判定這個幀沒有差錯，就接受(accept)。(2) 若余數 R 0，則判定這個幀有差錯，就丟棄。但這種檢測方法并不能確定究竟是哪一個或哪幾個比特出現了差錯。只要經過嚴格的挑選，并使用位數足夠多的除數 P，那么出現檢測不到的差錯的概率就很小很小。 20SummarizeDesign issuesService Provided to t

15、he network layerFraming Error-Correcting Codes Error-Detecting Codes21Homework Page2432, 3,5,14,1522Preparation Elementary data link protocols23差錯的檢測與控制（1） 差錯檢測 衡量通信線路傳輸質量的技術指標是誤碼率。Pe=錯誤接收的碼元數/接收的總碼元數（2）幾種冗余校驗方法 垂直冗余校驗水平冗余校驗水平垂直冗余校驗循環冗余校驗24垂直奇偶校驗 垂直奇偶校驗又稱縱向奇偶校驗，它能檢測出每列中所有奇數個錯，但檢測不出偶數個的錯，如下圖所示，因而對差錯的

16、漏檢率接近1/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 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垂直奇偶校驗方式25水平奇偶校驗 水平奇偶校驗又稱橫向奇偶校驗，它不但能檢測出各段同一位上的奇數個錯，而且還能檢測出突發長度=p的所有突發錯誤。其漏檢率要比垂直奇偶校驗方法低，但實現水平奇偶校驗時，一定要使用數據緩沖器。位數字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