CS代考计算机代写 ER algorithm Note: We will start at 12:53 pm ET

Note: We will start at 12:53 pm ET
à

18-441/741: Computer Networks Lecture 5: Physical Layer III
Swarun Kumar
2

Physical Layer: Outline
• Digitalnetworks
• CharacterizationofCommunicationChannels • FundamentalLimitsinDigitalTransmission
• ModemsandDigitalModulation
• LineCoding
• ErrorDetectionandCorrection
• WiredPHY101(iftimepermits)
• WirelessPHY101
3

From Signals to Packets
Analog Signal
“Digital” Signal
BitStream 00101110001
Packets
Packet Transmission
0100010101011100101010101011101110000001111010101110101010101101011010111001
Header/Body
Sender
Header/Body
Header/Body
Receiver
4

• Synchronization of clocks in transmitters and receivers.
– clockdriftcausesa loss of synchronization
• Example: assume ‘1’ and ‘0’ are
represented by V volts and 0 volts respectively
– Correctreception
– Incorrectreception due to slow clock at the receiver
10110100100
Synchronization
Data
T
S
clock
10111001000 Data
T
clock
S’
5

Synchronization (cont’)
• How to avoid a loss of synchronization? – Asynchronous transmission
– Synchronous transmission
6

•
Asynchronous Transmission
Avoids synchronization loss by
– specifying a short maximum length for the bit sequences (so that clock doesn’t drift much within sequence)
– and resetting the clock in the beginning of each bit sequence (by using a ‘start bit’)
Accuracy of the clock?
Bit sequence (n) Bit sequence (n+1) 1011 1011
Data
T clock
S
•
7

Asynchronous transmission: ASCII code
• ASCII(AmericanNationalStandardCodefor Information Interchange) code
– 7 bits to represent 128 letters, symbols, and control characters. (i.e. A=‘1000001’, CR(Carriage Return)=‘0001101’ )
– Asynchronous transmission sends sequences of 8 bits=one start bit + 7 ASCII bits.
– some systems add one parity bit to make number of ‘1’ to be even number
– i.e. ‘1100111’1 or ‘1010110’0
8

Synchronous Transmission
• Overcomestheinefficiencyofasynchronous transmission.
• Improvesefficiencybytransmittinglonger sequences of bits, called packets (variable length).
• Requiresextrainformationtoindicatetheend of the packet.
voltage 100011010
tim e
9

Encoding
• Encodingconvertsabinaryinformation sequence into a digital signal
– Sender then uses the digital signal to modulate the signal in a way that the receiver can recognize
• Encodingcanbedoneonebitatatimeorin blocks of multiple bits called a symbol
– Example: a symbol with 8 values means that 3 bits are sent in each time slot
• Transmissionissynchronous,i.e.,aclockis used to sample the signal.
– Receiver’s clock must be synchronized with the sender’s clock
10

Why Do We Need Encoding?
• Tomeetscertainelectricalconstraints. – Many of them! See next slide
• Createscontrolsymbols,besidesregular
data symbols. I
– E.g. start or end of frame, escape, …
cannotappearin data • Candoerrordetectionorerrorcorrection
– Some codes are illegal so receiver can detect certain classes of errors
– Minor errors can be corrected by having multiple adjacent signals mapped to the same data symbol
11

Unipolar NRZ
Polar NRZ
NRZ-inverted (differential encoding)
Bipolar encoding
Manchester encoding
Differential Manchester encoding
Line coding examples
5101011100 O
thready
25
25
Tapip
l
any
12

•
Spectrum of Line codes
Assume 1’s & 0’s independent & equiprobable
1.2
1 NRZ
0.8 0.6 0.4 0.2
0 -0.2
Bipolar
• NRZ has high content at low frequencies
• Bipolar tightly packed around 1/2T
• Manchester wasteful of bandwidth
Manchester
fT
13
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
pow er density

mB/nB Encoding nem
• m data bits are coded as symbols of n line bits
• Example: FDDI uses 4B5B
– 4 data bits for 5 line bits, so 100 Mbps uses 125 MHz. – Uses less frequency than Manchester encoding (1B2B)
• Each valid symbol has at least two 1s: get dense transitions.
• 16 data symbols, 8 control symbols – Data symbols: 4 data bits
– Control symbols: idle, begin frame, etc.
• Also: 8B10B (Gigabit Ethernet, Fiber channel) and 64B66B code (10G Ethernet)
14

4B/5B Encoding
Data Code
0000 11110
0001 01001
0010 10100
0011 10101
0100 01010
0101 01011
0110 01110
0111 01111
Data Code
1000 10010 1001 10011 1010 10110 1011 10111 1100 11010 1101 11011 1110 11100 1111 11101
15

Quiz Question
• The following are notable absentees in 4B/5B encoding.. Why?
– 00000 – 00001 – 11111 – 10001
ØNeed transitions NO transitions ØNeed at least two ones
ØNeed transitions
ØControl symbol! (start delimiter)
16

Physical Layer: Outline
• Digitalnetworks
• CharacterizationofCommunicationChannels • FundamentalLimitsinDigitalTransmission
• LineCoding
• ModemsandDigitalModulation
• ErrorDetectionandCorrection
• WiredPHY101
• WirelessPHY101
17

Error Control
• Channels introduce errors in digital communications
• Applications require certain reliability level
– Data applications require error-free transfer
– Voice & video applications tolerate some errors
• Error control may be needed to meet application requirement
• Error control ensures a data stream is transmitted to a certain level of accuracy despite errors
• Two basic approaches:
– Error detection & retransmission (ARQ) – Forward error correction (FEC)
18

Key Idea
• Alltransmitteddatablocks(“codewords”)are chosen so that they satisfy a pattern
• Ifreceivedblockdoesn’tsatisfypattern,itisin error
• Redundancy: Only a subset of all possible blocks can be valid codewords
• Undetectable Error: When channel transforms a codeword into another valid codeword
User information
Deliver user information or set error alarm
All inputs to channel satisfy pattern or condition
Channel output
Encoder
Channel
Pattern checking
19

Single Parity Check
• Appendanparitybittokinformationbits
Info Bits:
Check Bit: Codeword:
b1, b2, b3, …, bk
bk+1= b1+ b2+ b3+ …+ bk modulo 2 (b1, b2, b3, …, bk,, bk+1)
1st
i
• Allcodewordshaveeven#of1s
• Receivercheckstoseeif#of1siseven
– All error patterns that create an odd # of 1 bits are detectable
– All even-numbered error patterns are undetectable
• ASCIIcodeispreciselysuchascode(7+1bits)
20

Quiz Question: Single Parity Code
• Information (7 bits): (0, 1, 0, 1, 1, 0, 0) • Parity Bit? (“True”à1, ”False”à0)
b8 =0+1+0+1+1+0=1
Codeword (8 bits): (0, 1, 0, 1, 1, 0, 0, 1)
• Ifsingleerrorinbit3?(0,1,1,1,1,0,0,1) – # of 1’s =5, odd => Error detected
• Iferrorsinbits3and5?(0,1,1,1,0,0,0,1) – # of 1’s =4, even => Error not detected
21

Parity Checkbits & Error Detection
Information bits
k bits
Sent check bits
n – k bits
Received information bits
Recalculate check bits
Calculate check bits
Channel
Compare
Received check bits
Information accepted if check bits match
22

How good is the single parity check code?
• Redundancy: Single parity check code adds 1 redundant bit per k information bits: overhead = 1/(k+1)
• Coverage: all error patterns with odd # of
errors can be detected
– An error pattern is a binary (k+1)-tuple with 1’s where errors occur and 0’s elsewhere
– Of 2k+1 binary (k+1)-tuples, 1⁄2 are odd, so 50% of error patterns can be detected
• Isitpossibletodetectmoreerrorsifweadd more check bits?
• Yes,withtherightcodes
23

• •
What if bit errors are random?
Many transmission channels introduce bit errors at random, independently of each other, and with probability p
Some error patterns are more probable than others:
P[10000000]=p(1-p)7=(1-p)8( p )and 1- p
P[11000000]=p2(1-p)6 =(1-p)8( p )2 1- p
Inanyworthwhilechann0elp<0.5,andso(p/(1-p))<1 It follows that patterns with 1 error are more likely than patterns with 2 errors and so forth What is the probability that an undetectable error pattern occurs? • • • 24 Single parity check code with random bit errors • Undetectableerrorpatternifeven#ofbiterrors: P[error detection failure] = P[undetectable error pattern] = P[error patterns with even number of 1s] ænö 2 n-2 ænö 4 n-4 =ç2÷p (1- p) +ç4÷p (1- p) +... • Quiz! What’s the probability for n=32, p=10-3? èø èø æ32ö -3 2 -3 30 æ32ö -3 4 -3 28 P[undetectableerror]=ç2 ÷(10 ) (1-10 ) +ç4 ÷(10 ) (1-10 ) èø èø » 496 (10-6 ) + 35960(10-12 ) » 4.96(10-4 ) • Forthisexample,roughly1in2000 transmissions will result in an undetectable error 25 What is a good code? • Most channels will have relatively few bit errors • Erroneouscodewords transmitted over those channels will map to nearby n-tuples • If valid codewords are close to each other, then detection failures may occur • Good codes should the minimum maximize separation oooo xx Poor o x x x o o distance o o x x properties o o o x = valid codewords o = non-codewords Cxxox between valid codewords o o o o o x o x o o o Good distance properties xox 26 Two-Dimensional Parity Check • Moreparitybitstoimprovecoverage • Arrangeinformationascolumns • Addsingleparitybittoeachcolumn • Addafinal“parity”column • Usedinearlyerrorcontrolsystems 100100 010001 100100 110110 100111 Last column consists of check bits for each row Bottom row consists of check bit for each column 27 Error-detecting capability 100100 000001 detect force 100100 000001 100100 100110 detect only Two errors 0 One error O 100100 110110 100111 O 100100 000f101 100100 dqey Three errors 100111 100100 000101 100100 100010 100111 Four errors 110 100111 shaped rectangler detect cantbe 100 0 Arrows indicate failed check bits error 28 1, 2, or 3 errors can always be detected; Not all patterns >4 errors can be detected

Other Error Detection Codes
• Manyapplicationsrequireverylowerrorrate
• Needcodesthatdetectmorenumberoferrors
• Singleparitycheckcodesdonotdetectenough errors
• Two-dimensionalcodesrequiretoomanycheck bits
• Thefollowingerrordetectingcodesarewidely used in practice:
– Internet Check Sums
– CRC Polynomial Codes
29

Internet Checksum
• Several Internet protocols (e.g. IP , TCP , UDP) use check bits to detect errors in the header
• Achecksumiscalculatedforheadercontentsand included in a special field.
• Checksumispotentiallyrecalculatedatevery router, so algorithm selected for ease of implementation in software
• LetheaderconsistofL,16-bitwords, b0, b1, b2, …, bL-1
• Thealgorithmappendsa16-bitchecksumbL
30

Checksum Calculation
The checksum bL is calculated as follows:
• Treatingeach16-bitwordasaninteger,find
x = b0 + b1 + b2+ …+ bL-1 modulo 216-1 • Thechecksumisthengivenby:
bL = – x modulo 216-1
Thus, the headers must satisfy the following pattern
at the receiver:
0=b0 + b1 + b2+ …+ bL-1+ bL modulo216-1
• The checksum calculation is carried out in software using one’s complement arithmetic
31

Internet Checksum Example
Use Modulo Arithmetic
• Assume4-bitwords
• Usemod24-1(=15) arithmetic
• b0=1100=12
• b1=1010 = 10
• b0+b1=12+10=7mod15
Use Binary Arithmetic
• Note 16 =1 mod15
• So:10000=0001 mod15
• leadingbitwraps around
O
b +b 01
=1100+1010 =10110 =10000+0110 =0001+0110 =0111
• b2=-7=8mod15
• Therefore
• b2=10O00
=7
Take 1’s complement
b2 = -0111 =1000 32

Polynomial Codes
• Polynomialsinsteadofvectorsforcodewords
• Polynomialarithmeticinsteadofchecksums
• Implementedusingshift-registercircuits
• Alsocalledcyclicredundancycheck(CRC)
• Mostdatacommunicationsstandardsuse polynomial codes for error detection
– Have very simple hardware implementations
• Polynomialcodesalsobasisforpowerful error-correction methods
33

Binary Polynomial Arithmetic
• Binaryvectorsmaptopolynomials
(i ,i ,…,i ,i,i )®i xk-1 +i xk-2 +…+i x2 +ix1 +i k-1k-2210k-1k-2 210
Addition:
(x7 +x6 +1)+(x6 +x5)=x7 +x6 +x6 +x5 +1 =x7 +(1+1)x6 +x5 +1
Multiplication:
=x7+x5+1since 1+1=0mod2
(x+1)(x2 +x+1)=x(x2 +x+1)+1(x2 +x+1) =(x3 +x2 +x)+(x2 +x+1)
= x3 +1
34

Binary Polynomial Division
• DivisionwithDecimalNumbers
34 quotient
dividend = quotient x divisor + remainder 1222 = 34 x 35 + 32 x3tx
35 ) 1222 105
dividend remainder
divisor
32
• Polynomial Division
divisor
Note: Degree of r(x) is less than degree of divisor
172 140
xlix11161 5 x3btx4
= q(x) quotient 71512141 3 x5 txt
dividend t not
x3 + x2 + x x3+x+1)x6+x5
x6 +
x5 + x4 + x3
x4 + x3
x5 +
x3 + x2 x2
x2 + x x
x4 + x4 +
= r(x) remainder
35

Polynomial Coding
• kinformationbitsdefinepolynomialofdegreek-1
i(x)=i xk-1+i xk-2+…+ix2+ix+i k-1k-2 210
• Codehasbinarygeneratingpolynomialofdegreen-k g(x)=xn-k +gn-k-1xn-k-1 +…+g2x2 +g1x+1
• Findremainderpolynomialofatmostdegreen-k-1 q(x)
n-k xn-ki(x) = q(x)g(x) + r(x) g(x) ) x i(x)
s
r(x)
• Definethecodewordpolynomialofdegreen-1
is
b(x) = xn-ki(x) + r(x)
n bits
k bits n-k bits
36

Quiz Q: Find codeword if k=4, n-k0=3
And: Generator polynomial: g(x)= x3 + x + 1 Information: (1,1,0,0) i(x) = x3 + x2 Encoding: x3i(x) = x6 + x5
37

Quiz Q: Find codeword if k=4, n-k=3
And: Generator polynomial: g(x)= x3 + x + 1
Information: (1,1,0,0) Encoding: x3i(x) = x6 + x5
x3 + x2 + x
i(x) = x3 + x2
x3 + x + 1 ) x6 + x5 x6 +
x4 + x3
x5 + x4 + x3
x5 +
x4 +
x4 +
x3 + x2
x2
x2 + x
x
38

Quiz Q: Find codeword if k=4, n-k=3
And: Generator polynomial: g(x)= x3 + x + 1
Information: (1,1,0,0) Encoding: x3i(x) = x6 + x5
x3 + x2 + x
i(x) = x3 + x2
x3 + x + 1 ) x6 + x5 x6 +
1110
x4 + x3
1011 ) 1100000
1011
1110
1011
1010
1011
010
x5 + x4 + x3
x5 +
x4 +
x4 +
x3 + x2
x2
x2 + x
x
Transmitted codeword:
b(x)=x6 +x5+x b = (1,1,0,0,0,1,0)
39

The Pattern in Polynomial Coding • Allcodewordssatisfythefollowingpattern:
b(x) = xn-ki(x) + r(x) = q(x)g(x) + r(x) + r(x) = q(x)g(x)
• Allcodewordsareamultipleofg(x)!
• Receivershoulddividereceivedn-tuplebyg(x) and check if remainder is zero
• Ifremainderisnon-zero,thenreceivedn-tupleis not a codeword
40

Undetectable error patterns
(Transmitter) (Receiver)
b(x) + R(x)=b(x)+e(x)
e(x) Error polynomial
• e(x) has 1’s in error locations & 0’s elsewhere
• Receiver divides the received polynomial R(x) by g(x)
• Undetectable error: If e(x) is a multiple of g(x), that is, e(x) is a non-zero codeword, then
R(x) = b(x) + e(x) = q(x)g(x) + q’(x)g(x)
• The set of undetectable error polynomials is the set of nonzero code polynomials
• Choose the generator polynomial so that selected error patterns can be detected.
(Channel)
41

Designing good polynomial codes
• Select generator polynomial so that likely error patterns are not multiples of g(x)
• Detecting Single Errors
– e(x) = xi for error in location i+1
– If g(x) has more than 1 term, it cannot divide xi
• Detecting Double Errors
– e(x) = xi + xj = xi(xj-i+1) where j>i
– If g(x) has more than 1 term, it cannot divide xi
– If g(x) is a primitive polynomial, it cannot divide xm+1 for all m<2n-k -1 (Need to keep codeword length less than 2n-k -1) – Primitive polynomials can be found by consulting coding theory books 42 Standard Generator Polynomials • CRC-8: • CRC-16: • CCITT-16: • CCITT-32: =x8 +x2 +x+1 = x16 + x15 + x2 +1 = ( x + 1 )( x 1 5 + x + 1) = x16 + x12 + x5 +1 ATM CRC = cyclic redundancy check = x32 +x26 +x23 +x22 +x16 +x12 +x11 +x10 +x8 +x7 +x5 +x4 +x2 +x+1 43 Bisync HDLC, XMODEM, V.41 IEEE 802, DoD, V.42 Hamming Codes • Classoferror-correctingcodes • Capableofcorrectingallsingle-errorpatterns • Provablyoptimalfor1-biterrors • Verylessredundancy,e.g.1-biterrorproof–adds O(log n) bits of redundancy for n bit sequences 44 m=3 Hamming Code • Information bits are b1, b2, b3, b4 • Equations for parity checks b5, b6, b7 b =b +b +b 51 34 b=b+b +b 612 4 b7 = +b2 +b3 +b4 • There are 24=16 codewords • (0,0,0,0,0,0,0) is a codeword 45 My ”simple” proof of optimality Case b5 match b6 match b7 match No error b1 flipped b2 flipped b3 flipped b4 flipped b5 flipped b6 flipped b7 flipped Assume you got the following 7 bit sequences and make the following checks: b =b +b +b 51 34 b=b+b +b 612 4 b7 = +b2 +b3 +b4 46 My ”simple” proof of optimality Case b5 match b6 match b7 match No error ✔ ✔ ✔ b1 flipped ! ! ✔ b2 flipped ✔ ! ! b3 flipped ! ✔ ! b4 flipped ! ! ! b5 flipped ! ✔ ✔ b6 flipped ✔ ! ✔ b7 flipped ✔ ✔ ! Assume you got the following 7 bit sequences and make the following checks: b =b +b +b 51 34 b=b+b +b 612 4 b7 = +b2 +b3 +b4 47 Why is Hamming a “good code”? Set of n- tuples within distance 1 of b1 o b Distance3 1 o o o o Set of n- tuples within distance 1 of b2 o b o 2 o • Two valid bit sequences have a minimum distance of 3 bit flips • Spheres of distance 1 around each codeword do not overlap • If a single error occurs, the resulting n-tuple will be in a unique sphere around the original codeword • Thus, receiver can correct erroneous reception back to original codeword 48 Physical Layer: Outline • Digitalnetworks • CharacterizationofCommunicationChannels • FundamentalLimitsinDigitalTransmission • LineCoding • ModemsandDigitalModulation • ErrorDetectionandCorrection • WiredPHY101 • WirelessPHY101 49 Twisted Pair • Two insulated copper wires arranged in a regular spiral pattern to minimize interference 24 26 gauge 24 gauge 22 gauge 19 gauge • Various thicknesses, e.g. 0.016 inch (24 gauge) • Low cost • Telephone subscriber loop from customer to CO • Old trunk plant connecting telephone COs • Intra-building telephone from wiring closet to desktop 30 18 12 6 1 f (kHz) Lower attenuation rate for Higher Attenuation rate 50 10 100 1000 analog telephone for DSL Attenuation (dB/mi) Ethernet LANs • Evolved from 10 -> 100 à 1000 Mbps to now 10Gbps
• All use twisted pair in some form!
• 10BASE-T Ethernet
– 10 Mbps, Baseband, Twisted pair
– Two Cat3 pairs
– Manchester coding, 100 meters
• 100BASE-T4 Fast Ethernet
– 100 Mbps, Baseband, Twisted pair
– Four Cat3 pairs
– Three pairs for one direction at-a-time
– 100/3 Mbps per pair;
– 3B6T line code, 100 meters
• 1000BASE-T
– 8b10bencoding,Fourpairs 51
llllll

Optical Fiber
Electrical Optical fiber Receiver Electrical
Modulator
signal
signal
Optical source
• Light sources (lasers, LEDs) generate pulses of light that are transmitted on optical fiber
– Very long distances (>1000 km)
– Very high speeds (>40 Gbps/wavelength)
– Nearly error-free (BER of 10-15)
• Profound influence on network architecture
– Dominates long distance transmission
– Distance less of a cost factor in communications
– Plentiful bandwidth for new services
52

Transmission in Optical Fiber
Geometry of optical fiber
Light
Cladding Core
Jacket
Total Internal Reflection in optical fiber
qc
• Very fine glass cylindrical core surrounded by concentric layer of glass (cladding)
• Core has higher index of refraction than cladding
• Light rays incident at less than critical angle qc is completely reflected back into the core
53

Multimode & Single-mode Fiber
Multimode fiber: multiple rays follow different paths
Reflected path Direct path
Single-mode fiber: only direct path propagates in fiber
• Multi Mode: Thicker core, shorter reach
– Rays on different paths interfere causing dispersion & limiting bit rate
• Single Mode: Very thin core supports only one mode (path) • More expensive lasers, but achieves very high speeds
54

Huge Available Bandwidth
• Optical range from l1 to l1+Dl contains bandwidth
B=f1-f2=n- n
l1 l1 +Dl
ìDl ü =nïí Dl1 ïý»nDl
l 1 ïî 1 + l 1 ïþ l 12
100 50
10 5
1 0 . 5
0.1
0.8 1.0
1.2 1.4 1.6 1.8
55
Loss (dB/km)

Quiz Question
How much optical fiber bandwidth is available between: l1 = 1450 nm and l1+Dl =1650 nm:
Answer: B = 2(108 )m/s 200nm » 19 THz (1450nm)2
56

Wavelength-Division Multiplexing
• Different wavelengths carry separate signals
• Multiplex into shared optical fiber
• Each wavelength like a separate circuit
• A single fiber can carry 160 wavelengths, 10 Gbps
per wavelength: 1.6 Tbps!
l1 l2
lm
optical mux
l1 l2. lm
optical fiber
optical demux
l1 l2
lm
57

• •
How Do We Extend Range
Use combinations of optical amplifiers and regenerators
More amplifiers than regenerators (why?)
RR
…
………… OA OA R OA OA R
Optical amplifier
R
R
R
R
58

Related Posts