Source Coding
EC-413 1 / 37
Outline
Discrete memoryless source (DMS)
Mathematical model for DMS
Source coding: Data compression
Types of data compression
Classes of source codes
Kraft inequality
Optimal codes
EC-413 2 / 37
Mathematical Model for Information Source
Any information source produces an output that is random; i.e., the
source output is characterized in statistical terms.
Simplest type of a discrete source is
X
Binary 100101110 . . .
Source
Finite alphabet X = {0, 1}
EC-413 3 / 37
Mathematical Model for DMS
Definition: A source whose output satisfies the condition of statistical
independence among output letters is said to be memoryless. If the
source is discrete, it is called a discrete memoryless source (DMS).
The mathematical model for an DMS is a sequence of independent
identically distributed (iid) random variables {Xi }.
DMS {Xi }
EC-413 4 / 37
Source Coding: Data Compression
The purpose is to represent information compactly, in as few bits as
possible.
Applications:
Compressing text or program files (e.g. zip)
Compressing images (e.g. JPEG)
Compressing video (e.g. MPEG)
Types of data compression
Lossless data compression
decompressed data is exactly the same as the original.
Text and programs need to be compressed losslessly
Lossy data compression
decompressed data is not exactly the same as the original.
images and video need to be compressed lossy.
EC-413 5 / 37
Source Coding
X Source C
DMS
Encoder
EC-413 6 / 37
Source Code
Definition: A source code C for a random variable X is mapping from
the set X to the set D∗ ,
C : X 7→ D∗
x → C (x)
where X =the range of X (or the set of all possible values taken by
the random variable X ),
D∗ = the set of finite length strings of symbols from a D-ary
alphabet,
D-ary alphabet is D = {0, 1, · · ·, D − 1}
For D = 2, binary alphabet is D = {0, 1}
C (x) = the codeword corresponding to x,
l(x) = the length of C (x).
EC-413 7 / 37
Contd..
C
x1 00 C (x1 ) = 00
x2 01 C (x2 ) = 01
x3 10 C (x3 ) = 10
x4 11 C (x4 ) = 11
X D∗
D = 2 =⇒ D = {0, 1}
A set of codewords (codeword set) C is defined as
C = {C (x); xϵX }
EC-413 8 / 37
Contd..
For example , C (red) = 00, C (blue) = 11 is a source code for
X = {red, blue} with alphabet D = {0, 1}.
Definition: The expected length LC of a source code C for a random
variable X with PMF p(x) is given by
X
LC = P(x)l(x);
xϵX
where l(x) is the length of the codeword C (x)
EC-413 9 / 37
Contd...
Example: Let X be a random variable with following distribution and
codeword assignment:
1 1 1
P(X = 1) = , P(X = 2) = , P(X = 3) = ,
3 3 3
C (1) = 0, C (2) = 10, C (3) = 11
The entropy is
X
H(X ) = − P(x) log2 (P(x)) = 1.58 bit
x
The expected length is
X
LC = P(x)l(x) = 1.66 bit
xϵX
Observation
LC > H(X )
EC-413 10 / 37
Classes of source codes
Nonsingular code
Uniquely decodable code
Instantaneous code
EC-413 11 / 37
Nonsingular Code
Definition: A code C is said to be nonsingular if every element of the
set X maps into a different string in D∗ , (one to one mapping)
x ̸= x ′ ⇒ C (x) ̸= C (x ′ )
C
x1 00
x2 01
x3 10
x4 11
X D∗
one to one mapping
EC-413 12 / 37
Contd...
Drawback: When transmitting a sequence of source symbols, we
must ensure that codewords can be uniquely identified. One way to
achieve this is by inserting a special separator (e.g., a comma)
between codewords. However, this approach is inefficient as it
increases redundancy.
Solution: A more efficient approach is to design self-punctuating or
instantaneous codes, where no codeword is a prefix of another. This
ensures that a sequence of codewords can be decoded without
needing extra separators.
EC-413 13 / 37
Extension of a Code
Definition: The extension C ∗ of a code C is the mapping from the set
of finite length strings of symbols of X to the set of finite length
strings of the symbols of D∗ , defined by
C ∗ : X ∗ 7→ D∗
C ∗ (x1 x2 · · · xn ) = C (x1 )C (x2 ) · · · C (xn );
C ∗ (x n ) = C (x1 )C (x2 ) · · · C (xn );
where C (x1 )C (x2 ) · · · C (xn ) indicates concatenation of the
corresponding codewords
For example, C (x1 ) = 00, C (x2 ) = 11, then C ∗ (x1 x2 ) = 0011
EC-413 14 / 37
Contd...
C
x1 00
x2 01
x3 10
x4 11
X D∗
C∗
x1 x1 0000
x1 x2 0001
x3 x2 1001
x4 x1 1100
X∗ D∗
EC-413 15 / 37
Uniquely Decodable Code
Definition: A code is said to be uniquely decodable if its extension is
nonsingular.
C ∗ (x1 , x2 , . . . xn ) ̸= C (xi ), i = 1, 2 . . . , n
For example:
X C1 (Not Uniquely Decodable) C2 (Uniquely Decodable)
1 0 10
2 010 00
3 01 11
4 10 110
X = {1, 2, 3, 4}, X ∗ = {14, 31, ·, ·, ·}
C1∗ (14) = C1 (1)C1 (4) = 010 = C1 (2)
C1∗ (31) = C1 (3)C1 (1) = 010 = C1 (2)
EC-413 16 / 37
Instantaneous Code
Definition: A code is said to be an instantaneous code if no codeword
is a prefix of any other codeword
For example:
X C1 (Not Instantaneous) C2 (Instantaneous)
1 10 0
2 00 10
3 11 110
4 110 111
C1 (3) = 11 is the prefix of C1 (4) = 110
An instantaneous code can be decoded without reference to future
code words since the end of a codeword is immediately recognizable.
For example, the binary string 01011111010 produced by the code C2
is parsed as 0, 10, 111, 110, 10
An instantaneous code is a self punctuating code.
EC-413 17 / 37
Kraft Inequality
For any set of codewords over an alphabet of size D that form a
prefix-free code, the codeword lengths {l1 , l2 , · · ·, lm } must satisfy this
inequality
Xm
D −li ≤ 1.
i=1
Special case: Kraft inequality for binary instantaneous codes
m
X
2−li ≤ 1.
i=1
EC-413 18 / 37
Contd...
Example: Consider three codeword sets C1 , C2 , and C3 for a random
variable X
X C1 C2 C3
1 0 0 10
2 010 10 00
3 01 110 11
4 10 111 110
For C1 ; l1 = 1, l2 = 3, l3 = 2, l4 = 2
m m
X
−li
X 1 1 1 1 1 1 1 1 1 9
2 = l
= + 3 + 2 + 2 = + + + = > 1;
2 i 2 2 2 2 2 8 4 4 8
i=1 i=1
Hence C1 is not an instantaneous code.
EC-413 19 / 37
Contd...
X C1 C2 C3
1 0 0 10
2 010 10 00
3 01 110 11
4 10 111 110
For C2 ; l1 = 1, l2 = 2, l3 = 3, l4 = 3
m m
X X 1 1 1 1 1 1 1 1 1
2−li = l
= + 2 + 3 + 3 = + + + =1
2i 2 2 2 2 2 4 8 8
i=1 i=1
Hence, C2 is an instantaneous code because it satisfy both Kraft
inequality and prefix condition.
EC-413 20 / 37
Contd...
X C1 C2 C3
1 0 0 10
2 010 10 00
3 01 110 11
4 10 111 110
For C3 ; l1 = 2, l2 = 2, l3 = 2, l4 = 3
m m
X
−li
X 1 1 1 1 1 1 1 1 1 7
2 = = 2 + 2 + 2 + 3 = + + + = < 1,
2li 2 2 2 2 4 4 4 8 8
i=1 i=1
Hence, C3 is not an instantaneous code because it satisfy only Kraft
inequality but it does not satisfy prefix condition.
For example, C3 (3) = 11 is prefix of C3 (4) = 110
EC-413 21 / 37
Contd...
Any codeword set that satisfies the prefix condition has to satisfy the
Kraft inequality and the Kraft inequality is a sufficient condition for
the existence of a codeword set with the specified set of codeword
lengths.
Extended Kraft Inequality: For any countably infinite set of
codewords that form a prefix code, the codeword lengths l1 , l2 , ·, ·, ·
satisfy the extended Kraft inequality,
∞
X
D −li ≤ 1.
i=1
EC-413 22 / 37
Differences between various types of source codes
All codes
Nonsingular
codes
Uniquely
decodable codes
Instantaneous
codes
Observation:
The class of uniquely decodable codes is larger than the class of instantaneous, i.e.,
All instantaneous codes are uniquely decodable but all uniquely decodable codes are
not instantaneous codes.
EC-413 23 / 37
Classes of Codes
Nonsigular, But Not Uniquely Decodable,
X Singular C0 Instantaneous C3
Uniquely Decodable C1 But Not Instantaneous C2
1 0 0 10 0
2 0 010 00 10
3 0 01 11 110
4 0 10 110 111
C0 is singular code because it has many to one type mapping
C0 (1) = C0 (2) = C0 (3) = C0 (4) = 0.
C1 is nonsingular, but not uniquely decodable because its extension is
singular (many to one mapping), i.e.,C1∗ (14) = C1 (1)C1 (4) = 010 and
C1∗ (31) = C1 (3)C1 (1) = 010, both extensions have the same codeword 010.
C2 is uniquely decodable, but not instantaneous code because C2 (3) = 11 is
the prefix of C2 (4) = 110
C3 is instantaneous code because no codeword is a prefix of any other
codeword.
EC-413 24 / 37
Optimization Problem
A optimization problem has the following form
Objective function:
minimize g0 (y)
Constraint functions:
subject to gl (y) ≤ al l = 1, 2, . . . L
where
vector y = [y1 , y2 , . . . yn ] is optimization variable of problem
g0 (·) is the objective function
gl (·) are the constraint functions
al ’s are limits or bounds for the constraints.
EC-413 25 / 37
Contd..
Problem Statement: A homeowner wants to construct a house within
a budget and a fixed timeline while maximizing space utilization and
structural strength.
Optimization Objectives:
1) Minimize construction cost (materials, labor, and permits).
2) Minimize construction time while meeting deadlines.
3) Maximize space utilization within the given land area.
4) Ensure structural strength and energy efficiency.
Constraints:
Limited budget for materials and labor.
Time constraints due to weather conditions and deadlines.
Building regulations and zoning laws must be followed.
Availability of materials and labor.
EC-413 26 / 37
Optimal Codes
Definition: Optimal code is defined as a code with smallest possible
expected length LC for a random variable X with PMF p(x).
Problem Statement: To find the optimal prefix code. This is
equivalent to finding the set of codeword lengths l1 , l2 , · · ·, lm
satisfying
P the Kraft inequality and whose expected length
LC = Pi li is less than the expected length of any other prefix code.
Optimization problem: Minimize
X
LC = Pi li , Pi = P(X = xi ), li = l(xi )
over all integers l1 , l2 , · · ·, lm satisfying
X
D −li ≤ 1.
EC-413 27 / 37
Contd...
Let us relax the integer constraint on li and assume equality in the
Kraft inequality to obtain a lower bound.
Hence, we can write the constraint minimization using Lagrange
multipliers as the minimization of
X X
J= Pi li + λ D −li − 1
Differentiating w.r.t li , we obtain
dJ d ax
= Pi − λ D −li loge D, use = ax loge a
d li dx
dJ
Setting d li = 0, we obtain
Pi
D −li =
λ loge D
EC-413 28 / 37
Contd...
P
Pi
Substituting D −li = λ loge D in the Kraft equality D −li = 1
constraint, i.e.
X
1 = D −li .
X Pi
1 =
λ loge D
1 X
1 = Pi
λ loge D
1
λ =
loge D
1
we find λ = loge D and hence
Pi = D −li
yielding optimal code lengths li = − logD Pi
EC-413 29 / 37
Contd...
This non-integer choice of the codeword lengths yields expected
codeword length
X X
LC = Pi li = − Pi logD Pi = HD (X ).
Thus a bound on the optimal code length LC is HD (X ). This is the
lower bound, i.e.
LC ≥ HD (X )
and equality holds if and only if Pi = D −li .
EC-413 30 / 37
Contd...
Since li = − logD Pi may not equal to an integer, we round it up to
give integer codeword length assignments
l 1m
li = logD ;
Pi
where ⌈x⌉ is the smallest integer greater than equal to x. For
example ⌈2⌉ = 2, ⌈2.3⌉ = 3. These codeword lengths satisfy the
Kraft inequality, i.e.
X − log 1 X − log 1 X
D P D P
D i ≤ D i = Pi = 1
We can create a prefix code with these lengths
X l 1m
LC = Pi logD
Pi
X 1 X 1 X
< Pi logD +1 = Pi logD + Pi
Pi Pi
< HD (X ) + 1
EC-413 31 / 37
Bounds on the optimal prefix code expected length
HD (X ) ≤ LC < HD (X ) + 1
EC-413 32 / 37
Wrong Code
Theorem: The expected length
l under
m PMF pX (x) of the codeword
1
length assignment l(x) = log Q(x) satisfies
H(Xp ) + D(p(x) ∥ q(x)) ≤ Ep l(X ) < H(Xp ) + D(p(x) ∥ q(x)) + 1
Thus, assuming that the PMF is qX (x) when the true PMF is pX (x)
incurs a penalty of D(p(x) ∥ q(x)) bits in the average description
length.
EC-413 33 / 37
Contd...
Proof: The expected length is
X l 1 m
Ep l(X ) = P(x) log
x
Q(x)
X 1
< P(x) log +1
x
Q(x)
X P(x) 1
< P(x) log +1
x
Q(x) P(x)
X P(x) X 1 X
< P(x) log + P(x) log + P(x)
x
Q(x) x
P(x) x
| {z } | {z } | {z }
=D(p(x)∥q(x)) =H(Xp ) =1
< D(p(x) ∥ q(x)) + H(Xp ) + 1
The lower bound can also be derived similarly.
EC-413 34 / 37
References
T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons, 1991.
EC-413 35 / 37
QUESTIONS ?
EC-413 36 / 37
THANK YOU
EC-413 37 / 37