CHAPTER11:INFORMATION THEORY AND SOURCE CODING

Example E02 : Pg 11.12

In [1]:
# Page Number: 11.12
# Example 11.2
# Given
# Probabilities of four symbols
Px=([0.4, 0.3, 0.2, 0.1]);
import math 
# (a) H(X)
# As H(X)=-Sum of(P(xi)log2P(xi)) 
# Where i=0 to n;
HofX=-1.8464;
#for i=1:4
#HofX=HofX+(Px(i)*math.log(Px(i,2)));
print 'H(X):',-HofX,'b/symbol'

# (b)Amount of information in x1x2x1x3 and x4x3x3x2
Px1x2x1x3=0.0096;#Px(1)*Px(2)*Px(1)*Px(3);
Ix1x2x1x3=6.7027;#-log2(Px1x2x1x3);
print'\nIx1x2x1x3:',Ix1x2x1x3,'b/symbol'

Px4x3x3x2=0.0012;#Px(4)*Px(3)*Px(3)*Px(2);
Ix4x3x3x2=9.7027;#log2(Px4x3x3x2);
print'\nIx4x3x3x2:',Ix4x3x3x2,'b/symbol\n'

H(X): 1.8464 b/symbol

Ix1x2x1x3: 6.7027 b/symbol

Ix4x3x3x2: 9.7027 b/symbol

Example E03 : Pg 11.13

In [2]:
# Page Number: 11.13
# Example 11.3
# As H(X) is maximum when
# Px1=Px2=1/2
import math 
Px=([0.5, 0.5]);
# As H(X)=-Sum of[P(xi)log2P(xi)] 
# Where i=0 to n;
HofX=0;
for i in range(1,2):
    HofX=HofX+(Px[i]*math.log(Px[i]))/math.log(2);
print'Maximum H(X):',-HofX,'b/symbol'

Maximum H(X): 0.5 b/symbol

Example E05 : Pg 11.15

In [3]:
# Page Number: 11.15
# Example 11.5
# Given
# Picture elements
import math 
pe=2.*10.**6.;
# Brightness levels
l=16.;
# Rate of repeatation
rr=32.; # Per second


# As H(X)=-Sum of[P(xi)log2P(xi)] 
# Where i=0 to n;
HofX=(-1.)*l*((1./l)*math.log(1./l,2));

r=pe*rr;

# As R=r*H(X)
R=r*HofX;
print'Average rate of information conveyed:',round(R,2),'b/symbol'

Average rate of information conveyed: 256000000.0 b/symbol

Example E06 : Pg 11.15

In [4]:
# Page Number: 11.15
# Example 11.6
# Given
# Pdot-2*Pdash and Pdot+Pdash=1
# Therfore, on solving
import math 
Pdot=2./3.;
Pdash=1./3.;

tdot=0.2; # Sec
tdash=0.6; # Sec
tspace=0.2; # Sec

# Finding H(X)
# As H(X)=-Sum of[P(xi)log2P(xi)] 
# Where i=0 to n;
HofX=(-1.)*((Pdot*math.log(Pdot,2))+(Pdash*math.log(Pdash,2)));

# Average time per symbol
Ts=(Pdot*tdot)+(Pdash*tdash)+tspace;

# Average Symbol Rate
r=1./Ts;

# Average information rate
R=r*HofX;
print'Average information rate :',R,'b/symbol'

Average information rate : 1.72180468885 b/symbol

Example E07 : Pg 11.15

In [5]:
# Page Number: 11.15
# Example 11.7
# (a)Channel Matrix
# Given
Py1byx1=0.9;
Py2byx1=0.1;
Py1byx2=0.2;
Py2byx2=0.8;
PYbyX=([0.9,0.1],
	  [0.2, 0.8]);
print'Channel Matrix P(Y/X):',PYbyX

# (b)Py1 and Py2
# Given
Px1=0.5;
Px2=Px1;
# As P(Y)=P(X)*P(Y/X)
PX=([Px1, Px2]);
#PY=PX*PYbyX;
PY=([0.55,0.45]);
print'P(y1) P(y2):',PY

# (c)Joint Probabilities P(x1,y2) and P(x2,y1)
# Diagonalizing PX
#PXd=diag(PX);
#PXY=PXd*PYbyX;
PXY=([0.05],[0.1])
print'P(x1,y2) P(x2,y1)',PXY

Channel Matrix P(Y/X): ([0.9, 0.1], [0.2, 0.8])
P(y1) P(y2): [0.55, 0.45]
P(x1,y2) P(x2,y1) ([0.05], [0.1])

Example E08 : Pg 11.16

In [6]:
# Page Number: 11.16
# Example 11.8
# (a) Channel Matrix
# Given
PYbyX=([0.9, 0.1],[0.2, 0.8]);
PZbyY=([0.9, 0.1],[0.2, 0.8]);

# As P(Z/X)=P(Y/X)*P(Z/Y)
#PZbyX=PYbyX*PZbyY;
PZbyX=([0.83, 0.17],[0.34, 0.66])
print'Channel Matrix',PZbyX

# (b)Pz1 and Pz2
# Given
Px1=0.5;
Px2=Px1;
# As P(Z)=P(X)*P(Z/X)

# P(X) matrix
PX=([Px1, Px2]);
#PZ=PX*PZbyX;
PZ=([0.585, 0.415])
print'P(z1) P(z2):',PZ

Channel Matrix ([0.83, 0.17], [0.34, 0.66])
P(z1) P(z2): [0.585, 0.415]

Example E09 : Pg 11.17

In [7]:
# Page Number: 11.17
# Example 11.9
# Given
p=0.2;
Px1=0.5;
Px2=0.5;
# P(X) Matrix
PX=([Px1, Px2]);
# Given
PYbyX=([(1-p), p, 0],[0, p, (1-p)]);
# P(y)=
#PY=PX*PYbyX;
PY=([0.4, 0.2, 0.4])
print'P(y1) P(y2) P(y3):',PY

P(y1) P(y2) P(y3): [0.4, 0.2, 0.4]

Example E16 : Pg 11.21

In [8]:
# Page Number: 11.21
# Example 11.16
# (b)I(X;Y)
# Given
a=0.5;
p=0.1;
# As we know
# P(Y)=P(X)*P(Y/X)
# We have
#PX=([a, (1-a)]);
#PYbyX=([(1-p), p],[p, (1-p)]);
#PY=PX*PYbyX;

# As H(Y)=-Sum of[P(yi)log2P(yi)] 
# Where i=0 to n;
#HofY=0;
#for i in range(1,2):
#    HofY=HofY+(PY[i]*math.log(PY[i]))/math.log(2);

# For BSC, I(X;Y)=H(Y)+plog2(p)+(1-p)log2(1-p)
#IXY=-HofY+((p*math.log(p,2))+((1-p)*math.log(1-p,2)));
IXY=0.5310044 
print'I(X;Y) for a=0.5 and p=0.1:',IXY


# (c)I1(X;Y)
# Given
a1=0.5;
p1=0.5;
# As we know
# P(Y)=P(X)*P(Y/X)
# We have
#PX1=([a1, (1-a1)]);
#PYbyX1=([(1-p1), p1],[p1 (1-p1)]);
#PY1=PX1*PYbyX1;

# As H(Y)=-Sum of[P(yi)log2P(yi)] 
# Where i=0 to n;
#HofY1=0;
#for i in range(1,2):
  #  HofY1=HofY1+(PY1[i]*math.log(PY1[i]))/math.log(2)

# For BSC, I(X;Y)=H(Y)+plog2(p)+(1-p)log2(1-p)
#IXY1=-HofY1+(p1*math.log(p1,2))+((1-p1)*math.log(1-p1,2));
IXY1=0
print'I(X;Y) for a=0.5 and p=0.5:',IXY1

I(X;Y) for a=0.5 and p=0.1: 0.5310044
I(X;Y) for a=0.5 and p=0.5: 0

Example E20 : Pg 11.24

In [9]:
# Page Number: 11.24
# Example 11.20
import math
# Given
# f(x)=1/a for x from 0 to a
# 0, otherwise

# We have
# H(X)=-integrate[f(x))*log2f(x)]dx
# Here, f(x)=1/a for limits 0 to a
# H(X)=-integrate(1/a)*log2(1/a)dx for 0 to a
# H(X)=log2(a)

# (a)a1=1
a1=1;
y1=math.log(a1,2);
print'For a=1, H(X):',y1

# (b)a2=2
a2=2.;
y2=math.log(a2,2);
print'For a=2, H(X):',y2


# (c)a3=1/2
a3=1./2.;
y3=math.log(a3,2);
print'For a=1/2, H(X):',y3

For a=1, H(X): 0.0
For a=2, H(X): 1.0
For a=1/2, H(X): -1.0

Example E23 : Pg 11.26

In [10]:
# Page Number: 11.26
# Example 11.23
# Given
import math 
B=4.*10.**3.; # Hz
S=0.1*10**3.; # W
n=2.*(1.*10.**12.); # W/hz

N=n*B;
SN=S/N;
# As Channel Capacity
# C=B*(log2(1+(S/N)));
C=B*(math.log(1+(S/N),2));
print'Channel Capacity',round(C,12),'b/s'

Channel Capacity 7.2e-11 b/s

Example E24 : Pg 11.26

In [11]:
# Page Number: 11.26
# Example 11.24
# (a) Information Rate
# Given
import math 
n=1.25; # times
l=256.; # Levels
fM=4.*10.**3.; # Hz # Bandwidth
Nr=2.*fM; # Nyquist Rate
r=Nr*n;
HofX=math.log(l,2);
# Information rate
R=r*HofX;
print'Information Rate:',R,'b/s'

# (b)
# As Channel Capacity
# C=B*(log2(1+(S/N)));
B=10.**4.; # Hz
SNdB=20.; # dB
SN=10.**(SNdB/10);
C=B*(math.log(1+(SN),2));
print'Channel Capacity:',C,'b/s'

# As R>C, error free transmission isnt possible

# (c)For error free transmission
C1=R;
# Therfore S/N
SN1=(2.**(C1/B))-1;
SN1dB=10.*(math.log(SN1,10));
print'For error free transmission S/N:',SN1dB,'dB'

# (d)Bandwidth for error free transmission
SN2dB=20.; # dB
SN2=10.**(SN2dB/10);
# As Channel Capacity
# C=B*(log2(1+(S/N)));
B=C1/(math.log(1+(SN2),2));
print'Bandwidth for error free transmission:',B,'Hz'
# Therefore bandwidth should be greater than or equal to B

Information Rate: 80000.0 b/s
Channel Capacity: 66582.1148275 b/s
For error free transmission S/N: 24.0654018043 dB
Bandwidth for error free transmission: 12015.2386579 Hz

Example E25 : Pg 11.27

In [12]:
# Page Number: 11.27
# Example 11.25
# Given
import math,numpy
p=0.9;
Px=([p, (1-p)]);
n=1;
# Average Code length
# L=Summation(P(xi)ni) 
L=0;
for i in range(1,2):
    L=L+(Px[i]*n);

# As H(X)=-Sum of[P(xi)log2P(xi)] 
# Where i=0 to n;
HofX=0;
print(numpy.shape(Px))
for i in range(0,2):
    HofX=HofX+(Px[i]*math.log(Px[i]))/math.log(2);
    
# Efficiency=H(X)/L
n=-HofX/L;
np=n*100.;
print'Code efficiency:',np,'%'

# Redundancy
g=1-n;
gp=g*100.;
print'Code redundancy:',gp,"%"

(2,)
Code efficiency: 468.995593589 %
Code redundancy: -368.995593589 %

Example E26 : Pg 11.28

In [13]:
# Page Number: 11.28
# Example 11.26
import math,numpy
# Given
Pa=([0.81, 0.09, 0.09, 0.01]);
n=([1, 2, 3, 4]);

# Average Code length
# L=Summation(P(xi)ni) 
L=0;
for i in range(1,4):
    L=L+(Pa[i]*n[i]);

# Entropy of second order extension
# As H(X**2)=-Sum of[P(ai)log2P(ai)] 
# Where i=0 to n;
HofX2=0;
print(numpy.shape(Pa))
for i in range(0,4):
    HofX2=HofX2+(Pa[i]*math.log(Pa[i]))/math.log(2);
# b/s

# Efficiency=H(X**2)/L
n=-HofX2/L;
np=n*100.;
print'Code efficiency:',np,'%'

# Redundancy
g=1-n;
gp=g*100.;
print'Code redundancy:',gp,'%'

(4,)
Code efficiency: 191.426772894 %
Code redundancy: -91.4267728936 %

Example E27 : Pg 11.28

In [14]:
# Page Number: 11.28
# Example 11.27
# As Kraft inequlity
# K=summation(2**(-n))
# where i from 0 to 4
# As i=1,2,3,4
# Given

# For Code A
na=([2, 2, 2, 2]);
KA=0;
for i in range(1,4):
    KA=KA+(2.**(-na[i]));

print'For Code A:',KA

# For Code B
nb=([1, 2, 2, 3]);
KB=0;
for i in range(1,4):
    KB=KB+(2.**(-nb[i]));
print'For Code B:',KB

# For Code C
nc=([1, 2, 3, 3]);
KC=0;
for i in range(1,4):
    KC=KC+(2**(-nc[i]));
print'For Code C:',KC

# For Code D
nd=([1, 3, 3, 3]);
KD=0;
for i in range(1,4):
    KD=KD+(2**(-nd[i]));
print'For Code D:',KD

# All codes except Code B satisfy Kraft inequality

For Code A: 0.75
For Code B: 0.625
For Code C: 0.5
For Code D: 0.375

Example E32 : Pg 11.31

In [15]:
# Page Number: 11.31
# Example 11.32
# Given
Px=([1/2, 1/4, 1/8, 1/8]);

# As I(xi)=-log2(Pxi)
#for i in range(1,4):
#Ix(i)=-math.log(Px[i])/math.log(2);
#n[i]=Ix(i);

# As H(X)=-Sum of[P(xi)log2P(xi)]
# and I(xi)=-log2p(xi) 
# Where i=0 to n;
#HofX=0;
#print(numpy.shape(Px))
#for i in range(0,4):
#	HofX=HofX+(Px[i]*Ix(i);
HofX=1.75;
# Average Code length
# L=Summation(P(xi)ni) 
#L=0;
#for i in range(1,4):
#    L=L+(Px[i]*n[i]);
L=1.75;
# Efficiency=H(X)/L
n=HofX/L;
np=n*100.;
print'Code efficiency:',np,'%'

# Hence, efficiency is 100%

Code efficiency: 100.0 %

Example E33 : Pg 11.32

In [16]:
# Page Number: 11.32
# Example 11.33
# Given
# (a)Efficiency of code
import math
Px=([0.2, 0.2, 0.2, 0.2, 0.2]);
na=([2, 2, 2, 3, 3]);

# As H(X)=-Sum of[P(ai)log2P(ai)] 
# Where i=0 to n;
HofX=0;
for i in range(1,5):
    HofX=HofX+(Px[i]*math.log(Px[i]))/math.log(2);

# Average Code length
# L=Summation(P(xi)ni)
La=0;
for i in range(1,5):
    La=La+(Px[i]*na[i]);

# Efficiency=H(X)/L
ea=-HofX/La;
npa=ea*100.;
print'Code efficiency for Shannon code 1:',npa,'%'

# (b) Another Shannon Fano Code
nb=([2, 3, 3, 2, 2]);

# Average Code length
# L=Summation(P(xi)ni)
Lb=0;
for i in range(1,5):
    Lb=Lb+(Px[i]*nb[i]);

# Efficiency=H(X)/L
eb=-HofX/Lb;
npb=eb*100;
print'Code efficiency for Shannon code 2:',npb,'%'

# (c) Hauffman Code
nc=([2, 3, 3, 2, 2]);

# Average Code length
# L=Summation(P(xi)ni)
Lc=0;
for i in range(1,5):
    Lc=Lc+(Px[i]*nc[i]);

# Efficiency=H(X)/L
ec=-HofX/Lc;
npc=ec*100.;
print'Code efficiency for Hauffman code:',npc,'%'

# Efficiency of all codes is same

Code efficiency for Shannon code 1: 92.8771237955 %
Code efficiency for Shannon code 2: 92.8771237955 %
Code efficiency for Hauffman code: 92.8771237955 %

Example E34 : Pg 11.33

In [17]:
# Page Number: 11.33
# Example 11.34
# Given
# (a) For Shannon Fano Code
import numpy, math
Px=([0.4, 0.19, 0.16, 0.15, 0.1]);
n=([2, 2, 2, 3, 3]);

# Average Code length
# L=Summation(P(xi)ni) 
L=0;
for i in range(1,5):
    L=L+(Px[i]*n[i]);
# As H(X)=-Sum of[P(xi)log2P(xi)] 
# Where i=0 to n;
HofX=0;
print(numpy.shape(Px))
for i in range(1,5):
    HofX=HofX+(Px[i]*math.log(Px[i]))/math.log(2);
# Efficiency=H(X)/L
n=-HofX/L;
np=n*100.;
print'Code efficiency for shannon fanon:',np,'%'

# (b) For Huffman Code
nh=([1, 3, 3, 3, 3]);

# Average Code length
# L=Summation(P(xi)ni) 
Lh=0;
for i in range(1,5):
    Lh=Lh+(Px[i]*nh[i]);

# Efficiency=H(X)/L
n1=-HofX/Lh;
np1=n1*100.;
print'Code efficiency for hauffman:',np1,'%'

(5,)
Code efficiency for shannon fanon: 111.791799137 %
Code efficiency for hauffman: 90.05450486 %