Source Coding

Chirayu Athalye

Basic Concepts

Source Coding
Theorem

Source Coding
Techniques
Information and its Efficient Representation Rate Distortion
Function

References

Chirayu D. Athalye

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

Rate Distortion
Function
Example (Desired Additive Property of log(·) Measure)
References
Consider a binary source that generates equiprobable outputs {0, 1}.
The information content of each output from the source is
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. Rate Distortion
Function
Source C consists of two independent binary sources A and B that generates equiprobable References
outputs {0, 1}.
Thus, outputs {00, 01, 10, 11} generated by source C are equiprobable. Notice that


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 . Rate Distortion

Function

References

Remark
1 The mutual information I (xi ; yj ) can be positive, negative, or zero.
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, Rate Distortion
Function

P(Y = 0) = 0.5(1 − p) + 0.5p = 0.5. References

P(Y = 1) = 0.5p + 0.5(1 − p) = 0.5.

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

Rate Distortion
Function

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, Rate Distortion
Function

P(Y = 0) = 0.5(1 − p0 ) + 0.5p1 = 0.5(1 − p0 + p1 ). References

P(Y = 1) = 0.5p0 + 0.5(1 − p1 ) = 0.5(1 − p1 + p0 ).

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?
Rate Distortion
P(yj ) P(xi ) Function
By Bayes’ rule, = . Taking − log(·) of both sides, we get
P(yj | xi ) P(xi | yj ) References

I (xi ; yj ) = I (xi ) − I (xi | yj ).

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.
Rate Distortion
2 Since I (xi ; yj ) = I (yj ; xi ), we have I (X ; Y ) = I (Y , X ). Function

References

Entropy (Average Self Information)

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. Rate Distortion
Function
Its entropy is given by
References

H(X ) = −p log2 p − (1 − p) log2 (1 − p).

Binary entropy function is maximum when p = 0.5.
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. Rate Distortion
Function
H(X n )
HL := lim . References
n→∞ n
Statistical investigations show that HL ≤ 1.5 bits.
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

Rate Distortion
It follows from the definitions that Function

I (X ; Y ) = H(X ) − H(X | Y ) = H(Y ) − H(Y | X ). References

Remark:
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
Rate Distortion
Function
H(X , Y ) = H(X ) + H(Y ) − I (X ; Y )
References
= H(X ) + H(Y | X )
= H(Y ) + H(X | Y ).

In general,
n
X
H(X1 , . . . , Xn ) = H(Xk | X1 , . . . , Xk−1 ).
k=1
 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

Rate Distortion
Function

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

Rate Distortion
Remark Function

References
1 The definition of average mutual information can be extended to continuous RVs, but not
the physical interpretation.
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 Rate Distortion
Z ∞ Z ∞ Function

h(X | Y ) := − fX ,Y (x, y) log fX |Y (x | y) dxdy. 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(Xk | X1 , . . . , xk−1 ).
k=1
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)
Rate Distortion
It measures how much an approximating probability distribution g differs from a true Function

probability distribution f . References

Remark
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 Rate Distortion
Function
1 If we use log2 (·), then 0 ≤ JSD(p k q) ≤ 1.
References
2 Square root of Jensen-Shannon divergence is a metric (Jensen-Shannon distance).
3 Similarity between distributions is greater when Jensen-Shannon distance is closer to 0.
 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. Rate Distortion

Function
2 A prefix codes are uniquely decodable. References

Fixed Length Code (FLC) vs Variable Length Code (VLC)

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 Rate Distortion

Function

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

Rate Distortion
k=1 Function

References

Example (Binary Prefix Code)

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 . Rate Distortion
Function

References
Remark
1 For a prefix code, the minimum average length required to represent source symbols is equal to the
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 Rate Distortion
Function
Average Codeword Length: R̄ = nk pk = 1.7 bits.
References
k=1

Notice that H(X ) ≤ R̄ < H(X ) + 1 and η = 0.9912.

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 Coding
Used in file compression (zip and Deflate), image compression (JPEG), audio compression (MP3 Arithmetic Coding
and AAC), video compression (MPEG and AVC), etc. Lempel-Ziv Algorithm
Run Length Coding
Suitable for micro-controllers and real-time systems due to low computational complexity and
Rate Distortion
simple decoding. Function

References

How to Construct the Huffman Tree

1 Arrange source symbols in a decreasing order of probabilities.
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 Coding
To find the codeword, trace the Arithmetic Coding

path from the parent node. Lempel-Ziv Algorithm

Run Length Coding

Rate Distortion
Function
7
X Symbol Probability Self Information Codeword References
H(X ) = − pk log2 pk
k=1
x1 p1 = 0.46 1.1203 1
= 1.9781 bits. x2 p2 = 0.30 1.7370 00
x3 p3 = 0.12 3.0589 010
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 Coding

Arithmetic Coding
x5 p5 = 0.11 3.1814 011 Lempel-Ziv Algorithm
Run Length Coding
Table: Huffman Code. Rate Distortion
5 Function
X
H(X ) = − pk log2 pk = 2.1384 bits. References

k=1
5
X H(X )
R̄ = nk pk = 2.2 bits and η= R̄
= 0.972.
k=1

Remark
In case of a dyadic distribution, we have the following equality for each symbol:
Self Information = Huffman Codeword Length.
 Source Coding
Coding in Blocks (Efficient Technique) Chirayu Athalye

Instead of encoding symbol-by-symbol, we can encode blocks of B symbols. Basic Concepts

In this case, the bounds of the source coding theorem for a DMS are Source Coding
Theorem
B H(X ) ≤ R̄B < B H(X ) + 1, Source Coding
Techniques
where R̄B : average number of bits per block of B symbols. Huffman Coding
Shannon-Fano-Elias Coding
R̄B
Average number of bits per symbol: R̄ := B
. Notice that Arithmetic Coding
Lempel-Ziv Algorithm

1 Run Length Coding

H(X ) ≤ R̄ < H(X ) + , Rate Distortion
B Function

By selecting a large enough block-size B, we can make R̄ arbitrarily close to H(X ). References

Example

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

x1 0.4 1.3219 1
R̄ = 1.60 bits,
x2 0.35 1.5146 00
η = 0.9743. x3 0.25 2 01

Table: Huffman Code.

 Source Coding

Chirayu Athalye

Basic Concepts
Example (Contd..) Source Coding
Theorem
Let us group 2 symbols and apply the Huffman encoding algorithm.
Source Coding
Techniques
Symbol Pairs Probability Self Information Codeword Huffman Coding

x1 x1 0.16 2.6439 10 Shannon-Fano-Elias Coding

Arithmetic Coding
x1 x2 0.14 2.8365 001 Lempel-Ziv Algorithm

x2 x1 0.14 2.8365 010 Run Length Coding

Rate Distortion
x2 x2 0.1225 3.0291 011 Function
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 Coding
Arithmetic Coding

1 Compute the CDF FX . Let Lempel-Ziv Algorithm

Run Length Coding
F (x+ ) + F (x− )
F̄ (x) := . Rate Distortion
2 Function


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

Example

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 Coding
Arithmetic Coding
Lempel-Ziv Algorithm

What is Arithmetic Coding? Run Length Coding

Rate Distortion
Encoding: Function

References
1 Start with an interval [0, 1).
2 In an iterative manner, subdivide the interval according to symbol probabilities.
3 Each symbol in the given sequence narrows the interval.
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 Coding
Arithmetic Coding
Lempel-Ziv Algorithm
Run Length Coding

Rate Distortion
Function

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 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 Coding
Arithmetic Coding
3 Each new phrase is encoded as: (index of known prefix-string, next symbol). Lempel-Ziv Algorithm

4 It uses a fixed length codewords for phrases. Run Length Coding

Rate Distortion
5 It is a fast, practical, and adaptive method that learns patterns while encoding. Function

References

Advantages of Lempel-Ziv Algorithm over Huffman and Arithmetic Coding

1 In many real-life scenarios, we do not know symbol probabilities that are essential for
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 Coding
prefix-string. 100 11 0011 Arithmetic Coding

Lempel-Ziv Code: 101 01 0101 Lempel-Ziv Algorithm

Run Length Coding
110 101 0111
(000, 1), (000, 0), (001, 0), (001, 1), (010, 1), Rate Distortion
111 010 1010 Function
(011, 1), (101, 0), (110, 1). - 1011 1101 References

Table: Dictionary for Lempel-Ziv Algorithm.

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 close to 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 Coding

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

References
Example
Consider a bit stream: 1111111111110000000000000001111111.
It can be represented as: (12, 1), (15, 0), (7, 1). Notice that the maximum number of
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

Chirayu Athalye

Basic Concepts

Source Coding
Theorem

References Source Coding

Techniques

Rate Distortion
R. Bose, Information Theory, Coding and Cryptography (3rd edition), Chennai, TN, India: McGraw Hill Function
Education, 2016. References

T.M. Cover and J.A. Thomas, Elements of Information Theory (2nd edition), Hoboken, NJ, USA:
Wiley-Interscience, 2006.

Readings
1 [Information Theory, Coding and Cryptography (Bose), Chapter 1].