Course Code:EECE3121

Course: INFORMATION THEORY AND ERROR CONTROL CODING

• Dr. Ambar Bajpai

• Associate Professor
• Department of Electrical, Electronics and Communication Engineering
• GITAM School of Technology (GST),
• GITAM University, Bengaluru Campus

Educational Purpose Only 1

Course Description:

This course provides a basic understanding of the measure of information, source

coding, channel capacity and channel coding techniques. Source coding is used to
compress the size of the data generated from digital source by reducing redundancy.
Channel capacity is a much used metric for the maximum amount of traffic or signal
that can move over a particular infrastructure channel. Channel coding is used for
error detection and/or error correction by adding some redundant bits to source
coded data in order to improve performance.
Course Educational
Objectives:
● To introduce the principles and applications of information theory in terms of
probability and entropy and practical aspects of data compression and source
coding techniques.
● To explain the quantitative measure of information that may be used in order to
Build efficient solutions to communication engineering problems such as calculating
The capacity of a communication channel with and without noise.
● To explain linear block codes, cyclic codes, and convolution coding techniques for
Channel performance improvement against errors.
● To describe a suitable error control coding technique for burst error correction.

Educational Purpose Only 4

 • CO1 Describe the sampling of analog signals and
their reconstruction in time and frequency domain
• CO2 Explain the time division multiplexing of
analog telephone signals using pulse code
Course Modulation
• CO3 Describe the different carrier modulation
outcome schemes and compare their BER performance and
bandwidth requirements
• CO4 Derive the Nyquist criterion for distortionless
baseband transmission
• CO5 Describe the generation and detection of DS
and FH spread spectrum, OFDM systems

Educational Purpose Only 5

 • Module-1: Source Coding • Module-2: Channel
Learned and Introduction to information Capacity and Coding
theory, uncertainty and Channel models, channel
Upcoming information, average mutual capacity, information
information and entropy, capacity theorem, the
Module source coding theorem, Shannon limit, Channel
Huffman coding, the Coding, Type of errors.
Lempel-Ziv algorithm.

Educational Purpose Only 6

Textbooks
1- Ranjan Bose, Information Theory,
Coding and Cryptography, 2/e, Tata
McGraw- Hill, 2010.
2- Simon Haykin, Communication
Systems, 4/e, John Wiley and Sons,
2002.

Educational Purpose Only 7

Module I

Source Coding

Introduction to information theory, uncertainty and

information, average mutua information and entropy,
source coding theorem, Huffman coding, the Lempel-Ziv
algorithm.

Educational Purpose Only 8

 Module 1
INFORMATION THEORY

Dept. [Link] Subject ITC 9

Father of Digital Communication

The roots of modern digital communication

stem from the ground-breaking paper “A
Mathematical Theory of Communication” by
Claude Elwood Shannon in 1948.
 Model of a Digital Communication
System

Message Encoder
e.g. English symbols e.g. English to 0,1 sequence
Information
Coding
Source

Communication
Channel

Destination Decoding

Can have noise

Decoder or distortion
e.g. 0,1 sequence to English
Communication Channel Includes
And even this…
 Shannon’s Definition
of Communication

“The fundamental problem of

communication is that of reproducing
at one point either exactly or
approximately a message selected at
another point.”
“Frequently the messages have meaning”

“... [which is] irrelevant to the engineering problem.”

 Shannon Wants to…

• Shannon wants to find a way for “reliably” transmitting

data throughout the channel at “maximal” possible rate.

Information
Coding
Source

Communication
Channel

Destination Decoding

For example, maximizing the

speed of ADSL @ your home
In his 1948 paper he build a rich theory to the
problem of reliable communication, now
called “Information Theory” or “The Shannon
Theory” in honor of him.
Shannon’s Vision

Source Channel
Data
Encoding Encoding
Channel
Source Channel
User
Decoding Decoding
Example: Disk Storage

Data Zip Add CRC

Channel
Verify
User Unzip
CRC
In terms of Information Theory
Terminology
Source
Zip = Encoding Data Compression

= Source
Unzip Data Decompression
Decoding

Channel Error Protection

Add CRC = Encoding

Verify Channel
CRC = Decoding Error Correction
Example: VCD and DVD

MPEG RS
Moive
Encoder Encoding
CD/DVD
MPEG RS
TV
Decoder Decoding

RS stands for Reed-Solomon Code.

Example: Cellular Phone

Speech CC
Encoding Encoding
Channel
Speech CC
Decoding Decoding

GSM/CDMA
CC stands for Convolutional Code.
Example: WLAN IEEE 802.11b

CC
Data Zip
Encoding
Channel
CC
User Unzip
Decoding

IEEE 802.11b
CC stands for Convolutional Code.
Shannon Theory
• The original 1948 Shannon Theory contains:

1. Measurement of Information
2. Source Coding Theory
3. Channel Coding Theory
Measurement of Information

• Shannon’s first question is

“How to measure information
in terms of bits?”

= ? bits

= ? bits
Or Lottery!?

= ? bits
Or this…

= ? bits

= ? bits
 1.1 INTRODUCTION

❑The block diagram of an information system can be

drawn as shown in figure. the meaning of the word
"information "in information theory is "message" or
"intelligence".
❑This message may be an electrical message such as
voltage, current or power or speech message • picture
message such as fascimile or television or music message.
A source which produces these messages is called
"information source".

Dept. [Link] Subject ITC 27

 INTRODUCTION

Block diagram of an information system

Dept. [Link] Subject ITC 28
 INTRODUCTION

Information sources can be classified into two categories:

[Link] information sources
[Link] information sources.
Analog information sources, such as a microphone actuated ( speech, or a TV
camera scanning a scene, emit one or more continuous amplitude electrical finals
with respect to time. The output of discrete information sources such as a teletype
or the numerical output of a computer consists of a sequence of discrete symbols
or letters.
An analog information source can be transformed into a discrete information
source through the process of sampling and quantizing.

Dept. [Link] Subject ITC 29

 INTRODUCTION

Discrete information sources are characterized by

(a) source alphabet
(b) symbol rate
(c) source alphabet probabilities and
(d) probabilistic dependence of symbols in a sequence.
• Example of source alphabet (discrete information source) a teletype having 26
letters of the English Alphabet plus several special characters such as full stop,
comma etc. along with numerals.
• The Symbol rate refers to the rate at which the teletype produces characters. Ex: If
the teletype operates at the speed of 10 characters/sec, then the symbol rate is said
to be symbols/sec.

Dept. [Link] Subject ITC 30

 INTRODUCTION
SOURCE ENCODER:
• Let the input to the source encoder be a string Of source symbols from the source Alphabet
• S = {s1, s2,…sn }occurring at a rate of “Rs," symbols/sec.

• The source encoder converts the symbol sequence into a binary sequence of 0's and 1 by
assigning code-words to the symbols in the input sequence.

• Binary coding is preferred, because of its high efficiency of transmission and also the case with
which they can be transmitted over the channel [other types of coding such as ternary,
quaternary coding etc.

• The simplest way of coding is to assign a fixed length binary code-we, to each symbol in the
input sequence. But, fixed-length coding of individual symbols in, source output is efficient
only if the symbols occur with equal probabilities in a statistics independent sequence. In most
practical situations, the symbols occur with unequal probabilities.
Dept. [Link] Subject ITC 31
 INTRODUCTION

TRANSMITTER:
• The transmitter couples the input message signal to the channel.
• Sometimes be possible to couple the input transducer directly to the channel.
• It is often necessary to process and modify the input signal for efficient
transmission over the channel.
• Signal processing operations performed by the transmitter include armplification,
filtering and modulation.
• The most important of these operations is modulation - a process designed to
match the properties of the transmitted signal to the channel through the use of
carrier wave.

Dept. [Link] Subject ITC 32

 INTRODUCTION

CHANNEL:

• A communication channel provides the electrical connection

between the source and the destination.

• The channel may be a pair of wires (2-line transmission system)

or a telephone cable or free space over which the information
bearing signal is radiated.

• Due to physical limitations, communication channels have only

finite bandwidth and the information bearing signal suffers
amplitude and phase distortion as it travels over the channel. In
addition to the distortion, the signal power also decreases due to
attenuation
Dept. [Link]
of the channel. Subject ITC 33
Next Session
1.2 Measure of Information

Dept. [Link] Subject ITC 34

 MEASURE OF INFORMATION

• In order to know and compare the "information content" of

various messages produced by an information source, a measure
is necessary to quantitatively know that information content.
For this, let us consider an information source producing
independent sequence of symbols from source alphabet S = {s1,
s2,… sq} with probabilities P = {p1, p2, …pq} respectively.
• Let SK be a symbol chosen for transmission at any instant of
time with a probability equal to pK. Then the "Amount of
Information" or "Self-Information" of message SK (provided it
is correctly identified by the receiver) is given by

Dept. [Link] Subject ITC 35

 1.1 MEASURE OF INFORMATION

If the base of the logarithm is 2, then the units are called "BITS", which is the
short form of "Binary Units".

If the base is ''10", the units are "HARTLEYS" or "DECITS".

If the base is "e", the units are "NATS" and

if the base, in general, is "r", the units are called "r-ary units"

Dept. [Link] Subject ITC 36

 MEASURE OF INFORMATION
Suppose that you are planning a trip to Chennai, Tamil Nadu state from Bangalore in
peak winter time (may be chrismas time). To know the weather at Chennai, you
telephone the weather bureau or browse through internet and receive one of the
following forecasts.
1. Sun will rise in east on the day of trip
2. Weather will be dry, sultry and sunny for most of the day
3. It will be a very cold day,
4. There will be snowfall on that particular day in Chennai.

Dept. [Link] Subject ITC 37

All events are probabilistic!
• Using Probability Theory, Shannon showed
that there is only one way to measure
information in terms of number of bits:

H ( X ) = −  p( x ) log 2 p( x )
x

called the entropy function

For example
• Tossing a dice:
• Outcomes are 1,2,3,4,5,6
• Each occurs at probability 1/6
• Information provided by tossing a dice is

6 6
H = − p(i ) log 2 p(i ) = − p(i ) log 2 p(i )
i =1 i =1
6
1 1
= − log 2 = log 2 6 = 2.585 bits
i =1 6 6
 Wait!
It is nonsense!

The number 2.585-bits is not an integer!!

What does you mean?
Shannon’s First Source
Coding Theorem

• Shannon showed:
“To reliably store the information
generated by some random source
X, you need no more/less than, on
the average, H(X) bits for each
outcome.”
Let’s Do Some Test!
File Size Compression
Ratio
No 8,000,000 100%
Compression bits
Shannon 2,585,000 32.31%
bits
Winzip 2,930,736 36.63%
bits
WinRAR 2,859,336 35.74%
bits
Follow-up Story
Later in 1952, David Huffman,
while was a graduate student in
MIT, presented a systematic
method to achieve the optimal
compression ratio guaranteed by (1925-1999)
Shannon. The coding technique is therefore called
“Huffman code” in honor of his achievement.
Huffman codes are used in nearly every application
that involves the compression and transmission of
digital data, such as fax machines, modems,
computer networks, and high-definition television
(HDTV), to name a few.
 Problems
➢Example 1.1 : The binary symbols '0' and '1' are transmitted with probabilities ¼ and
¾ respectively. Find the corresponding self-informations.

Dept. [Link] Subject ITC 44

 Problems
•Solution

•Self-information in a '0' = I0 = log(1/ P0) = log 4 = 2 bits.

•Self-information in a '1' = I1 = log(1/ P1) = log 4/3 I1=0.415 bits.

Thus, it can be observed that more information is carried by a less likely message.
Logarithmic expression is chosen for measuring information because of the
follow reasons:
[Link] content or self-information of any message cannot be negative.
Each message must contain certain amount of information.
[Link] lowest possible self-information is "zero" which occurs for a sure event since P
(sure event) = 1.

Dept. [Link] Subject ITC 45

 Zero-Memory Source
• It represents a model of a discrete information source emitting sequence of symbols from a
fixed finite source alphabet
• S = {s1, s2,….sq} Successive symbols are selected according to some fixed probability law and are
statistically independent of one another.
• This means that there is no connection between any two symbols and that the source has no
memory.
• Such type of sources are called "memoryless" or "zero-memory" sources.

Dept. [Link] Subject ITC 46

Next Session
AVERAGE INFORMATION CONTENT
(ENTROPY) OF SYMBOLS IN LONG
INDEPENDENT SEQUENCES

Dept. [Link] Subject ITC 47

 AVERAGE INFORMATION
CONTENT (ENTROPY) OF
SYMBOLS IN LONG INDEPENDENT
SEQUENCES

Dept. [Link] Subject ITC 48

 AVERAGE INFORMATION
CONTENT (ENTROPY) OF
SYMBOLS IN LONG INDEPENDENT
SEQUENCES

Dept. [Link] Subject ITC 49

 Information Rate

Dept. [Link] Subject ITC 50

 Field of Interest
• Information theory deals with the problem
of efficient and reliable transmission of
information.
• It specifically encompasses theoretical and applied aspects
of
- coding, communications and communications networks
- complexity and cryptography
- detection and estimation
- learning, Shannon theory, and stochastic processes

Dept. [Link]
51
Subject ITC
Express everything in bits: 0 and 1
• Discrete finite ensemble:
• a,b,c,d -> 00, 01, 10, 11

Dept. [Link]
52
Subject ITC
 Problems
1. Consider a discrete memoryless source with a source
alphabet A = { so, s1, s2} with respective probs. p0 = ¼,
p1 = ¼, p2 = ½. Find the entropy of the source

Dept. [Link] Subject ITC 53

 Problems

Dept. [Link] Subject ITC 54

 Problems

Dept. [Link] Subject ITC 55

 Problems

Dept. [Link] Subject ITC 56

3

Dept. [Link] Subject ITC 57

Dept. [Link] Subject ITC 58
4.

Dept. [Link] Subject ITC 59

Dept. [Link] Subject ITC 60
5.

Dept. [Link] Subject ITC 61

Dept. [Link] Subject ITC 62
Dept. [Link] Subject ITC 63
Dept. [Link] Subject ITC 64
Dept. [Link] Subject ITC 65
Dept. [Link] Subject ITC 66
Dept. [Link] Subject ITC 67
Dept. [Link] Subject ITC 68
Dept. [Link] Subject ITC 69
Dept. [Link] Subject ITC 70
Dept. [Link] Subject ITC 71
Dept. [Link] Subject ITC 72
Dept. [Link] Subject ITC 73
Dept. [Link] Subject ITC 74
Dept. [Link] Subject ITC 75
Dept. [Link] Subject ITC 76
Uncertainty and Information
▪ Intuitive Feel : Occurence of a less probable event conveys more
information
▪ Mathematical Measures:
▪ Definition 1 Consider a discrete random variable X with
possible outcomes xi, i = 1, 2, ..., n. The self information of
the event X = xi is defined as

I(xi) = log 1 = – log P(xi).

 P( x ) 
 i 

When the base of the logarithm is 2 the units of I(x) are in bits
and when the base is e, the units are in nats (natural units).

77
Uncertainty and Information
▪ Definition 2 : The mutual information I(xi; yj) between xi
and yj is defined as

 P ( xi | y j ) 
I(xi; yj) =log  
 P ( xi ) 

▪ Definition 3: The conditional self information of the event

X = xi given Y = yj is defined as

 1 
I(xi | yj) =log  = – log P(xi | yj).
 P( x | y ) 
 i j 

78
❑ Source Coding Theorem
❑ Source Coding
❑ Fixed and Variable Length Coding
❑ Prefix Coding
❑ Kraft McMillan Inequality
Source
Coding
Properties
of Codes
Properties
of Codes
Properties
of Codes
Properties
of Codes
Properties
of Codes
 Source Coding Theorem

▪ Objective Efficient coding of symbols generated by a source

▪ Discrete Memoryless Source (DMS)
▪ Definition 8 A code is a set of vectors called codewords.
▪ Fixed length codes, Variable length codes
▪ Definition 9 A prefix code is one in which no codeword
forms the prefix of any other codeword. Such codes are
also called uniquely decodable or instantaneous codes.
▪ Theorem 1 (Kraft Inequality) A necessary and sufficient
condition for the existence of a binary code with codewords
having lengths n1 n2 ... nL that satisfy the prefix condition
L

2
k =1
− nk
 1.

86
Source Coding …
Source Coding …
Source Coding …
Source Coding …(Encoding)
Source Coding …
Kraft McMillan Inequality
 Source Coding Theorem
▪ Theorem 2 (Source Coding Theorem) Let X be the ensemble
of letters from a DMS with finite entropy H(X) and the output
symbols xk, k = 1, 2, ..., L, occurring with probabilities P(xk), k
= 1, 2, ..., L. It is possible to construct a code that satisfies the
prefix condition and has an average length R that satisfies the
inequality
H(X)  R  H(X) + 1.

▪ Definition 10 The efficiency of a prefix code is defined as

H ( x)
=
R

Indian Institute of Ranjan Bose

94
Technology, Delhi Department of Electrical Engineering
•Quantity of Information (noiseless system)

I = log 2( 1 / p ) = −log 2 p ( bit )

a) Depends on probability of event.
b) Depends on length of message.

•Average Information: Entropy probability of

event
Source producing many symbols of probabilities p1 , p2 , p3
etc.

H = − pklogpk (bits)
•Redundancy

Actual entropy
R = 1−
Maximum entropy

•Conditional entropy
H(j|i)
If there is intersymbol influence, average
information is given by

H ( j | i ) = − p(ij ) log p( j | i )

i j

Conditional probability
Joint probability (probability of j given i)
•Coding in noiseless channel : Source coding

(Speed of transmission is the main consideration )

•Important properties of codes

1. uniquely decodable (all combinations of code words distinct)

2. instantaneous (no code words a prefix of another)
3. compact (shorter code words given to more probable
symbols)
Important parameters
H Average Length L =  pi li ,
Efficiency of coding E =
L
wher li is length (in binary
e digits)
• Coding methods
i

1
Special case : If the symbol probabilit ies p =   ,
 2
i

where  is an integer , then perfect coding is obtained by

i

setting the length of code words l =

i i

▪ Fano-Shannon method
▪ Huffman’s Method
Huffman Coding
▪ A variable length encoding algorithm was suggested by
Huffman in 1952, based on the source symbol probabilities
P(xi), i = 1, 2, ..., L. The algorithm is optimal in the sense
that the average number of bits required to represent the
source symbols is a minimum and also meets the prefix
condition.

99
Huffman Coding
• Huffman coding is an entropy encoding algorithm used for lossless data
compression.
• In this algorithm fixed length codes are replaced by variable length codes.
• When using variable-length code words, it is desirable to create a prefix code,
avoiding the need for a separator to determine codeword boundaries. Huffman
Coding uses such prefix code.
Algorithm and Example

• Huffman procedure works as follow:

• 1. Symbols with a high frequency are expressed using shorter encodings than
• symbols which occur less frequently.
• 2. The two symbols that occur least frequently will have the same length.
• The Huffman algorithm uses the greedy approach i.e. at each step the algorithm
• chooses the best available option. A binary tree is built up from the bottom up.
▪ Example 3 Consider a DMS with seven possible symbols xi, i = 1, 2, ..., 7 and the
corresponding probabilities p1 = 0.37, p2 = 0.33, p3 = 0.16, p4 = 0.07, p5 = 0.04, p6
= 0.02, and p7
= 0.01. We first arrange the probabilities in the decreasing order and then construct
the Huffman tree.
Huffman Coding
▪ Example 3 (Continued)
x 0.3 0
1 7
x 0 1.0
0.3 0
2 3
x 0 0.6
0.1 6 1
3 6
x 0 0.3
4
0.0
7
0 1 R
0 0.1
x 0.0 4 1 H(X) = 2.1152 bits
5 4 0.0
0
x 0.0
0.0
7 1 = 2.1700 bits
6 2
x 3 1
0.0
1
7 1

Huffman Coding Tree

104
Huffman Coding
Huffman Entropy analysis
Properties of Huffman Coding
1. Unique Prefix Property: No Huffman code is a
prefix of any other Huffman code - precludes any
ambiguity in decoding
2. Optimality: minimum redundancy code - proved
optimal for a given data model (i.e., a given,
accurate, probability distribution):
• The two least frequent symbols will have the same
length for their Huffman codes, differing only at the last
bit
• Symbols that occur more frequently will have shorter
Huffman codes than symbols that occur less frequently
• The average code length for an information source S is
strictly less than η + 1
Huffman summary
• Achieves entropy when occurrence probabilities
are negative powers of 2
• Alphabet and its distribution must be known in
advance
• Given the Huffman tree, very easy (and fast) to
encode and decode
• Huffman code is not unique (because of some
arbitrary decisions in the tree construction)
Comparing the algorithms:

Huffman Coding Vs. Arithmetic

Coding
The Lempel-Ziv Algorithm

▪ Lempel-Ziv algorithm is a Variable-to-Fixed Length Source

Coding Algorithm, does not need source statistics
▪ Huffman coding is optimal for a DMS source but not the best
choice for a source with memory
▪ Lempel-Ziv algorithm utilizes the statistical inter-dependence of
the letters in the alphabet along with their individual probabilities
of occurrence.
▪ Lempel-Ziv algorithm is widely used in practice. The compress
and uncompress utilities of the UNIX operating system use a
modified version of this algorithm.

110
The Lempel-Ziv Algorithm
Input String 101011011010101011
Table 1 Dictionary for the Lempel-Ziv algorithm
Dictionary Dictionary Fixed Length
Location content Codeword
001 1 0001
010 0 0000
011 10 0010
100 11 0011
101 01 0101
110 101 0111
111 010 1010
- 1011 1101

Coded String 00010000001000110101011110101101

111
Dictionary-based Coding
• LZW uses fixed-length code words to represent
variable-length strings of symbols/characters that
commonly occur together, e.g., words in English
text
• LZW encoder and decoder build up the same dictionary
dynamically while receiving the data

• LZW places longer and longer repeated entries into

a dictionary, and then emits the code for an
element,
112 rather than the string itself, if the element
has already been placed in the dictionary
LZW compression for string
“ABABBABCABABBA”
• The output codes are: 1 2 4 5 2 3 4 6 1. Instead of
sending 14 characters, only 9 codes need to be sent
(compression ratio = 14/9 = 1.56).
S C Output Code
1
String
A
2 B
3 C
A B 1 4 AB
B A 2 5 BA
A B
AB B 4 6 ABB
B A
BA B 5 7 BAB
B C 2 8 BC
C A 3 9 CA
A B
AB A 4 10 ABA
A B
AB B
ABB A 6 11 ABBA
113
A EOF 1
LZW decompression (1 2 4 5 2 3
4 6 1)
S K Entry/output Code String

1 A
2 B
3 C

NIL 1 A
A 2 B 4 AB
B 4 AB 5 BA
AB 5 BA 6 ABB
BA 2 B 7 BAB
B 3 C 8 BC
C 4 AB 9 CA
AB 6 ABB 10 ABA
ABB 1 A 11 ABBA
A EOF

ABABBABCABABBA
114
Comparison
 Summary
▪Uncertainty and Information

▪Average Mutual Information and Entropy

▪Information Measures for Continuous Random variables

▪Source Coding Theorem

▪Huffman Coding

▪The Lempel-Ziv Algorithm

▪Run Length Encoding