Transcript Week4_2 - FSU Computer Science

Some of the Existing Systems
Wired Communication – Telephone
Company
• Dial-up – 56kbps
• DSL – Digital Subscriber Line
– ADSL: Asymmetric DSL, different upload and
download bandwidth
– Available bandwidth is about 1.1MHz, divided into
256 channels, one for voice, some unused or for
control, the rest divided among upstream and
downstream data. My DSL at Pittsburgh was 100kbps
upstream and 768kbps downstream
– How ADSL is set up. Fig. 2-29. The ADSL modem is 250
QAM modems operating at different frequencies. The
actual QAM depends on the noise.
Wired Communications – The Cable TV
Company
• Cable frequency allocation. Fig. 2-48.
– Downstream channel bandwidth is 6MHz, and
may use QAM-64.
– Upstream channel is worse so use QAM-4.
– Upstream – stations contend for access (MAC
layer issue, will be discusses later)
– Downstream – no contention, from the head end
to user
– Shared medium, so some security is needed
Wired communication – Optical
Backbone
• SONET – Synchronous Optical Network
– OC-1: 51.84Mbps
– OC-3: 3*51.84Mbps
– OC-9: 9*51.84Mbps
–…
• Used for backbone switching
Cellular Phone Networks
•
•
•
•
User – base station – Telephone network
FDMA – Frequency division multiplexing
TDMA – Time division multiplexing
CDMA – Code division multiplexing
GSM – Global System for Mobile
Communications
• Second generation cell phone system (digital, first
generation analog).
• GSM-900 and GSM-1800 are most widely used
– GSM-900 uses 890 - 915 MHz to send information from the
Mobile Station to the Base Transceiver Station (uplink) and 935 960 MHz for the other direction (downlink).
• FDMA + TDMA
• Each user transmitting on a frequency and receiving on
another frequency.
• 124 pairs of 200 KHz channels. Each channel divided into 8
time slots for 8 users.
• Each user is has a chance to transmit every 4.615 ms. Each
time he can send 114 data bits – 24.7kbps.
CDMA
• Your 3G network uses CDMA.
• A good analogy in the book – You have a
group of people in a room. TDMA means they
talk in turn. FDMA means that those who
wants to talk sit in different corners and can’t
hear other pair. CDMA means each pair talks
in a different language and other people’s
voice is noise to them.
CDMA
• The whole bandwidth is used by every user.
Meaning that they can send out symbols really
fast.
• The trick is to make what A sent appear as 0 to B.
– Because we have a fast symbol rate, for each data bit,
we send out, say, 8 bits, call the “small bits” chips.
– Given a bit, if 1, send out, say, -1,-1,-1,1,1,-1,1,1, and if
0, 1,1,1,-1,-1,1,-1,-1
– This is called the chip sequence.
– The key is that each station has a unique chip
sequence (language), and different languages are
orthogonal.
– Fig. 2-45.
Wireless LAN Physical Layer
• 802.11b,g in the 2.4G band and 802.11a in the 5G band.
People now consider 802.11 as the notion of MAC layer
protocol, while a, b, g, or n, are about physical layer.
• 802.11b. 1, 2, 5.5, 11Mbps.
– 1Mbps: BPSK modulation. 1 bit into 11 chips with Barker
sequence +1 +1 +1 −1 −1 −1 +1 −1 −1 +1 −1. Why spread
spectrum? Required by FCC but was later removed
– 2Mbps: QPSK.
– 5.5M and 11M: use some bits to select chip sequence and use
two bits for QPSK
• 802.11a. Up to 54Mbps. OFDM.
• 802.11g. Up to 54Mbps. OFDM.
• 802.11n. Up to 600Mbps. OFDM on MIMO.
OFDM (Orthogonal Frequency Division
Multiplexing)
• In wireless communications, in addition to the
bandwidth limit and additive noise, you also have
multipath fading!
• The faster your symbol rate is, the more badly you will
be affected by multipath fading.
• In effect, OFDM is like DSL: given a wideband channel,
divide it into many sub channels. Each sub-channel can
be modulated/demodulated independently. Because
each sub-channel is of a much smaller bandwidth,
multipath fading is much less severe.
• In implementation, use IFFT and FFT.
MIMO
• Used in 802.11n.
• t transmit antennas and r receive antennas.
With the knowledge of channel matrix, by preprocessing the data, equivalent to min{t,r}
channels.
Error Control Code
Error Control Code
• Widely used in many areas, like communications, DVD,
data storage…
• In communications, because of noise, you can never be
sure that a received bit is right
• In physical layer, what you do is, given k data bits, add n-k
redundant bits and make it into a n-bit codeword. You send
the codeword to the receiver. If some bits in the codeword
is wrong, the receiver should be able to do some
calculation and find out
–
–
–
–
There is something wrong
Or, these things are wrong (for binary codes, this is enough)
Or, these things should be corrected as this for non-binary codes
(this is called Block Code)
Error Control Codes
• You want a code to
– Use as few redundant bits as possible
– Can detect or correct as many error bits as
possible
Error Control Code
• Repetition code is the simplest, but requires a
lot of redundant bits, and the error correction
power is questionable for the amount of extra
bits used
• Checksum does not require a lot of redundant
bits, but can only tell you “something is
wrong” and cannot tell you what is wrong
(7,4) Hamming Code
• The best example for introductory purpose and is also
used in many applications
• (7,4) Hamming code. Given 4 information bits,
(i0,i1,i2,i3), code it into 7 bits C=(c0,c1,c2,c3,c4,c5,c6).
The first four bits are just copies of the information
bits, e.g., c0=i0. Then produce three parity checking
bits c4, c5, and c6 as (additions are in the binary field)
– c4=i0+i1+i2
– c5=i1+i2+i3
– c6=i0+i1+i3
• For example, (1,0,1,1) coded to (1,0,1,1,0,0,0).
• Is capable of correcting one bit error
Generator matrix
• Matrix representation. C=IG where
• G is called the generator matrix
Parity check matrix
• It can be verified that CH=(0,0,0) for all
codeword C
Error Correction
• Given this, suppose you receive R=C+E. You
multiply R with H: S=RH=(C+E)H=CH+EH=EH. S
is called the syndrome. If there is only one `1’
in E, S will be one of the rows of H. Because
each row is unique, you know which bit in E is
`1’.
• The decoding scheme is:
– Compute the syndrome
– If S=(0,0,0), do nothing. If S!=(0,0,0), output one
error bit.
How G is chosen
• How G is chosen such that it can correct one
error?
• The key is – Any combinations of the row vectors
of G has weight at least 3 (having at least three
`1’s) – and codeword has weight at least 3.
• 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
codewords
The existence of H
• We didn’t compare a received vector with all
codewords. We used H.
• The existence of H is no coincidence (need
some basic linear algebra!) Let \Omega be the
space of all 7-bit vectors. The codeword space
is a subspace of \Omega spanned by the row
vectors of G. There must be a subspace
orthogonal to the codeword space spanned by
3 vectors which is the column vectors of H.
Cyclic Code
Linear Block Code
• Hamming Code is a Linear Block Code. Linear
Block Code means that the codeword is
generated by multiplying the message vector
with the generator matrix.
• Minimum weight as large as possible. If
minimum weight is 2t+1, capable of detecting
2t error bits and correcting t error bits.
Cyclic Codes
• Hamming code is useful but there exist codes
that offers same (if not larger) error control
capabilities while can be implemented much
simpler.
• Cyclic code is a linear code that any cyclic shift
of a codeword is still a codeword.
• Makes encoding/decoding much simpler, no
need of matrix multiplication.
Cyclic code
• Polynomial representation of cyclic codes. C(x) = C_{n1}x^{n-1} + C_{n-2}x^{n-2} + … + C_{1}x^{1} + C_{0}x^{0},
where, in this course, the coefficients belong to the
binary field {0,1}.
• That is, if your code is (1010011) (c6 first, c0 last), you
write it as x^6+x^4+x+1.
• Addition and subtraction of polynomials --- Done by
doing binary addition or subtraction on each bit
individually, no carry and no borrow.
• Division and multiplication of polynomials. Try divide
x^3+x^2+x+1 by x+1.
Cyclic Code
• A (n,k) cyclic code can be generated by a
polynomial g(x) which has degree n-k and is a
factor of x^n-1. Call it the generator polynomial.
• Given message bits, (m_{k-1}, …, m_1, m_0), the
code is generated simply as:
• In other words, C(x) can be considered as the
product of m(x) and g(x).
Example
• A (7,4) cyclic code g(x) = x^3+x+1.
• If m(x) = x^3+1, C(x) = x^6+x^4+x+1.
Cyclic Code
• One way of thinking it is to write it out as the
generator matrix
• So, clearly, it is a linear code. Each row of the
generator matrix is just a shifted version of the
first row. Unlike Hamming Code.
• Why is it a cyclic code?
Example
• The cyclic shift of C(x) = x^6+x^4+x+1 is C^1(x)
= x^5+x^2+x+1.
• It is still a code polynomial, because it the
code polynomial if m(x) = x^2+1.
Cyclic Code
• Given a code polynomial
• We have
• C^1(x) is the cyclic shift of C(x) and (1) has a
degree of no more than n-1 and (2) divides
g(x) (why?) hence is a code polynomial.
Cyclic Code
• So, to generate a cyclic code is to find a
polynomial that (1) has degree n-k and (2) is a
factor of x^n-1.
Generating Systematic Cyclic Code
• A systematic code means that the first k bits
are the data bits and the rest n-k bits are
parity checking bits.
• To generate it, you let
where
• The claim is that C(x) must divide g(x) hence is
a code polynomial. 33 mod 7 = 6. Hence 336=28 can be divided by 7.
Division Circuit
• Division of polynomials can be done efficiently by the
division circuit. (just to know there exists such a thing, no
need to understand it)
Remaining Questions for Those Really
Interested
• Decoding. Divide the received polynomial by
g(x). If there is no error you should get a 0
(why?). Make sure that the error polynomial
you have in mind does not divide g(x).
• How to make sure to choose a good g(x) to
make the minimum degree larger? Turns out
to learn this you have to study more – it’s the
BCH code.
Cyclic code used in IEEE 802
• g(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 +
x 8 + x7 + x 5 + x 4 + x 2 + x + 1
– all single and double bit errors
– all errors with an odd number of bits
– all burst errors of length 32 or less
Other codes
• RS code. Block code. Used in CD, DVD, HDTV
transmission.
• LDPC code. Also block code. Reinvented after
first proposed 40 some years ago. Proposed to
be used in 802.11n. Achieve close-to-Shannon
bound
• Trellis code. Not block code. More closely
coupled with modulation.
• Turbo code. Achieve close-to-Shannon bound.