lOMoARcPSD|22905522

ITC course file - notes

Information Theory and Coding (Guru Gobind Singh Indraprastha University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])
 lOMoARcPSD|22905522




       
        

  
  
 
 
 
 





            
           





  

        
          
            
     



            
            



 
 


 
 

 
 
 
 

  



Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ACADEMIC PLAN FOR V SEMESTER

Subject: Information Theory and Coding Subject Code: ETEC - 304

Branch: ECE Credits: 4
Total Teaching Weeks in semester: 15 weeks Total Lectures available: 44

Lecture Reference
S. No. TOPICS TO BE COVERED
Number Text
I term
1 Introduction to Information Theory 1 T1, T2
Review of Probability Theory, Random Variables and Random
2 2 T1, T2
Processes
3 Uncertainty, Information and Entropy 3 T1, T2
4 Mutual Information 4 T1, T2
5 Information Rate, Conditional and Joint Entropies 5 T1, T2
6 Source Coding Theorem, Types of Source codes, Prefix Codes 6 T1, T2
7 AEP, Data Compression and Kraft McMillian Inequality 7 T1, R1
8 Optimal Codes and bounds on optimal Code lengths 8 T1, R1
9 Huffman Coding and its optimality 9 T1, R1
10 Lempel Ziv Coding 10 T1, R1
11 Markov's Chain and entropy of (discrete) stochastic processes 11 T1, R1
12 Discrete Memoryless Channels 12 T1, R1
13 Binary Symmetric Channels 13 T1, R1
14 Channel Coding and Channel Capacity theorem 14 T1, T2
15 Channel Capacity theorem and Shannon Limit 15 T1, T2
16 Information Capacity of a coloured Noise Channel 16 T1, T2
17 Differential Entropy - Definition and Examples (Uniform and
17 T1, R1
Gaussian)
18 AEP for Continuous Random Variables 18 T1, R1
19 Relation of Differential Entropy to Discrete Entropy 19 T1, R1
20 Joint and Conditional Differential Entropy 20 T1, R1
21 Relative Entropy and Mutual Information 21 T1, R1
22 Properties of Differential Entropy, Relative Entropy and Mutual
22 T1, R1
Information
II Term
23 Introduction to Error Correcting codes, some basic definition 23 T1, R2, R4
24 Linear Block Codes, Generator Matrix, Examples 24 T1, R2, R4
25 Parity Check matrix, Singleton Bound and Maximum length codes 25 T1, R2, R4
26 Repetition Codes, Hamming Codes, Duality of Linear Block Codes 26 T1, R2, R4
27 Syndrome Decoding of Linear Block codes 27 T1, R2, R4
28 Introduction to Cyclic codes, generator polynomials and polynomial
28 T1, R2, R4
division

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

29 Cyclic Redundancy Check Codes, Golay Codes 29 T1, R2, R4

30 BCH codes, Reed Solomon Codes 30 T1, R2, R4
31 Introduction to Convolution Codes and their polynomial description 31 T1, R2, R4
32 State Diagrams and Convolution code generation 32 T1, R2, R4
33 Tree Diagram and Convolution Code generation 33 T1, R2, R4
34 Trellis Diagram and Convolution code generation 34 T1, R2, R4
35 Trellis Code Modulation 35 T1, R2, R5
36 Maximum Likelihood Detection of Convolution Codes 36 T1, R2, R5
37 Viterbi's Algorithm for TCM detection 37 T1, R2, R5
38 Evaluating the free distance of a TCM 38 T1, R2, R5
39 Turbo Codes - Encoding 39 T1, R2, R5
40 Turbo Codes - Decoding 40 T1, R2, R5
41 Performance of Turbo Codes 41 T1, R2, R5
42 Punctured Codes and Their decoding 42 T1, R2, R5
43 Introduction to Cryptography, Overview of Encryption Techniques 43 T1, R2, R5
a. Overview of Encryption techniques (contd.)
44 44 T1, R2, R5
b. Basic operations used in Encryption algorithms

Text Books:
[T1] Simon Haykins, “Communication Systems”, 4th edition Wiley, 2001.
[T2] J G Proakis, “Digital Communications”, McGraw Hill, 2001.

Reference Books:
[R1] T M Gover, J M Thomos, “Elements of Information Theory”, Wiley, 1999.
[R2] Arijit Saha, Nilotpal Manna, Surajit Mandal, “Information Theory, Coding and Cryptography”,
Pearson Education, 2013.
[R3] Schaum’s Outlines, Analog and Digital Communications, Second Edition.
[R4] Amitabha Bhattacharya, “Digital Communication”, TMH 2006.
[R5] J. H. Van Lint.. “Introduction to Coding Theory”, Springer -Verlag.

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Introduction to the subject

After a detailed discussion on the digital communication basics, we now know that analog data can
be converted to digital (binary) form and can be coded appropriately to be sent over communication
channels. We also understood the need for better bandwidth efficiency and higher data rates of
transmission. Thus we come to two very specific questions in communication theory. What is the
ultimate level of data compression and what is the absolute maximum transmission rate? The study
of information theory answers both these questions and also indicates methods of achieving these
limits.

Due to its significant role in the field, information theory is widely considered a branch of
communication theory. But in its true sense, the study of information theoretic concepts have
applications in Mathematics, statistics, economics, computer science, physics, probability, etc. We,
however, shall restrict our discussion on the use of information theory in the field of communication.

The foundations of Information theory are traced back to the an article in the Bell System Technical
Journal, 1948 with the title “The Mathematical Theory of Communication” by the American
Electrical engineer, Claude E. Shannon. This paper became the ground work for most of the modern
day communication theory and information theory and thus Shannon is truly called the father of
modern day Information theory.

Through this subject, we try to develop an understanding of the basic meaning of information in
relation to communication theory, the method of data compression and limits on the same, and
finally limits on the transmission media for optimum communication.

Let us start by developing an intuitive feel of what information really means.

Consider the following sentences:

a) Tomorrow, the sun will rise from the east.

b) The phone will ring in the next one hour.
c) It will snow in Delhi next winter.

Each of these represents different amounts of information. The first statement gives almost no
information at all. This statement states something that is sure to happen and hence occurs with a
probability of 1. The second statement gives us some more information. The phone may or may not
ring in the next hour. The probability of the same will therefore be less than one. The third statement
represents a very rare occurrence, meaning that the probability of its occurrence is very low.
Therefore this statement gives us the largest amount of information. It is interesting to observe that
as the probability of the occurrence of an even decreases, the amount of information that it reports
increases. Also note that the amount of information in the statements has nothing to do with the
length of the statements.

We can now develop a mathematical measure of information as suggested by the research done by
Shannon.

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Uncertainty and Information

Definition: Consider a discrete random variable X with the possible outcomes xi , i = 1, 2, 3,.., n.
The self information of the event X = xi is defined as

1
𝐼(𝑥𝑖 ) = 𝑙𝑜𝑔𝑟 ( ) = −𝑙𝑜𝑔(𝑃(𝑥𝑖 ))
𝑃(𝑥𝑖 )

We may note here that a high probability event conveys less information than a low probability
event. For an event with P(xi) = 1, I(xi) = 0. Since a lower probability implies a higher degree of
uncertainty (and vice versa), a random variable with a higher degree of uncertainty contains more
information.

The above can be observed as a direct inference of the following properties of information.

1. Information conveyed by a message cannot be negative. It has to be at least 0.

2. If the event is definite, that is the probability of occurrence of the event is 1, then the
information conveyed by the event is 0.
3. The information conveyed by a composite statement made by messages which are
independent is simply given by the sum of the individual self-information contents. That is
I(m1,m2) = I(m1) + I(m2)

Further, with the knowledge of inverse proportionality of Information content with probability of
even, the above properties combined give us the result that the logarithm function is the only form in
which information content can be represented.

The units for I(xi) are determined by the base of the logarithm ‘r’.

i) If r = 2, the unit is bits

ii) If r = e, the unit is Nats
iii) If r = 10, the unit is Hartley or Decits

Example 1: Consider a binary source which tosses a fair coin and outputs a 1 if a head appears and a
0 is a tail appears. For the source, P(1) = P(0) = 0.5. The information content of each output from the
source is

𝐼(𝑥𝑖 ) = − 𝑙𝑜𝑔2 𝑃(𝑥𝑖 ) = −𝑙𝑜𝑔2 (0.5) = 1 𝑏𝑖𝑡

Indeed, we have to use only one bit to represent the output from this binary source. Now suppose the
successive outputs from this binary source are statistically independent, i.e., the source is
memoryless. There are thus 2m possible outcomes each of which is equiprobable with probability 2-m.
The self information of each possible outcome is

𝐼(𝑥𝑖 ) = − 𝑙𝑜𝑔2 𝑃(𝑥𝑖 ) = −𝑙𝑜𝑔2 (2−𝑚 ) = 𝑚 𝑏𝑖𝑡𝑠

Again, we observe that, we indeed need m bits to represent the possible m outputs.

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Example 2: Consider a source emitting two symbols s0 and s1 with the corresponding probabilities ¾
and ¼ respectively. Find the self-information of the symbols in

a) Bits
b) Decits
c) Nats

Solution:

a) We have

1
𝐼(𝑠0 ) = 𝑙𝑜𝑔2 ( ) = 0.415 𝑏𝑖𝑡𝑠
3⁄
4

1
𝐼(𝑠1 ) = 𝑙𝑜𝑔2 ( ) = 2 𝑏𝑖𝑡𝑠
1⁄
4
b) We have

1
𝐼(𝑠0 ) = 𝑙𝑜𝑔10 ( ) = 0.124 𝑑𝑒𝑐𝑖𝑡𝑠
3⁄
4

1
𝐼(𝑠1 ) = 𝑙𝑜𝑔10 ( ) = 0.602 𝑑𝑒𝑐𝑖𝑡𝑠
1⁄
4
c) We have

1
𝐼(𝑠0 ) = 𝑙𝑜𝑔𝑒 ( ) = 0.287 𝑁𝑎𝑡𝑠
3⁄
4

1
𝐼(𝑠1 ) = 𝑙𝑜𝑔𝑒 ( ) = 1.386 𝑁𝑎𝑡𝑠
1⁄
4

Average Information of a Zero memory source

A zero memory source or a discrete memoryless source is the one in which the emission of the
current symbol is independent of the emission of the previous symbols. Consider a source emitting
symbol S = {s1, s2, s3,…,sn} with respective probabilities P = {p1, p2, p3,…, pn}.

Now consider a long message of length ‘L’ emitted by the source. Then it contains

p1L number of symbols of ‘s1’,

p2L number of symbols of ‘s2’,

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

pnL number of symbols of ‘sn’

The self information of each si is given by

1
𝐼(𝑠𝑖 ) = 𝑙𝑜𝑔2 𝑏𝑖𝑡𝑠
𝑝𝑖

On an average, in a long sequence of length L, each symbol will occur p iL number of times. Hence,
total information conveyed by any particular symbol si will be

1
𝑝𝑖 𝐿 𝑙𝑜𝑔2 ( ) 𝑏𝑖𝑡𝑠
𝑝𝑖

Therefore, the total information conveyed by the source is simply the sum of all these information
contents, that is,

1 1 1
𝐼(𝑆) = 𝑝1 𝐿 𝑙𝑜𝑔2 ( ) + 𝑝2 𝐿 𝑙𝑜𝑔2 ( ) + ⋯ + 𝑝𝑛 𝐿 𝑙𝑜𝑔2 ( )
𝑝1 𝑝2 𝑝𝑛

Thus, the average information conveyed by the source by emitting ‘L’ symbols is denoted by its
entropy H(S), which is given by the expression

𝐼(𝑆) 1 1 1
𝐻(𝑆) = = 𝑝1 𝑙𝑜𝑔2 ( ) + 𝑝2 𝑙𝑜𝑔2 ( ) + ⋯ + 𝑝𝑛 𝑙𝑜𝑔2 ( )
𝐿 𝑝1 𝑝2 𝑝𝑛

We can simply rewrite this as

𝑛
1
𝐻(𝑆) = ∑ 𝑝𝑖 𝑙𝑜𝑔2 ( ) 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
𝑝𝑖
𝑖=1

Hence, H(S) or entropy gives the measure of the average information content of the symbols of a
source S.

For a Binary memoryless source, the entropy would hence be

1 1
𝐻(𝑆) = 𝑝 log + (1 − 𝑝) log
𝑝 1−𝑝

Where p represents the probability of occurrence of one of the symbols and 1-p represents the
probability of the other symbol.

The average rate of transmission can also be defined for an information system if the symbol rate or
baud rate of the system is known. If the baud rate of the system is rS sym/s, then the average rate of
information is given by

RS = H(S) * rs bits/s

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Note: The entropy of X can also be interpreted as the expected value of the random variable
log(1/p(X)), where X is a random variable with probability mass function (discrete form of
probability distribution function) p(X).

Note: By definition of entropy, we can change its unit by using the formula:

Hb(X) = (log b a) Ha(X)

Example 3: A discrete memoryless source emits one of the five possible symbols every second. The
symbol probabilities are {1/4, 1/8, 1/8, 3/16, 5/16}. Find the average information content of the
source in bits/sym, nats/sym and Hartley/sym.

Solution:

Average information content or Entropy of this source can be given by

5
1
𝐻2 (𝑆) = ∑ 𝑝𝑖 𝑙𝑜𝑔2 ( ) 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
𝑝𝑖
𝑖=1

1 1 1 1 1 1 3 3 5 5
= − ( log 2 + log 2 + log 2 + log 2 + log 2 ) = 2.227 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
4 4 8 8 8 8 16 16 16 16
Also

𝐻𝑒 (𝑆) = 𝐻2 (𝑆) log 𝑒 2 = 2.227 × 0.693 = 1.543 𝑛𝑎𝑡𝑠/𝑠𝑦𝑚

and

𝐻10 (𝑆) = 𝐻2 (𝑆) log10 2 = 2.227 × 0.3010 = 0.6704 𝐻𝑎𝑟𝑡𝑙𝑒𝑦/𝑠𝑦𝑚

Example 4: The international Morse code uses a sequence of symbols of dots and dashes to transmit
letters of the English alphabet. The dash is represented by a current pulse of duration 2 ms and dot by
duration of 1 ms. The probability of dash is half as that of dot. Consider 1ms duration of gap is given
in between the symbols. Calculate

a) Self information of a dot and a dash

b) Average information content of a dot-dash code
c) Average rate of information

Solution

a) Let pdot and pdash be the probabilities of dot and dash, respectively. Given
1
𝑝𝑑𝑎𝑠ℎ = 𝑝𝑑𝑜𝑡
2
Also pdot + pdash = 1. Therefore,
1 2
𝑝𝑑𝑜𝑡 + 𝑝𝑑𝑜𝑡 = 1 ⇒ 𝑝𝑑𝑜𝑡 =
2 3
We can also deduce that

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

1 1
𝑝𝑑𝑎𝑠ℎ = 𝑝𝑑𝑜𝑡 =
2 3
Now,
2
𝐼(𝑑𝑜𝑡) = − log 2 𝑝𝑑𝑜𝑡 = −log 2 = 0.5849 𝑏𝑖𝑡𝑠
3
1
𝐼(𝑑𝑎𝑠ℎ) = − log 2 𝑝𝑑𝑎𝑠ℎ = −log 2 = 1.5849 𝑏𝑖𝑡𝑠
3

b) 𝐻(𝑆) = −(𝑝𝑑𝑜𝑡 log 2 𝑝𝑑𝑜𝑡 + 𝑝𝑑𝑎𝑠ℎ log 2 𝑝𝑑𝑎𝑠ℎ ) = 0.9182 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚

c) From the probabilities of dot and dash, it is clear that for every three symbols transmitted,
there will be one symbol of type dash and two of type dot. Also the duration of dash is 2ms
and that of dot is 1ms, and the 1ms gap is left in between the symbols. Therefore a total of
(1+1+1+1+2+1) = 7ms time is required to transmit an average of 3 symbols (∙ ∙ −). So the
symbol rate is given by
3 3000
7 𝑠𝑦𝑚 𝑠𝑦𝑚
𝑟𝑠 = = 7
𝑚𝑠 𝑠
3000
⇒ 𝑅𝑠 = 𝐻(𝑆) × 𝑟𝑠 = 0.9182 × = 393.51 𝑏𝑖𝑡𝑠/𝑠
7

Properties of Entropy:

1. Entropy is a continuous function of probability.

2. Entropy of a system is the same irrespective of the order in which the symbols are arranged.

3. Entropy is never negative. It can take a minimum value of 0 if the event in question is certain
or deterministic.

4. Entropy has maximum value when all the possible outcomes of an event are equiprobable.
(Proof attached separately, Sheet 1)

Source Efficiency and Source Redundancy

Source Efficiency is defined as the ratio of the average information conveyed by the source to that of
the maximum average information

𝐻(𝑆)
𝜂𝑆 = × 100%
𝐻(𝑆)𝑚𝑎𝑥

Source redundancy can be defined

𝐻(𝑆) 𝐻(𝑆)𝑚𝑎𝑥 − 𝐻(𝑆)

𝑅𝜂𝑆 = [1 − ] × 100% = × 100%
𝐻(𝑆)𝑚𝑎𝑥 𝐻(𝑆)𝑚𝑎𝑥

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Example 5: Consider a system emitting one of the three symbols A, B and C, with respective
probabilities 0.6, 0.25 and 0.15. Calculate its efficiency and redundancy.

Solution: The efficiency is given by

𝐻(𝑆)
𝜂𝑆 = × 100%
𝐻(𝑆)𝑚𝑎𝑥

Now

1 1 1
𝐻(𝑆) = 0.6 log 2 + 0.25 log 2 + 0.15 log 2 = 1.3527 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
0.6 0.25 0.15
And

𝐻(𝑆)𝑚𝑎𝑥 = log 2 3 = 1.5849 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚

The efficiency is hence given by

1.3527
𝜂𝑆 = × 100% = 85.35%
1.5849
And the redundancy is

1.5849 − 1.3527
𝑅𝜂𝑆 = × 100% = 14.65%
1.5849

Mutual Information

Consider two discrete random variables X and Y with possible outcomes xi, i = 1, 2, 3, .. , n, and yj, j
= 1, 2, 3, .., m respectively. Suppose we observe some outcome Y = yj and we want to determine the
amount of information this event provides about the event X=xi. We may note that this information
will have to satisfy the following extreme case conditions.

1. If X and Y are independent, occurrence of Y=yj provides no information about X=xi.

2. If X and Y are fully dependent events, in which case the occurrence of Y = yj determines the
occurrence of the event X=xi.

A suitable measure that satisfies these conditions is the logarithm of the ratio of the conditional
probability

𝑃(𝑋 = 𝑥𝑖 |𝑌 = 𝑦𝑗 ) = 𝑃(𝑥𝑖 |𝑦𝑗 )

divided by the probability

𝑃(𝑋 = 𝑥𝑖 ) = 𝑃(𝑥𝑖 )

The mutual information, I(xi; yj) between xi and yj, can thus be defined as

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

𝑃(𝑥𝑖 |𝑦𝑗 )
𝐼(𝑥𝑖 ; 𝑦𝑗 ) = log 2 ( )
𝑃(𝑥𝑖 )

As before, the units of I(x) are determined by the base of the logarithm, which is usually selected as
2 for which the units are Bits. Note that

𝑃(𝑥𝑖 |𝑦𝑗 ) 𝑃(𝑥𝑖 |𝑦𝑗 )𝑃(𝑦𝑗 ) 𝑃(𝑥𝑖 ; 𝑦𝑗 ) 𝑃(𝑦𝑗 |𝑥𝑖 )

= = =
𝑃(𝑥𝑖 ) 𝑃(𝑥𝑖 )𝑃(𝑦𝑗 ) 𝑃(𝑥𝑖 )𝑃(𝑦𝑗 ) 𝑃(𝑦𝑗 )

by Baye’s Theorem

Therefore,

𝑃(𝑥𝑖 |𝑦𝑗 ) 𝑃(𝑦𝑗 |𝑥𝑖 ) 𝑃(𝑥𝑖 ; 𝑦𝑗 )

𝐼(𝑥𝑖 ; 𝑦𝑗 ) = log ( ) = log ( ) = log ( ) = 𝐼(𝑦𝑗 ; 𝑥𝑖 )
𝑃(𝑥𝑖 ) 𝑃(𝑦𝑗 ) 𝑃(𝑥𝑖 )𝑃(𝑦𝑗 )

Physical interpretation of I(xi; yj) = I(yj; xi) is that the information provided by the occurrence of the
event Y=yj about the event X=xi is identical to the information provided by the occurrence of the
event X=xi about the event Y=yj.

Let us now verify the two extreme cases:

1. When the random variables X and Y are statistically independent, P(x i | yj) = P(xi), which
leads to I(xi; yj) = 0.
2. When the occurrence of Y=yj uniquely determines the occurrence of the event X=xi, P(xi | yj)
= 1, and the mutual information becomes

1
𝐼(𝑥𝑖 ; 𝑦𝑗 ) = log ( ) = − log 𝑃(𝑥𝑖 ).
𝑃(𝑥𝑖 )

This is the self information of the event X=xi.

Joint Entropy

The joint entropy H(X, Y) of a pair of discrete random variables (X, Y) with a joint distribution p(x,
y) is defined as

𝐻(𝑋, 𝑌) = − ∑ ∑ 𝑝(𝑥, 𝑦) log 2 𝑝(𝑥, 𝑦),

𝑥∈𝑋 𝑦∈𝑌

which can also be expressed as

𝐻(𝑋, 𝑌) = −𝐸{log 𝑝(𝑋, 𝑌)}

i.e. the expected value of log(p(X,Y)).

Conditional Entropy

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

If (X, Y) ~ p(x, y), the conditional entropy H(Y|X), i.e. the entropy of Y given the value of X, is
defined as

𝐻(𝑌|𝑋) = ∑ 𝑝(𝑥)𝐻(𝑌|𝑋 = 𝑥)
𝑥∈𝑋

= − ∑ 𝑝(𝑥) ∑ 𝑝(𝑦|𝑥) log 𝑝(𝑦|𝑥)

𝑥∈𝑋 𝑦∈𝑌

= − ∑ ∑ 𝑝(𝑥, 𝑦) log 𝑝(𝑦|𝑥)

𝑥∈𝑋 𝑦∈𝑌

= −𝐸{log 𝑝(𝑌|𝑋)}

The naturalness of the definition of joint entropy and conditional entropy is exhibited by the fact that
the entropy of a pair of random variables is the entropy of one plus the conditional entropy of the
other. This can be proved by the following theorem called the Chain Rule of Entropy.

𝐻(𝑋, 𝑌) = 𝐻(𝑋) + 𝐻(𝑌|𝑋)

Proof:

𝐻(𝑋, 𝑌) = − ∑ ∑ 𝑝(𝑥, 𝑦) log 𝑝(𝑥, 𝑦)

𝑥∈𝑋 𝑦∈𝑌

= − ∑ ∑ 𝑝(𝑥, 𝑦) log(𝑝(𝑥)𝑝(𝑦|𝑥))
𝑥∈𝑋 𝑦∈𝑌

= − ∑ ∑ 𝑝(𝑥, 𝑦) log 𝑝(𝑥) − ∑ ∑ 𝑝(𝑥, 𝑦) log 𝑝(𝑦|𝑥)

𝑥∈𝑋 𝑦∈𝑌 𝑥∈𝑋 𝑦∈𝑌

= − ∑ 𝑝(𝑥) log 𝑝(𝑥) − ∑ ∑ 𝑝(𝑥, 𝑦) log 𝑝(𝑦|𝑥)

𝑥∈𝑋 𝑥∈𝑋 𝑦∈𝑌

= 𝐻(𝑋) + 𝐻(𝑌|𝑋)

The same can be extended for n random variables. Let X1, X2, X3, … , Xn be jointly distributed with
density function p(x1, x2, x3, … , xn). Then,

𝐻(𝑋1 , 𝑋2 , ⋯ , 𝑋𝑛 ) = 𝐻(𝑋1 ) + 𝐻(𝑋2|𝑋1) + ⋯ + 𝐻(𝑋𝑛 |𝑋𝑛−1 ⋯ 𝑋1)

𝑛

= ∑ 𝐻(𝑋𝑖 |𝑋𝑖−1 ⋯ 𝑋1 )
𝑖=1

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Average Mutual Information and Entropy

Average mutual information can be calculated just as the average self information.

𝐼(𝑋, 𝑌) = ∑ ∑ 𝑃(𝑥𝑖 , 𝑦𝑗 )𝐼(𝑥𝑖 , 𝑦𝑗 )

𝑥∈𝑋 𝑦∈𝑌

𝑃(𝑥𝑖 |𝑦𝑗 )
= ∑ ∑ 𝑃(𝑥𝑖 , 𝑦𝑗 ) log ( )
𝑃(𝑥𝑖 )
𝑥∈𝑋 𝑦∈𝑌

= − ∑ ∑ 𝑃(𝑥𝑖 , 𝑦𝑗 ) log 𝑃(𝑥𝑖 ) − (− ∑ ∑ 𝑃(𝑥𝑖 , 𝑦𝑗 ) log(𝑃(𝑥𝑖 |𝑦𝑖 )))

𝑥∈𝑋 𝑦∈𝑌 𝑥∈𝑋 𝑦∈𝑌

= − ∑ 𝑃(𝑥𝑖 ) log 𝑃(𝑥𝑖 ) − 𝐻(𝑋|𝑌) = 𝐻(𝑋) − 𝐻(𝑋|𝑌)

𝑥∈𝑋

Thus, physically, it may be interpreted that average mutual information is the reduction of
uncertainty of X due to the knowledge of Y.

By symmetry, it also follows that

𝐼(𝑋, 𝑌) = 𝐻(𝑌) − 𝐻(𝑌|𝑋)

This means that X says as much about Y as Y says about X.

Since by Chain rule we know that

𝐻(𝑋, 𝑌) = 𝐻(𝑋) + 𝐻(𝑌|𝑋)

We may rewrite the expression for average mutual information as

𝐼(𝑋, 𝑌) = 𝐻(𝑋) + 𝐻(𝑌) − 𝐻(𝑋, 𝑌).

We may also note that,
𝐼(𝑋, 𝑋) = 𝐻(𝑋) − 𝐻(𝑋|𝑋) = 𝐻(𝑋)
Thus the average mutual information of a random variable with itself is the entropy of the random
variable. This is also a testament to the fact that entropy is referred to as Average Self Information.
Hence in summary, we may collect the following results and follow them as a theorem.

𝐼(𝑋, 𝑌) = 𝐻(𝑋) − 𝐻(𝑋|𝑌)

𝐼(𝑋, 𝑌) = 𝐻(𝑌) − 𝐻(𝑌|𝑋)

𝐼(𝑋, 𝑌) = 𝐻(𝑋) + 𝐻(𝑌) − 𝐻(𝑋, 𝑌)

𝐼(𝑋, 𝑌) = 𝐼(𝑌, 𝑋)

𝐼(𝑋, 𝑋) = 𝐻(𝑋)

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

The following Venn Diagram further explains the relationship between Conditional entropy, joint
entropy, entropy and average mutual information of two random variables.

Extension of a zero memory source

Consider a zero memory source emitting two symbols ‘s1’ and ‘s2’ with probabilities ‘p1’ and ‘p2’
respectively. Obviously, p1+p2=1. Also the entropy of the source S is given by

1 1
𝐻(𝑆) = 𝑝1 log + 𝑝2 log
𝑝1 𝑝2

Now consider the second order extension of the source S. This source is denoted as S2. Now the
source S2 will have four combinations viz. s1s1, s1s2, s2s1 and s2s2. Since in a zero memory source,
the symbols are statistically independent, corresponding probabilities are given by

𝑃(𝑠1 𝑠1 ) = 𝑝(𝑠1 )𝑝(𝑠1 ) = 𝑝12

𝑃(𝑠1 𝑠2 ) = 𝑝(𝑠1 )𝑝(𝑠2 ) = 𝑝1 𝑝2

𝑃(𝑠2 𝑠1 ) = 𝑝(𝑠2 )𝑝(𝑠1 ) = 𝑝1 𝑝2

𝑃(𝑠2 𝑠2 ) = 𝑝(𝑠2 )𝑝(𝑠2 ) = 𝑝22

The entropy of the second order extension of the source is given by

1 1 1 1
𝐻(𝑆 2 ) = 𝑝12 log ( 2
2 ) + 𝑝1 𝑝2 log (𝑝 𝑝 ) + 𝑝2 𝑝1 log (𝑝 𝑝 ) + 𝑝2 log ( 2 )
𝑝1 1 2 2 1 𝑝2

Simplifying and using the fact that p1+p2=1, one may simplify this to be

1 1
𝐻(𝑆 2 ) = 2 (𝑝1 log + 𝑝2 log )
𝑝1 𝑝2
Which simply means that
𝐻(𝑆 2 ) = 2 ∙ 𝐻(𝑆)

In general, it can be observed in a similar fashion that for an n-th order extension of S,

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

𝐻(𝑆 𝑛 ) = 𝑛 ∙ 𝐻(𝑆)

Source Coding Theorem

An important problem in communications is the efficient representation of data generated by a

discrete source. The process by which this representation is accomplished is called source encoding.
For efficient source coding, we need the statistical knowledge of the source. The primary motivation
is the compression of data due to efficient representation of the symbols.

Suppose a discrete memoryless source outputs a symbol every t seconds. Each symbol is selected
from a finite set of symbols xi, i=1, 2, …, L, occurring with probabilities P(xi), i=1, 2, …, L. The
entropy of this DMS in bits per symbol is given by
𝐿
1
𝐻(𝑋) = ∑ 𝑃(𝑥𝑖 ) log 2 ≤ log 2 𝐿
𝑃(𝑥𝑖 )
𝑖=1

where the equality holds when the symbols are equally likely. It implies that the average number of
bits per source symbol is H(X) and the source rate is H(X)/t bits/sec. Now let us suppose that we
wish to represent the 26 letters in the English alphabet using bits. We observe that 2 5=32>26. Hence
each of the letters can be uniquely represented using 5 bits. This is an example of a Fixed Length
Code (FLC). Each letter has a corresponding 5 bits long codeword.

Note: A code is a set of vectors called codewords.

The fixed length code of the English alphabet is useful only if we take the assumption that each of
the letters in the alphabet are equally probable to occur. However, we know that some of the letters
are less common (x, q, j, z, etc.) while some others are more frequently used (e, s, t, etc.). It appears
that allotting equal number of bits to both the frequently used letters as well as not so commonly
used letters is NOT an efficient way of representation (coding), Intuitively, we should represent the
more frequently occurring letters by a fewer number of bits and represent the more frequently
occurring letters by larger number of bits. In this manner, if we have to encode a whole page of
written text, we might end up using fewer number of bits overall. Hence, when the source symbols
are not equally probable, a more efficient method to use is a Variable Length Code (VLC). The
Morse code is an example of a VLC. In the Morse code, the letters of the alphabet and the numerals
are encoded into streams of marks and spaces, denoted as dots “˖” and dashes “–“, respectively. In
the English language the letter E occurs most often while the letter Q occurs least often. The Morse
code, hence allocates the shortest code, i.e. a single dot “˖” as codeword for the letter E, and encodes
Q with the longest codeword in the code “– – ˖ – “.

Our primary interest is in the development of an efficient source encoder that satisfies two functional
requirements:

1. The codewords produced by the encoder are in binary form.

2. The source code in uniquely decodable, so that the original sequence can be reconstructed
perfectly from the encoded binary sequence.

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Consider the scheme given below.

We assume that the source has an alphabet with K different symbols and that the kth symbol s k has
the probability pk, k=1, 2, 3, … , K. Let the binary codeword assigned to the symbol sk be of length
given by lk measured in bits. We define the average codeword length, L, of the source encoder as
𝑘

𝑳 = ∑ 𝑝𝑖 𝑙𝑖
𝑖=1

In physical terms, L represents the average number of bits per source symbol used in the source
encoding process. Let Lmin define the minimum possible value of L. We then may define the coding
efficiency of the source encoder as

𝑳𝒎𝒊𝒏
𝜂𝐶 =
𝑳
The efficiency of this model, hence, increases when L reaches Lmin. A source encoder is hence called
efficient when η approaches unity.

But how do we evaluate the minimum value of L i.e. Lmin?

The answer to this fundamental question is answered by Shannon’s First Theorem: The Source-
coding Theorem, which may be stated as follows:

Given a discrete memoryless source S, of entropy H(S) the average codeword length L for any
distortionless source encoding scheme is bounded as

𝑳 ≥ 𝐻(𝑆)

It is intuitively apparent as well that the above condition will be true as the entropy represents the
average minimum number of bits required to represent the various symbols at the output of the
source which will always be less than the actual average of the number of bits used to represent these
symbols.

The efficiency of the source encoder is hence given by

𝐻(𝑆)
𝜂𝐶 = × 100%
𝑳
The redundancy of the implemented code is given by

The redundancy of the code is given by

𝑅𝜂𝐶 = (1 − 𝜂𝐶 )

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Data Compaction and Types of Source Codes

A common characteristic of signals generated by physical sources is that, in their natural form, they
contain a significant amount of information that is redundant, the transmission of which is therefore
wasteful of primary communication resources. For efficient signal transmission, the redundant
information should be removed from the signal prior to transmission. This operation, with no loss of
information, is ordinarily performed on a signal in digital from, in which case we refer to it as data
compaction or lossless data compression. The code resulting from such an operation provides a
representation of the source output that is not only efficient in terms of the average number of bits
per symbol but also exact in the sense that the original data can be reconstructed with no loss of
information. The entropy of the source establishes the fundamental limit on the removal of
redundancy from the data. Applications such as military or medical information systems demand
utmost reliability and hence the compression has to be lossless.

Some applications such as video conferencing and personal communication can tolerate certain
degree of loss in the information, in which case, a higher compression ratio can be achieved,
however at the cost of degradation of the reliability of the system. Lossy compression algorithms are
used for such applications.

Most of the codes realized in real time are variable length codes. Let us discuss different types of
codes.

a) Block codes

In this type, each symbol will be mapped onto a block of code symbols defined in the code
alphabet. The block codes can be of either fixed or variable length. For example:

Symbol Codeword 1 Codeword 2

A 00 1
B 01 01
C 10 110
D 11 111

b) Non-singular Codes

A block code is said to be non-singular if all its codewords are distinct. For example:

Symbol Codeword 1 Codeword 2

A 00 1
B 01 01
C 10 110
D 11 111
Non-Singular Singular

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

c) Uniquely Decodable Codes

A non singular block code is said to be uniquely decodable if its nth extension is also non-
singular for all finite values of ‘n’.

Symbol Codeword 1 Codeword 2

A 00 1
B 01 01
C 10 110
D 11 111
d) Instantaneous codes

A uniquely decodable code is said to be an instantaneous code if the end of any codeword can be
determined without the interpretation of the succeeding symbol.

It must be understood here how uniquely decodable codes are different from instantaneous code.
The requirement is that the code should be able to decode the information without any ambiguity
or need of additional information. Consider the following uniquely decodable code.

Symbol Codeword 1
A 0
B 01
C 11
D 10
Let the transmitted information be ‘ABCAD’ and hence, the corresponding codeword transmitted
is ‘00111010’. The receiver decodes it as ‘A’ because ‘0’ is a valid codeword for ‘A’. The next
bit received is also ‘0’. Although the transmitted codeword was ‘01’ corresponding to symbol
‘B’, the receiver incorrectly decodes it as ‘A’ because ‘0’ itself is a valid codeword. Next bit that
it receives is ‘1’ that is not a valid codeword and, hence, it accepts the next bit getting ‘11’ which
is a valid codeword and, hence, it decoded by the receiver will be ‘AACDD’, which is not the
same as that of the transmitted information. Thus, the codewords assigned for the symbols are
not instantaneous.

The problem with the decoding in the previous scenario is that the codeword for B has started
with symbol ‘0’ that itself is a valid codeword. Thus, the receiver has incorrectly decoded the
information as soon as the first symbol of the second codeword is received. From the above
scenario, we can conclude that the decoding would be unsuccessful if any of the codewords start
with any of the valid codewords of the system. In other words, the necessary and sufficient
condition for a uniquely decodable code to be instantaneous is that no codeword should be a
prefix of any other codeword. Thus they are also called prefix codes.

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

It can be proven that all prefix codes must satisfy the condition
𝑁

∑ 𝑟 −𝑙𝑘 ≤ 1
𝑘=1

where ‘r’ is the number of symbols in code alphabet, that is r=2 for binary, 3 for ternary, etc. This
is known as the Kraft McMillan Inequality. Please refer to Sheet 2 for proof.

If the Kraft McMillan inequality is not satisfied, we cannot construct a prefix code for a given set
of codeword lengths. However, the satisfaction of the inequality does not imply that the
corresponding codewords are prefix. In other words, all prefix codes satisfy Kraft McMillan
Inequality, but all codes satisfying the inequality need not be prefix.

e) Optimal Codes

Instantaneous codes are called optimal if the lengths of the codewords assigned to the symbols
are of minimum length.

Basically, it can be proven that for optimal codes the average length of the codeword should lie
in the range

𝐻(𝑆) ≤ 𝐿 ≤ 𝐻(𝑆) + 1

Example 6: Following table gives different codes for a set of five symbols. Determine which of
the following are valid prefix codes.

Code A Code B Code C Code D

0 1 00 10

10 01 110 111

110 111 1110 110

1110 10 001 01

111 00 011 00

Solution

Code A: It is not a prefix code as the codeword ‘111’ is a prefix of the codeword ‘1110’

Code B: It is not a prefix code as the codeowrd ‘1’ is a prefix of the codewords ‘111’ and ‘10’

Code C: It is not a prefix code as the codeword ‘00’ is a prefix of the codeword ‘001’

Code D: It is a valid prefix code since no codeword is a prefix of other codewords.

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Example 7: Which of the sets of the following requirements shown in the table below can be
considered for the construction of the binary prefix codes?

Code P Code Q Code R Word Length

1 2 1 1

1 1 1 2

2 2 1 3

2 1 2 4

Solution: Any set of lengths of the codewords that satisfy the Kraft McMillan Inequality can be
considered for the construction of the prefix codes.

Code P: 1 code word of length 1, 1 code word of length 2, 2 code words of length 3, 2 code
words of length 4.
6
9
∑ 2−𝑙𝑖 = (1 × 2−1 ) + (1 × 2−2 ) + (2 × 2−3 ) + (2 × 2−4 ) = >1
8
𝑖=1

Hence the code P cannot be a valid prefix code.

Code Q: Using similar method

6
25
∑ 2−𝑙𝑖 = (2 × 2−1 ) + (1 × 2−2 ) + (2 × 2−3 ) + (1 × 2−4 ) = >1
16
𝑖=1

Hence Q can also not be valid prefix code

Code R: For this code

5

∑ 2−𝑙𝑖 = (1 × 2−1 ) + (1 × 2−2 ) + (1 × 2−3 ) + (2 × 2−4 ) = 1

𝑖=1

Therefore, R can be made into a valid prefix code. Possible set of codewords are as follows:

1 0

01 10

001 110

0001 1110

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Huffman Code

Huffman Code is one of the pioneer works in variable length coding and gives an optimum source
code representation for a discrete memoryless source with the source symbols that are not equally
probable. The steps of the Huffman coding algorithm are as given below.

1. Arrange the source symbols in a non-increasing order of their probabilities.

2. Take the bottom two symbols and tie them together as shown in figure below. Add the
probabilities of the two symbols and write it on the combined node. Label the two branches
with a ‘1’ and a ‘0’ as depicted in the figure.

3. Treat the sum of probabilities as a new probability associated with a new symbol. Again pick
the two smallest probabilities, tie them together to form a new probability. Each time we
perform a combination of two symbols we reduce the total number of symbols by one.
Whenever we tie together two probabilities (nodes), we label the two branches with a ‘1’ and
a ‘0’.
4. Continue this procedure until only one probability is left which has to be 1. This completes
the construction of what we call the Huffman Tree.
5. To find out the prefix codeword for any symbol, follow the branches from the final node back
to the symbol. While tracing back the route, read out the labels on the branches. This is the
codeword for the symbol.

Example 8: Consider a DMS with seven possible symbols xi, i=1,2,…,7 and the corresponding
probabilities P(xi) ={0.37, 0.04, 0.16, 0.02, 0.01, 0.33, 0.07}. Construct the Huffman Tree for the
given example and find the prefix code for the same.

Solution:

We first arrange the probabilities in decreasing order and then construct the Huffman tree.

Symbol Probability Self-Information Codeword

X1 0.37 1.4344 1
X6 0.33 1.5995 00
X3 0.16 2.6439 010
X7 0.07 3.8365 0110
X2 0.04 4.6439 01110
X4 0.02 5.6439 011110
X5 0.01 6.6439 011111

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

We can find the entropy of the source to be

7

𝐻(𝑆) = − ∑ 𝑃(𝑥𝑘 ) log 2 𝑃(𝑥𝑘 ) = 2.1152 𝑏𝑖𝑡𝑠

𝑘=1

and the average number of binary digits needed per symbol is calculated to be
7

𝐿 = ∑ 𝑝𝑖 𝑙𝑖 = 1(0.37) + 2(0.33) + 3(0.16) + 4(0.07) + 5(0.04) + 6(0.02) + 6(0.01)

𝑖=1
= 2.1700 𝑏𝑖𝑡𝑠

Efficiency of this code is

𝐻(𝑆) 2.1152
𝜂𝐶 = × 100% = × 100% = 97.47%
𝑳 2.1700

Practice more problems for Huffman code and also note that the code is not unique. At any stage of
the code, in case we have a condition where two symbols have same probability, then either can be
taken on the upper branch hence leading to different set of codewords. But even in this condition, the
average number of bits of the code is not going to be affected.

Practice Problems:

Repeat Example 8 for the following set of probabilities.

a) {0.46, 0.02, 0.01, 0.03, 0.06, 0.30, 0.12}

b) {1/2, 1/22,1/23, 1/24, 1/25, 1/26, 1/26}
c) {1/8, 1/8, 1/8, 1/8, 1/8, 1/8, 1/8, 1/8}

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Lempel Ziv Coding

The source coding algorithms discussed in the previous sections require the statistics of the symbols
a priori. However, in real time situations, the symbol probabilities would be unknown. Also most of
the information sources depends on the previous symbols emitted. However, Huffman codes do not
consider such dependencies for coding. Thus, although Huffman codes work fine for memoryless
sources, they fail to achieve optimal efficiency for sources with memory.

For the sources with memory, better coding efficiency can be achieved by considering correlations
amongst symbols in source coding. One such source coding algorithm was developed by Lempel and
Ziv resulting in the Lempel-Ziv algorithm that is popularly known as LZ algorithm.

LZ algorithm is a dictionary-based approach in which a common dictionary is built at both sender

and receiver and depending upon the string to be sent. It is accomplished by parsing the source data
streams into segments that are the shortest sequences not encountered previously. The larger the
amount of source data, the better will be the compression. To illustrate consider the following
example.

Given a data stream

000111101101010101000101010101011101010101010

Thus the data parsing can be done in the following fashion.

Data to be parsed Code Book

0001111011010101010001010101010111010101010100 -
001111011010101010001010101010111010101010100 0
1111011010101010001010101010111010101010100 0,00
111011010101010001010101010111010101010100 0,00,1
1011010101010001010101010111010101010100 0,00,1,11
11010101010001010101010111010101010100 0,00,1,11,10
10101010001010101010111010101010100 0,00,1,11,10,110
01010001010101010111010101010100 0,00,1,11,10,110,101
010001010101010111010101010100 0,00,1,11,10,110,101,01
001010101010111010101010100 0,00,1,11,10,110,101,01,010
010101010111010101010100 0,00,1,11,10,110,101,01,010,001
01010111010101010100 0,00,1,11,10,110,101,01,010,001,0101
111010101010100 0,00,1,11,10,110,101,01,010,001,0101,
01010
010101010100 0,00,1,11,10,110,101,01,010,001,0101,
01010,111
010100 0,00,1,11,10,110,101,01,010,001,0101,
01010,111,010101
--- 0,00,1,11,10,110,101,01,010,001,0101,
01010,111,010101,010100

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

The process of codebook formation is as follows.

Encoding begins at the left most bits. The first bit in any case will be unknown to the codebook and
hence, in this case, 0 will be the first entry in the codebook. As the next bit is also 0, the bit after that
will also be taken into account and hence the next unknown codeword will be 00. Thus the entry in
the codebook after 0 will be 00 and the data left to be parsed will be all the remaining bits. We
continue like this till we reach the end of the incoming codes and the dictionary then has the
information of each possible subsequence as shown in the table above. Now, we have to encode
these subsequences.

For each of the subsequences we can allocate an index starting from 1. Now, for each of the
subsequences, separate the last bit (rightmost) and the rest of it. Now, the numerical representation of
these subsequences will be of the form <index position of the prefix, last bit>. For the subsequence
of single bit, the index position of prefix can be chosen as 0. Do this for all entries in the codebook.
The codeword would hence be the binary representation of the index position with the last bit
appended at the end. LZ code is a fixed length code and hence the binary representation of the index
position will be of the minimum number of bits required to represent the highest index position used
in the numerical representation.

Following table shows the method codeword assignment for the above used example. Here

CB : Code Book IP : Index Position NR: Numerical Representaiton CW: Code Word

CB 0 00 1 11 10 110 101 01 010 001 0101 01010 111 010101 010100

IP 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

NR 0,0 1,0 0,1 3,1 3,0 4,0 5,1 1,1 8,1 2,1 9,1 11,0 4,1 12,1 12,0

CW 00000 00010 00001 00111 00110 01000 01011 00011 10001 00101 10011 10110 01001 11001 11001

Hence for the given sequence, the codeword transmitted will be

000000001000001001110011001000010110001110001001011001110110010011100111001

It is important to note here that for a small number of bits, as in our case, the code is achieving no
compression. In fact, the sequence of 44 bits was coded in 75 bits! But one must remember that this
system is designed to work on large binary data of thousands of bits. It is observed that if
compressing a file of English data, Lempel Ziv code will give nearly 55% compression against 46%
of Huffman code for systems with memory.

Important Note:

Some texts approach LZ coding in a little different way. They assume that 0 and 1 are parts of the
dictionary at the index locations 1 and 2 respectively, before even the first bit of data comes in. The
rest of the process remains the same but 0 and 1 are not assigned any codeword. It must be noted that
both methods are correct although not same. It is a good practice to state the assumption up front if
one of the methods is applied.

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Markov Chain Model (Markov Sources)

Till now we have assumed sources that were memoryless. In other words, we considered that the
emission of a symbol from the source is independent of the previous emissions. But most of the
sources in real time do have memory. For example, in English, if the first letter of a word is ‘Q’, it is
more likely that the succeeding letter would be ‘U’ and so on. Thus in real time, most of the sources
are dependent. Hence the discussion for a memoryless source won’t be sufficient.

A dependent probabilistic model is thus required to model such sources. One such model is the
Markov model. In basic sense, the emission of a symbol ‘s’ of an nth order Markov source depends
upon n previous symbols.

Markov Model

A system with memory can be represented using a state diagram. A state diagram represents all
possible states of a system along with the transition probabilities. Also the symbols emitted by the
source in each of the transitions are depicted in a state diagram. From the state diagram, one can
construct a tree diagram from which the probabilities of the symbols emitted by the source can be
determined. The probabilities of the messages of length ‘L’ can be determined by constructing a tree
diagram of L stages.

Entropy and Information rate of Markov Source

Entropy of state ‘k’ can be denoted by Hk. It can be obtained by considering all outgoing
probabilities of state ‘k’:
𝐿
1
𝐻𝑘 = ∑ 𝑝𝑙𝑘 𝑙𝑜𝑔2 ( ) 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
𝑝𝑙𝑘
𝑙=1
where L is the total number of outgoing probabilities.
Entropy of the source is given by
𝑀

𝐻(𝑆) = ∑ 𝑝𝑘 𝐻𝑘 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
𝑘=1
where pk is the probability of the kth state.
The average information rate of the source will be given by

𝑅𝑠 = 𝑟𝑠 𝐻(𝑆) 𝑏𝑖𝑡𝑠/𝑠
Average Information per symbol
The average information content per symbol in a message of length L is given by

1 1
𝐺𝐿 = ∑ 𝑝(𝑚𝑖 ) log 2 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
𝐿 ∀𝑖 𝑝(𝑚𝑖 )

where p(mi) is the probability of the messages of length L. This depends upon our definition of what
we want the symbol to represent. The average amount of information per symbol in a long message
decreases with increase in L and will be at least equal to H(S), that is,
𝐺1 ≥ 𝐺2 ≥ 𝐺3 ≥ ⋯ ≥ 𝐻(𝑆)

In other words lim 𝐺𝐿 = 𝐻(𝑆)

𝐿→∞

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Example 9: For the Markov Source given by the following state diagram, evaluate:

a) State Probabilities
b) State Entropies
c) Source Entropy
d) G1, G2

Also prove that G1 > G2 > H(S).

X 1 2 Y

Solution

a) For state 1,

5 3
𝑝(1) = 𝑝(1) + 𝑝(2)
6 5
For state y,

1 2
𝑝(2) = 𝑝(1) + 𝑝(2)
6 5
Also, we know that

𝑝(1) + 𝑝(2) = 1

Solving we get that

18 5
𝑝(1) = 𝑎𝑛𝑑 𝑝(2) =
23 23
b) We know that
𝐿
1
𝐻𝑘 = ∑ 𝑝𝑙𝑘 𝑙𝑜𝑔2 ( ) 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
𝑝𝑙𝑘
𝑙=1
Therefore
1 5 6
𝐻1 = log 2 6 + log 2 = 0.65 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
6 6 5
and
3 5 2 5
𝐻2 = log 2 + log 2 = 0.9709 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
5 3 5 2

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

c) Source Entropy is given by

𝑀

𝐻(𝑆) = ∑ 𝑝𝑘 𝐻𝑘 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
𝑘=1
Hence
𝐻(𝑆) = 𝑝(1)𝐻1 + 𝑝(2)𝐻2 = 0.7197 𝑏𝑖𝑦𝑠/𝑠𝑦𝑚

d) To find G1 and G2 we need to make the tree diagrams, as shown below.

5/6 1 XX
X

1
5/6
2 XZ
1/6
18/23 1

3/5 1 ZX
1/6 Z

2/5 2 ZZ

Z 5/6 1 ZX

1
3/5
2 ZZ
1/6
5/23 2

Y 3/5 1 YZ
2/5
2

2/5 2 YY

Hence, the paths of length 1 are either X, Y or Z which have probabilities

18 5 15
𝑝(𝑋) = × =
23 6 23
5 2 2
𝑝(𝑌) = × =
23 5 23

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

and

18 1 5 3 6
𝑝(𝑍) = × + × =
23 6 23 5 23
Hence

1 1
𝐺1 = ∑ 𝑝(𝑚𝑖 ) log 2 = 1.2142 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
1 𝑖 𝑝(𝑚𝑖 )

Similarly, from the second stage of the tree we can get the probabilities of all symbols of
length 2 which are given as follows:

18 5 5 25 5 18 5 3 1 1
𝑝(𝑋𝑋) = × × = , 𝑝(𝑋𝑍) = , 𝑝(𝑍𝑍) = ( + ) × × = ,
23 6 6 46 46 23 23 5 6 10
6 5 6 4
𝑝(𝑍𝑌) = , 𝑝(𝑍𝑋) = , 𝑝(𝑌𝑍) = , 𝑝(𝑌𝑌) =
115 46 115 115
Therefore

1 1
𝐺2 = ∑ 𝑝(𝑚𝑖 ) log 2 = 1.0597 𝑏𝑖𝑡𝑠/𝑠𝑦𝑚
2 𝑖 𝑝(𝑚𝑖 )

From the solution of (c) and (d) parts above, we can easily see that G1 > G2 > H(S).

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Channel Coding

Channel coding refers to the class of signal transformations designed to improve communication
performance by enabling the transmitted signals to better withstand the effects of various channel
impairments such as noise, interference and fading.

Broadly, channel coding can be classified into 2 areas of study.

a) Waveform Coding
b) Structured Sequences

Waveform coding deals with transforming the symbol waveforms into “better waveforms” so as to
make their detection more immune to errors. It involves coding the existing signal waveforms to
form orthogonal or bi-orthogonal systems. For an M-ary signal, it can be seen that the probability of
bit error reduces with increase in M if the waveforms are orthogonally or bi-orthogonally coded. The
problem with this system is that increasing M also increases the bandwidth requirement of the
system.

Structured sequences deal with transforming data sequences themselves into “better sequences”
having structured redundancies or redundancy bits. The redundant bits can then be used for detection
and correction of errors. Study of structured sequences is classified into 3 major types: Block coding,
Convolution Coding and Turbo Coding.

The aim of our discussion is to develop and understanding of all these three types of coding
techniques. But before a detailed discussion on channel coding can commence, it is important to
understand the concept of channel models and channel capacity.

Discrete Memoryless Channels

Analogous to the concept of memoryless systems, i.e. a system in which the output of the system
depends only on the current input of the system and not on past or future values, a memoryless
channel in one in which every output sequence, say Y = [Y1, Y2, …, YN]T depends only on its
corresponding input sequence say X= [X1, X2, …, XN]T. This means that the different outputs
observed and different time instants are independent of each other. In case of a channel that has
memory, the current output would be dependent on outputs of other time instants as well. Now, since
the codeword alphabet is discrete in nature which means there are a discrete set of possible inputs,
such channels are called Discrete Memoryless Channels.

A discrete memoryless channel would thus be a statistical model with an input X and an output Y
that is a noisy version of X; both X and Y are random variables. Every unit of time, the channel
accepts an input symbol X selected from an input alphabet and, in response, it emits an output
symbol Y from the output alphabet. The channel is said to be discrete when both of the alphabets
have finite sizes. It is said to be memoryless when the current output depends only on the current
input symbol and not any of the previous ones.

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

The figure above shows a discrete memoryless channel described in terms of an input alphabet

X={x0, x1, x2, … , xJ-1},

an output alphabet,

Y={y0, y1, y2, … , yK-1}

and a set of state transition probabilities

p(yk|xj) = P(Y=yk | X=xj) for all j and k

Note that the input alphabet and output alphabet may be different in size. A convenient way of
describing a discrete memoryless channel is to arrange the various transition probabilities of the
channel in the form of a matrix as follows:

𝑝(𝑦0 |𝑥0 ) 𝑝(𝑦1 |𝑥0 ) 𝑝(𝑦𝑘−1 |𝑥0 )

⋯
𝑝(𝑦0 |𝑥1 ) 𝑝(𝑦1 |𝑥1 ) 𝑝(𝑦𝑘−1 |𝑥1 )
𝑃=[ ]
⋮ ⋱ ⋮
𝑝(𝑦0 |𝑥𝑗−1 ) 𝑝(𝑦1 |𝑥𝑗−1 ) ⋯ 𝑝(𝑦𝑘−1 |𝑥𝑘−1 )

The J-by-K matrix P is called the channel matrix, or transition matrix. Note that each row of the
channel matrix P corresponds to a fixed channel input, whereas each column of the matrix
corresponds to a fixed channel output. Note also that a fundamental property of the channel matrix P,
as defined here, is that the sum of the elements along any row of the matrix is always equal to one;
that is,
𝐾−1

∑ 𝑝(𝑦𝑘 |𝑥𝑗 ) = 1 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑗

𝑘=0

Suppose now that the inputs to a discrete memoryless channel are selected according to the
probability distribution {p(xj), j=0,1,…,J-1}. In other words, the even that the channel input X=xj
occurs with probability x

𝑝(𝑥𝑗 ) = 𝑃(𝑋 = 𝑥𝑗 ) 𝑓𝑜𝑟 𝑗 = 0,1, … , 𝐽 − 1

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Having specified the random variable X denoting the channel input, we may now specify the second
random variable Y denoting the channel output. The joint probability density of the random variables
X and Y is given by

𝑝(𝑥𝑗 , 𝑦𝑘 ) = 𝑃(𝑋 = 𝑥𝑗 , 𝑌 = 𝑦𝑘 ) = 𝑝(𝑦𝑘 |𝑥𝑗 )𝑝(𝑥𝑗 )

The marginal probability density of the output random variable Y is obtained by averaging out the
dependence of 𝑝(𝑥𝑗 , 𝑦𝑘 ) on xj, as shown by
𝐽−1

𝑝(𝑦𝑘 ) = ∑ 𝑝(𝑦𝑘 |𝑥𝑗 )𝑝(𝑥𝑗 ) 𝑓𝑜𝑟 𝑘 = 0,1, … , 𝐾 − 1

𝑗=0

Please note that the following pages have been directly picked from Communication Systems -
Simon Haykins, 4th Edition, Chapter 9. You will find the required pre-requisites in the content before
this. The following is all relevant to your course and it is important that you study all of it.

Binary Symmetric Channel

The transition matrix for a binary symmetric channel is hence given by

1−𝑝 𝑝
𝑃=[ ]
𝑝 1−𝑝

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Channel Capacity

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Channel Coding Theorem

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Differential Entropy

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Gaussian Distribution

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Information Capacity Theorem

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Implications of the Source Coding theorem

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Information Capacity of a Colored Noise Channel

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ETEC-304 Information Theory and Coding

Quiz – 1
Name: ______________________________ Roll No. _________________
Time Allotted: 30 mins Total Marks: 15 Student Score:_____
Please write your final answers in the space provided and hand over the sheet on completion.

1) To convert the unit of entropy from bits/sym to nats/sym, we multiply it with the value ______________.
[1 mark]
2) According to the source coding theorem, the maximum value of average codeword length must be less than
___________________. [1 mark]
3) Which one of the following is not the correct expression for average mutual information? [1 mark]
a. I(X,Y) = H(X) – H(Y|X) c. I(X,Y) = H(Y) – H(Y|X)
b. I(X,Y) = H(X) – H(X|Y) d. I(X,Y) = H(X) + H(Y) – H(X,Y)
4) Information Capacity of the telephone network with bandwidth 3.4 kHz and SNR 30dB is equal to -
___________________. [2 marks]
5) For a source code to be a valid prefix code, which of the following is not a requirement? [1 mark]
a. The code is uniquely decodable. c. The code satisfies the Kraft McMilan inequality.
b. The code is optimal. d. All the above conditions are required.
6) For evaluating the source entropy of a Markov Source, which of the following is a must to be known?
[1 mark]
a. State Probabilities c. State entropies
b. State change conditional probabilities d. None of the above
7) According to the channel coding theorem, the capacity of a binary symmetric channel has to be greater than
_______________. [1 mark]
8) An advantage of Lempel Ziv code over Huffman code is that it doesn’t require the knowledge of
____________________. [1 mark]
9) Value of Shannon limit on the value of Eb/No is ______________. [1 mark]
10) Draw the Huffman tree for the following set of symbol probabilities and determine their binary representations,
S=[S1 S2 S3 S4] = [0.5, 0.25, 0.125, 0.125]. Write the answer below. [5 marks]

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

AUSTRALIAN NATIONAL UNIVERSITY
Department of Engineering

ENGN 3226 Digital Communications

Problem Set #8 Block Codes
Q1
Consider a (6,3) linear block code defined by the generator matrix
 
1 0 0 1 1 0
→
−
G =  0 1 0 0 1 1 
0 0 1 1 0 1
→
−
(a) Determine if the code is a Hamming code. Find the parity check matrix H of the code in systematic form.
(b) Find the encoding table for the linear block code.
(c) What is the minimum distance dmin of the code. How many errors can the code detect. How many errors
can the code correct.
(d) Draw the hardware encoder diagram.
(e) Find the decoding table for the linear block code.
(f) Draw the hardware
 syndrome generator diagram. − 
(g) Suppose →−c = 1 1 1 0 0 0 is sent and →

r = 1 1 1 0 0 1 is received. Show how
the code can correct this error.

Q2
Consider a (7,4) linear block code defined by the generator matrix
 
1 0 0 0 1 1 0
→
−  0 1 0 0 0 1 1 
G =   0 0 1 0 1 1 1 


0 0 0 1 1 0 1
→
−
(a) Determine if the code is a Hamming code. Find the parity check matrix H of the code in systematic form.
(b) Find the encoding table for the linear block code.
(c) What is the minimum distance dmin of the code. How many errors can the code detect. How many errors
can the code correct.
(d) Draw the hardware encoder diagram.
(e) Find the decoding table for the linear block code.
(f) Draw the hardware syndrome generator diagram.
(g) Suppose →−c = 1 0 0 1 0 1 1 is sent and → −r =  1 1 0 1 0 1 1  is received. Show
 

how the code can correct this error.

Q3
Consider a (5,1) linear block code defined by the generator matrix
→
−  
G = 1 1 1 1 1
→
−
(a) Find the parity check matrix H of the code in systematic form.
(b) Find the encoding table for the linear block code.
(c) What is the minimum distance dmin of the code. How many errors can the code detect. How many errors
can the code correct.
(d) Draw the hardware encoder diagram.
(e) Find the decoding table for the linear block code (consider single bit errors only).
(f) Draw the hardware syndrome generator diagram. 
(g) Suppose →−c = 1 1 1 1 1 is sent and → −r = 0 1 1 1 1  is received. Show how the code
 

can correct this error.

Problem Set #8 page 1

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

Q4
Consider the generator polynomial for a (7,3) cyclic code defined by

g(p) = p4 + p3 + p2 + 1
(a) Find the encoding table for the cyclic code.
(b) What is the minimum distance dmin of the code.

Q5
Consider the generator polynomial for a (7,4) cyclic code defined by
g(p) = p3 + p2 + 1

(a) Find the encoding table for the cyclic code.

(b) What is the minimum distance dmin of the code.
(c) Find the systematic output codeword for input →
−  
c = 1 1 1 1 .

Problem Set #8 page 2

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

AUSTRALIAN NATIONAL UNIVERSITY
Department of Engineering

ENGN 3226 Digital Communications

Problem Set #8 Solution

Q1: Complete Solution

(a)
Testing for hamming code, we have
m = n−k = 6−3 = 3
k = 2m − m − 1 = 23 − 3 − 1 = 4 6= 3
n = 2m − 1 = 23 − 1 = 7 6= 6
Hence (6, 3) is not a Hamming code.

We have
 
1 0 0 1 1 0
→
−  0
G = 1 0 0 1 1 
0 0 1 1 0 1
 
1 1 0
→
−  0
P = 1 1 
1 0 1
 
1 0 1
→
−T  1
P = 1 0 
0 1 1
 
1 0 1
→
−  1
I3 = 1 0 
0 1 1
→
− − .→
→ −
H = [ P T .. I n−k ]
 
1 0 1 1 0 0
→
−
H =  1 1 0 0 1 0 
0 1 1 0 0 1

(b)
The encoding table for (6, 3) linear block code is

Message Code word Weight of code word

000 000000 0
001 001101 3
010 010011 3
011 011110 4
100 100110 3
101 101011 4
110 110101 4
111 111000 3

Problem Set #8 page 3

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

This is calculated as follows
 
1 0 0 1 1 0
→
− →
−
c0=→
−  
m0 G = 0 0 0  0 1 0 0 1 1 
0 0 1 1 0 1
 
= 0 0 0 0 0 0
 
→
− →
−  1 0 0 1 1 0
c1=→
− 
m1 G = 0 0 1  0 1 0 0 1 1 
0 0 1 1 0 1
  →
−
= 0 0 1 1 0 1 (3rd row of G )
 
→
− →
−  1 0 0 1 1 0
c2=→
− 
m2 G = 0 1 0  0 1 0 0 1 1 
0 0 1 1 0 1
  →
−
= 0 1 0 0 1 1 (2nd row of G )
 
→
− →
−  1 0 0 1 1 0
c3=→
− 
m3 G = 0 1 1  0 1 0 0 1 1 
0 0 1 1 0 1
  →
− →
−
= 0 1 1 1 1 0 (2nd row of G + 3rd row of G )
 
→
− →
−  1 0 0 1 1 0
c4=→
− 
m4 G = 1 0 0  0 1 0 0 1 1 
0 0 1 1 0 1
  →
−
= 1 0 0 1 1 0 (1st row of G )
 
→
− →
−  1 0 0 1 1 0
c5=→
− 
m5 G = 1 0 1  0 1 0 0 1 1 
0 0 1 1 0 1
  →
− →
−
= 1 0 1 0 1 1 (1st row of G + 3rd row of G )
 
→
− →
−  1 0 0 1 1 0
c6=→
− 
m6 G = 1 1 0  0 1 0 0 1 1 
0 0 1 1 0 1
  →
− →
−
= 1 1 0 1 0 1 (1st row of G + 2nd row of G )
 
→
− →
−  1 0 0 1 1 0
c7=→
− 
m7 G = 1 1 1  0 1 0 0 1 1 
0 0 1 1 0 1
  →
− →
− →
−
= 1 1 1 0 0 0 (1st row of G + 2nd row of G + 3rd row of G )

(c)
From encoding table, we have

dmin = 3
e = dmin − 1 = 2
 
1
t ≤ (dmin − 1) ≤ 1
2
Hence the (6, 3) linear block code can detect 2 bit errors and correct 1 bit error in 6 bit output codeword.

Problem Set #8 page 4

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

(d)
The output for general code word is
 
1 0 0 1 1 0
→
− →
−
c =→
−  
mG = m1 m2 m3  0 1 0 0 1 1 
0 0 1 1 0 1
 
= m1 m2 m3 m1 + m3 m1 + m2 m2 + m3

The hardware encoder implementation is

m (6,3) Linear block code encoder c

m1 m2 m3 c1 c2 c3 c4 c5 c6

Figure 1: Figure for Question 1 (d).

(e)
We have
 
1 0 1 1 0 0
→
−
H =  1 1 0 0 1 0 
0 1 1 0 0 1
 
1 1 0
 0 1 1 
 
→
−T  1 0 1 
H =  
 1 0 0 
 
 0 1 0 
0 0 1
The decoding table is
Error Pattern Syndrome Comment
000000 000 all 0’s
→
−
100000 110 1st row of H T
→
−
010000 011 2nd row of H T
→
−T
001000 101 3rd row of H
→
−
000100 100 4th row of H T
→
−
000010 010 5th row of H T
→
−
000001 001 6th row of H T

Problem Set #8 page 5

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

(f)
The syndrome for general received word is
 
1 1 0

 0 1 1 

→ −r →
−s = → −T
H =

r1 r2 r3 r4 r5

r6 
1 0 1 


 1 0 0 

 0 1 0 
0 0 1
 
= r1 + r3 + r4 r1 + r2 + r5 r2 + r3 + r6

The hardware syndrome generator implementation is

r (6,3) Linear block code syndrome generator s

r1 r2 r3 r4 r5 r6 s1 s2 s3

Figure 2: Figure for Question 1 (h).

(g)
Given that →
− is sent and →
−r =
   
c = 1 1 1 0 0 0 1 1 1 0 0 1 is received.
 
1 1 0
 0 1 1 
 
→ −r →
−s = → −T
H =

1 1 1 0 0 1 
 1 0 1 

 1 0 0 
 
 0 1 0 
0 0 1
 
= 0 0 1

From decoding table, this syndrome corresponds to error pattern →

−
e = [000001]. Hence the corrected code
word is
→
−
y = →
−r + →
−
e
   
= 1 1 1 0 0 1 + 0 0 0 0 0 1
 
= 1 1 1 0 0 0

Problem Set #8 page 6

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

Q2: Partial Solution

(a)
Testing for hamming code, we have
m = n−k = 7−4 = 3
k = 2m − m − 1 = 23 − 3 − 1 = 4
n = 2m − 1 = 23 − 1 = 7
Hence (7, 4) is a Hamming code.

We have
→
− − .→
→ −
G = [ I k .. P ]
 
1 0 0 0 1 1 0
→
−  0 1 0 0 0 1 1 
G = 
 0 0 1

0 1 1 1 
0 0 0 1 1 0 1
→
− − .→
→ −
H = [ P T .. I n−k ]
 
1 0 1 1 1 0 0
→
−
H =  1 1 1 0 0 1 0 
0 1 1 1 0 0 1

(b)
The encoding table for (7, 4) linear block code is

Message Code word Weight of code word

0000 0000000 0
0001 0001101 3
0010 0010111 4
0011 0011010 3
0100 0100011 3
0101 0101110 4
0110 0110100 3
0111 0111001 4
1000 1000110 3
1001 1001011 4
1010 1010001 3
1011 1011100 4
1100 1100101 4
1101 1101000 3
1110 1110010 4
1111 1111111 7

(c)
From encoding table, we have
dmin = 3
e = dmin − 1 = 2
 
1
t ≤ (dmin − 1) ≤ 1
2
Hence the (7, 4) linear block code can detect 2 bit errors and correct 1 bit error in 7 bit output codeword.

Problem Set #8 page 7

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

(d)
The output for general code word is
 
1 0 0 0 1 1 0
→
− →
−  0 1 0 0 0 1 1 
c =→
− 
mG = m1 m2 m3 m4  0

0 1 0 1 1 1 
0 0 0 1 1 0 1
 
= m1 m2 m3 m4 m1 + m3 + m4 m1 + m2 + m3 m2 + m3 + m4
The hardware encoder implementation is

m (7,4) Hamming code encoder c

m1 m2 m3 m4 c1 c2 c3 c4 c5 c6 c7

Figure 3: Figure for Question 2 (d).

(e)
We have
 
1 1 0

 0 1 1 

 1 1 1 
→
−T  
H = 
 1 0 1 


 1 0 0 

 0 1 0 
0 0 1
The decoding table is
Error Pattern Syndrome
0000000 000
1000000 110
0100000 011
0010000 111
0001000 101
0000100 100
0000010 010
0000001 001

Problem Set #8 page 8

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

(f)
The syndrome for general received word is
 
1 1 0

 0 1 1 

 1 1 1 
→ −r →
−s = → −T
H =

r1 r2 r3 r4 r5 r6

r7  1 0 1


 

 1 0 0 

 0 1 0 
0 0 1
 
= r1 + r3 + r4 + r5 r1 + r2 + r3 + r6 r2 + r3 + r4 + r7

The hardware syndrome generator implementation is

r (7,4) Hamming code syndrome generator s

r1 r2 r3 r4 r5 r6 r7 s1 s2 s3

Figure 4: Figure for Question 2 (h).

(g)
Given that →
− is sent and →
−r =
   
c = 1 0 0 1 0 1 1 1 1 0 1 0 1 1 is received.
 
1 1 0
 0 1 1 
 
 1 1 1
 
→ −r →
−s = → −T
=

1 1 0 1 0 1 1 

H  1 0 1 

 1 0 0 
 
 0 1 0 
0 0 1
 
= 0 1 1

From decoding table, this syndrome corresponds to error pattern →

−
e = [0100000]. Hence the corrected code
word is
→
−
y = →
−r + →
−
e
   
= 1 1 0 1 0 1 1 + 0 1 0 0 0 0 0
 
= 1 0 0 1 0 1 1

See also Lecture 19, Example 1.

Problem Set #8 page 9

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

Q3: Solution
(a)

→
− − .→
→ −
G = [ I k .. P ]
→
−  
G = 1 1 1 1 1
→
− − .→
→ −
H = [ P T .. I n−k ]
 
1 1 0 0 0
→
−  1 0 1 0 0 
H = 
 1 0 0

1 0 
1 0 0 0 1

(b)
The encoding table for (5, 1) linear block code is

Message Code word Weight of code word

0 00000 0
1 11111 5

(c)
From encoding table, we have

dmin = 5
e = dmin − 1 = 4
 
1
t ≤ (dmin − 1) ≤ 2
2
Hence the (5, 1) linear block code can detect 4 bit errors and correct 2 bit errors in 5 bit output codeword.

(d)
The output for general code word is
→
− →
−
c =→ −   
mG = m1 1 1 1 1 1
 
= m1 m1 m1 m1 m1

The hardware encoder implementation is

m (5,1) Linear block code encoder c

m1 c1 c2 c3 c4 c5

Figure 5: Figure for Question 3 (d).

Problem Set #8 page 10

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

(e)
We have
 
1 1 1 1
 1 0 0 0 
→
−T  
H = 
 0 1 0 0 

 0 0 1 0 
0 0 0 1
The decoding table is
Error Pattern Syndrome
00000 0000
10000 1111
01000 1000
00100 0100
00010 0010
00001 0001

(f)
The syndrome for general received word is
 
1 1 1 1
 1 0 0 0 
→ −r →
−s = → −T
H =

r1 r2 r3 r4 r5

 0 1 0 0


 
 0 0 1 0 
0 0 0 1
 
= r1 + r2 r1 + r 3 r1 + r4 r1 + r5

The hardware syndrome generator implementation is

r (5,1) Linear block code syndrome generator s

r1 r2 r3 r4 r5 s1 s2 s3 s4

Figure 6: Figure for Question 3 (h).

Problem Set #8 page 11

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

(g)
Given that →
− is sent and →
−r =
   
c = 1 1 1 1 1 0 1 1 1 1 is received.
 
1 1 1 1
 1 0 0 0 
→ −r →
−s = → −T
=

0 1 1 1 1 
 
H  0 1 0 0 

 0 0 1 0 
0 0 0 1
 
= 1 1 1 1

From decoding table, this syndrome corresponds to error pattern →

−
e = [1000]. Hence the corrected code word
is
→
−
y = →
−r + →
−
e
   
= 0 1 1 1 1 + 1 0 0 0 0
 
= 1 1 1 1 1

Q4: Complete Solution

(a)
Given that the generator polynomial for a (7,3) cyclic code is
g(p) = p4 + p3 + p2 + 1

The output code words are given by

c(p) = M(p)g(p)
Tabulating the results
Input M(p) c(p) = M(p)g(p) Code word Weight of code word
000 0 0 0000000 0
001 1 p4 + p3 + p2 + 1 0011101 4
010 p p5 + p4 + p3 + p 0111010 4
011 p+1 p5 + p2 + p + 1 0100111 4
100 p 2 p6 + p5 + p4 + p3 1111000 4
101 2
p +1 p6 + p5 + p3 + 1 1101001 4
110 2
p +p p6 + p3 + p2 + p 1001110 4
111 2
p + p+1 p6 + p4 + p + 1 1010011 4

Note: XOR addition is used here, e.g.

(p2 + 1)(p4 + p3 + p2 + 1) = p6 + p5 + p4 + p2 + p4 + p3 + p2 + 1
= p6 + p5 + (1 + 1)p4 + p3 + (1 + 1)p2 + 1
= p6 + p5 + (0)p4 + p3 + (0)p2 + 1
= p6 + p5 + p3 + 1

(b)
dmin = 4.

Problem Set #8 page 12

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ANU ENGN 3226

Q5: Partial Solution

(a)
See Lecture 19, Slide 18 for solution.

(b)
dmin = 3.

(c)
Given that →
−  
c = 1 1 1 1 .

Given that the generator polynomial for a (7,4) cyclic code is

g(p) = p3 + p2 + 1

The systematic output code word is

pn−k = p3
M(p) = p3 + p2 + p + 1
pn−k M(p) = (p3 )(p3 + p2 + p + 1) = p6 + p5 + p4 + p3
pn−k M(p) p6 + p5 + p4 + p3
=
g(p) p3 + p2 + 1
p2 + p + 1
= p3 + p + 1 +
p3 + p2 + 1
b(p) = p2 + p + 1
c(p) = pn−k M(p) + b(p)
= p6 + p5 + p4 + p3 + p2 + p + 1
→
−
c =

1 1 1 1 1 1 1


See Lecture 19, Example 3 for detailed steps.

Problem Set #8 page 13

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])

 lOMoARcPSD|22905522

ETEC-304 Information Theory and Coding

Quiz – 2
Name: ______________________________ Roll No. _________________
Time Allotted: 30 mins Total Marks: 15 Student Score:_____
Please write your final answers in the space provided.

1) Which of the following is NOT a requirement for a linear block code?

a. All zeros must be a codeword
b. Modulo-2 addition of any two codewords is also a codword
c. Any cyclic shift in a codeword leads to another codeword in the same code
d. All of these are required. [1 mark]
2) A (5, 1) repetition code can correct upto _____ errors and detect upto ____ errors. [1 mark]
3) For an (n, k) linear block code, what would be the length of the syndrome for any error. [1 mark]
a. n b. k c. n – k d. n + k
4) Hamming distance between the codewords (11101001) and (00100101) is ____. [1 marks]
5) For the code generated by the given generator matrix G, what would be the generator matrix for its dual code.
1 0 0 1 1 1
𝐺 = [0 1 0 1 1 0] Ans. [2 marks]
0 0 1 1 0 1

6) For a given (n, k) cyclic block code, if the generator polynomial is g(x), then the parity check polynomial h(x) is
given by ____________. [1 mark]
7) For given message bits (110100), the convolution code as generated by a (2, 1, 2) code, with generator polynomials
g1(x) = 1+x and g2(x) = 1+x+x2 would be _______________________ [3 marks]
8) Draw the trellis diagram for the convolution encoder of question (7) [5 marks]

Downloaded by KRITIKA SRIVASTAVA (kritikasrivastava356@[Link])