EE122: Error Detection and Reliable TransmissionEECS 122: Introduction to Computer Networks Error Detection and Reliable TransmissionToday’s Lecture: 24High Level ViewOverviewError DetectionTwo-dimensional ParityHow Many Errors Can you Detect?Slide 9Slide 10Slide 11Checksum1’s Complement RevisitedCyclic Redundancy Check (CRC)Slide 15Arithmetic Modulo 2Some Polynomial Arithmetic Modulo 2 PropertiesExample (Sender Operation)Example (Receiver Operation)CRC PropertiesCode wordsHamming DistanceError CorrectionPerfect Parity CodesExample: (7,4)-Parity CodeSlide 26Reliable TransmissionError correction or Retransmission?Erasure CodesExample: Digital FountainErasure Coding ApproachesPowerPoint PresentationSlide 33Slide 34Slide 35LT Encoding PropertiesWhat Do You Need To Know?Katz, Stoica F04EE122: Error Detection and Reliable TransmissionNovember 19, 2003Katz, Stoica F04EECS 122: Introduction to Computer Networks Error Detection and Reliable TransmissionComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17763Katz, Stoica F04Today’s Lecture: 24Network (IP)ApplicationTransportLinkPhysical27, 8, 910,1114, 15, 1621, 2223617,1819, 20244Katz, Stoica F04High Level ViewGoal: transmit correct informationProblem: bits can get corrupted-Electrical interference, thermal noiseSolution-Detect errors-Recover from errors •Correct errors•Retransmission already done this5Katz, Stoica F04OverviewError detection & recoveryReliable Transmission6Katz, Stoica F04Error DetectionProblem: detect bit errors in packets (frames)Solution: add extra bits to each packetGoals: -Reduce overhead, i.e., reduce the number of redundancy bits-Increase the number and the type of bit error patterns that can be detectedExamples:-Two-dimensional parity-Checksum-Cyclic Redundancy Check (CRC) -Hamming Codes7Katz, Stoica F04Two-dimensional ParityAdd 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 packetExample: five 7-bit character packet, even parity 01101001011010001011011101011001011101101000110 18Katz, Stoica F04How Many Errors Can you Detect?All 1-bit errorsExample:01101001011010000011011101011001011101101000110 1error bitodd number of 1’s9Katz, Stoica F04How Many Errors Can you Detect?All 2-bit errorsExample:011010010110100000111 11101011001011101101000110 1error bitsodd number of 1’s on columns10Katz, Stoica F04How Many Errors Can you Detect?All 3-bit errorsExample:011010010110100000111 11001011001011101101000110 1error bitsodd number of 1’s on column11Katz, Stoica F04How Many Errors Can you Detect?Most 4-bit errorsExample of 4-bit error that is not detected:011010010110100000111 11001001001011101101000110 1error bitsHow many errors can you correct?12Katz, Stoica F04ChecksumSender: add all words of a packet and append the result (checksum) to the packetReceiver: add all words of a packet and compare the result with the checksumCan detect all 1-bit errorsExample: Internet checksum-Use 1’s complement addition13Katz, Stoica F041’s Complement RevisitedNegative number –x is x with all bits invertedWhen two numbers are added, the carry-on is added to the resultExample: -15 + 16; assume 8-bit representation15 = 00001111 -15 = 1111000016 = 00010000+00000000 1+100000001 -15+16 = 114Katz, Stoica F04Cyclic 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 + x0Choose a divisor k-degree polynomial C(x)Compute reminder R(x) of M(x)*xk / C(x), i.e., compute A(x) such thatM(x)*xk = A(x)*C(x) + R(x), where degree(R(x)) < kLet 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)15Katz, Stoica F04Cyclic 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 216Katz, Stoica F04Arithmetic Modulo 2Like binary arithmetic but without borrowing/carrying from/to adjacent bitsExamples: Addition and subtraction in binary arithmetic modulo 2 is equivalent to XOR101 +010111101 +0011001011 +011111001011 -01111100101 -010111101 -001100a b a b0 0 00 1 11 0 11 1 017Katz, Stoica F04Some 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 + x5 + x3 + x2 + x0 (10101101) C(x) = x3 + x1 + x0 (00001011) B(x) - C(x) = x7 + x5 + x2 + x1 (10100110)18Katz, Stoica F04Example (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)Compute T(x) = M(x)*xk - R(x) 11011100 xor 1 = 11011101Send T(x) 101) 11011100 101 111 101 101 101 100 101 1R(x)19Katz, Stoica F04Example (Receiver Operation)Assume T’(x) = 11011101 -C(x) divides T’(x) no errorsAssume T’(x) = 11001101-Reminder R’(x) = 1 error!101) 11001101 101 110 101 111 101 101 101 1R’(x)Note: an error is not detected iff C(x) divides T’(x) – T(x)20Katz, Stoica F04CRC PropertiesDetect all single-bit errors if coefficients of xk and x0 of C(x) are oneDetect all double-bit errors, if C(x) has a factor with at least three termsDetect all number of odd errors, if C(x) contains factor (x+1) Detect all burst of errors smaller than k bits21Katz, Stoica F04Code wordsCombination of the n payload bits and the k check bits as being a n+k bit code wordFor any error correcting scheme, not all n+k bit strings will be valid code wordsErrors 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 errors22Katz, Stoica F04Hamming DistanceGiven code words A and B, the Hamming distance between them is the number
View Full Document
Unlocking...