[SOLVED] 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 doesnt 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. 11001111 or 10101100
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.
Receivers clock must be synchronized with the senders 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 1s & 0s 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
Ifreceivedblockdoesntsatisfypattern,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? (Truea1, Falsea0)
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 1s =5, odd => Error detected
Iferrorsinbits3and5?(0,1,1,1,0,0,0,1) # of 1s =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 1s where errors occur and 0s elsewhere
Of 2k+1 binary (k+1)-tuples, 12 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))<1It follows that patterns with 1 error are more likely than patterns with 2 errorsand so forthWhat 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 =c2p (1- p) +c4p (1- p)+… Quiz! Whats the probability for n=32, p=10-3?e e32o -3 2 -3 30 32o -3 4 -3 28P[undetectableerror]=c2 (10 ) (1-10 ) +c4 (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 ooooxx Pooro x x x o o distanceoox x properties o o ox = valid codewords o = non-codewords Cxxox between valid codewords o o o ooxox o o oGood distance propertiesxox26Two-Dimensional Parity Check Moreparitybitstoimprovecoverage Arrangeinformationascolumns Addsingleparitybittoeachcolumn Addafinalparitycolumn Usedinearlyerrorcontrolsystems 100100 010001 100100 110110 100111Last column consists of check bits for each row Bottom row consists of check bit for each column27Error-detecting capability 100100 000001detectforce100100 000001100100 100110detect only Two errors 0One errorO 100100 110110 100111O 100100 000f101 100100dqeyThree errors100111100100 000101 100100 100010 100111Four errors110 100111shaped rectangler detectcantbe1000Arrows indicate failed check bitserror 281, 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 ones 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 1s 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 1s in error locations & 0s 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 +1ATMCRC = cyclic redundancy check= x32 +x26 +x23 +x22 +x16 +x12 +x11 +x10 +x8 +x7 +x5 +x4 +x2 +x+143BisyncHDLC, XMODEM, V.41 IEEE 802, DoD, V.42Hamming Codes Classoferror-correctingcodes Capableofcorrectingallsingle-errorpatterns Provablyoptimalfor1-biterrors Verylessredundancy,e.g.1-biterrorproofadds 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, b7b =b +b +b 51 34b=b+b +b 612 4b7 = +b2 +b3 +b4 There are 24=16 codewords (0,0,0,0,0,0,0) is a codeword 45 My simple proof of optimalityCaseb5 matchb6 matchb7 matchNo errorb1 flippedb2 flippedb3 flippedb4 flippedb5 flippedb6 flippedb7 flippedAssume you got the following 7 bit sequences and make the following checks:b =b +b +b 51 34b=b+b +b 612 4b7 = +b2 +b3 +b446 My simple proof of optimalityCaseb5 matchb6 matchb7 matchNo 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 34b=b+b +b 612 4b7 = +b2 +b3 +b447 Why is Hamming a good code?Set of n- tuples within distance 1 of b1ob Distance31 o oooSet of n- tuples within distance 1 of b2 ob o 2o 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 49Twisted Pair Two insulated copperwires arranged in a regularspiral pattern to minimize interference 2426 gauge24 gauge22 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 desktop3018 12 61f (kHz) Lower attenuation rate forHigher Attenuation rate 50101001000 analog telephonefor 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
iDl u =nii Dl1 iynDl
l 1 ii 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

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