DC Digital Communication MODULE IV PART1
DC Digital Communication MODULE IV PART1
DC Digital Communication MODULE IV PART1
Module IV –Part I
INFORMATION Information theory and coding: Discrete
messages - amount of information – entropy -
THEORY information rate. Coding- Shannon’s theorem,
Channel capacity - capacity of Gaussian channel-
Bandwidth S/N Trade off - Use of orthogonal signal
to attain Shannon‘s limit - Efficiency of
MODULE III orthogonal signal transmission.
PART I
1
3/23/2009
NOTES EXAMPLE
In this case if we are using binary PCM code for representing the
M messages the number of binary digits required to represent all EXAMPLE 1
the 2N messages is also N. A source produces one of four possible symbols during each
i.e when there are M (=2N) equally likely messages the amount of interval having probabilities: p(x1)=1/2, p(x2)=1/4, p(x3) = p(x4)
information conveyed by each message is equal to the number of = 1/8. Obtain the information content of each of these
binary digits needed to represent all the messages. symbols.
When two independent messages mk and mI are correctly
identified the amount of information conveyed is the sum of the
information associated with each of the messages individually. ANS:
1 1 I(x1)=log22 =1 bit
I k = log 2 I I = log 2 I(x2)=log24 =2 bits
pk pI
When the messages are independent the probabilities of the I(x3)=log28 =3 bits
composite message is pkpI. I(x4)=log28 =3 bits
1 1 1
I k , I = log 2 = log 2 + log 2 = Ik + I I
pk p I pk pI
2
3/23/2009
EXAMPLE 2 EXAMPLE 3
The probabilities of five possible outcomes of an experiment are given An analog signal band limited to 10kHz is quantized into 8 levels of
as a PCM system with probabilities of 1/4, 1/5, 1/5,1/10, 1/10, 1/20,
1 1 1 1 1/20 and 1/20 respectively. Find the entropy and rate of information.
P( x1 ) = , P( x2 ) = , P( x3 ) = , P( x4 ) = P( x5 ) =
2 4 8 16
fm= 10 kHz fs = 2 x 10kHz = 20 kHz
Determine the entropy and information rate if there are 16 outcomes per Rate at which messages are produced r = fs = 20 ×10 messages / sec
3
second.
5
1 1 ⎛1 ⎞ ⎛1 ⎞ ⎛ 1 ⎞
H ( X ) = ∑ P( xi ) logg2 bits/symbol
y H ( X ) = log2 4 + ⎜ log2 5 ⎟ × 2 + ⎜ log2 10 ⎟ × 2 + ⎜ log2 20 ⎟ × 3
i =1 P( xi ) 4 ⎝5 ⎠ ⎝ 10 ⎠ ⎝ 20 ⎠
1 1 1 1 1
= log2 2 + log 2 4 + log2 8 + log 2 16 + log2 16 = 2.84 bits/messages
2 4 8 16 16
1 2 3 4 4
= + + + + =
15
= 1.875 bits/outcome R = rH ( X )
2 4 8 16 16 8
= 20000 × 2.84
Rate of outcomes r = 16 outcomes/sec
15 = 56800 bits/sec
Rate of information R = rH ( X ) = 6 × = 30 bits/sec
8
3
3/23/2009
4
3/23/2009
The conversion of the output of a DMS into a sequence of Source coding theorem states that for a DMS X with entropy
binary symbols (binary codes) is called source coding. H(x) the average code word length per symbol is bounded as
The device that performs this is called source encoder. L ≥ H ( x)
If some symbols are known to be more probable than others
and L can be made as close to H(x) as desired for some
then we may assign short codes to frequent source symbols
and long code words to rare source symbols. suitably chosen code. When Lmin = H ( x ) the code
Such a code is called a variable length code. efficiency
ffi i i η = H ( x)
is
L
As an example, in Morse code the letter E is encoded into a
single dot where as the letter Q is encoded as ‘_ _ . _ ‘. This is No code can achieve efficiency greater than 1, but for any
because in English language letter E occurs more frequently source, there are codes with efficiency as close to 1 as
than the letter Q. desired.
The proof does not give a method to find the best codes. It
just sets a limit on how good they can be.
5
3/23/2009
CLASSIFICATION OF CODES
. PREFIX
Consider aCODING (INSTANTANEOUS
discrete memory-less CODING)
source of alphabet {x0, x1,…,
xi Code Code Code Code Code Code xm-1} with statistics {p0, p1, …, pm-1}
1 2 3 4 5 6 Let the code word assigned to source symbol xk be denoted by
x1 00 00 0 0 0 1 {mk1, mk2, …, mkn} where the individual elements are 0s and 1s
and n is the code word length.
x2 01 01 1 10 01 01 Initial part of code word is represented by mk1, …, mki for some i≤n
Any sequence made of the initial part of the code word is called a
x3 00 10 00 110 011 001 prefix of the code word.
A prefix code is defined as a code in which no code word is a
x4 11 11 11 111 0111 0001
prefix of any other code word.
It has the important property that it is always uniquely decodable.
Fixed Length Codes: 1,2 Prefix Code: 2,4,6
But the converse is not always true.
Variable Length Code: 3,4,5,6 Uniquely Decodable Code: 2,4,6 Thus, a code that does not satisfy the prefix condition is also
Distinct Code: 2,3,4,5,6 Instantaneous Codes: 2,4,6 uniquely decodable.
6
3/23/2009
EXAMPLE EXAMPLE
We are transmitting 3.6fm bits/second. There are four levels, 2 binary digits symbols
these four levels may be coded using binary PCM as shown
Binary digit rate = × 2 fm
symbol second
below.
= 4 f m binary digits/sec ond
Symbol Probabilities Binary digits
Q1 1/8 00 Since one binary y digit
g is capable
p of conveying
y g 1 bit of
Q2 3/8 01 information, the above coding scheme is capable of
Q3 3/8 10 conveying 4fm information bits/sec.
Q4 1/8 11 But we have seen earlier that we are transmitting 3.6fm bits of
Two binary digits are needed to send each symbol. Since information per second.
symbols are sent at the rate 2fm symbols/sec, the transmission This means that the information carrying ability of binary PCM
rate of binary digits will be: is not completely utilized by this transmission scheme.
7
3/23/2009
8
3/23/2009
9
3/23/2009
⎢⎣ P( y1 | xm ) P( y2 | xm ) ................. P( yn | xm )⎥⎦
If the probabilities
p P(X)
( ) are represented
p byy the row matrix,, then we
have [P(X)] = [p(x1) p(x2) ………………...p(xm)]
The output probabilities P(y) are represented by the row matrix
[P(Y)] = [p(y1) p(y2)………………….p(yn)]
The output probabilities may be expressed in terms of input
probabilities as
[P(Y)] = [P(X)] [P(Y|X)]
10
3/23/2009
x1 1 y1 x1=0 y1=0
1-p
p
x2 1 y2
x3 1 y3 p
x2=1 y2=1
xm 1 ym 1-p
This common transition probability is represented by p. (i) Find the channel matrix of the binary channel.
(ii) Find p(y1) and p(y2) when p(x1)=p(x2)=0.5
(iii) Find the joint probabilities p(x1,y2) and p(x2,y1) when
p(x1)=p(x2)=0.5
11
3/23/2009
SOLUTION EXAMPLE 2
Two binary channels of the above example are connected in
⎛ p(y1 | x1) p(y2 | x1) ⎞ ⎛ 0.9 0.1⎞
Channel Matrix p(y | x)= ⎜ ⎟ =⎜ ⎟ cascade. Find the overall channel matrix and draw the resultant
⎝ p(y1 | x2 ) p(y2 | x2 ) ⎠ ⎝ 0.2 0.8 ⎠ equivalent channel diagram. Find p(z1), p(z2) when
⎛ 0.9 0.1⎞ p(x1)=p(x2)=0.5
[P (Y )] = [P ( X )][P (Y | X )] = [0.5 0.5] ⎜ ⎟ = [0.55 0.45]
⎝ 0.2 0.8⎠
p( y1) = 0.55, p(y 2 ) = 0.45 x1 0.9 0.9 z1
⎛ 0.5 0 ⎞⎛ 0.9 0.1⎞ ⎛ 0.45 0.05⎞
[P ( X ,Y )] = [P ( X )]d [P (Y | X )] =⎜ ⎟⎜ ⎟=⎜ ⎟
⎝ 0 0.5⎠⎝ 0.2 0.8⎠ ⎝ 0.1 0.4 ⎠
⎛ p(x1, y1) p(x1, y2 ) ⎞ ⎛ 0.45 0.05 ⎞ z2
⎜ ⎟=⎜ ⎟ x2
⎝ p(x2, y1) p(x2, y2 ) ⎠ ⎝ 0.1 0.4 ⎠ 0.8 0.8
SOLUTION EXAMPLE 3
A channel has the channel matrix
P (Z | X ) = [P (Y | X )][ P (Z | Y ]
⎡1 − p p 0 ⎤
⎛ 0.9 0.1⎞⎛ 0.9 0.1⎞ ⎛ 0.83 0.17 ⎞ [P (Y | X )] = ⎢ p 1 − p ⎥⎦
=⎜ ⎣ 0
⎟⎜ ⎟=⎜ ⎟
⎝ 0.1 0.8 ⎠⎝ 0.2 0.8 ⎠ ⎝ 0.34 0.66 ⎠ (i) Draw the channel diagram
x1 0.83 (ii) If the source has equally likely outputs compute the
z1
probabilities associated with the channel outputs
p p for p
p=0.2
[P (Z )] = [P ( X )][P (Z | X )] x1=0 y1=0
x2 z2
0.66 y2=e (erasure)
⎛ 0.83 0.17 ⎞
P(Z) = [0.5 0.5] ⎜ ⎟ = [0.585 0.415] x2=1 y3=1
⎝ 0.34 0.66 ⎠
SOLUTION EXAMPLE
1
5
This channel is known as binary erasure channel (BEC) x1
3
y1
1 1
It has two inputs x1=0 and x2=1 and three outputs y1=0, y2=e, 1 3 4
3 1
y3=1 where e denotes erasure. This means that the output is in 4
1
doubt and hence it should be erased 2
x2 y2
1
⎡ 0 .8 0 .2 0 ⎤ 4
[ P (Y )] = [0 . 5 0 . 5 ]⎢
0 . 8 ⎥⎦
1
⎣ 0 0 .2 4
x3 1 y3
= [0 . 4 0 . 2 0 . 4 ]
2
(i) Find the channel matrix
1 1.
(ii) Find output probabilities if p ( x1 ) = , p( x2 ) = p(x3 ) =
2 4
(iii) Find the output entropy H (Y ) .
12
3/23/2009
13
3/23/2009
m −1
⎛ 1 ⎞ m−1 n −1 ⎛ 1 ⎞
H(X|Y) represents the average loss of information about a I ( X ;Y ) = ∑ p( xi )log2 ⎜ ⎟ − ∑∑ p( xi , y j )log2 ⎜⎜ ⎟⎟
transmitted symbol when a symbol is received. i =0 ⎝ p( xi ) ⎠ i =0 j =0 ⎝ p( xi | y j ) ⎠
It is called equivocation of X w. r. t. Y.
14
3/23/2009
15
3/23/2009
i. Given a source of M equally likely messages with M>>1 Consider a continuous random variable X with the probability
which is generating information at a rate R, given a channel density function fX(x).
with channel capacity C, then if R≤C, there exists a coding By analogy with the entropy of a discrete random variable we
technique such that the output of the source may be can introduce the definition
transmitted over the channel with a probability of error in ∞
⎛ 1 ⎞
the received message which may be made arbitrarily small. h( X ) =
−∞
∫f X ( x)log2 ⎜ ⎟ dx
⎝ f X ( x) ⎠
ii. Given a source of M equally likely messages with M>>1 h(x) is called differential entropy of X to distinguish it from the
which is generating information at a rate R; then if R>C, the ordinary or absolute entropy. The difference between h(x) and
probability of error is close to unity for every possible set of H(X) can be explained as below.
M transmitter signals.
16
3/23/2009
EXAMPLE EXAMPLE
1
h( x) = ∫ 1 2 log 2 2 dx = 1 2 [x ]−1 = 1bit
A signal amplitude X is a random variable uniformly 1
distributed in the range (-1,1). The signal is passed through
an amplifier of gain 2. The output Y is also a random variable −1
2
uniformly distributed in the range (-2,+2). Determine the
differential entropies of X and Y
h( y ) = ∫
−2
1
4 log 2 4 dy = 1 4 × 2[ x]−22 = 2bits
Δx
Δx , Δy → 0 ⎝ dx ⎠ determine the transmitted value X.X
= log 2 = 1bit i.e., R1 = R2 + 1 bits Consider the event that at the transmitter a value of X in the
interval (x, x+∆x) has been transmitted (∆x→0).
R1, reference entropy of X is higher than the reference Here the amount of information transmitted is log [1 f X ( x ) Δx ]
entropy R2 for Y. Hence if X and Y have equal absolute since the probability of the above event is fx(x)∆x.
entropies their differential entropies must differ by 1 bit. Let the value of Y at the receiver be y and let fx(x|y) is the
conditional pdf of X given Y.
Then fx(x|y) ∆x is the probability that X will lie in the interval Comparing with the discrete case we can write the mutual
information between random variable X and Y as
(x, x+∆x) when Y=y provided ∆x→0. There is an uncertainty
about the event that X lies in the interval (x,x+∆x). ∞ ∞
⎡ f ( x | y) ⎤
This uncertainty log [1 f X ( x | y ) Δx ] arises because of channel I ( X ;Y ) = ∫∫ f XY ( x, y ) log 2 ⎢ X
⎣ f X ( x) ⎦
⎥dxdy
noise and therefore represents a loss of information. −∞ −∞
17
3/23/2009
C = max[ I ( X ; Y )]
It is found that the PDF that maximizes h(x) is Gaussian
distribution ggiven by
y
( x − μ )2
C = max[ I ( X ; Y )] f X ( x) =
1
e
−
2σ 2
2πσ
Also the random variables X and Y must have the same mean μ
and same variance σ2
18
3/23/2009
∫ fY ( x ) = 1, ∫ (x − μ) fY ( x )dx = σ 2
2
⎡ 1 ( x−μ ) ⎤ 2
∞ −∞ −∞
−
h (Y ) ≤ − ∫ fY ( x ) log 2 e log e ⎢
2
e 2σ ⎥dx ⎡ 1 ⎤
−∞
∞ ⎣⎢ 2πσ ⎦⎥ h(Y) ≤ −log ge 2πσ ⎥
g2 e ⎢− − log
∞
⎡ ( x − μ )2 ⎤ ⎣ 2 ⎦
≤ − log 2 e ∫ fY ( x ) ⎢ − − log 2πσ ⎥dx 1
≤ log2 e + log2 e.loge 2πσ h (Y ) ≤
1
(
lo g 2 2 π σ 2 e )
2σ 2
e
−∞ ⎣ ⎦ 2 2
1
⎧ ∞
⎛ ( x − μ )2 ⎞
∞
⎫ ≤ lo g 2 e + lo g 2 2 π σ
≤ − log 2 e ⎨ ∫ fY ( x ) ⎜ − ⎟ dx − ∫ fY ( x ) log e 2πσ dx ⎬ 2
⎩ −∞ ⎝ 2σ 2
⎠ −∞ ⎭ 1 1
≤ lo g 2 e + lo g 2 2 π σ 2
2 2
1
≤
2
(
lo g 2 2 π σ 2 e )
Because the channel is band limited both the signal x(t) and the
noise n(t) are bandlimited to B Hz . y(t) is also bandlimited to
B Hz.
CHANNEL CAPACITY OF A BAND LIMITED AWGN CHANNEL CAPACITY OF A BAND LIMITED AWGN
CHANNEL (SHANNON HARTLEY THEOREM) CHANNEL (SHANNON HARTLEY THEOREM)
∞ ∞
All these signals are therefore completely specified by samples h (Y | X ) = ∫ f X ( x ) dx ∫ fY ( y | x ) log 2 (1 fY ( y | x ))dy
taken at the uniform rate of 2B samples / second . −∞ −∞
Now we have to find the maximum information that can be For a given x, y is equal to a constant x+n .
transmitted per sample .
Hence the distribution of Y when X has a given value is
Let x,n and y represent samples of x(t) , n(t) and y(t) . identical to that of n except for a translation by x .
The information I(X;Y) transmitted per sample is given by If fn represents the PDF of the noise sample n
I(X;Y) = h(Y)-h(Y|X) fY ( y | x ) = f N ( y − x )
By definition ∞ ∞
h (Y | X ) = ∫
∞ ∞ ∫−∞
fY ( y | x)log2 (1 fY ( y | x) dy = ∫ f N ( y − x)log2 (1 f N ( y − x))dy
−∞
−∞ −∞∫ f XY ( x , y ) log(1 / fY ( y | x )) dxdy putting y-x = z
∞ ∞
=∫ ∫
∞ ∞
−∞ −∞
f X ( x ) fY ( y | x )log(1 fY ( y | x ) dxdy ∫ −∞
f Y ( y | x ) log 2 (1 f Y ( y | x ) = ∫ −∞
f N ( z ) log 2 (1 f N ( z )) dz
19
3/23/2009
CHANNEL CAPACITY OF A BAND LIMITED AWGN CHANNEL CAPACITY OF A BAND LIMITED AWGN
CHANNEL (SHANNON HARTLEY THEOREM) CHANNEL (SHANNON HARTLEY THEOREM)
η
As B →∞, x → 0 For a maximum C we can trade off S/N and B.
S If S/N is reduced we have to increase the BW . If the BW is to
C ∞ = lim log 2 (1 + x )1/ x be reduced we have to increase S/N and so on .
x→0 η
20
3/23/2009
∫g
2
x1 x1
x2 integral ( x)dx
∫
n
f ( x ) g n ( x )dx x1
cn =
x1
∫
x2
g n2 ( x )dx A set of functions which are both orthogonal and normalised
x1
is called orthonormal set.
MATCHED FILTERS RECEPTION OF MARY FSK MATCHED FILTERS RECEPTION OF MARY FSK
Let a message source generates M messages each with equal s1 (t )
T
likelihood.
Let each message be represented by one of the orthogonal set ∫
0
e1
of signals s1(t), s2(t), ……., sn(t). The message interval is T.
The signals are transmitted over a communication channel s2 (t )
where they are corrupted by Additive White Gaussian Noise AWGN T
(AWGN). SOURCE OF
M
∫ e2
At the
th receiver
i a determination
d t i ti off which
hi h message has
h b
been 0
. . . . .
MESSAGES
transmitted is made through the use of M matched filters or
. . . . .
correlators.
Each correlator consists of a multiplier followed by an integrator.
The local inputs to the multipliers are si(t). sM (t) T
Suppose that in the absence of noise the signal si(t) is
transmitted and the output of each integrator is sampled at the
end of a message interval.
∫ 0
eM
21
3/23/2009
MATCHED FILTERS RECEPTION OF MARY FSK MATCHED FILTERS RECEPTION OF MARY FSK
Then because of the orthogonality condition all the integrator will
( si (t ) + n(t ) ) si (t )dt
T
have zero output except for the ith integrator whose output will be ei = ∫
T 0
∫ s i 2 ( t )d t T T
0
It is adjusted to produce an output of Es, symbol energy.
= ∫ si 2 (t )dt + ∫ n(t ) si (t )dt = Es + ni
0 0
In the presence of an AWGN wave from n(t), the output of the lth
correlator will be T To determine which message has been transmitted we shall
T
el = ( si (t ) + n(t )) sl (t )dt = ∫ sl (t )n (t )dt + ∫ si (t ) sl (t )dt
T
compare the matched filters output e1, e2 …….., eM.
∫T
0 0
0 We may decide that si(t) has been transmitted if the
= ∫ n(t ) sl (t )dt ≡ nl corresponding output ei is larger than the output of any of the
0
The quantity nl is a random variable which is gaussian, which has a filters.
mean value of zero and has a mean square value given by The probability that some arbitrarily selected output el is less than
σ2=ηEs/2 the output ei is given by
The correlator corresponding to the transmitted message will el 2
have an output 1 ei −
T
ei = ∫ ( si (t ) + n (t )) si (t )dt
p ( e l < ei ) =
2π σ ∫ −∞
e 2σ 2
d e l ................(1)
0
MATCHED FILTERS RECEPTION OF MARY FSK MATCHED FILTERS RECEPTION OF MARY FSK
M −1
⎡ 1 E s + ni −
el 2 ⎤
The probability that e1 and e2 both are smaller than ei is given
by
pL = ⎢
⎢⎣ 2π σ ∫ −∞
e 2σ 2
de l ⎥
⎥⎦
p( e1 < ei and e2 < ei ) = p( e1 < ei ) p( e2 < ei ) When el = −∞, x = −∞
= [ p(e1 < ei )] = [ p(e2 < ei )] el
2 2
Let =x Es n
2σ When el = Es + ni , x = + i
2σ 2σ
The probability pL that ei is that largest of the outputs is given del = 2σ dx
by
pL = p( ei > e1 , e2 , e3 ,.....eM ) = [ p( el < ei )]M −1 ⎡ Es n
+ i ⎤
M −1
2σ σ
M −1 ⎢ 1 ⎥
∫
2
⎡ 1 ei −
el 2 ⎤ pL = ⎢ e− x dx ⎥
= ⎢
⎢⎣ 2π σ ∫ −∞
e 2σ 2
de l ⎥
⎥⎦
⎢
⎣
π −∞
⎥
⎦
MATCHED FILTERS RECEPTION OF MARY FSK MATCHED FILTERS RECEPTION OF MARY FSK
22
3/23/2009
pe 1
ni 0.5 M=2
If y = and using eq (4)
2σ 0.1
M=4
M −1 10-22
⎛ Es
+y ⎞ M=16
η
⎛ 1 ⎞
M ∞
⎜ ⎟
∫ ∫
2 2
pC = ⎜ ⎟ e− y ⎜ e− x dx ⎟ dy 10-3
M=1024
⎝ π ⎠ −∞
⎜⎜ −∞
⎟⎟ 10-4 M=2048
⎝ ⎠
pe = 1 − pc 10-5
M→α
ln 2 Si = Si
0.71 2 3 6 10 20 ηR η log M
2
23