EECS 122 Introduction to Computer Networks Error Detection and Reliable Transmission Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 High Level View Goal transmit correct information Problem bits can get corrupted Electrical interference thermal noise Solution Detect errors Recover from errors Correct errors Retransmission already done this Katz Stoica F04 2 Overview Error detection recovery Reliable Transmission Katz Stoica F04 3 Error Detection Problem detect bit errors in packets frames Solution add extra bits to each packet Goals Reduce overhead i e reduce the number of redundancy bits Increase the number and the type of bit error patterns that can be detected Examples Two dimensional parity Checksum Cyclic Redundancy Check CRC Hamming Codes Katz Stoica F04 4 Two dimensional Parity Add one extra bit to a 7 bit code such that the number of 1 s in the resulting 8 bits is even for even parity and odd for odd parity Add a parity byte for the packet Example five 7 bit character packet even parity 0110100 1 1011010 0 0010110 1 1110101 1 1001011 0 1000110 1 Katz Stoica F04 5 How Many Errors Can you Detect All 1 bit errors Example error bit 0110100 1 1011010 0 0000110 1 1110101 1 1001011 0 1000110 1 odd number of 1 s Katz Stoica F04 6 How Many Errors Can you Detect All 2 bit errors Example error bits 0110100 1 1011010 0 0000111 1 1110101 1 1001011 0 1000110 1 odd number of 1 s on columns Katz Stoica F04 7 How Many Errors Can you Detect All 3 bit errors Example error bits 0110100 1 1011010 0 0000111 1 1100101 1 1001011 0 1000110 1 odd number of 1 s on column Katz Stoica F04 8 How Many Errors Can you Detect Most 4 bit errors Example of 4 bit error that is not detected error bits 0110100 1 1011010 0 0000111 1 1100100 1 1001011 0 1000110 1 How many errors can you correct Katz Stoica F04 9 Checksum Sender add all words of a packet and append the result checksum to the packet Receiver add all words of a packet and compare the result with the checksum Can detect all 1 bit errors Example Internet checksum Use 1 s complement addition Katz Stoica F04 10 1 s Complement Revisited Negative number x is x with all bits inverted When two numbers are added the carry on is added to the result Example 15 16 assume 8 bit representation 15 00001111 15 11110000 16 00010000 15 16 1 1 00000000 1 00000001 Katz Stoica F04 11 Cyclic Redundancy Check CRC Represent a n 1 bit message as an n degree polynomial M x E g 10101101 M x x7 x5 x3 x2 x0 Choose a divisor k degree polynomial C x Compute reminder R x of M x xk C x i e compute A x such that M x xk A x C x R x where degree R x k Let T x M x xk R x A x C x Then T x is divisible by C x First n coefficients of T x represent M x Katz Stoica F04 12 Cyclic Redundancy Check CRC Sender Compute and send T x i e the coefficients of T x Receiver Let T x be the n k degree polynomial generated from the received message If C x divides T x no errors otherwise errors Note all computations are modulo 2 Katz Stoica F04 13 Arithmetic Modulo 2 Like binary arithmetic but without borrowing carrying from to adjacent bits Examples 101 010 111 101 001 100 1011 0111 1100 101 010 111 101 001 100 1011 0111 1100 Addition and subtraction in binary arithmetic modulo 2 is equivalent to XOR a b a b 0 0 0 0 1 1 1 0 1 1 1 0 Katz Stoica F04 14 Some Polynomial Arithmetic Modulo 2 Properties If C x divides B x then degree B x degree C x Subtracting adding C x from to B x modulo 2 is equivalent to performing an XOR on each pair of matching coefficients of C x and B x E g B x x7 B x C x x7 x 5 x3 x 2 x0 C x x3 x1 x0 00001011 x5 10100110 x2 x1 10101101 Katz Stoica F04 15 Example Sender Operation Send packet 110111 choose C x 101 k 2 M x xK 11011100 Compute the reminder R x of M x xk C x 101 11011100 101 111 101 101 101 100 101 1 R x Compute T x M x xk R x 11011100 xor 1 11011101 Send T x Katz Stoica F04 16 Example Receiver Operation Assume T x 11011101 C x divides T x no errors Assume T x 11001101 Reminder R x 1 error 101 11001101 101 110 101 111 101 101 101 1 R x Note an error is not detected iff C x divides T x T x Katz Stoica F04 17 CRC Properties Detect all single bit errors if coefficients of xk and x0 of C x are one Detect all double bit errors if C x has a factor with at least three terms Detect all number of odd errors if C x contains factor x 1 Detect all burst of errors smaller than k bits Katz Stoica F04 18 Code words Combination of the n payload bits and the k check bits as being a n k bit code word For any error correcting scheme not all n k bit strings will be valid code words Errors can be detected if and only if the received string is not a valid code word Example even parity check only detects an odd number of bit errors Katz Stoica F04 19 Hamming Distance Given code words A and B the Hamming distance between them is the number of bits in A that need to be flipped to turn it into B E g H 011101 000000 4 If all code words are at least d Hamming distance apart then up to d 1 bit errors can be detected Katz Stoica F04 20 Error Correction If all the code words are at least a hamming distance of 2d 1 apart then up to d bit errors can be corrected Just pick the codeword closest to the one received How many bits are required to correct d errors when there are n bits in the payload Example d 1 Suppose n 3 Then any payload can be transformed into 3 other payload strings e g 000 into 001 010 or 100 Need at least two extra bits to differentiate between 4 possibilities In general need at least k log2 n 1 bits A scheme that is optimal is called a perfect parity code Katz Stoica F04 21 Perfect Parity Codes Consider a codeword of n k bits b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 Parity bits are in positions 20 21 22 23 24 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 A parity bit in position 2h checks …
View Full Document
Unlocking...