计算机网络和协议分析8.ppt

Advanced Computer Networks
计算机网络
Review
Data link layer design issues
Service Provided to the network layer
Framing
Error-Correcting Codes
Error-Detecting Codes
2
The Data Link Layer
Chapter 3
3
Topics
Error detection and correction
Hamming code
CRC (Cyclic Redundancy Check)
4
Error-Correcting Codes
2. Error Detection and Correction
101011
010101
111000
010010
1010110
0101011
1110001
0100100
010100
Even
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)
., 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.
5
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:
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.
6
The bits that are powers of 2 (1, 2, 4, 8, 16, etc.) are check 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 code
Correct single errors!
7
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?
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.
1
The original 8-bit data value was 0xAF.
8
Goal: detect “errors” (., flipped bits) in transmitted frame (note: used at transport layer only)
Sender
Receive
Error-Detecting Codes
9
Modulo 2 arithmetic
No carries for addition or borrows