EE122 Encoding Framing November 17 2003 Katz Stoica F04 EECS 122 Introduction to Computer Networks Encoding and Framing Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 Today s Lecture 23 2 17 18 6 19 20 10 11 7 8 9 Application 14 15 16 21 22 24 23 Transport Network IP Link Physical Katz Stoica F04 3 Questions Why are some links faster than others What limits the amount of information we can send on a link How can we increase the capacity of a link Katz Stoica F04 4 Signals Analog vs Digital Signal a function s t that varies with time t stands for time Analog varies continuously Example voltage representing audio analog phone call Digital discrete values varies abruptly Example voltage representing 0s an 1s Katz Stoica F04 5 Signals Periodic vs Aperiodic Period repeat over and over again once per period Signal strength Period T is the time it takes to make one complete cycle Frequency f is the inverse of period f 1 T measured in hz T 1 f Aperiodic don t repeat according to any particular pattern Katz Stoica F04 6 Data vs Signal data signal data communication medium signal data Analog Telephone Analog Digital Modem Analog Analog CODEC Digital Digital Digital Transmitter Digital Katz Stoica F04 7 Attenuation Links become slower with distance because of signal attenuation Amplifiers and repeaters can help Katz Stoica F04 8 Noise A signal s t sent over a link is generally Distorted by the physical nature of the medium This distortion may be known and reversible at the receiver Affected by random physical effects n t noise Fading Multipath effects s t r t transmitted signal received signal Also interference from other links link Wireless Crosstalk Dealing with noise is what communications engineers do Katz Stoica F04 9 Noise Limits the Link Rate Suppose there were no noise Then if send s t always receive s t Take a message of N bits say b1b2 bN and send a pulse of amplitude of size 0 b1b2 bN Can send at an arbitrarily high rate This is true even if the link distorts the signal but in a known way In practice the signal always gets distorted in an unpredictable random way Receiver tries to estimate the effects but this lowers the effective rate Katz Stoica F04 10 Physical Layer Functions Signal Adaptor Adaptor Adaptor Adaptor Adaptor convert bits into physical signal and physical signal back into bits Functions 1 2 3 4 Encode bit sequence into analog signal Transmit bit sequence on a physical medium Modulation Receive analog signal Convert Analog Signal to Bit Sequence Katz Stoica F04 11 Block Diagram NRZI Katz Stoica F04 12 Modulation The function of transmitting the encoded signal over a link often by combining it with another carrier signal E g Frequency Modulation FM Combine the signal with a carrier signal in such a way that the i frequency of the received signal contains the information of the carrier 1 1 0 0 1 Bit sequence 1 1 0 0 1 Modulated signal 1 1 0 0 1 Received signal 1 1 0 0 1 Received bit sequence E g Frequency Hopping OFDM Signal transmitted over multiple frequencies Sequence of frequencies is pseudo random Katz Stoica F04 13 Outline Relation between bandwidth and link rate Fourier transform Nyquist s Theorem Shannon s Theorem Encoding Framing Katz Stoica F04 14 Fourier Transform Any periodic signal g t with period T 1 f can be constructed by summing a possibly infinite number of sines and cosines 1 g t c an sin 2 nft bn cos 2 nft 2 n 1 n 1 To construct signal g t we need to compute the values a0 a1 b0 b1 and c Compute coefficients using Euler s formulae But it s an infinite series Often the magnitude of the an s and bn s get smaller as the frequency n times 2 f gets higher Key point a reasonable reconstruction can be often be made from just the first few terms harmonics Tough the more harmonics the better the reconstruction Katz Stoica F04 15 Fourier Transform Example sin 2 f t 1 3 sin 6 f t g3 t Note f 1 T Katz Stoica F04 16 Bandwidth Data Rate Physical media attenuate reduce different harmonics at different amounts After a certain point no harmonics get through Bandwidth the range of frequencies that can get through the link Example Voice grade telephone line 300Hz 3300Hz The bandwidth is 3000Hz Data rate highest rate at which hardware change signal Katz Stoica F04 17 Outline Signal study Fourier transform Nyquist s Theorem Shannon s Theorem Encoding Framing Katz Stoica F04 18 Nyquist s Theorem aka Nyquist s Limit Establish the connection between data rate and bandwidth actually the highest frequency in the absence of noise Developed in the context of analog to digital conversion ACDs Say how often one needs to sample an analog signal to reproduce it faithfully Suppose signal s t has highest frequency fmax Assume B fmax i e lowest frequency is 0 Then if T 1 2B then it is possible to reconstruct s t correctly Niquist s Theorem Data rate bits sec 2 B hz Katz Stoica F04 19 Why Double the Frequency Assume a sine signal then We need two samples in each period to identify sine function More samples won t help Katz Stoica F04 20 Nyguist s Theorem Revisited If signal has V distinct levels then Data rate 2 B log 2V V distinct values can be used to encode log2 V bits Bi level encoding V 2 Data rate 2 B Example of achieving 2 B with bi level encoding 1 2B 5V 0V 1 B Can you do better than Nyquist s limit Yes if clocks are synchronized sender and receiver we only need one sample per period This is because the synchronized starting sample counts as one of the two points Katz Stoica F04 21 Outline Signal study Fourier transform Nyquist s Theorem Shannon s Theorem Encoding Framing Katz Stoica F04 22 Shannon Theorem Establish the connection between bandwidth and data rate in the presence of noise Noisy channel Consider ratio of signal power to noise power Consider noise to be super imposed signal Decibel dB 10 log10 S N S N of 10 10 dB S N of 100 20 dB S N of 1000 30 dB Katz Stoica F04 23 Shannon Theorem cont d Data rate in the presence of S N is bounded as follows Data rate B log 2 1 S N Example Voice grade line S N 1000 B 3000 C 30Kbps Technology has improved S N and B to yield higher speeds such as 56Kb s Higher bandwidth higher rate Intuition Signal has more space to hide from noise Noise gets diluted across frequency space Katz Stoica F04 24 Outline Signal study Fourier transform Nyquist s Theorem Shannon s Theorem Encoding Framing Katz Stoica F04 25 Encoding Specify
View Full Document
Unlocking...