ECT306 INFORMATION THEORY

& CODING

7/30/2022
 Module 2-Channels and Channel Coding
• Discrete memoryless channels. Capacity of discrete memoryless
channels. Binary symmetric channels (BSC), Binary Erasure
channels (BEC). Capacity of BSC and BEC. Channel code. Rate of
channel code. Shannon‟s channel coding theorem (both
achievability and converse without proof) and operational meaning
of channel capacity.
• Modeling of Additive White Gaussian channels. Continuous-input
TRACE KTU
channels with average power constraint. Differential entropy.
Differential Entropy of Gaussian random variable. Relation
between differential entropy and entropy. Shannon-Hartley theorem
(with proof – mathematical subtlities regarding power constraint
may be overlooked).
• Inferences from Shannon Hartley theorem – spectral efficiency
versus SNR per bit, power-limited and bandwidth-limited regions,
Shannon limit, Ultimate Shannon limit.
7/30/2022
 RATE OF INFORMATION TRANSMISSION OVER A
DISCRETE CHANNEL
• We have the entropy of the input symbols given by

• Consider a discrete memoryless channel accepting symbols at

TRACE KTU
the rate of , rs message symbols/sec .
• The average rate at which information is going into the
channel is given by

7/30/2022
• At the receiver, it is not possible to reconstruct the input
symbol sequence with certainty by operating on the receiving
sequence.
• This is due to errors introduced when the signals pass through
the channel.
• Some amount of information is lost in the channel due to
noise.
• This information which is lost in the channel has been called
TRACE KTU
equivocation H(X/Y). Hence the net amount of information
which is the mutual information I(X;Y) , is given by equation
as

7/30/2022
• The average rate of information transmission Rt is given by,

• or

TRACE KTU

7/30/2022
CAPACITY OF A DISCRETE MEMORYLESS CHANNEL
• The capacity of a discrete memoryless noisy channel is defined
as the maximum possible rate of information transmission over
the channel. The maximum rate of transmission occurs when
the source is matched to the channel.

TRACE KTU
• Therefore channel capacity C is defined as

7/30/2022
 SHANNON‟S THEOREM ON CHANNEL CAPACITY
(SHANNON‟S SECOND THEOREM)

Positive Statement
TRACE KTU
• Shannon‟s theorem on channel capacity states that “when the
rate of information transmission Rt ≤ C , then there exists a
coding technique which enables transmission over a channel
with as small a probability of error as possible, even in the
presence of noise in the channel.”
7/30/2022
 This theorem indicates that for Rt ≤ C , transmission of
information is achieved without errors, even in the presence of
noise.

Negative Statement

“If Rt > C , then reliable transmission of information is not

TRACE KTU
possible without errors. Thus when Rt > C , then the errors
cannot be controlled by any coding technique and the
probability of error of receiving the correct message becomes
close to unity.”

7/30/2022
 CHANNEL EFFICIENCY AND REDUNDANCY

TRACE KTU

7/30/2022
 COMMUNICATION CHANNELS
• In the channel diagram channel input belongs to source
alphabet A with 3 symbols and channel output belongs to other
alphabet B with 4 symbols.

TRACE KTU

7/30/2022
 SPECIAL TYPE OF CHANNELS
• Symmetric/Uniform Channels
• Binary Symmetric Channels (BSC)
• Binary Erasure Channels (BEC)

TRACE KTU

7/30/2022
 Symmetric or Uniform Channel
• A channel is said to be symmetric or uniform channel, if the
second and subsequent rows of the channel matrix contain the
same elements as that of first row, but in a different order.

TRACE KTU

7/30/2022
 TRACE KTU

7/30/2022
 Channel Capacity of Symmetric or Uniform Channel
• Consider a symmetric or uniform channel, there are „s‟ number
of output messages and „r‟ number of input messages.
• The channel matrix or probability transition matrix is given by

TRACE KTU

• Since it is a symmetric or uniform channel each rows of

channel matrix contain same elements but in different order.

7/30/2022
• So channel matrix can be written as

TRACE KTU
• Where P1, P2, P3…….., Ps-3, Ps-2, Ps-1, Ps are the conditional
probabilities P(yj/xi).
• The sum of all the elements in any row of the channel matrix is
equal to unity.

7/30/2022
The equivocation H(Y/X) is given by

TRACE KTU

7/30/2022
We know

Let

or
TRACE KTU
The mutual information I(X;Y) is given by

7/30/2022
The channel capacity is given by

h is a constant, therefore

TRACE KTU
• The entropy of a output symbol becomes maximum if and only
when all the received symbols become equiprobable.
• Since there are s number of output symbols, we have

So we get channel capacity of symmetric or uniform channel as,

7/30/2022
Example 1

• Solution
TRACE KTU
Channel capacity is given by

rs is 1 message-symbol/sec
7/30/2022
Example 2

• Solution

TRACE KTU
Channel capacity is given by

7/30/2022
 Binary Symmetric Channel (BSC)
• A symmetric channel which has two input and two
output is called Binary Symmetric Channel.
• Most commonly and widely used channel

TRACE KTU

7/30/2022
Let

Let p = probability of error

= probability of reception of „1‟ when „0‟ is transmitted

= probability of reception of „0‟ when „1‟ is transmitted

Channel matrix of a BSC can be written as

TRACE KTU

7/30/2022
• Since it is a symmetric channel the equivocation is given by

To Find H(Y)
TRACE KTU
Entropy of output symbol is given by

7/30/2022
 TRACE KTU
• Mutual information I(X;Y) is given by

7/30/2022
• Since BSC is a symmetric channel, the channel capacity is
found by using the general equation of symmetric channel
capacity.

TRACE KTU
• In case of BSC no of output symbols s=2

7/30/2022
• When the input symbol probability
• Mutual information I(X;Y) becomes

TRACE KTU

• When the input symbols become equiprobable, the mutual

information maximizes and becomes equal to channel capacity C.
7/30/2022
Example 1 (Previous Unvi Question)

Solution:
Mutual information
TRACE KTU

Channel capacity
7/30/2022
 BINARY ERASURE CHANNEL (BEC)
• Whenever an error occurs, the symbol will be received as “y”.
• No decision will be made about the information
• An immediate request will be made through a reverse channel
for retransmission (ARQ – Automatic Repeat Request) of the
transmitted signal till a correct symbol is received at the output.
• Since the error is totally erased in this type of channel, it is
TRACE KTU
called „Binary Erasure Channel‟.
• The disadvantage with this is the requirement of a reverse
channel.

7/30/2022
 Channel Diagram of BEC

TRACE KTU

7/30/2022
 Channel Capacity of BEC

TRACE KTU

7/30/2022
 TRACE KTU

7/30/2022
 TRACE KTU

7/30/2022
 TRACE KTU

7/30/2022
 TRACE KTU

7/30/2022
Example 1 (Previous Unvi Question) - BSC

Solution:

TRACE KTU
Mutual information

7/30/2022
 = 0.9799 bits/message symbol

= 0.8113 bits/message symbol

Channel capacity
TRACE KTU
= 0.1887 bits/message symbol

7/30/2022
Example 2 - BSC
Q. A message source produces two independent symbols A and B
with probabilities P(A)=0.4 and P(B)=0.6. Calculate the
efficiency of the source and hence its redundancy. If the
symbols are received in average with 4 in every 100 symbols
in error, calculate the transmission rate of the system. Draw its
channel diagram also.
Solution:

7/30/2022
 = 0.7331 bits/messag e symbol
Transmission rate
= 73.31 bits/sec

7/30/2022
Channel Diagram

7/30/2022
 Continuous Sources and Channels
Differential Entropy-Entropy of continuous signals
• The entropy in the case of discrete message symbols is given by
• That means the entropy of a continuous random variable is
infinitely large.
• i.e, the uncertainty associated with a CRV is of the order of
infinity.

• Therefore the differential entropy can be defined as,

 Maximization of Entropy
• In the case of discrete source symbols, the entropy becomes
maximum when all the symbols are equiprobable.

• In the case of practical continuous sources, there may be

different constraints such as peak signal constraint, average
signal constraint, average power restriction or peak power
limitation etc.
• The objective is to maximize the entropy function subjected to
such restrictions.
• Normalizing constraint which follows from the condition of
pdf is
 Peak Signal Limitation
• When the signal is limited to ±M, then

• This kind of signal limitation is found in practical cases of

AM,FM and pulse modulation techniques.
• The entropy becomes maximum, under peak signal constraint,
if the signal is uniformly distributed.
i.e.

• Maximum value of Entropy is given by,

• If M is the peak signal voltage, then the peak signal power Pm
is given by,

• Then, maximum entropy is given by,

• If the signal is bandlimited to B Hz and is sampled at Nyquist

rate rs=2B samples/sec , then maximum entropy is given by,
 Average signal limitation
• Under this limitation we have

• This kind of limitation come across in pulse amplitude

modulation and also in analog amplitude modulation, with
average carrier amplitude limitation.
• If the average value equal to λ, then the ccontinuous entropy of
X maximizes when it is exponentially distributed with
parameter 1/λ .
i.e.,
• The maximum entropy is given by,

• If the signal is bandlimited to B Hz and is sampled at Nyquist

rate rs=2B samples/sec , then
 Average power limitation
• Under this limitation we have

• Random noise with specified variance, audio frequency

telephony and other similar situations are examples of some
instances where average power limitation being specified.

• The entropy will be maximum when it is Gaussian distribution

with mean zero and variance σ 2 .

i.e.,
• The maximum entropy is given by

• If the signal is bandlimited to B Hz and is sampled at Nyquist

rate rs=2B samples/sec , then

• If X represents Gaussian noise (AWGN) with an average

power σ 2 =N, then
 Average power limitation with unidirectional
distribution (causal systems)
• Under this limitation we have

• AM with average carrier power constraint is an example.

• The maximum entropy is given by

• If the signal is bandlimited to B Hz and is sampled at Nyquist

rate rs=2B samples/sec , then
Numerical Problem
Q. A continuous random variable, X is uniformly distributed in the
interval (0, 4). Find the differential entropy H(X). Suppose that X is
a voltage which is applied to an amplifier whose gain is 8. Find the
differential entropy of the output of the amplifier.
• Solution
The PDF of X is given by,

=1/4
Differential entropy

H(X)=2 bits/sample
Let Y be the output of amplifier
Y=8X (1)
By theorem of probability density function

Differentiating eqn (1)

dy = 8 dx
dx/dy =1/8
f(y)=1/32
X varies from 0 to 4, Y varies from 0 to 32
Differential entropy of Y is,

= 5 bits/sample
 Joint, Conditional Entropy
• Consider a pair of continuous random variable (X, Y )
distributed according to the joint p.d.f. f(x, y). The joint
entropy is given by

• Conditional entropy is given by

 Mutual Information
• Mutual information I(X;Y) is given by

• The mutual information between two continuous random

variables X, Y with joint p.d.f f(x, y) is given by
 Rate of Transmission and Channel Capacity
The rate of transmission of continuous signal is given by

Channel capacity is given by

Consider a continuous random variable Y defined by,
Y=X+N
Where X & N are statistically independent. Show that the
conditional entropy of Y, given X is, H(Y/X)=H(N).
Where H(N) is the differential entropy of N.
Proof
The equivocation for continuous signal is given by,

We have,
Since y = x+n
dy=dn with x constant
Also y-x=n
Substitute these in above equation
Substitute eqn(4) in (3) we get,
Properties of Mutual Information
Property 1
Property 2
Proof
Put
Property 3
Proof

Also

We have
Property 4
Proof

From (1)

Substitute (3) in (2)

 Gaussian Channel

• So far we have studied limits on the maximum

rate at which information can be sent over a
channel reliably in terms of the channel
capacity.
• We next formulate the information capacity
theorem for band limited, power limited
Gaussian channels.
 Gaussian Channel
• An important and useful channel is the Gaussian channel.
Source Output
data data

Channel Physical Demodulator Channel

Modulator
encoder channel and detector decoder

Input Output
waveform waveform

y(t )  x(t )  n(t )

 Gaussian Channel
• This is a time discrete channel with output Yk at time k.
• This output is the result of the sum of the input Xk and the
noise Nk.
• This noise is drawn from a Gaussian distribution with mean
zero and variance .
• Thus, Yk=Xk+Nk
• The noise Nk is independent of the input Xk.
 Capacity of a Gaussian Channel
• Since the transmitter is usually power-limited (Let S is the
transmitted signal power in Watts), let us put a constraint on
the average power in Xk .

2
E[ X k ]  S
wherek  1,2,...K

• Thus the information capacity of the channel is given by

C  Max{I ( X ; Y ) E[ X ]  S}
2
k
f xk ( x )

72
 Capacity of a Gaussian Channel

I ( X k ; Yk )  H (Yk )  H (Yk X k )
• Xk and Nk are independent random variables
• Therefore
H (Yk X k )  H ( N k )

• Hence we can write,

I ( X k ; Yk )  H (Yk )  H ( N k )

73
 Capacity of a Gaussian Channel
• If we assume Yk to be Gaussian, and Nk is Gaussian by
definition, then Xk is also Gaussian.
• In order to maximize the mutual information between the
channel input Xk and channel output Yk the transmitted signal
should be Gaussian.
• Therefore we can write

C  I ( X k ; Yk ) E[ X k2 ]  S

and also Xk is Gaussian

 Capacity of a Gaussian Channel
• We know that if two independent Gaussian random variables
are added, the variance of the resulting Gaussian random
variable should be the sum of the variances.

• Let N0B is the variance of noise random variable.

• Where N0/2 (Also represented as η/2)is the two sided power

spectral density of noise signal.

• Therefore, the variance of the received sample Yk equals

 Capacity of a Gaussian Channel
• It can be shown that the maximum differential entropy of a
Gaussian random variable with variance σ2 is
1
H (Yk ) max  log 2 (2e 2 )
2
1
H (Yk ) max  log 2 [2e( S  N 0 B)]
2
1
H ( N k ) max  log 2 [2e( N 0 B)]
2
• Channel capacity

C  H (Yk )  H ( N k )max
C  H (Yk ) max  H ( N k ) max 
Capacity of a Gaussian Channel

C  H (Yk ) max  H ( N k ) max

1 1
C  log 2 [2e( S  N 0 B)]  log 2 [2e( N 0 B)]
2 2
1  2e( S  N 0 B) 
C  log 2  
2  2e( N 0 B) 
1  S 
C  log 2 1  bits / channeluse
2  N0 B 
 Capacity of a Gaussian Channel
1  S 
C  log 2 1  bits / channeluse
2  N0 B 
• We are transmitting 2B samples per second, i.e.,the channel is
being 2B times in one second.
• Therefore, the information capacity can be expressed as

1  S 
C  2 B log 2 1  
2  N0 B 
 S 
C  B log 2 1  bits / sec
 N0 B 
 Capacity of a Gaussian Channel
 S 
C  B log 2 1  bits / sec
 N0 B 

• Let N=N0B is the noise power, then channel capacity can be

written as
 S
C  B log 2 1  bits / sec
 N
• This basic formula for the capacity of the band-limited ,
AWGN waveform channel with band-limited and average
power – limited input was first derived by Shannon in 1948.
• It is known as Shannon‟s third theorem, or the Information
Capacity Theorem or Shannon- Hartley theorem.
 Capacity of a Gaussian Channel
 S
C  B log 2 1  bits / sec
 N
C  B log 2 1  SNRbits / sec
• SNR is the signal to noise ratio.
• Capacity varies linearly with Bandwidth, B and
logarithmically with SNR.
 Information Capacity Theorem
• The Information Capacity Theorem is one of the
important result in Information Theory.
• In a single formula one can see the trade off between
the channel bandwidth, the average transmitted power
and the noise power spectral density.
• Given the channel BW and the SNR the channel
capacity can be computed.
• The channel capacity is the fundamental limit on the
rate of reliable communication for a power limited
and bandlimited Gaussian channel.
Problems
• Given an AWGN channel with 5 K Hz bandwidth and the
noise power spectral density η/2=10-9 W/Hz. The signal power
required at the receiver is l mW. Calculate the capacity of this
channel.
Solution:
Given η/2=N0/2=10-9
S= l mW
B=5 KHz
C=?
• A telephone channel has a BW of 3000Hz and the SNR=20dB.
Determine the channel capacity. If the SNR is increased to
25dB, determine the capacity.

Solution:

S/N=?
B=3000 Hz
C=?
 Information Capacity Theorem or
Shannon – Hartley theorem
It states that the capacity of a band limited Gaussian
channel with AWGN is given by,

where
B=channel bandwidth in Hz
S=Signal power in Watts
N=Noise power in watts=N0B or ηB
where the two sided power spectral density of noise is
(N0/2) watts/Hz or (η/2)
Implications of Shannon – Hartley theorem
1st Implication or Capacity of a channel with
infinite bandwidth
From Shannon Hartley Law we have,

• When B is increased, channel capacity C also increases and ,

the maximum rate of information transmission can be
enhanced to any value as we need.
• However, the channel capacity does not become infinite.
• This is because, B increases, the noise power N which is
dependent on B, also increases thereby reducing (S/N) .
• The product of B and will increase only up to
a certain value and becomes constant with increasing B.
• This value is denoted as
 Shannon‟s Limit
• An ideal system is defined as one that transmits data at a bit
rate Rt equal to the channel capacity C.
• Then the average transmitted power can be expressed as,

• Where Eb = transmitted energy per bit in joules

Using N=ηB and S= EbC in eqn (1) we get for an ideal system

or

The quantity C/B is called “ Bandwidth efficiency”

• The quantity Eb/η is given by

• When (Rt /B) is plotted as a function of (Eb/η), we

get the bandwidth efficiency diagram.

• The resulting curve represents the capacity boundary

for which Rt =C.
Bandwidth-Efficiency Diagram
Based on the diagram following observations are made:
1. For infinite bandwidth, the signal -to - noise ratio Eb/η
approaches the limiting value.

Using L‟ Hospital Rule, the above limit can be evaluated as

below:
• Taking ln on both sides,

• Differentiating,

• Differentiating both numerator and denominator of the RHS of

eqn (2) with respect to „x‟, we get
This value 0.693 or -1.6 dB is called “Shannon’s Limit”..
• The Shannon‟s limit is a fraction.
• This implies that for very large bandwidths, reliable
communication is possible even for the case when the
signal power is less than the noise power.
• The channel capacity corresponding to this limiting
value is given by,
2. The capacity boundary, defined by the curve for
critical bit rate Rt=C.
It separates combinations of system parameters that
have the potential for supporting error free
transmission (Rt<C) from those for which error-free
transmission is not possible (Rt>C).

[Link] Bandwidth-Efficiency diagram highlights trade-

off between (Eb/η) and (Rt/B).
• This is given by 2nd implication of Shannon-Hartley
law.
 Information Capacity Theorem or
Shannon – Hartley theorem
It states that the capacity of a band limited Gaussian
channel with AWGN is given by,

where
B=channel bandwidth in Hz
S=Signal power in Watts
N=Noise power in watts=N0B or ηB
where the two sided power spectral density of noise is
(N0/2) watts/Hz or (η/2)
Implications of Shannon – Hartley theorem
1st Implication or Capacity of a channel with
infinite bandwidth
From Shannon Hartley Law we have,

• When B is increased, channel capacity C also increases and ,

the maximum rate of information transmission can be
enhanced to any value as we need.
• However, the channel capacity does not become infinite.
• This is because, B increases, the noise power N which is
dependent on B, also increases thereby reducing (S/N) .
• The product of B and will increase only up to
a certain value and becomes constant with increasing B.
• This value is denoted as
 Shannon‟s Limit
• An ideal system is defined as one that transmits data at a bit
rate Rt equal to the channel capacity C.
• Then the average transmitted power can be expressed as,

• Where Eb = transmitted energy per bit in joules

Using N=ηB and S= EbC in eqn (1) we get for an ideal system

or

The quantity C/B is called “ Bandwidth efficiency”

• The quantity Eb/η is given by

• When (Rt /B) is plotted as a function of (Eb/η), we

get the bandwidth efficiency diagram.

• The resulting curve represents the capacity boundary

for which Rt =C.
Bandwidth-Efficiency Diagram
Based on the diagram following observations are made:
1. For infinite bandwidth, the signal -to - noise ratio Eb/η
approaches the limiting value.

Using L‟ Hospital Rule, the above limit can be evaluated as

below:
• Taking ln on both sides,

• Differentiating,

• Differentiating both numerator and denominator of the RHS of

eqn (2) with respect to „x‟, we get
This value 0.693 or -1.6 dB is called “Shannon’s Limit”..
• The Shannon‟s limit is a fraction.
• This implies that for very large bandwidths, reliable
communication is possible even for the case when the
signal power is less than the noise power.
• The channel capacity corresponding to this limiting
value is given by,
2. The capacity boundary, defined by the curve for
critical bit rate Rt=C.
It separates combinations of system parameters that
have the potential for supporting error free
transmission (Rt<C) from those for which error-free
transmission is not possible (Rt>C).

[Link] Bandwidth-Efficiency diagram highlights trade-

off between (Eb/η) and (Rt/B).
• This is given by 2nd implication of Shannon-Hartley
law.
Implications of Shannon – Hartley theorem
2nd Implication - Bandwidth-SNR Trade Off
• An important implication of Shannon-Hartley law is the
exchange of bandwidth with, signal to noise ratio and vice
versa.

• Therefore Channel Capacity,

• Keeping the channel capacity C2 same as C1 and if signal-to-
noise ratio is increased to 15, then

• We get B2=3 KHz

• Since the noise power N=ηB , as the bandwidth gets reduced
from 4 to 3 KHz, the noise also decreases indicating an
increase in signal power as shown below.
• We have N1= ηB1= (η) (4KHz)
• And N2= ηB2= (η) (3KHz)
• Thus a 25% reduction in Bandwidth from 4 KHz to 3 KHz
requires a 60 % approximate increase in signal power for
maintaining the same channel capacity.
• Let us look into the exact significance by drawing the “trade -
off curve”.
• From Shannon-Hartley law
Bandwidth to (S/N) Trade-Off Curve
• It shows a plot of (B/C) as a function of (S/N).
• Using this trade off curve the same channel capacity can be
obtained by increasing bandwidth if (S/N) is small.
• Furthermore, the curve also indicates that there exists a
threshold point at around (S/N)=10 up to which the exchange
rate of bandwidth with (S/N) is advantageous.
• Beyond (S/N)=10, the reduction in B with increasing (S/N) is
very poor.
• FM, PM and PCM systems including DM and ADM systems
require larger bandwidths with reasonably good (S/N) ratio.