[SOLVED] CS 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 6: Physical Layer IV
Swarun Kumar
2

Physical Layer: Outline
Digitalnetworks
CharacterizationofCommunicationChannels FundamentalLimitsinDigitalTransmission
LineCoding
ModemsandDigitalModulation
ErrorDetectionandCorrection(cotd.)
WiredPHY101
WirelessPHY101
3

Recap: CRC = Polynomial Codes
Do Long Division on (mod 2) polynomials
Let i(x) denote information bits in polynomial form
Then:
q(x)
g(x) ) xn-ki(x)
Add
r(x)
Codeword xn-ki(x) + r(x)
4

The Pattern in Polynomial Coding Allcodewordssatisfythefollowingpattern:
in modular
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
K
5

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)
(Channel)
Undetectable error: If e(x) is a multiple of g(x), that is, c
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.
6

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 mm
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 7 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+18BisyncHDLC, XMODEM, V.41 IEEE 802, DoD, V.42 Hamming Codes Classoferror-correctingcodes Capableofcorrectingallsingle-errorpatterns Provablyoptimalfor1-biterrors Verylessredundancy,e.g.1-biterrorproofadds O(log n) bits of redundancy for n bit sequences 9 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 10 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 +b411 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 +b412 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 TwOovalidbitsequenceshaveaminimumdistanceof3bitflips 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 codeword13 Physical Layer: Outline Digitalnetworks CharacterizationofCommunicationChannels FundamentalLimitsinDigitalTransmission LineCoding ModemsandDigitalModulation ErrorDetectionandCorrection WiredPHY101 WirelessPHY101 14Twisted 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 15101001000 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 16
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
17

Transmission in Optical Fiber
Geometry of optical fiber
Light
Cladding Core
dont fold 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
18

Multimode & Single-mode Fiber
Multimode fiber: multiple rays follow different paths
Reflected path Direct path
Single-mOode 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
19

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
100 50
10 5
1 0 . 5
0.1
l 1 ii 1 +
l 1 i l 12
lights has in
not
c
why v
digspeed
0.8 1.0
1.2 1.4 1.6 1.8
dirty medium
20
Loss (dB/km)

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

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
22

How Do We Extend Range
Use combinations of optical amplifiers and regenerators
More amplifiers than regenerators (why?)
4
cheaper
RR

OA OA R OA OA R
Optical amplifier
R
R
R
R
23

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

Wireless vs. Wired
Wirelessisflaky
Environment, people, mobility affects signals
Wirelessisabroadcastmedium Collisions!
Interference Noise
Wirelessishalf-duplex
Only transmit or receive.. Not both
25

Outline Wireless
WiFiPHY
Wireless channel
OFDM
Multiple antennas (MIMO)
Cellular Whirlwind (2Ga5G)
26

But hey, we already know Wi-Fi
(Noisy) Wireless Channel
27

x
Wireless signals: Basic Equation
In narrowband:
h
y
TX
RX

But in the real world
TX
RX
Multipath
29

More generally:
delay
Wireless signals

Wireless signals
But time is continuous!
son

Challenges: How do I estimate h?
Send known x(t) as preamble
eh y(t)/x(t)

But what is the channel? Attenuation & Phase shift
d
h = 1/d * ej2d/
Consistent with 1/d2 power fading
TX
RX

But what is the channel? Attenuation & Phase shift
d
h = 1/d * ej2d/
d/ = d*f/c = f*t, where t is signal time
TX
RX

But what is the channel? Attenuation & Phase shift
d
h = 1/d * e j2d/ = 1/d * e j2ft
d/ = d*f/c = f*t, where t is signal time
TX
RX

How do channels capture
multipath?
d
superposition
d
h = 1/d * ej2d/ + 1/d * ej2d/
Channels can combine differently on different frequencies
aChannels are frequencTy-selective
TX
RX

Challenge: Frequency Selective
Fading
Fourier

FDM
Frequency Division Multiplexing
Divide bandwidth into small chunks: subcarriers
It
gaps But so much waste!

OFDM
Orthogonal Frequency Division Multiplexing
Get rid of guard bands by orthogonal frequency division

OFDM
Orthogonal Frequency Division Multiplexing
WiFi, LTE uses OFDM!

MIMO multiple input
Why so many antennas? multiple output
41

singlein single out Recap: SISO PHY
Our discussion so far had single antenna transmitters and receivers
Single Input Single Output
TX
RX

SISO: Channel Model
(Assuming narrowband)
y = hx + n

MIMO
Multiple Input Multiple Output
2 x More antennasa2 x More data
TX
RX

x1 x2
h11 h12
y1 y2
TX
MIMO
y1 = h11x1 + h21x2 y2 = h12x1 + h22x2
h21 h22
RX

x1 x2
h11 h12
h22
How do you solve?
y1 y2
MIMO
y1 =h11 h21 x1 y2 h12h22 x2
TX
h21
RX

x1 x2
h11 h12
y1 y2
MIMO
x1 =h11 h21 1y1 x2 h12 h22 y2
TX
h21 h22
RX

Estimating Channels
Preamble 1
Preamble 2
Data
h11 h21 Measure on Antenna 1 h12 h22 Measure on Antenna 2

Gains of MIMO
2 antennasa2 data: [y1 y2]
nantennasan moredata Assumption: H is invertible

Quiz Question
Which of these has a gain (in Shannon Capacity) that is identical to that of doubling the number of antennas available on your wireless transmitter & receiver:
[B] Doubling Signal Power [C] Doubling Noise Power [D] Halving Noise Power
New Shannon Formula: C = n B log(1+SNR)
O
[A] Doubling Bandwidth
F
bag
50

Outline Wireless
WiFiPHY
Wireless channel
OFDM
Multiple antennas (MIMO)
Cellular Whirlwind (2Ga5G)
51

The Advent of Cellular Networks
Mobile radio telephone system was based on: High power transmitter/receivers
Could support about 25 channels inaradiusof~80Km
To increase network capacity:
Multiple low-power transmitters (100W or less)
Small transmission radius -> area split in cells
Each cell with its own frequencies and base station
Adjacent cells use different frequencies
The same frequency can be reused at sufficient distance

Cellular Network Design Options
Simplestlayout
Adjacent antennas not equidistant how do you handle users at the edge of the cell?
Ideallayout
But we know signals travel whatever way they feel like
d
2d
d
d
d

The Hexagonal Pattern
A hexagon pattern can provide equidistant access to neighboring cell towers
Used as the basis for planning
d=3R
In practice, variations from ideal due to topological reasons
Signal propagation Tower placement
d
R

Cell sectoring
Celldividedintowedgeshapedsectors
3-6sectorspercell,eachwithownchannels Useofdirectionalantennas
Evenmoremessywithsmall+bigcells!

Cellular Standards
1Gsystems:analogvoice
Not unlike a wired voice line (without the wire)
2Gsystems:digitalvoice
Many standards
Example: GSM FDMA/TDMA, most widely deployed, 200 countries, a billion people
2.5Gsystems:voiceanddatachannels
Example: GPRS evolved from GSM, packet- switched, 170 kbps (30-70 in practice)

Cellular Standards
3G:voice(circuit-switched)anddata(packet- switched)
Several standards
Uses Code Division Multiple Access (CDMA) UMTS
4G:10Mbpsandup,seamlessmobility between different cellular technologies
LTE the dominating technology
Packet switched (took them so long!)
5G:mm-wave,morebandwidth,massiveMIMO

Time
Pilot sub-carriers
LTE in a Nutshell: Essentially OFDM
Each color represents a user
Each user is assigned a frequency- time tile which consists of pilot sub-
carriers and data sub-carriers
Block hopping of each users tile for
frequency diversity
Frequency
Courtesy: Harish Vishwanath
58

LTE in a Nutshell: Or rather, OFDM-A!
Call a chunk of subcarrier-time resource blocks
Assign each user a chunk of resource blocks coordinated by the cell tower
User #1 scheduled User #2 scheduled
data1 data2 data3 data4
Time-frequency fading, user #2 Time-frequency fading, user #1
1 ms
Time
Frequency 180 kHz
Courtesy: Zoltan Turanyi
59

5G in one slide(!)
LTE bandwidths (in US) ~ 10-20 MHz
5G plays three games to increase based on C = n B log(1+S(I)NR)
Increase n: Massive MIMO
Increase B (option 1): mm-wave frequencies
Increase B (option 2): buy more spectrum (costs $$) Reduce I: smaller cells (femto cells)
Only major change to PHY: allow subcarrier width to change (fixed in LTE), otherwise mostly same as LTE (still uses OFDMA, etc.)
60