Note: We will start at 12:53 pm ET
à
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 1’s in error locations & 0’s 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 +1
ATM
CRC = cyclic redundancy check
= x32 +x26 +x23 +x22 +x16 +x12 +x11 +x10 +x8 +x7 +x5 +x4 +x2 +x+1
8
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
9
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
10
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
11
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
12
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
• 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 codeword
13
Physical Layer: Outline
• Digitalnetworks
• CharacterizationofCommunicationChannels • FundamentalLimitsinDigitalTransmission
• LineCoding
• ModemsandDigitalModulation
• ErrorDetectionandCorrection
• WiredPHY101
• WirelessPHY101
14
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 15
10
100
1000
analog telephone
for DSL
Attenuation (dB/mi)
Ethernet LANs
• Evolved from 10 -> 100 à 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
ìDl ü =nïí Dl1 ïý»nDl
100 50
10 5
1 0 . 5
0.1
l 1 ïî 1 +
l 1 ïþ 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
• Wirelessis“flaky”
– 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 (2Gà5G)
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”
èh ≈ y(t)/x(t)
But… what is the channel? • “Attenuation” & “Phase shift”
d
h = 1/d * ej2πd/λ
• Consistent with 1/d2 power fading
TX
RX
But… what is the channel? • “Attenuation” & “Phase shift”
d
h = 1/d * ej2πd/λ
• 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 j2πd/λ = 1/d * e j2πft
• d/λ = d*f/c = f*t, where “t” is signal time
TX
RX
How do channels capture
multipath?
d’
superposition
d
h = 1/d * ej2πd/λ + 1/d’ * ej2πd’/λ
Channels can combine differently on different frequencies
àChannels 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 antennasà2 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 antennasà2⇥ data: [y1 y2]
• nantennasàn⇥ 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 (2Gà5G)
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 user’s 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: Zoltán Turányi
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