Transcript Week8_1

Midterm Review
Physical Layer
• Physical layer design goal: send out bits as fast as
possible with acceptable low error ratio
• C=B*log(1+S/N)
– C is the capacity of the channel, B is the bandwidth of the
channel, S is power of the signal and N is the power of the
noise
– Channel capacity means how many bits you can send out
per second reliably
– Bandwidth means how fast you can change the voltage.
More precisely, the range of frequencies pass the channel.
– Noise: anything other than the intended signal. Added to
the signal.
Detection – with Noise
•
•
Detection really depends on the noise. In the binary case when the transmitted
signal is either 0 or 5V with equal probability, if we know that noise takes values 3V and 2V with probability 0.7 and 0.3, respectively. How would you design the
detector?
First step, check the possible outcomes:
– If send 0V, two possible outcomes:
•
•
-3V. Prob: 0.7.
2V. Prob: 0.3.
– If send 5V, two possible outcomes:
•
•
2V. Prob: 0.7.
7V. Prob: 0.3.
– So, a total of only 3 possible outcomes.
•
Second step, check for each outcome, what should the output be.
– No ambiguity when received -3V and 7V, 0 and 1, respectively.
– What should we say when received 2v? From 0V, probability 0.5*0.3= 0.15. From 5V,
0.5*0.7=0.35. So will say when received 2V, the bit is 1.
– What is the probability that we give the wrong detection result? When received 2V and was
from bit 0 and we say it is from bit 1, so it is 0.15.
Basic Wireless System
• The very basic wireless communication system
– Sender: given the bit stream, convert it to the baseband
waveform by a Low Pass Filter, then multiply with the carrier
waveform (2.4GHz if 802.11g, 1.8GHz if some cellphones), and
send.
– Receiver: given the signal received from the antenna, multiply it
with a locally generated carrier, send it to the low pass filter,
regenerate the baseband waveform.
Some Important Concepts
•
•
•
•
•
•
•
•
•
Bandwidth – How fast can signals change. Or, the width of the frequency range
that can pass the system.
Noise – Will be added to the signal. Random, but some statistics can be known
with which we make our detection rules.
Data rate – How fast can we send bits, can be measured in bps. Upper bounded by
the Shannon’s theorem given the bandwidth and noise.
Propagation delay – How long does it take for the symbol to reach to the
destination.
Symbol – A point on the plane to represent one bit or multiple bits.
Sample – A reading of the received signal at some time instant. Usually a
corrupted version of the symbol.
Filter – Some device or software that can remove certain frequency components in
the received waveform.
Carrier – A sine wave to be multiplied with the baseband waveform.
Baseband waveform – The waveform that is a smoothed version of the square
waveform after the low pass filter. To be multiplied with the carrier.
Error Correction
• The (7,4) Hamming code:
• Error correction – calculating the syndrome,
check it matches with row of H.
Error Correction
• How is G chosen such that it can correct one error?
• The key is –
• First:
• ANY linear combinations of the row vectors of G has weight at least 3 (having
at least three `1’s)
• ANY codeword is a linear combination of the row vectors
• So a codeword has weight at least 3.
• Second:
• The sum of any two codeword is still a codeword
• So the distance (number of bits that differ) is also at least 3.
• So if one bit is wrong, won’t confuse it with other codeword.
• Because if there is only one bit wrong, the received vector will have
one bit difference with the original codeword C0. If it is also only one
bit away from another codeword C1, it means that C0 and C1 have at
most two bit difference, a contradiction.
Cyclic Code
• Cyclic code is a linear code that any cyclic shift of a
codeword is still a codeword.
• A (n,k) cyclic code can be generated by a polynomial g(x)
which has
– degree n-k and
– is a factor of xn - 1.
•
•
•
•
Call it the generator polynomial.
C(x) can be considered as the product of m(x) and g(x).
Error Detection. Divide the received polynomial by g(x).
Error if the remainder is not 0.
Systematic code:
Remember this is binary field!
Stop and Wait
• Sender (maintains “m” as the sequence number up to which has
been ACKed)
1.
2.
Grab data from the network layer.
Send to physical layer with the current sequence number , i.e., m+1
and start timer.
Wait for ACK.
3.
•
•
If got an ACKm+1, m:=m+1, repeat 1.
Else, timeout, repeat 2.
• Receiver (maintains “m” as the sequence number up to which has
been received)
1.
2.
3.
Wait for data.
Get data from the physical layer. If it is with the expected sequence
number, i.e., m+1, give it to the network layer, m:=m+1.
send ACKm. Goto 1.
Go-Back-N
Sender.
while (1) {
If network layer got data, if current window not full yet, read data, send to physical
layer with the frame ID. Start timer. Increment frame ID by one.
If got ACKm, if m is outside the window, don’t do anything. If m is inside the window,
consider all frames in the window with frame ID no more than the m acked. Forward
window to m+1.
If timeout for frame m, start to resend all frames in the window with frame ID no less
than m.
}
Receiver
while (1){
Wait to get data from the physical layer (blocked here until data got). After getting
data: (1) If the data is with the expected frame ID m, give the frame to the network
layer, increment the frame ID by one; (2) Send the ACK with the current frame ID.
}
• Note: assuming the sequence number is the frame ID.
4/1/2016 11:31:12 AM
Selective Repeat
Sender.
while (1) {
If network layer got data, if current window not full yet, read data, send to physical layer
with the frame ID. Start timer. Increment frame ID by one.
If got ACKm, if m is outside the window, don’t do anything. If m is inside the window,
consider all frames in the window with frame ID no more than the m acked. Forward
window to m+1.
If timeout for frame m, resend frame m.
}
Receiver
while (1) {
Wait (blocked here) and get frame from the physical layer. If it is within the receiver window
and hasn’t been received before, fill in the slot, and forward the beginning of the receiver
window if necessary, and deliver to the network layer all frames between the beginning of
the old receiver window and the new receiver window – 1, inclusive. Send ACKm (m+1= the
beginning of the current receiver window).
}
• Note: assuming the sequence number is the frame ID.
4/1/2016 11:31:12 AM
MAC
• In broadcast channels/multiaccess channels/random access channels,
multiple sources may compete for a shared channel. Two properties:
• When one station transmits, anyone can hear (something)
• When more than station transmit, collision
• The biggest problem now is how to determine who gets the channel.
• ALOHA as the starting point.
• Then tricks such as
– CSMA: listen before transmit
– CD: collision detection. Early abort.
– CA: collision avoidance. Minimize the probability of collision. Wait for a random
time after the medium is free.
– Exponential backoff: If collision, double the window size. Adaptively adjust the
contention window based on the local belief about the number of contending
stations.
– Ethernet: CSMA/CD/ Exponential backoff.
– Wi-Fi: CSMA/CA/ Exponential backoff.
802.3
http://www.erg.abdn.ac.uk/users/gorry/course/lan-pages/csma-cd.html
DCF Idea
• When get a packet to send, sense the channel. If channel
is busy, wait until the channel is free for DIFS. Start to
backoff for a random time. If busy before reaching zero,
freeze bo counter, and reactivate when idle for DIFS
again. If counted to 0 and channel is still idle, send.
• After receives a packet, send ACK.
• If no ACK received, double the window and retry.