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 +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-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, 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 à 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
Reviews
There are no reviews yet.