Source Coding

Chirayu Athalye

Basic Concepts

Source Coding
Theorem

Source Coding
Techniques
Information and its Efficient Representation Applications

AEP: Asymptotic
Equipartition Property

Entropy Rate of a
Chirayu D. Athalye Stochastic Process

References

Department of Electrical & Electronics Engineering,

BITS Pilani, K K Birla Goa Campus.

2026
 Source Coding

Self Information Chirayu Athalye

Let X be a discrete random variable with possible outcomes {x1 , . . . , xn }. The self information Basic Concepts
of the event X = xi is given by Self Information and Mutual
Information
  Average Mutual Information
1 and Entropy
I (xi ) := log = − log P(xi ) ≥ 0.
P(xi ) Information Measures for
Continuous RVs
KL Divergence and JS
Remark: Divergence

Source Coding
1 The unit of self information depends on the base of log (Common Choices: 2 or e). Theorem

2 Depending upon whether the base is 2 or e, we have bits or nats as the unit. Source Coding
Techniques

Applications

Example (Desired Additive Property of log(·) Measure) AEP: Asymptotic

Equipartition Property
Consider a binary source that generates equiprobable outputs {0, 1}. Entropy Rate of a
Stochastic Process
The information content of each output from the source is
References

I (xi ) = − log2 (0.5) = 1 bit.

Suppose the source is memoryless (i.e., successive outputs are statistically independent).
There are 2m equiprobable m-bit blocks. The self information of an m-bit block is
I (xi ) = − log2 2−m = m bits.


 Source Coding

Chirayu Athalye

Why log(·) is used to measure the information? Basic Concepts

Self Information and Mutual
Consider two independent sources. Information
Average Mutual Information
For independent events, the probabilities multiply. and Entropy
Information Measures for
Continuous RVs
For independent sources, the information must add up. KL Divergence and JS
Divergence
Thus, a logarithmic measure of information is apt.
Source Coding
Theorem

Source Coding
Example (Desired Additive Property of log(·) Measure) Techniques

Consider a discrete memoryless source C that generates 2 bits simultaneously. Applications

AEP: Asymptotic
Source C consists of two independent binary sources A and B that generates equiprobable Equipartition Property
outputs {0, 1}. Entropy Rate of a
Stochastic Process
Thus, outputs {00, 01, 10, 11} generated by source C are equiprobable. Notice that References


I (cij ) = − log2 P(cij ) = − log2 P(ai ) P(bj ) = − log2 (0.25) = 2 bits.
Thus, the information content of the source C is sum of the information content of sources
A and B.
 Source Coding

Chirayu Athalye
Mutual Information
Basic Concepts
Let X and Y be random variables with possible outcomes {x1 , . . . , xn } and {y1 , . . . , ym }. Self Information and Mutual
Information

The mutual information between xi and yj is given by Average Mutual Information

and Entropy
 Information Measures for
 < 0, if P(xi | yj ) < P(xi ),
  Continuous RVs

P(xi | yj ) KL Divergence and JS

I (xi ; yj ) := log = 0, if P(xi | yj ) = P(xi ), Divergence

P(xi )  Source Coding

> 0, if P(xi | yj ) > P(xi ).

Theorem

Source Coding
Interpretation of I (xi ; yj ): Information provided (reduction in uncertainty) by the occurrence of Techniques

the event Y = yj about the event X = xi . Applications

AEP: Asymptotic
Equipartition Property

Remark Entropy Rate of a

Stochastic Process
1 The mutual information I (xi ; yj ) can be positive, negative, or zero. References

2 Since P(xi | yj ) P(yj ) = P(yj | xi ) P(xi ), we have I (xi ; yj ) = I (yj ; xi ).

3 If X and Y are statistically independent, then I (xi ; yj ) = 0.
4 If x and Y are fully dependent (i.e., P(xi | yj ) = 1), then I (xi ; yj ) = I (xi ).
 Source Coding

Example (Binary Symmetric Channel (BSC)) Chirayu Athalye

Let random variables X and Y represent the input and output of a BSC. Basic Concepts
Self Information and Mutual
Information
Average Mutual Information
P(Y = 0|X = 0) = 1 − p, and Entropy
Information Measures for
P(Y = 0|X = 1) = p, Continuous RVs
KL Divergence and JS
P(Y = 1|X = 1) = 1 − p, Divergence

P(Y = 1|X = 0) = p. Source Coding

Theorem

Source Coding
Techniques
Let P(X = 0) = P(X = 1) = 0.5. Using the total probability theorem, Applications

AEP: Asymptotic
P(Y = 0) = 0.5(1 − p) + 0.5p = 0.5. Equipartition Property

Entropy Rate of a
P(Y = 1) = 0.5p + 0.5(1 − p) = 0.5. Stochastic Process

References
Mutual information about occurrence of the event X = 0 given that we observed Y = 0 is
 
1−p

I (x0 ; y0 ) = I (y0 ; x0 ) = log2 = log2 2(1 − p) .
0.5
p


Similarly, I (x1 ; y0 ) = I (y0 ; x1 ) = log2 0.5 = log2 (2p).
 Source Coding
Example (Binary Symmetric Channel (BSC)) Chirayu Athalye

Remark: Basic Concepts

1 Suppose p = 0 (i.e., an ideal noiseless channel). Then, Self Information and Mutual
Information
Average Mutual Information
I (x0 ; y0 ) = log2 (2) = 1 bit and I (x1 ; y0 ) = log2 (0) = −∞. and Entropy
Information Measures for
Continuous RVs
2 Whereas, if p = 0.5, then KL Divergence and JS
Divergence

I (x0 ; y0 ) = log2 (1) = 0 and I (x1 ; y0 ) = log2 (1) = 0. Source Coding

Theorem

Source Coding
Techniques

Applications

AEP: Asymptotic
Equipartition Property

Entropy Rate of a
Stochastic Process

References

Figure: Plot of mutual information I (x0 ; y0 ) = log2 2(1 − p) vs error probability p.
 Source Coding

Example (Binary Channel) Chirayu Athalye

Let random variables X and Y represent the input and output of a binary channel. Basic Concepts
Self Information and Mutual
Information
Average Mutual Information
P(Y = 0 | X = 0) = 1 − p0 , and Entropy
Information Measures for
P(Y = 0 | X = 1) = p1 , Continuous RVs
KL Divergence and JS
P(Y = 1 | X = 1) = 1 − p1 , Divergence

P(Y = 1 | X = 0) = p0 . Source Coding

Theorem

Source Coding
Techniques
Let P(X = 0) = P(X = 1) = 0.5. Using the total probability theorem, Applications

AEP: Asymptotic
P(Y = 0) = 0.5(1 − p0 ) + 0.5p1 = 0.5(1 − p0 + p1 ). Equipartition Property

P(Y = 1) = 0.5p0 + 0.5(1 − p1 ) = 0.5(1 − p1 + p0 ). Entropy Rate of a

Stochastic Process

References
Mutual information about occurrence of the event X = 0 given that we observed Y = 0 is
   
1 − p0 2(1 − p0 )
I (x0 ; y0 ) = I (y0 ; x0 ) = log2 = log2 .
0.5(1 − p0 + p1 ) 1 − p0 + p1
 
Similarly, I (x1 ; y0 ) = I (y0 ; x1 ) = log2 1−p2p01+p1 .
 Source Coding
Conditional Self Information Chirayu Athalye
Let X and Y be random variables with possible outcomes {x1 , . . . , xn } and {y1 , . . . , ym }.
Basic Concepts
The conditional self information of the event X = xi given Y = yj is defined as Self Information and Mutual
Information
  Average Mutual Information
1 and Entropy
I (xi | yj ) := log = − log P(xi | yj ) ≥ 0.
P(xi | yj ) Information Measures for
Continuous RVs
KL Divergence and JS
Interpretation of I (xi | yj ): The self information about the event X = xi having observed the Divergence

event Y = yj . Source Coding

Theorem

Source Coding
Techniques
How self information, mutual information, and conditional self information are related?
Applications
P(yj ) P(xi )
By Bayes’ rule, = . Taking − log(·) of both sides, we get AEP: Asymptotic
P(yj | xi ) P(xi | yj ) Equipartition Property

Entropy Rate of a
Stochastic Process
I (xi ; yj ) = I (xi ) − I (xi | yj ).
References
This follows from the definitions too!
Interpretation:
1 I (xi ): How surprising is the event X = xi .
2 I (xi | yj ): How surprising is the event X = xi once we know Y = yj has occurred.
3 I (xi ; yj ): How much knowing Y = yj reduces/increases the surprise of the event X = xi .
 Source Coding

Chirayu Athalye

Average Mutual Information

Basic Concepts
Let X and Y be random variables with possible outcomes {x1 , . . . , xn } and {y1 , . . . , ym }. Self Information and Mutual
Information
Average Mutual Information
The average mutual information between X and Y is given by and Entropy
Information Measures for
n X
m n X
m  
X X P(xi | yj ) Continuous RVs

I (X ; Y ) := P(xi , yj ) I (xi ; yj ) = P(xi , yj ) log . KL Divergence and JS

i=1 j=1 i=1 j=1

P(xi ) Divergence

Source Coding
Theorem
Remark: Source Coding
Techniques
1 I (X ; Y ) ≥ 0; equality holds iff X and Y are statistically independent.
Applications
2 Since I (xi ; yj ) = I (yj ; xi ), we have I (X ; Y ) = I (Y , X ). AEP: Asymptotic
Equipartition Property

Entropy Rate of a
Entropy (Average Self Information) Stochastic Process

References
The average self information of a random variable X with possible outcomes {x1 , . . . , xn } is
given by n n
X X
H(X ) := P(xi ) I (xi ) = − P(xi ) log P(xi ) ≥ 0
i=1 i=1
 Source Coding

Chirayu Athalye
Remark
Basic Concepts
1 The term entropy originates from statistical mechanics, where it quantifies the level of Self Information and Mutual

disorder or randomness within a system. Information

Average Mutual Information

and Entropy
2 The entropy of X can be interpreted as E − log P(X ) . Information Measures for
Continuous RVs
KL Divergence and JS
Divergence
Example (Entropy of a Binary Source) Source Coding
Theorem

Source Coding
Consider a binary source X that emits 0 and 1 with Techniques
probabilities p and (1 − p), respectively. Applications

Its entropy is given by AEP: Asymptotic

Equipartition Property

H(X ) = −p log2 p − (1 − p) log2 (1 − p). Entropy Rate of a

Stochastic Process

Binary entropy function is maximum when p = 0.5. References

Figure: Binary Entropy Function.

Remark: Entropy of a discrete source is maximum when symbols generated from the source are
equiprobable.
 Source Coding

Chirayu Athalye

Example (Entropy and Redundancy of English) Basic Concepts

Self Information and Mutual
Let X be a random variable with possible outcomes {a, . . . , z}. Information
Average Mutual Information
and Entropy
If every letter is equiprobable, then H(X ) = log2 (26) = 4.7 bits. (Maximum Entropy). Information Measures for
Continuous RVs

However, all letters don’t have the same probability. If we consider the normalized letter KL Divergence and JS
Divergence

frequency of different alphabets, then H(X ) ≈ 4.14 bits. Source Coding

Theorem
Certain n-grams (e.g., qu, th, ex, the, ing, etc.) occur more frequently than others. Source Coding
Techniques
Let HL be the entropy per letter of the English language. Applications

H(X n ) AEP: Asymptotic

HL := lim . Equipartition Property
n→∞ n
Entropy Rate of a
Statistical investigations show that HL ≤ 1.5 bits. Stochastic Process

References
Therefore, the redundancy of English is
   
HL 1.5
REng := 1 − ≥ 1− = 0.681.
log2 (26) log2 (26)
 Source Coding

Chirayu Athalye
Conditional Entropy (Average Conditional Self Information)
Basic Concepts
Let X and Y be random variables with possible outcomes {x1 , . . . , xn } and {y1 , . . . , ym }. Self Information and Mutual
Information
Average Mutual Information
The conditional entropy of X given Y is defined as and Entropy
Information Measures for
n X
X m n X
X m Continuous RVs

H(X | Y ) := P(xi , yj ) I (xi | yj ) = − P(xi , yj ) log P(xi | yj ). KL Divergence and JS

Divergence
i=1 j=1 i=1 j=1
Source Coding
Theorem

Source Coding
How Entropy, Average Mutual Information, and Conditional Entropy are related? Techniques

Applications
It follows from the definitions that
AEP: Asymptotic
I (X ; Y ) = H(X ) − H(X | Y ) = H(Y ) − H(Y | X ). Equipartition Property

Entropy Rate of a
Remark: Stochastic Process

References
1 Since I (X ; Y ) ≥ 0, we have H(X ) ≥ H(X | Y ); i.e., observation of Y can only decrease
the entropy.
2 H(X ) = H(X | Y ) iff X and Y are statistically independent.
3 I (X ; X ) = H(X ).
 Source Coding

Joint Entropy Chirayu Athalye

Let X and Y be discrete random variables with the joint PMF pX ,Y . Basic Concepts
Self Information and Mutual
The joint entropy of (X , Y ) is given by Information
Average Mutual Information
n X
X m and Entropy


H(X , Y ) := − pX ,Y (xi , yj ) log pX ,Y (xi , yj ) . Information Measures for
Continuous RVs

i=1 j=1 KL Divergence and JS

Divergence

Source Coding
Theorem

Source Coding
Techniques
Chain Rule for Entropy
Applications

H(X , Y ) = H(X ) + H(Y ) − I (X ; Y ) AEP: Asymptotic

Equipartition Property

= H(X ) + H(Y | X ) Entropy Rate of a

Stochastic Process
= H(Y ) + H(X | Y ). References

In general,
n
X
H(X1 , . . . , Xn ) = H(X1 ) + H(Xk | X1 , . . . , Xk−1 ).
k=2
 Source Coding

Chirayu Athalye

Basic Concepts
Self Information and Mutual
Information
Average Mutual Information
and Entropy
Information Measures for
Continuous RVs
KL Divergence and JS
Divergence

Source Coding
Example Theorem

Source Coding
Techniques

Applications

AEP: Asymptotic
Equipartition Property

Entropy Rate of a
Stochastic Process

References
 Source Coding
Information Measures for Continuous Random Variables (RVs)
Chirayu Athalye

Basic Concepts
Self Information and Mutual
Information
Average Mutual Information Average Mutual Information
and Entropy

Let X and Y be continuous RVs with the joint PDF fX ,Y . Information Measures for
Continuous RVs
KL Divergence and JS
The average mutual information between X and Y is given by Divergence

Z ∞ Z ∞ Source Coding
fX |Y (x | y)
 
Theorem
I (X ; Y ) := fX ,Y (x, y) log dxdy.
−∞ −∞ fX (x) Source Coding
Techniques

Applications
Remark AEP: Asymptotic
Equipartition Property
1 The definition of average mutual information can be extended to continuous RVs, but not
Entropy Rate of a
the physical interpretation. Stochastic Process

References
2 Note that the information content of a continuous RV is infinite.
3 Thus, instead of entropy, we consider differential entropy for a continuous RV.
4 However, there is no physical interpretation attached to the differential entropy.
 Source Coding
Differential Entropy Chirayu Athalye

The differential entropy of a continuous random variable X with PDF fX is given by

Basic Concepts
Z ∞
Self Information and Mutual
h(X ) := − fX (x) log fX (x) dx Information
Average Mutual Information
−∞ and Entropy
Information Measures for
Continuous RVs
KL Divergence and JS
Remark: h(X + c) = h(X ) and h(aX ) = h(X ) + log |a|. Divergence

Source Coding
Theorem
Conditional Differential Entropy Source Coding
Techniques
The conditional differential entropy of a continuous random variable X given Y is defined as Applications
Z ∞ Z ∞
AEP: Asymptotic
h(X | Y ) := − fX ,Y (x, y) log fX |Y (x | y) dxdy. Equipartition Property
−∞ −∞ Entropy Rate of a
Stochastic Process

References
Remark
1 I (X ; Y ) = h(X ) − h(X | Y ) = h(Y ) − h(Y | X ).
n
X
2 Chain Rule for Differential Entropy: h(X1 , . . . , Xn ) = h(X1 ) + h(Xk | X1 , . . . , Xk−1 ).
k=2
3 If X and Y are independent, then h(X + Y ) ≥ h(X ).
 Source Coding
Relative Entropy (Kullback-Leibler (KL) Divergence) Chirayu Athalye

KL divergence between two PMFs p, q : X → [0, 1] is given by

Basic Concepts
 
X p(x) Self Information and Mutual

DKL (p k q) := p(x) log . Information

x∈X
q(x) Average Mutual Information
and Entropy

    Information Measures for

Continuous RVs
0
Convention: 0 log q(x) = 0 and p(x) log p(x)0
= ∞, where p(x) 6= 0. KL Divergence and JS
Divergence

KL divergence between two PDFs f and g is given by Source Coding

Z ∞   Theorem
f (x) Source Coding
DKL (f k g ) := f (x) log dx. Techniques
−∞ g (x)
Applications
It measures how much an approximating probability distribution g differs from a true AEP: Asymptotic
probability distribution f . Equipartition Property

Entropy Rate of a
Stochastic Process
Remark References

1 Gibbs’ Inequality: DKL (p k q) ≥ 0.

2 Gibbs inequality can be proved by applying Jensen’s inequality to − log(·).
3 Note that DKL (p k q) 6= DKL (q k p). Thus, KL divergence fails to induce a metric 1 .



4 Note that I (X , Y ) = DKL pX ,Y (x, y) k pX (x) pY (y) ≥ 0.
1
distance function
 Source Coding

Chirayu Athalye

Basic Concepts
Self Information and Mutual
Information
Average Mutual Information
Jensen-Shannon Divergence and Entropy
Information Measures for

Jensen-Shannon divergence between two probability distributions p and q is given by Continuous RVs
KL Divergence and JS
Divergence
DKL (p k r ) + DKL (q k r ) p+q
JSD(p k q) = , where r= . Source Coding
2 2 Theorem

Source Coding
Techniques
Remark Applications
1 If we use log2 (·), then 0 ≤ JSD(p k q) ≤ 1. AEP: Asymptotic
Equipartition Property
2 Square root of Jensen-Shannon divergence is a metric (Jensen-Shannon distance). Entropy Rate of a
Stochastic Process
3 Similarity between distributions is greater when Jensen-Shannon distance is closer to 0.
References
 Source Coding

Chirayu Athalye
Code and Prefix Code
Basic Concepts
1 A code is a set of codewords (sequence of bits assigned to symbols).
Source Coding
2 A prefix code is a code in which no codeword forms a prefix of any other codeword. Theorem
Code and Prefix Code
Kraft Inequality

Remark Source Coding Theorem

Source Coding
1 In a prefix code, when a sequence of bits corresponding to a possible codeword is detected, Techniques

we can declare that symbol decoded. Applications

AEP: Asymptotic
2 A prefix codes are uniquely decodable. Equipartition Property

Entropy Rate of a
Stochastic Process
Fixed Length Code (FLC) vs Variable Length Code (VLC) References

1 Suppose we want to represent {a, . . . , z} using bits.

2 FLC: We need dlog2 26e = 5 bits to represent English alphabets.
3 However, since these letters are not equiprobable, allocating equal number of bits to all
letters is an inefficient representation.
4 VLC: We should encode more frequently occurring letters using fewer bits, and assign more
bits to letters that occur less frequently.
 Source Coding

Chirayu Athalye

Basic Concepts

Source Coding
Theorem
Code and Prefix Code
Kraft Inequality
Source Coding Theorem

Source Coding
Techniques

Example Applications

AEP: Asymptotic
Equipartition Property

Entropy Rate of a
Stochastic Process

References
 Source Coding

Kraft Inequality Chirayu Athalye

1 An equivalent condition for the existence of a binary code with codewords of length Basic Concepts
`
Source Coding
X
n1 ≤ · · · ≤ n` that satisfy the prefix condition is 2−nk ≤ 1. Theorem
Code and Prefix Code
k=1
Kraft Inequality
2 An equivalent condition for the existence of an M-alphabet code with codewords of length Source Coding Theorem

`
X Source Coding
n1 ≤ · · · ≤ n` that satisfy the prefix condition is M −nk ≤ 1. Techniques

Applications
k=1
AEP: Asymptotic
Equipartition Property

Example (Binary Prefix Code) Entropy Rate of a

Stochastic Process

References
We want to generate a prefix code for symbols {x1 , . . . , x4 }.
Consider a binary tree with the parent node labeled as n0 .
Two branches with labels 0 and 1 emanating from each node.
First codeword c1 = 0 at node n00 . Ignore all heirs of n00 .
Second codeword c2 = 10 at node n010 . Ignore all heirs of n010 .
c3 = 110 and c4 = 111 at nodes n0110 and n0111 , respectively.
Prefix Code: {0, 10, 110, 111}; satisfies Kraft’s inequality.
 Source Coding
Source Coding Theorem Chirayu Athalye

Let X be a DMS that generates symbols {x1 , . . . , x` } with probabilities {p1 , . . . , p` }.

Basic Concepts
If H(X ) < ∞, then it is possible to construct a prefix code whose average length R̄ Source Coding
Theorem
satisfies the inequality: H(X ) ≤ R̄ < H(X ) + 1. Code and Prefix Code
`
X Kraft Inequality
Remark: Let {n1 , . . . , n` } be codeword lengths. FYI, R̄ := pk nk . Note that Source Coding Theorem

k=1 Source Coding

Techniques
H(X ) = R̄ ⇐⇒ pk = 2−nk . Applications

AEP: Asymptotic
Equipartition Property
Remark Entropy Rate of a
Stochastic Process
1 For a prefix code, the minimum average length required to represent source symbols is equal to the
References
entropy of the source.
2 A source with higher entropy requires, on an average, more # of bits to represent source symbols
using a prefix code.
3 Efficient representation of symbols leads to compression of data.
4 Source coding theorem is primarily used for compression of data (speech, text, image, video, etc.)

H(X )
The efficiency of a prefix code is defined as η := ≤ 1.
R̄
 Source Coding

Chirayu Athalye
Example
Suppose a source X generates symbols {x1 , . . . , x4 } with probabilities {0.5, 0.3, 0.1, 0.1}. Basic Concepts

Source Coding
4
X Theorem

Source Entropy: H(X ) = − pk log2 pk = 1.685 bits. Code and Prefix Code
Kraft Inequality
k=1 Source Coding Theorem

If we use the prefix code {0, 10, 110, 111} to represent {x1 , . . . , x4 }, then Source Coding
Techniques
4
X Applications

Average Codeword Length: R̄ = nk pk = 1.7 bits. AEP: Asymptotic

Equipartition Property
k=1
Entropy Rate of a
Notice that H(X ) ≤ R̄ < H(X ) + 1 and η = 0.9912. Stochastic Process

References
Suppose the source symbol probabilities are {0.5, 0.25, 0.125, 0.125}. In this case,
H(X ) = R̄ = 1.7 bits and η = 1.

Remark (Dyadic Distribution)

1 A dyadic distribution is a PMF where probabilities are of the form pk = 2−nk (nk ∈ Z).
2 For a dyadic distribution, H(X ) = R̄.
 Source Coding
Source Coding Techniques
Chirayu Athalye

Huffman Coding Basic Concepts

Source Coding
1 It is a variable length prefix code that is optimal among all prefix codes. Theorem
2
2 It is a greedy algorithm . Source Coding
Techniques
Applications: Huffman Coding
Shannon-Fano-Elias (SFE)
Used in file compression (zip and Deflate), image compression (JPEG), audio compression (MP3 Coding

and AAC), video compression (MPEG and AVC), etc. Arithmetic Coding
Lempel-Ziv Algorithm
Suitable for micro-controllers and real-time systems due to low computational complexity and Run Length Encoding
(RLE)
simple decoding.
Applications

AEP: Asymptotic
How to Construct the Huffman Tree Equipartition Property

Entropy Rate of a
1 Arrange source symbols in a decreasing order of probabilities. Stochastic Process

References
2 In an iterative manner, combine the two symbols with the lowest probabilities into a new symbol
whose probability is their sum.
3 Continue until only one symbol is left. (At each step, we reduce the total # of symbols by 1.)
4 Whenever we combine two symbols, we label the corresponding two branches (edges) with 0 and 1.
5 The codeword for a symbol is obtained using labels on the path from the final (parent) node to
that symbol.
2
An algorithmic strategy that builds a solution step-by-step making the optimal choice at each step.
 Source Coding

Example Chirayu Athalye

Basic Concepts

Consider a DMS with 7 symbols. Source Coding

Theorem
Arrange symbols in ↓-order of Source Coding
probabilities to construct the Techniques
Huffman tree. Huffman Coding
Shannon-Fano-Elias (SFE)
Coding
To find the codeword, trace the
Arithmetic Coding
path from the parent node. Lempel-Ziv Algorithm
Run Length Encoding
(RLE)

Applications
7
X Symbol Probability Self Information Codeword AEP: Asymptotic
H(X ) = − pk log2 pk Equipartition Property
k=1
x1 p1 = 0.46 1.1203 1
Entropy Rate of a
= 1.9781 bits. x2 p2 = 0.30 1.7370 00 Stochastic Process
x3 p3 = 0.12 3.0589 010 References
7
X x4 p4 = 0.06 4.0589 0110
R̄ = nk pk = 1.99 bits
k=1
x5 p5 = 0.03 5.0589 01110
H(X ) x6 p6 = 0.02 5.6439 011110
η= R̄
= 0.9940.
x7 p7 = 0.01 6.6439 011111

Remark: For a given set of probabilities, Huffman coding is not unique.

 Source Coding

Example Chirayu Athalye

Basic Concepts
Symbol Probability Self Information Codeword
Source Coding
x1 p1 = 0.4 1.3219 1 Theorem

x2 p2 = 0.2 2.3219 000 Source Coding

Techniques
x3 p3 = 0.18 2.4739 001 Huffman Coding

x4 p4 = 0.11 3.1814 010 Shannon-Fano-Elias (SFE)

Coding
x5 p5 = 0.11 3.1814 011 Arithmetic Coding
Lempel-Ziv Algorithm

Table: Huffman Code. Run Length Encoding

(RLE)
5
X Applications
H(X ) = − pk log2 pk = 2.1384 bits. AEP: Asymptotic
k=1 Equipartition Property

Entropy Rate of a
5
X Stochastic Process
H(X )
R̄ = nk pk = 2.2 bits and η= R̄
= 0.972. References
k=1

Remark
In case of a dyadic distribution, we have the following equality for each symbol:
Self Information = Huffman Codeword Length.
 Source Coding
Why Source Coding? Chirayu Athalye

By applying source coding techniques, we can store or transmit the information content of a Basic Concepts
data string using fewer bits than the original representation. Source Coding
Theorem
1 Entropy Encoder: A coding scheme designed for a memoryless source with known
Source Coding
probability distribution. E.g.: Huffman, SFE, Arithmetic Coding, etc. Techniques
Huffman Coding
2 Universal Encoder: A coding scheme for a source with memory whose probability Shannon-Fano-Elias (SFE)
distribution is not known a priori. E.g.: LZ Algorithm, Run Length Coding, etc. Coding
Arithmetic Coding
Lempel-Ziv Algorithm
Run Length Encoding
Coding in Blocks (Efficient Technique) (RLE)

Applications
Instead of encoding symbol-by-symbol, we can encode blocks of B symbols.
AEP: Asymptotic
Equipartition Property
In this case, the bounds of the source coding theorem for a DMS are
Entropy Rate of a
B H(X ) ≤ R̄B < B H(X ) + 1, Stochastic Process

References
where R̄B : average number of bits per block of B symbols.
R̄B
Average number of bits per symbol: R̄ := B
. Notice that
1
H(X ) ≤ R̄ < H(X ) + ,
B
By selecting a large enough block-size B, we can make R̄ arbitrarily close to H(X ).
 Source Coding
Example Chirayu Athalye

H(X ) = 1.5589 bits, Symbol Probability Self Information Codeword Basic Concepts

x1 0.4 1.3219 1 Source Coding

R̄ = 1.60 bits, Theorem
x2 0.35 1.5146 00
Source Coding
η = 0.9743. x3 0.25 2 01 Techniques
Huffman Coding
Shannon-Fano-Elias (SFE)
Table: Huffman Code. Coding
Arithmetic Coding
Let us group 2 symbols and apply the Huffman encoding algorithm. Lempel-Ziv Algorithm
Run Length Encoding
Symbol Pairs Probability Self Information Codeword (RLE)

x1 x1 0.16 2.6439 10 Applications

x1 x2 0.14 2.8365 001 AEP: Asymptotic

Equipartition Property
x2 x1 0.14 2.8365 010
Entropy Rate of a
x2 x2 0.1225 3.0291 011 Stochastic Process

x1 x3 0.1 3.3219 111 References

x3 x1 0.1 3.3219 0000

x2 x3 0.0875 3.5146 0001
x3 x2 0.0875 3.5146 1100
x3 x3 0.0625 4 1101
R̄2
Note that R̄ = 2
= 1.588 bits and η = 0.9812 (improved efficiency).
 Source Coding

Shannon-Fano-Elias Coding Chirayu Athalye

1 It uses Cumulative Distribution Function (CDF) to allocate codewords. Basic Concepts

2 This coding scheme can only ensure R̄ < H(X ) + 2. (suboptimal performance) Source Coding
Theorem

Source Coding
Basic Idea for Encoding Techniques
Huffman Coding

Let X be a source that generates symbols {x1 , . . . , x` } with probabilities {p1 , . . . , p` }. Shannon-Fano-Elias (SFE)
Coding
Arithmetic Coding
1 Compute the CDF FX . Let Lempel-Ziv Algorithm
F (x+ ) + F (x− ) Run Length Encoding
F̄ (x) := . (RLE)
2 Applications


2 The codeword for xk is the binary expansion of F̄ (xk ) truncated to d− log2 pk e + 1 bits. AEP: Asymptotic
Equipartition Property

Entropy Rate of a
Example Stochastic Process

References

Symbol Probability F (x+ ) F̄ (x) d− log2 pk e + 1 F̄ (x) (Binary) Codeword

x1 0.25 0.25 0.125 3 0.001 001
x2 0.5 0.75 0.5 2 0.10 10
x3 0.125 0.875 0.8125 4 0.1101 1101
x4 0.125 1 0.9375 4 0.1111 1111
 Source Coding
Arithmetic Coding Chirayu Athalye

1 Lossless data compression technique that represents an entire message as a fraction in the Basic Concepts
interval [0, 1). Source Coding
Theorem
2 Unlike Huffman coding, it encodes the entire (finite-length) sequence at once.
Source Coding
3 Thus, it avoids inefficiencies of Huffman coding that assigns codewords symbol-by-symbol. Techniques
Huffman Coding
4 Arithmetic coding can achieve R̄ (average codeword length) closer to the entropy limit. Shannon-Fano-Elias (SFE)
Coding
Arithmetic Coding
Lempel-Ziv Algorithm
What is Arithmetic Coding? Run Length Encoding
(RLE)

Encoding: Applications

1 Start with an interval [0, 1). AEP: Asymptotic

Equipartition Property
2 In an iterative manner, subdivide the interval according to symbol probabilities. Entropy Rate of a
Stochastic Process
3 Each symbol in the given sequence narrows the interval.
References
4 Any number within the final interval uniquely represents the given sequence.
Decoding:
1 Start with the same probability model.
2 Use the encoded number to determine which sub-interval it falls into.
3 Output that symbol. Narrow the interval and repeat.
 Source Coding
Example Chirayu Athalye

Consider symbols {A, B, C } with probabilities {0.5, 0.25, 0.25}. Divide [0, 1) as
Basic Concepts

A : [0, 0.5) B : [0.5, 0.75) C : [0.75, 1). Source Coding

Theorem
Let the symbol stream be BACA. Source Coding
Techniques
Huffman Coding
Shannon-Fano-Elias (SFE)
Coding
Arithmetic Coding
Lempel-Ziv Algorithm
Run Length Encoding
(RLE)

Applications

AEP: Asymptotic
Equipartition Property

Entropy Rate of a
Stochastic Process

References

Binary representation of any x ∈ [0.59375, 0.609375) represents the stream BACA.

Remark: A symbol with higher probability causes smaller reduction in the interval, and thus
contribute fewer bits
 Source Coding

Chirayu Athalye

Basic Concepts
Lempel-Ziv (LZ) Algorithm (Dictionary-Based Method)
Source Coding
Theorem
1 Lossless data compression algorithm that exploits patterns and repetitions in data-stream
Source Coding
without prior knowledge of symbol probabilities. Techniques
Huffman Coding
2 It builds an explicit dictionary of substrings (phrases) during encoding. Shannon-Fano-Elias (SFE)
Coding
3 Each new phrase is encoded as: (index of known prefix-string, next symbol). Arithmetic Coding
Lempel-Ziv Algorithm
4 It uses a fixed length codewords for phrases. Run Length Encoding
(RLE)
5 It is a fast, practical, and adaptive method that learns patterns while encoding. Applications

AEP: Asymptotic
Equipartition Property
Advantages of Lempel-Ziv Algorithm over Huffman and Arithmetic Coding
Entropy Rate of a
Stochastic Process
1 In many real-life scenarios, we do not know symbol probabilities that are essential for
References
Huffman and arithmetic coding.
2 For a source with memory, where the occurrence of one symbol alter the probabilities of
subsequent symbols, Huffman and arithmetic coding are far from being optimal.
 Source Coding
Example
Chirayu Athalye

Location Content Codeword Basic Concepts

000 ∅ - Source Coding

Consider a bit stream: 101011011010101011. Theorem
001 1 0001
Parsed String: 1, 0, 10, 11, 01, 101, 010, 1011. 010 0 0000
Source Coding
Techniques
The first occurrence of 1 and 0 have the null 011 10 0010 Huffman Coding
Shannon-Fano-Elias (SFE)
prefix-string. 100 11 0011 Coding
Arithmetic Coding
Lempel-Ziv Code: 101 01 0101 Lempel-Ziv Algorithm

110 101 0111 Run Length Encoding

(000, 1), (000, 0), (001, 0), (001, 1), (010, 1), (RLE)
111 010 1010 Applications
(011, 1), (101, 0), (110, 1). - 1011 1101 AEP: Asymptotic
Equipartition Property
Table: Dictionary for Lempel-Ziv Algorithm. Entropy Rate of a
Stochastic Process

References
1 For a large size string, unlike the example above, we get a rich Lempel-Ziv (LZ) dictionary. As a
result, the Lempel-Ziv algorithm typically gives near-optimal compression.
2 Size of an LZ dictionary grows exponentially with the number of bits assigned for location.

The variant of Lempel-Ziv Algorithm we studied is also known as LZ78.

Lempel-Ziv-Welch (LZW) code is an optimized version of LZ78.
 Source Coding

Run Length Coding Chirayu Athalye

1 A lossless data compression technique that compresses data by replacing consecutive Basic Concepts

repeated symbols (called a run) with a pair (run length, symbol). Source Coding
Theorem
2 It can compress any type of data; the compression ratio depends on the content of data. Source Coding
Techniques
3 Inefficient compared to other compression techniques; thus, often used in conjunction with Huffman Coding

other methods. Shannon-Fano-Elias (SFE)

Coding

4 Easy to implement and quick to execute. Effective for data with long runs. Arithmetic Coding
Lempel-Ziv Algorithm
5 Supported by file formats such as TIFF, JPG, BMP, PCX, etc. Run Length Encoding
(RLE)

Applications

Example AEP: Asymptotic

Equipartition Property
Consider a bit stream: 1111111111110000000000000001111111. Entropy Rate of a
Stochastic Process
It can be represented as: (12, 1), (15, 0), (7, 1). Notice that the maximum number of
References
repetitions is 15, which can be represented with 4 bits.
Run Length Code: (1100, 1), (1111, 1), (0111, 1). Compression Ratio: 15 : 34 = 1 : 2.2667.

Fax machines use a combination of a run length code and Huffman code. Read about the
coding technique used in fax machines.
 Source Coding
(Non-Uniform) Optimum Quantizer Design Chirayu Athalye

Consider a (continuous) random variable X with PDF fX (·). Basic Concepts

fX need not be a uniform distribution. Source Coding
Theorem
We want to design an L-level {x̃1 , . . . , x̃L } optimum quantizer X̃ that minimizes3 Source Coding
L Z xk Techniques
X
Mean Square Quantization Error: D := (x̃k − x)2 fX (x) dx. Applications
Optimum Quantizer Design
k=1 xk−1
Image Compression

AEP: Asymptotic
Necessary conditions for optimality are obtained by differentiating D w.r.t. xk and x̃k : Equipartition Property

Entropy Rate of a
∂D h i
= fX (xk ) (x̃k − xk )2 − (x̃k+1 − xk )2 = 0, k = 1, . . . , L − 1, Stochastic Process
∂xk References
Z xk
∂D
= (x̃k − x) fX (x) dx = 0, k = 1, . . . , L.
∂ x̃k xk−1

Source coding techniques can be used to encode an optimum quantizer X̃ .

∂D
Remark: ∂x k
is obtained using (Leibniz) rules for Differentiation Under Integral Sign. If we
assume fX (xk ) 6= 0, then
∂D x̃k + x̃k+1
= 0 =⇒ xk = .
∂xk 2
3

2

In general, instead of the mean square error X̃ − X , we could have some other error function E X̃ − X .
 Source Coding
Example (Non-Uniform Optimum Quantizer) Chirayu Athalye

Let X be a random variable with the standard normal distribution N (µ = 0, σ 2 = 1). Basic Concepts

We want to design an 8-level quantizer that minimizes the mean square quantization error: Source Coding
Theorem
8 Z xk
X 1 x2 Source Coding
D= √ |x̃k − x|2 e − 2 dx. Techniques

k=1
2π xk−1 Applications

Optimum Quantizer Design
k xk x̃k P(x̃k ) = P xk−1 < X < xk Huffman Code Image Compression

0 −∞ – – – AEP: Asymptotic
Equipartition Property
1 -1.748 -2.152 0.04 0010
Entropy Rate of a
2 -1.05 -1.344 0.107 011 Stochastic Process
In this case,
3 -0.5 -0.756 0.162 010 References

4 0 -0.245 0.191 10 Dmin = 0.0345,

5 0.5 0.245 0.191 11 H(X̃ ) = 2.82 bits.
6 1.05 0.756 0.162 001
7 1.748 1.344 0.107 0000
8 ∞ 2.152 0.04 0011

Table: Optimum Quantization and Huffman Coding

For Huffman coding, R̄ = 2.88 bits, which is strictly less than 3 bits required to represent
8-level quantizer.
 Source Coding

Chirayu Athalye

Image Compression Basic Concepts

Source Coding
Depending on the resolution, an image may require anywhere from 102 to 108 bytes. Theorem

Compared to an arbitrary data, imagery data has higher redundancy. Source Coding
Techniques

Close relationship between neighboring pixels in an image can be exploited to improve the Applications

compression ratios. Optimum Quantizer Design

Image Compression

Lossy Compression: Images can be sampled and quantized sufficiently finely so that they AEP: Asymptotic
Equipartition Property
are satisfactory to discerning eyes; less important data to human eyes can be compromised.
Entropy Rate of a
Lossless Compression: Source coding techniques can be used for compressing imagery data Stochastic Process

for storage and transmission. References

JPEG (Joint Photographic Expert Group) Image Compression Standard

1 A description of 29 distinct coding systems (having different trade offs w.r.t. quality vs
compression and computation time) for compression of images.
2 Typical lossless compression for natural images is 2 : 1.
 Source Coding
Discrete Cosine Transform (DCT) [Computational Complexity: O(NM)]
Chirayu Athalye

Consider an image y (·, ·) with (N × M) pixels. Its DCT is given by

Basic Concepts
N−1
X M−1    
X πk π` Source Coding
Y (k, `) := 4y (n, m) cos (2n + 1) cos (2m + 1) . Theorem

n=1 m=1
2N 2M Source Coding
Techniques

In the JPEG image reduction, DCT is applied to (8 × 8) pixel blocks. Applications

Optimum Quantizer Design
DCT coefficients of an image sub-block represent its spatial frequency. Image Compression

In natural images, maximum information (energy) lies in low frequency components (upper-left AEP: Asymptotic
Equipartition Property
corner of the DCT matrix) as opposed to high frequency (lower-right corner of the DCT matrix).
Entropy Rate of a
Stochastic Process

References

Figure: DCT Coefficients for a (4 × 4) Image Block.

 Source Coding
JPEG Lossy Compression Techniques Chirayu Athalye

1 Small weights (below some threshold) are set to zero. Reduces image complexity at the Basic Concepts
2 Remaining weights are quantized. cost of fidelity. Source Coding
Theorem

Source Coding
Zig-Zag Code: 4 333 222 1 222 00000. Techniques

Applications

Zig-Zag Code: Optimum Quantizer Design

Image Compression
It gradually moves from low to high AEP: Asymptotic
frequencies, avoiding abrupt change Equipartition Property
in the values. Entropy Rate of a
Stochastic Process
It leads to a run of (high frequency)
References
Figure: Quantization and Zig-Zag Coding. zeros (ideal for RLE).

JPEG Lossless Compression Techniques

RLE followed by the arithmetic or Huffman coding is applied to the zig-zag code.

Performance of JPEG Compression

1 Photographic quality images can be preserved with compression ratios 20-25 : 1.
2 Compression ratios in the range 200-230 : 1 give usable quality images (for non-critical purposes).
 Source Coding
AEP
Chirayu Athalye

Basic Concepts
Weak Law of Large Numbers Source Coding
Theorem
Let X1 , X2 , . . . are independent and identically distributed (i.i.d.) random variables with mean Source Coding
µ. Let Techniques
X1 + · · · + Xn Applications
Mn = .
n AEP: Asymptotic
For every ε > 0, we have
Equipartition Property
lim P |Mn − µ| ≥ ε = 0. Entropy Rate of a
n→∞ Stochastic Process

P References
Remark: We say Mn converges to µ in probability, denoted as Mn −
→ µ.

Asymptotic Equipartition Property (AEP)

If X1 , X2 , . . . are i.i.d. random variables with PMF p : X → [0, 1], then
n
1 1X P
X
− log p(X1 , . . . , Xn ) = − log p(Xk ) −→ H(X1 ) = − p(x) log p(x).
n n x∈X
k=1

Remark: AEP is a consequence of the weak law of large numbers.

 Source Coding
Entropy Rate of a Discrete Stochastic Process Chirayu Athalye

The entropy rate of a discrete stochastic process X = {X1 , X2 , . . .} is given by Basic Concepts

H(X1 , . . . , Xn ) Source Coding

H(X ) := lim . Theorem
n→∞ n
Source Coding
Remark: Techniques

Applications
1 If X1 , X2 , . . . are i.i.d. random variables, then by the chain rule for entropy,
AEP: Asymptotic
H(X1 ) + · · · + H(Xn ) Equipartition Property
H(X ) = lim = H(X1 ). Entropy Rate of a
n→∞ n Stochastic Process
2 If X1 , X2 , . . . are independent but not identically distributed random variables, then References

n
1X
H(X ) = lim H(Xk ).
n→∞ n
k=1

Stationarity
1 A discrete stochastic process {Xk : k ∈ N} is said to be stationary if for all n, m ∈ N, we
have the following PMF equality: pX1 ···Xn = pXm+1 ···Xm+n .
2 A stationary process behaves the same way at different time instances.
3 Stationarity =⇒ {Xk : k ∈ N} are identically distributed.
 Source Coding
Markov Chain Chirayu Athalye

A discrete stochastic process {Xk : k ∈ N0 } is said to be a Markov chain if for all n ∈ N,

Basic Concepts

P(Xn | Xn−1 , . . . , X0 ) = P(Xn | Xn−1 ). Source Coding

Theorem
A Markov chain consists of Source Coding
1 State Space: A finite set of states S = {s1 , . . . , sm }. Techniques

2 Transition Probability Matrix: Applications

AEP: Asymptotic
p11 · · · p1m
 
Equipartition Property

P =  .. .. ..  , where pij = P(Xn = sj | Xn−1 = si ).

 Entropy Rate of a
. . .  Stochastic Process
pm1 · · · pmm References

Note that P is non-negative matrix

with row-sums equal to 1.

Initial Distribution: ν (0) = P(X0 = s1 ) P(X0 = sm ) ∈ R1×m .

 
3 ···
Note that ν (n+1) = ν (n) P, where ν (n) denotes the state-probability distribution at time n.
 Source Coding

Chirayu Athalye
Remark (Stationary Markov Chain)
Basic Concepts
νm R1×m of a Markov chain is said to be
 
1 State-probability distribution ν = ν1 ···
Source Coding
stationary if νP = ν. Theorem

2 Note that if ν (0) = ν, then ν (n) = ν for all n ∈ N. Source Coding

Techniques
3 Markov chain is stationary iff its initial distribution is stationary. Applications

AEP: Asymptotic
Equipartition Property
Entropy Rate of Stationary Markov Chain Entropy Rate of a
Stochastic Process
By using the chain rule for the entropy, the Markov property and stationarity, we get
References

n
!
H(X1 , . . . , Xn ) 1 X
H(X ) = lim = lim H(X1 ) + H(Xk | Xk−1 , . . . , X1 ) (Chain Rule)
n→∞ n n→∞ n
k=2
n
!
1 X
= lim H(X1 ) + H(Xk | Xk−1 ) (Markov Property)
n→∞ n
k=2
1 
= lim H(X1 ) + (n − 1) H(X2 | X1 ) (Stationarity)
n→∞ n

= H(X2 | X1 ).
 Source Coding

Example (Markov Chain) Chirayu Athalye

Basic Concepts

Source Coding
Consider a two-state stationary Markov chain with Theorem
 
1 − p1 p1 Source Coding
P= . Techniques
p2 1 − p2 Applications

AEP: Asymptotic
Solving νP = ν and ν1 + ν2 = 1, we get the stationary distribution as Equipartition Property

Entropy Rate of a
p2 p1 Stochastic Process
ν1 = and ν2 = .
p1 + p2 p1 + p2 References

The entropy rate of this Markov chain is given by

2 X
X 2
H(X2 | X1 ) = − P(si , sj ) log P(si | sj )
i=1 j=1
2
X 2
X
=− P(sj ) P(si | sj ) log P(si | sj )
j=1 i=1
   
= −ν1 (1 − p1 ) log(1 − p1 ) + p1 log p1 − ν2 (1 − p2 ) log(1 − p2 ) + p2 log p2
= ν1 H(p1 ) + ν2 H(p2 ).
 Source Coding

Chirayu Athalye

Basic Concepts

Source Coding
Theorem
References Source Coding
Techniques

R. Bose, Information Theory, Coding and Cryptography (3rd edition), Chennai, TN, India: McGraw Hill Applications
Education, 2016. AEP: Asymptotic
Equipartition Property
T.M. Cover and J.A. Thomas, Elements of Information Theory (2nd edition), Hoboken, NJ, USA:
Entropy Rate of a
Wiley-Interscience, 2006. Stochastic Process

References

Readings
1 [Information Theory, Coding and Cryptography (Bose), Chapter 1].
2 [Elements of Information Theory (Cover and Thomas), Chapters 2-5 & 9].