计算机网络和协议分析

• 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 it is in binary except that the subtraction is done modulo 2, as above.
–Error-Correcting Codes
–Error-Detecting Codes
Chapter 3
The Data Link Layer
Sep’10 CN
Topics
Error detection and correction – Hamming code – CRC (Cyclic Redundancy Check)
• 2. A 12-bit Hamming code whose hexadecimal value is 0xE4F arrives at a receiver. What was the original value in hexadecimal? Assume that not more than 1 bit is in error. The original 8-bit data value was 0xAF.
Advanced Computer Networks
计算机网络
Weihong Chen Department of Computer Science Hunan City University Sep 2010
Review
• Data link layer design issues –Service Provided to the network layer –Framing
2.2 Error-Detecting Codes
Goal: detect “errors” (e.g., flipped bits) in transmitted frame (note: used at transport layer only) Sender Receive
Modulo 2 arithmetic
Sep’10 CN
Exercise
• 1. 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? 101001001111
பைடு நூலகம்
Sep’10 CN
2. Error Detection and Correction 2.1 Error-Correcting Codes
?
• 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
Sep’10 CN
Generator 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 polynomial M(x), the frame must be longer than G(x)
Sep’10 CN
Hamming code
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 check bit forces the parity of some collection of bits, including itself, to be even (or odd). Correct single errors!
Sep’10 CN
Hamming 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:
• 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.
101011 010101 111000 010010 Even check 1010110 0101011 1110001 0100100 010100
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.