程序代写代做代考 Week 3 – Data Link Layer COMP90007 Internet Technologies – cscodehelp代写

Week 3 – Data Link Layer COMP90007 Internet Technologies
Lecturer: Semester 2, 2021
© University of Melbourne 2021
1

Error Detection Codes
 Parity Bit (1 bit): (Hamming distance=2)  Internet Checksum (16 bits): (Hamming
distance=2)
 Cyclic Redundancy Check (CRC) (Standard 32-bit CRC: Hamming distance=4)
23

How it works?
 Sender: calculates R check bits using a function of data bits:
Codeword
 Receiver: receives the codeword and calculates the same function on the data and match the results with received check bits:
R=R’ ?
DATA
R=F(D)
DATA
R’
R=F(D)
24

Parity Bit
Given data 10001110, count the number of 1s Sender: Add parity bit  100011100 (for even parity)
100011101 (for odd parity) Receiver: Check the received data for errors.
Hamming distance is 2 for Parity Bit…
2 – 1 = 1 error bit can be detected and
(2 – 1) / 2 = 1⁄2 not even 1 bit error can be corrected
25

Internet Checksum
 There are different variations of checksum  Internet Checksum (16-bit word):
Sum modulo 216 and add any overflow of high order bits back into low-order bits
26

Example of Checksum
Calculate checksum (5-bit word) for data
00110 10001 11001 01011
1
00110
+10001 = 10111
The checksum is
one’s complement
of 11100 which is 00011
2 11001
+10111 = 10000 +1 = 10001
4
3
01011
+10001 = 11100
Data sent: 00110 10001 11001 01011 00011
27

Cyclic Redundancy Check
 Based on a generator polynomial G(x)
 e.g. G(x) = x4+x+1 (10011)
 Steps:
 LetrbethedegreeofG(x)(r=4).Appendrzerobitstothelow- order end of the frame so it now contains m + r bits and corresponds to the polynomial xrM(x).
 DividethebitstringcorrespondingtoG(x)intothebitstring corresponding to xrM(x), using modulo 2 division.
 Subtracttheremainder(whichisalwaysrorfewerbits)from the bit string corresponding to xrM(x) using modulo 2 subtraction.
 Theresultisthechecksummedframetobetransmitted.Callits polynomial T(x).
28

Example
Data: 1101001 and G(x) = x4+x+1 (10011)
5 bits polynomial add 4 bits as the checksum – so add 0000
10011 11010010000 10011
010010 10011
000011000 10011
010110 10011
00101
Data sent: 11010010101
29

Error Correction: Hamming Code
 n=2k-k-1 (n: number of data, k: check bits) Example: Data: 0101 – > requires 3 check bits
4 = (23) – 3 – 1
 Put check bits in positions p that are power of 2, starting with position 1
 Check bit in position p is parity of positions with a p term in their value
30

Example
 Data: 0101  requires 3 check bits Position
Data
1. Calculate the parity bits for P1, P2, P4 (rule: even parity)
P1 + P3 + P5 + P7 = ?+0+1+1 (even) P1 = 0 P2+P3+P6+P7=?+0+0+1(odd) P2=1 P4 + P5 + P6 + P7 = ?+1+0+1 (even) P4 = 0
Put check bits in positions p that are power of 2, starting with position 1
111
P1
P2
P3
P4
P5
P6
P7
?
?
0
?
1
0
1
Data sent: 0100101
Example 1: At the receiver: 0100100
P1 + P3 + P5 + P7 = 0+0+1+0= 1× P2 + P3 + P6 + P7 = 1+0+0+0= 1× P4 + P5 + P6 + P7 = 0+1+0+0= 1×
error
error Example 2: At the receiver: 0000101
P1 + P3 + P5 + P7 = 0+0+1+1= 0 P2 + P3 + P6 + P7 = 0+0+0+1= 1 × P4 + P5 + P6 + P7 = 0+1+0+1= 0
Error bit: P1, P2, P4P(1+2+4)=P7
Error bit: P2
31

Error Control Discussion
 Error Correction: More efficient in noisy transmission media e.g., wireless
 Error Detection: More efficient in the transmission media where low error rates occur, e.g. quality copper
 The error can occur in the check bits
 Require assumption on a specific number of errors occurring in transmission
32