8
jet
riy=yp) = 5 vy 2.
HX| Y=yx) Srestowtee| 7a,i50
Thus quantity is itself a random variable that takes
HX | Y=) 1) with probabilities p).--PO'x-) respectively.
‘The mean value of H(X| Y =)’x) over the output alphabet y’ is
K
K
-1
DHX Y=) POW
=0
HY)
"
Ket Jel i
yy ves) POD Hoe| SET ]
x50 j=0
5 1 -
(x;..¥4) logy [ tum lyn) |
an PO 2] BG, Le 2
The quantity HCXIY) js called a conditional entropy. It represents the amount of
uncertainty remaining about the channel input after the channel output has been
observed.
Now, considering both the uncertainty conditions (before and after applyi
inputs), we come to know that the difference i.e., H(X) - H(X | Y) ees
the uncertainty about the channel input that is resolved by ob: ae ae
output, This called as the Mutual Information of the channel ears
el. T
Ommanic
Wi
whole thing jy
Denoting the mutual Information as I(X5 Y) we ean a mn
in write the
follows
equation, as
WX; Y¥) = W(X) ~ XY)
Hence, this is the equational representation of mutual information.
Properties of Mutual Information
“The mutual information I(X;Y) has the following important properties,
Property1:
‘The mutual information of a channel is symmetric i.e.
W(X; Y) = 1(¥s X) (
vere the mutual information I(X; Y) is a measure of the uncertainty aba th
ved by observing the channel output and the ruta
channel input that is resol
ion I(Y;X) is a measure of the uncertainty about the channel output that is
informati
|
resolved by sending the channel input.
Proof:
Jel 1
H(X) = <) log, |
ee wel ]
K
k
_ a
= & pe) tors Pt) ] x P01 x)
Jel Kel 1
= YL poxlx) pep toes] sep
joo k=O ]
mae
c= SS wooeal ay | =
We know that
HX ¥) Sus 1
; (x, y,) log] oy
Ne cel see |
1G Y) = HO) -H(X|Y)
Substituting 7
ubstituting H(X) and HICX | Y) and then combining terms we get,
A
det Ket , :
-F'5 69) oa al A) Information Theo,
From Baye; Sere ae a
rom Baye’s rule for condit:onal probabilities, we have
PEL _ pols) (8)
P(x) PO)
ae ' | ; r of
Hence, substituting equation (8) into equation (7) and interebanging the ove
summation, we may write
IQGY) = = = P(X jY4) logy eae |
= 1(%X) @)
Hence the proof.
Property 2
The mutual information is always non negative.
WX; Y) > 0 +10)
Proof
To prove this property, we first note that
Pp ye) -(11)
POY”) = Do)
Hence, substituting equation (11) in equation (7), we may express the mutual
information of the channel as
IK! PCC ¥4) |
SY) = PEI
1X; Y) yy 2% PC» 5) logs [ pee) pO) (12)
Next, a direct application of the fundamental inequaltiy yields the desired result,
W(X; ¥) 20
with equality if and only if,
PU» Ye) = PC) PO) for all and k (3)
This property states that we cannot lose information, on the average, by
observing the output of a channel. Moreover, the average information is zero if, and
he input and output symbols of the channel are Statistically independent, as Property 3
‘The mutual information of a channel may be
expressed in terms of
,
entropy of the channel output as
WX; Y) = H(Y)- HY] X)
where H(Y | X) is a conditional entropy. oll
Proof:
This property follows directly from defining equation (3) for mutual informa,
.
ofachannel and property 1.
Property 4
The mutual information of a channel is related to the joint entropy of th!
channel input and channel output by : |
1(X:Y) = H(X)+H(Y)-H(%Y) Al}
where the joint entropy H(X, Y) is defined by
0,1) = SS pe, 0 06 (a5) Al
Q %, EP ots ple)
Proof
To prove this property, we first rewrite the definition for joint entropy HY)
as
1
HOG Y) = [eee |
1 K=1
EX per ys) loge! Tee, yy)
J=0 k=O
Jel
+
iso
K-1 1
XP) logy [ PG) POW) ]
The first double summation term on the right side of equation (17) is recogni!
as the negative of the mutual information of the channel I (X ; Y) » previous
given in equation (12). As for the second summation term, we manipulate it
follows,
at
Ald) Information The
aS : 7 _
E pe,)) log,| —_
_] el oe |
/ 1 VS po 29
y aolea|ee! K-1 ie
Stal ay | Eason hel wo]
Tio feo &
10
1 rl
- 7 o aie
= ¥ ple) log, all ) log y ]
2 pl) oe a + &, Pow L pow
(18)
= HX) +H)
: : “tthe result.
Accordingly, using equations 12 and 18 in equation (17) we 26 HE ms
eal)!
H(X, Y) = -1(X; ¥) + W(X) + HY)
By rearranging this equation, we will get
1(X;Y) = H(X) + H(Y)-H% Y)
diagram,
Hence, the proof.
Mutual Information, of a channel can be conclude usi
Fig, 1.8. Mustrating the relations amoug various channel parameters
‘The entropy ofchannel input X is represented by the circle on the left. The
el output Y is represented by the circle of the right. The mutual
is represented by the over between these two circles.
entropy of chann'
information by the channel We have so far discussed mutual information, The maximum averag
IE muy
ation in an instant of a signaling interval, when transmitted by a
Y a diser,
inform,
bilities of the rate of maximum reliable transmy
memoryless,channel, the probal
of data, can be understood as the channel capacity. It is denoted by C any
i
measured in bits per channel use.
Consider a discrete memoryless channel with input alphabet X, output alphet
Y and transition probabilities p(s |%))-
‘The mutual information of the channel is defined as
Jer Ke POs)
WX;¥) = Z pa y0 | DO)
yao ke0 PV
Pty Ii) = PO lpPGp
Jel
pO) = PU lx) Pe)
j=0
| information of a chante
e three equations we see that, the mutual
which the channel is uset
ly on the channel, but also on the way in
)} is independent of the channel. We c=
From thest
depends not onl
‘The input probal
then maximize the average ™
to {p(x}.
Hence, we define the channel capacity of a diserete memoryless channel «s
erage mutual information I(X ; Y) in any single use of the chant:
ability distributions {pCi
bility distribution {p)
autual information I(X ; Y) of the channel with respe
maximum av
where the maximization is over all possible input prol
on X.
‘The channel capacity is commonly denoted by C, thus
C= max I(X;Y)
[se eat eee 5
Information Theory
rr
1,12, CHANNEL CODING THEOREM OR SHANNON’ SECOND THEOREM
The noist ent i A a
na se present in a channel creates unwanted errors between the input and
output sequet e ot jlity sl
put sequences of a digital communication system. The eror probability should
be very low, nearly ‘eve such 2
me z low, nearly < 10-6 for a reliable communication. In order (0 achieve such @
high levi . i
gh level of performance, we may have to resort to the sue of channel coding:
The channel coding in a communication system, introduces redundancy with @
control, so as to improve the reliability of the system. The source coding reduces
redundancy to improve the efficiency of the system.
Channel coding consists of two parts of action.
1. Mapping incoming data sequence into a channel input sequences.
it sequence into an output data
2. Inverse Mapping the channel output
sequence.
The final target is that the overall effect of the channel noise should be
minimized.
‘The mapping is done by the transmission, with the help of an encoder, whereas
the inverse mapping is done by the decoder in the receiver.
Discrete Channel pee Channel
|. |_| i
memoryless encoder memoryless decoder Destination
| seus channel
i Transmitter Receiver
| Noise
i
in which the message sequence is divided into sequential
h k-bit block is mapped into an »-bit block where
* Consider block codes,
blocks of & bits long, and eacl
n2k.
The number of redundant bits added by encoder to each transmitted bloc!
n—k bits. The ratio kin is called the code rate.
Fig, 19. Block diagram of digital communication system Digital Communicge
i
k
Code rate, r= “>, always <1
_ No. of message bits in a block
~ No. of bits in code word
The accurate reconstruction of the original source sequence at 4
ity of symbol error should be les,
destination requires average probabil
Consider a discrete memoryless source with an alphabet $ and
H(S) bits per source symbol and source emits symbols once ¢
entropy
very T,
seconds.
H(S) ,
Average information rate of the source ae bits/sec
The decoder delivers decoded symbols to the destination from the sours,
alphabet S and the same source rate of symbol every Ts. {
The discrete memoryless channel has a channel capacity equal to C bis|
per use of the channel and used once every T, seconds, |
. Cc |
Channel capacity per units = =| bits /see
2
|
This represents the maximum rate of information transfer over the channel. The
Channel coding theorem for a discrete memoryless channel is stated in two parts a
follows, - No po:
ility of transmi
» with small
probability of error,
- i ation
ion and reconstruction of inform
¢ of the
Henee, the maximum rate
oo. e critical rau
of the transmission is equal to the eri
channel capacity,
a
ake place over
fe i ich ¢: ake
for reliable error-free messages, which can take Pp) 7
is called as “Channel Coding Theor
lowing points,
serete memoryle
Inn
important to note the foll
iG
It doesnot show us how to construct a good code.
It do
a »mbol error after
ot have a precise result for the probability of symbol
decoding the channel output.
Binary Symmetric Channel
; ications channel model
--A binary symmetric channel is a common communications channt chest
. ‘ e] Q itte! shes:
used in coding theory and information theory. In this model, a transmitter wi
send a bit (a zero or a one) and the receiver receives a bit.
It is assumed that the bit is usually transmitted correctly, but that it will ee
ipped” with a small probability. This channel is used frequently in information
theory because it is one of the simplest channel to analyse.
41.10. Binary symmetric channel
A binary symmetric channel with cross over Probability p denoted by is a
channel with binary input and binary output and Probability of error P; that is, if .
3 » if x Digital Commune
a.
is the transmitted random variable and Y is the received random Variable, th
> then
channel is characterized by the conditional probabilities,
p.(¥=0[X=0) =
p.(Y=0| X=1) = p
p.(Y=1|X=0) = p
p(Y=1|X=1) = 1-p |
“It is assumed that 0 1/2 then the receiver can swap i
output (interpret when it sees 0 and vice versa) and obtain an equival le
channel with crossover probability 1 —p < 1/2. |
This channel is used by theorists because it is one of the simplest nois,
channels to analyse. Many problems is communicative theory can te!
|
reduced to a binary symmetric channel.
Conversely, being able to transmit effectively over the Binary symmetric
channel can give rise to solutions for more complicated channels.
Channels Capacity for Binary Symmetric Channel
By symmetry, the capacity for the binary symmetric channel is achieved with
: a 1
channel input probability-p(x,) = p(x,) = 3» Where x and x, are each 0 or 1. Hence
© = 105 ¥) 96) = ple,) = of
From the binary symmetric channel diagram we have
POI) = pO |x) =p “8
and B04) = pO [x)= 1 —p 8)
Therefore, substituting
capacity equation with J =
P(*,) accordance with
X(Dp) =
'g these channel transition probabilities into chant!
K = 2, and then setting the input probability via)”
~Po log py~(1~p,) log, (1 - py) ald) ‘mation Theory
We find that the eap;
acity of the binary symmetric channel
(5)
C= 1+plog, p+(1-p) log, (Ip)
Based on equation (4) we may define the entropy function re)
1 LL) 7
Xp) = vlogs () + (py oes (725)
Hence, we may rewrite equation (5) as (7)
C= 1-X(p)
a en
The channel capacity © varies with the probability of error F
following figure.
as shown in
Channel Capacity, ©
i
2 05
Transition Probability, P
ig. LL Variation of channel capacity ofa binary symmetric channel with transition
ae probability p
1. When the channel is noise-free permitting to set p = 0, the channel
capacity C attains its maximum value of one bit per channel use, which
is exactly the information in each channel input. At this value of Ps
entropy function X(p) attains its minimum value of zero,
the
2. When the channel is noisy, producing a conditional probability of ertor p
=}, the channel capacity C attains its minimum value of zero, whereas
the entropy function X(p) attains its maximum value of unity, of the Channel Coding Theorem to Binary Symmetric Channels
nels
‘Application
iscrete memoryless source that emits equally likely bi
ally likely binary 5
‘yMib
Consider a di
vith the source entropy equall to one bit
ae per source g
Yb
seconds, W
ate of the source is (
once every Ts
the information r I/¢) bits per second.
|
she couee sequence is app 10 9 Dinar channel ener wih coder |
-
she encoder produees a symbol once every conds, Hence, the chang
an
sety per unit time is (C/T.) units per second, where C is determined by th
the
capa
prescribed channel transition probability p in accordance with following entropy’
function.
xia) = plosa(2)# =p) toea(725)
c = 1-X(p) “a
Accordingly, the channel coding theorem implies that if
(9)
arbitrarily low by the use of a suitable
‘The probability of error can be made
Is the code rate of the encoder.
encoding scheme, But the ratio T, /Ts equa
T,
ra (10
ic
Ts T,
T,
7 oandr
Hence, from the channel coding theorem, we may state that for any = vind fh
< 0.9192, there exists a code of large enough length 7 and © oe w the, given
hat when the code is
appropriate decoding algorithm, such th
channel, the average probability of decoding error
Repetition
codes
Goad capacity
a value
=10°
‘Average probabily of error
0.01 01 10
|
ks
Fig, 1.12, Mlustrating significance of the channel coding theorem
Example 2:
Consider a simple coding scheme that involves the use of a repetition code, in
which each bit of the message is repeated several times.
Let each bit (0 or 1) be repeated » times,
= 3, we transmit 0 and 1 as 000 and 111, respectively.
where 7 = 2m +1 is an odd integer.
For example, for *
Comma
IFin a block of received bits the number of Os exceeds the nun
1
the decoder decides in favor of a 0. Otherwise it decides in favor ofa, °
Tony
Hence, an error occurs when m + 1 or more bits out of m= 2 m + Lj
tence, . * 1 bit
received incorrectly. Because of the assumed symmetric nature of the chany ,
Ba aa - Mel
average probability of error, P, is independent of a prior; probabilities of y at
any
We find P, as
“fn
a= 3 ("Jeane FF
i=m+l t
where P is the transition probability of the channel.
Table 1.1. Average Probability of Repetition Code
1 [A ability of
Code Rate r=", verage Probability of error, p,
1 102
3x 10-4
10-6
4x 107
108
5x 10-10
1
3
L
5
a
7
1
9
1
I
SARS RUS ee
1.13. CHANNEL CAPACITY THEOREM
x Cais & zero-mean stationary process X(/) that is band-limited to B hertz. Lt
x» K= 1, 2, .. m denote the continuous random variables obtained by unifort
sampling of the process X(/) at the rate of 2B samples per second.
The: i in
me asl ate transmitted in T seconds over a noisy channel, also ba
(0 B Hertz, Hence, the number of samples, n is given by RE ea aaa
—-
(1.57
Information Theory
ee
We reler 0X, aso Te ehiannel output Je
Xi, a8 a sample of the transmitted signal. ‘The ea aA
Perturbed by additive white Gaussian noise of zero mean and power °PS
density Ny/ 2. The noise is band-limited to B hertz.
Let the continuous R.
. samples of
andom variables Yj, k= 1, Que # denote samPl
hown by
U (2)
Yy = X +N, k=1,2000
‘The noise sample Ny. is Gaussian with zero mean and variance given bY
oe = NB
we assume that the samples Y,, k = 1,2, .
3)
nare statistically independent .
ibed is called a
A channel for which the noise and the received signal are as deser
X——_—>| Ye
Fig. 1.13. Model of discrete-time, memory-less Gaussian Channel
The transmitter is power limited and assign a cost to each channel input to make
meaningful statements about the channel. So cost can be defined as
ED] =P k=1,2..,n (4)
where p is the average transmitted power. We define the channel capacity as
C= max (1K, 5 ¥) EK?) =p} 83)
LEED
where I(X;, 5 Yq) is the average mutual information between a sample of the
transmitted signal, X,, and the corresponding sample of the received signal Y,,. The
. F ‘a
maximization in above equation can be performed with respect to f Xx), the
probability density function of X,. Ke), The average mutual information (X,
+ Y4) can be expressed j
one op |
quivatent forms, Among thatene is Ms
UX EY = AOD FOI)
sft
Slave Ny and Ny are independent random variables and their sum equate y
als
such as
an REN, kein
We find that the conditional differential entropy of Yq, given Xy, is equal to
conditional entropy of Ny.
YEN) = AND
Substituting equation (7) into equation (6) we get
1X2 Yi) = AY ANY (8)
|
Since A(Nq) mizing I (X, ; Yj)
independent of the distribution of X,, may
i} st
requires maximizing 4(Y,) and the differential entropy of sample Yj of the received)
signal, Pr
For A(Y,) to be ma
imum, Y, has to be a Gaussian random variable (i.e) the| | t1
samples of the received signal represent a noise like process. 7
Since N, is Gaussian by assumption, the sample X, of the transmitted signal
must be Gaussian too. The maximization specified in equation (5) is attained by
choosing the samples of the
transmitted signal from a noise like process of average
power p. So we
can reformulate equation (5) as
CaO EE
X, Gaussian, E[X? ] =p a
For the evaluation of the
—_ channel capacity C we proceed in three stages,
he variance of sample iver si °
ee ple Yi, of the receiver signal equals p + o?. Hence
rential entropy of Y, as
AY) =
1
2 bg, [2x e (+62) 0)
os od ~~ T159
Frerential
2, fence, the dif
2. The v, -
1als 6?
atianee of the no}
: nee of the noise sample Ny equ
entropy of Ny as
‘ A)
KN:
N 2 (2m 0)
recognizing
3. By substitu .
YY substituting equations (10) and (11) in equation (9) and
we get the
the definiti A
¢ definition of channel capacity given in equation (9),
desired result as
(12)
c=lt P :
2 logs +5) bits/channel use
withthe channel used times forthe transmission of samples ofthe process
/T) times.
X(t) in T seconds, we find that the channel capacity per unit time is (1
The number n equals 2 BT and the channel capacity per unit time as
>
c= Bie (1435 ) bits/s (13)
Statement
Shannon’s channel capacity theorem is also referred as the Shannon-
information that can be
Hartley Law. Hartley showed that the amount of
transmitted over a given channel is proportional to the product of the channel
bandwidth and the time of operation.
ve white
B hertz, disturbed by addi
Capacity of a channel of bandwidth
iy /2 and limited in bandwidth to B,
Gaussian noise of power spectral density I
is given by
P
c= Btog,(1 +h ) bits/s
rage transmitted power.
where P is the ave!
theorem is one of the most remarkable results of
‘The channel capacity
on theory ina single formula.
informati
Channel capacity theorem highlights most vividly the interplay between
ey system parameters.
three k Digital Communje
—~
@ Chann
(average transmitted power and
Power spectral density at the channel output,
el bandwidth
(iii) nois
The theorem implies that for given average transmitted power P and chap,
bandwidth B. we can transmit information at the rate C bits per second Ny
arbitrarily small probability of error by employing sufficiently complex ened,
Systems, z
It is not possible to transmit at a rate higher than C bits per second by ay,
encoding system without a definite Probability of error.
Hence, the channe! capacity theorem defines the fundamental limit on the rate
power-limited, band-limited Gaussian channel, 7
must have statistical propeniy
error-free transmission for a
Spproach this limit, the transmitted signal
approximating those of white Gaussian noise.
Ideal System
We define an ideal system as one that transmits data at a bit rate R 6 equal to th:
channel capacity C. We may then express the average transmitted power as
P=E,C alt
where E, is the transmitted energy per bit, Accordingly, the ideal system i
defined by the equation
5 > ba (1+$88 }
B (ENB J
Y per-bit to noise power spectral density ratio E, / Nj.
we may define the energy
terms of the bandwidth efficiency, C/B for the ideal system as
E, 2c/B _ | 7
No CB wll
This equation is displayed as the curve labeled “eapacity boundary’ in belo
figure.
A plot of bandwidth effcieney Ry / B vérsus E, / Ny in figure called t
bandwidth efficiency diagram, Based on this diagram, we can have the followit!
observations.
Pm see density ratio Be! 9|
jo-no'
1
niting value
lim ) ae
soe
This value is called the Shannon limit. Expressed 19 decibels. it equals
— 1.6 dB. The corresponding limiting value of the channel eapaci®) fe
cs)
WN VG
104
f capacity boundary
for which Rp = ©
KX
Region for which
Rp C). The latter region
v
is shown shaded in -
Disctal Comm
No. Rye
Seam highlights potential trade-ofl among
ProPability of symbol érror P.. We may view movement of the oper
YN for a Fixed ;
Point along a horizontal line as trading P, versus
On the other hand, we may view movement of the operating
8 Vertical line ag trading P, versus R,/B, for a fixed E,/Ny.
point
The Shannon limit may also be defined in terms of the I2y/Ny required by
ideal system for error-free transmission to be possible. We may write for the
system,
[0 (EYN) =,
U Gano Jog, { 2
1 = 3 bom (5%
log, ¢
and = che
*o 202
The desired form for fy (x) is therefore described by
_ —pn)
Ix @) = Ee en (=S*) (B
which is recognized as the probability density of a Gaussian random variabj
of mean pt and variance 62,
lex
Already we have the entropy of a discrete random variable as
100 = f Fy 6) tog, [w]e
ral =(e=pp I
109 = fy o7(=85"*) og ot Jax
A(X) = ¥ tog, (2m e 62)
We may summarize the results of this, example, as follows.
1. For a given variance o?, the Gaussian Random variable has the larges!
differential entropy attainable by any random variable. (i.e) if X i84)
Gaussian Random variable and Y is any other random variable with th
same mean and variance, then for all Y.
A(X) = ACY)
where the equality holds if , and énly if, y = xX 1.67)
The entro , stermined by
he entre PY Of at Gaussian random variable X is uniquely deter
the variance
Mranee of N (Le, iL is independent of the mean of X)
TWO MARKS QUESTIONS WITH ANSWERS
What is information
Information can be defined as the inverse of probability of occurrence
. aE
i) = log Ps
Give to properties of information,
* Information must be Non-negative.
ty is more
* If probability then information is more and if probabili
then information is |
3. What is entropy?
Entropy can be defined as the average amount of information per source
symbol,
KeI 1
HS) = Dry toes( 55)
a0 Pe
H(S) is called the entropy of a discrete memoryless source with source
alphabet.
4. Give two properties of entropy.
“If H(S) = 0, if and only if the probability p, = 1 for some k, and the
remaining probabilities in the set are all zero. This lower bound on
entropy corresponds to no uncertainty.
. a le
IP H(S) = log, &. ifand only ifpy = Z for all & (i.e all the symbols in the
alphabet S are equiprobables. This upper bound on entropy corresponds
to maximum uncertainty. ° Pi
5. What is discrete source?
If a source emits symbols $ = {sq s), 5
ao Se} from a fix i
a xed finit
alphabet then the source is said to be discrete source. . fon Rate,
. per ot bits OF intomy,
| Information site“ is presented in average num :
Ros)
os are generated.
is nate at which mes
NUS) ~ is the entropy of the source.
hat isa presi
code?
In Pretix code no codeword is the prefix of any other codeword, jy
Variable
th code, The binary digits are assigned to the mess:
their Probabilities of eccurrence.
Define
Mutual Information,
Mutual intormation 1(X.Y) ofa channel is defined by
KX Y) = A(X) —HEXIY) bits/symbol
HX) ~ enutopy of the source
HQXIY) - Conditional entropy of Y
9. State any. Sour properties of mutual information,
* The mutual information ofa channel j
KX:¥) = (Y:x)
* The mutual information is always non negg
ative.
KX;¥) 20
symmetric
* The mutual information of a channel may be
expressed in terms of
entropy of the channel output as
IXSY) = HOY) -Hy]
* The mutual information of a chanr
nel is re]
fated to the joint entropy of th
channel input and channel output by
IXY) = HEQeHy— HX. Y)
ee heony
il
{109}
|
Cf the entropy UNV) of a communication system
to,
Define
© the yi
SMficy
where 104
and Y is he receiver,
ents uncertainty of X on
onal entropy. I repres
is Kno
8 Known. tn other words HUX]Y) is an average meastre of
aller V is received.
umeeraingy jay
HAI) te
KNIYY represents the inform
i ‘ition lost in the noisy cl
+ AN event has a six po
la
sible outcomes with probabilities 1/2, 1/4, 1/8, WAG
US2. Vi
* Mind the entropy of the system,
I
Poe 5.pyet iy ot 1
7 Ae P2 ys Pa 76+ Pa
+ Ps 39
WS Ep, tows dp)
2 +(F) tow ons (i) toes 06) ($4) toes 624 (53) toe 6)
1.5625
12. When is the average information delivered by a source of alphabet size i
maximum?
re equally likely
Average information is maximum when the two n
ise, py = py = V2. Then the maximum average information is
q,
i log, @+4 log,(2)
= 1 bit /message
13. Name the source coding techniques.
1. A Prefix coding
2, Shannon-Fano coding
Huffman coding
we
14 Write the expression for code redunudaney in terms af entropy.
Code redundancy is the measure of redundancy of bits in the encoded
‘ode -
message sequence.
Redundancy = 1 code efficiency | f = ive 2 If's0, why?
15. ds he information y Fa continuous system non negati “ 7 Lal
Yes, the information of stem is non neg i
tha IXY) > 0 sone orgs property.
16, State Shannon's
continuous 3)
frst theorem,
Shannon's First The
HS), the
utee OF entry,
ven a discrete memory .
‘orem:
" ce encoding is bounded a
'1GC code word length L for any source encodin
[> IK) numb
e average number
The entropy H(S) represens a fuidamental limit onthe average nur a
bits per source symbol i,
JT. What is data compaction? |
Data compaction
; ; ation so that he
'S used to remove redundant information s th |
decoder Teconstructs {
he original data with no less of information |
18. Whavis decision ree? Where itis used?
The decision tree is a tree that has an in
Corresponding to source symbols 55, s), Spo Sy_, Once each terminal Site
mits its symbol, the decoder is reset to its inital state, |
Decision tee is used for decoding operation
19. What is ‘instantaneous code?
ial state and terminal states
of prefix codes,
Ifa codeword is not a prefi
instantaneous code;
eg.
0
10
110
1110
20. What is uniquely decipherable code?
ix of any other codeword, then it is said to be
Ifa codeword is not a Combination of, ANY other code itis sa,
‘Word th 0
be uniquely decipherable code, Smits said 101
1001
, / — . i sing
21. How ant encoding operation is taken place in, Lempel-Ziv. coding "
» binary sequence?
ties , . fa stream
Encoding operation can be taken place by Parsing the source ae
nto d previously.
ements that are the shoftest subsequences not encounters’
22. What is discrete channel?
The channel is said to be diserete when both the alphabets have finite sizes.
23. What is memoryless channel?
The channel is said to be memoryless when the current output symbol
of the previous choices.
depends only on the current input symbol and not any
24. Define a discrete memoryless channel,
For the discrete memoryless channels, input and output both are discrete
random variables. The current output depends only upon current input for such.
channel.
What is the important property while using the conditional probability
Ol¥y?
The sum of all the elements along the column side should be equal to 1.
to
on
What is the important property while using the conditional probability
(1X)?
The sum of all the elements along the row side should be equal to 1.
26.
2% Define channel capacity?
We define the channel capacity of a discrete memoryless channel as the
maximum average mutual information IX ; Y) in any single use of the Pigital Comuriac ‘ig
if
cl hannel, i
28. State the channel coding theorem fora
source with ana)
s. Let discre'
‘ete memory
Letad
produce symbols at every
capacity C and used once every le
1
nitled
source output can be trans
cheme for which s pe
ability of error.
a coding
ith the small proba
There exists
constructed W
over the channel and can be 1
ng) | &
~ T,
aling at the cr! ical rate.
Then, the s id to be
29, Explain Shannon-s -Fano-Coding ?
tained by the following simple procedure
An efficient code can be ol
known an Shannon Fano algorithm.
Algorithm:
Step 1 : List the sour
Partition the sets into two sets that are as close to equiprobabk
symbols in order to decreasing probability.
Step 2 +
as possible and assign 0 to the upper set and assign 1 [0 the
lower set.
Step 3 : Continue this process each time partitioning the sets with *
nearly probabilities as possible unti .
a mntil further partitioning is
possible. partitioning 1S
30. Define Huffman coding.
The Huffman code is a si
a source code wh d
ose average Wi engl
‘orld lene!
approaches the fundamental limit set b:
set by the ent ofa di q
source. tropy of a discrete memory! [ taformation Theory
prescribed set
he
The Co s used to synthesize the code is to replace t ne.
ss source with @ simpler one
REVIEW QUESTIONS il
al information
1. Define mutual information, Find the relation between the MUNA”
and the joint entropy of the channel input and channel outPut: ca
important properties of mutual! information.
using Huffman
Encode the source symbols with following set of probabilities
y
coding .
m = { 0.4, 0.2, 0.12, 0.08, 0.08, 0.04}
3. Explain in detail Huffman coding algorithm and compare this with the other
types of coding.
4, Explain the properties of entropy and with suitable example. Explain the
entropy of binary memory less source.
5, Discuss source coding theorem, give the advantages and disadvs
channel coding in detail and discuss the data conipaction.
antages of
Derive the channel capacity theorem.
Explain the information capacity theorem.
Explain the Shannon-Fano coding.
Explain the discrete memoryless channels.
1
ule Ow
ye aN
}
Gessivne wilervetle Which QoQ
