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

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