New version page

Berkeley ELENG 122 - Error Detection and Reliable Transmission

Documents in this Course
Lecture 6

Lecture 6

22 pages

Wireless

Wireless

16 pages

Links

Links

21 pages

Ethernet

Ethernet

10 pages

routing

routing

11 pages

Links

Links

7 pages

Switches

Switches

30 pages

Multicast

Multicast

36 pages

Switches

Switches

18 pages

Security

Security

16 pages

Switches

Switches

18 pages

Lecture 1

Lecture 1

56 pages

OPNET

OPNET

5 pages

Lecture 4

Lecture 4

16 pages

Ethernet

Ethernet

65 pages

Models

Models

30 pages

TCP

TCP

16 pages

Wireless

Wireless

48 pages

Load more
Upgrade to remove ads

This preview shows page 1-2-17-18-19-36-37 out of 37 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

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 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 this5Katz, Stoica F04OverviewError detection & recoveryReliable Transmission6Katz, Stoica F04Error 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 Codes7Katz, Stoica F04Two-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 01101001011010001011011101011001011101101000110 18Katz, Stoica F04How Many Errors Can you Detect?All 1-bit errorsExample:01101001011010000011011101011001011101101000110 1error bitodd number of 1’s9Katz, Stoica F04How Many Errors Can you Detect?All 2-bit errorsExample:011010010110100000111 11101011001011101101000110 1error bitsodd number of 1’s on columns10Katz, Stoica F04How Many Errors Can you Detect?All 3-bit errorsExample:011010010110100000111 11001011001011101101000110 1error bitsodd number of 1’s on column11Katz, Stoica F04How Many Errors Can you Detect?Most 4-bit errorsExample of 4-bit error that is not detected:011010010110100000111 11001001001011101101000110 1error bitsHow many errors can you correct?12Katz, Stoica F04Checksum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 addition13Katz, Stoica F041’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 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 + 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 thatM(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)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 2Like binary arithmetic but without borrowing/carrying from/to adjacent bitsExamples: 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 = 11011101Send 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 errorsAssume 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 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 bits21Katz, Stoica F04Code 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 errors22Katz, Stoica F04Hamming DistanceGiven code words A and B, the Hamming distance between them is the number


View Full Document
Download Error Detection and Reliable Transmission
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Error Detection and Reliable Transmission and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Error Detection and Reliable Transmission 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?