Huffman coding, Shannon codes, and

Shannon-Fano-Elias Coding

EC-413 1 / 33
Last Time

Data compression (Source coding)

Lossless compression.
Lossy compression.
Types of source codes
Nonsingular code
Uniquely decodable code
Instantaneous or prefix code
Kraft inequality for instantaneous code
Optimal code (shortest expected length)
Bounds on the expected length of the optimal D-ary code

HD (X ) ≤ Lc < HD (X ) + 1

EC-413 2 / 33
Outline

Kraft inequality for uniquely decodable code

Huffman coding
Shannon codes
Shannon-Fano-Elias Coding

EC-413 3 / 33
Kraft inequality for uniquely decodable code

MacMillan Inequality: The codeword lengths l1 , l2 , ·, ·, ·, lm of any

uniquely decodable D-ary code must satisfy the Kraft inequality,
m
X
D −li ≤ 1.
i=1

Special case: MacMillan Inequality for uniquely decodable binary

(D = 2) codes
m
X
2−li ≤ 1.
i=1

EC-413 4 / 33
Extended MacMillan Inequality

A uniquely decodable code for any infinite source alphabet X also

satisfy the Kraft inequality
∞
X
D −li ≤ 1.
i=1

Note that both, uniquely decodable and instantaneous codes
provide

the same set of achievable codeword lengths {l1 , l2 , ·, ·, ·} .

EC-413 5 / 33
D-ary Huffman Coding Scheme

An optimal prefix-free code for a given PMF.

Algorithm: Proceeding this way,
Arranging the symbols in a decreasing order of their probabilities
Combining at a time the D least likely symbols into one symbol, repeat
this until we are finally left with only D symbol
These D (reduced) symbols are now assigned 0, 1, · · ·, D − 1 as their
first digits in the code sequence.
Now go back and assigns the 0, 1, · · ·, D − 1 to the second digit for the
D symbols that were combined in the previous step
Keep regressing this way until the original probabilities column is
reached
Huffman coding is not unique as it depends on where one puts the
merged probabilities. Moreover, the set of codeword lengths for
optimal prefix code is also not unique.

EC-413 6 / 33
Binary Huffman Coding Scheme Example

Example: A zero-memory source emits six messages (symbols)

m1 , m2 , m3 , m4 , m5 , m6 with probabilities
0.30, 0.25, 0.15, 0.12, 0.10, 0.08, respectively. Find the binary Huffman
code. Determine its expected codeword length and the entropy.
Given
X = {m1 , m2 , m3 , m4 , m5 , m6 }
P(m1 ) = 0.30, P(m2 ) = 0.25, P(m3 ) = 0.15, P(m4 ) = 0.12,
P(m5 ) = 0.10, P(m6 ) = 0.08
D = 2 ⇒ D = {0, 1}

EC-413 7 / 33
 1st 2nd 3rd 4th
Message Probabilities Reduction Reduction Reduction Reduction

m1 0.30 0.30 0.30 0.43 0.57

m2 0.25 0.25 0.27 0.30 0.43

m3 0.15 0.18 0.25 0.27

m4 0.12 0.15 0.18

m5 0.10 0.12

m6 0.08

EC-413 8 / 33
 1st 2nd 3rd 4th
Message Probabilities Reduction Reduction Reduction Reduction

m1 0.30 0.30 0.30 0.43 1 0.57 0

00
m2 0.25 0.25 0.27 0.30 0.43 1

m3 0.15 0.18 0.25 0.27

01
m4 0.12 0.15 0.18

m5 0.10 0.12

m6 0.08

EC-413 9 / 33
 1st 2nd 3rd 4th
Message Probabilities Reduction Reduction Reduction Reduction

m1 0.30 00 0.30 00 0.30 00 0.43 1 0.57 0

00
m2 0.25 10 0.25 10 0.27 01 0.30 0.43 1

10
m3 0.15 010 0.18 11 0.25 0.27
01
010
m4 0.12 011 0.15 0.18
11
110
m5 0.10 0.12
011
m6 0.08
111

EC-413 10 / 33
 Huffman Code
Message Probabilities Codes Length
l(mi )

m1 0.30 00 2

m2 0.25 10 2

m3 0.15 010 3

m4 0.12 011 3

m5 0.10 110 3

m6 0.08 111 3

EC-413 11 / 33
Contd....
The expected length LC is computed as
6
X
LC = P(mi )l(mi )
i=1
= P(m1 )l(m1 ) + P(m2 )l(m2 ) + P(m3 )l(m3 ) + P(m4 )l(m4 )
+P(m5 )l(m5 ) + P(m6 )l(m6 )
= 0.30 × 2 + 0.25 × 2 + 0.15 × 3 + 0.12 × 3
+0.10 × 3 + 0.08 × 3
= 2.54 binary digits = 2.54 bits.

The entropy H(X ) of the source is computed as

6
X 1
H(X ) = P(mi ) log2 = 2.418 bits.
P(mi )
i=1

EC-413 12 / 33
Code Efficiency η and Redundancy γ

The merit of any code is measured by its expected length, LC in

comparison to its entropy, H(X ). We defined the code efficiency η as

H(X )
η= .
LC
The redundancy γ is defined as

γ = 1 − η.

EC-413 13 / 33
Contd...

We have

H(X ) = 2.418 bits.

LC = 2.54 bits.

The code efficiency η is

H(X ) 2.418
η= = = 0.952 = 95.2%
LC 2.54
The redundancy γ is

γ = 1 − η = 1 − 0.952 = 0.048 = 4.8%

EC-413 14 / 33
Contd...

If we may not have a sufficient number of symbols so that we can

combine them D at a time.
In such a case, we add dummy symbols to the end of the set of
symbols. The dummy symbols have probability 0 .
we need the total number of symbols to be D + k(D − 1), where k is
the number of total reductions.

EC-413 15 / 33
4-ary Huffman Coding Scheme Example

Example: A zero-memory source emits six messages (symbols)

m1 , m2 , m3 , m4 , m5 , m6 with probabilities
0.30, 0.25, 0.15, 0.12, 0.10, 0.08, respectively. Find the 4-ary
(quaternary) Huffman code. Determine its expected codeword length,
the efficiency and the redundancy.
Given
X = {m1 , m2 , m3 , m4 , m5 , m6 }
P(m1 ) = 0.30, P(m2 ) = 0.25, P(m3 ) = 0.15, P(m4 ) = 0.12,
P(m5 ) = 0.10, P(m6 ) = 0.08
D = 4, ⇒ D = {0, 1, 2, 3}

EC-413 16 / 33
4-ary Huffman Coding Scheme

1st
Message Probabilities Reduction
k=1

m1 0.30 0.45
m2 0.25 0.30
m3 0.15 0.25
m4 0.12
m5 0.10
m6 0.08

After first reduction we are left with less than 4, hence we must add few dummy messages with zero probability of
occurrence to proceed as usual.
The number of messages is 6, then we must add one dummy message m7 with zero probability of occurrence to make
the total number of messages 7, that is D + k(D − 1) = 4 + 1 × (4 − 1) = 7 (k is equal to 1 because after first
reduction we are left with less than 4 ).

EC-413 17 / 33
Contd...

1st
Message Probabilities Reduction
k=1

m1 0.30 0.30
m2 0.25 0.30
m3 0.15 0.25
m4 0.12 0.15
m5 0.10
m6 0.08
Dummy
Symbol m7 0.00

EC-413 18 / 33
Contd...

1st
Message Probabilities Reduction
k=1

m1 0.30 0.30 0
m2 0.25 0.30 1
m3 0.15 0.25 2
m4 0.12 0.15 3
m5 0.10
m6 0.08
m7 0.00

EC-413 19 / 33
Contd...

1st
Message Probabilities Reduction
k=1

m1 0.30 0 0.30 0
m2 0.25 2 0.30 1
m3 0.15 3 0.25 2
m4 0.12 10 0.15 3
m5 0.10 11
m6 0.08 12
m7 0.00 13

EC-413 20 / 33
Contd...

4-ary Code
Message Probabilities Huffman Length
Codes l(mi )

m1 0.30 0 1
m2 0.25 2 1
m3 0.15 3 1
m4 0.12 10 2
m5 0.10 11 2
m6 0.08 12 2
m7 0.00 13 2

EC-413 21 / 33
Contd....
The expected length LC is computed as
6
X
LC = P(mi )l(mi )
i=1
= 0.30 × 1 + 0.25 × 1 + 0.15 × 1 + 0.12 × 2
+0.10 × 2 + 0.08 × 2
= 1.3, 4-ary digits = 1.3, quaternary digits.

The entropy H(X ) of the source is computed as

6
X 1
H(X ) = P(mi ) log4 = 1.209 quaternary digits.
P(mi )
i=1

The code efficiency η = H(X ) 1.209

LC = 1.3 = 0.93. = 93%
The redundancy γ = 1 − η = 1 − 0.93 = 0.07 = 7%
EC-413 22 / 33
Shannon Codes
l m
1
Definition: Codes that use the codeword lengths of l(x) = log P(x)
are called Shannon codes
Shannon Coding scheme can be used to construct a uniquely
decodable code.
Example: Consider a random variable X with PMF
p(x) = 0.9999 δ(x − x1 ) + 0.0001 δ(x − x2 )
X =x Probabilities Shannon lengths Huffman lengths
x1 0.9999 1 bit 1 bit
x2 0.0001 14 bits 1 bit
l m
1
So, we can say that using codeword lengths of l(x) = log P(x)
(which is called Shannon coding) may be much worse than optimal
code for some particular symbol.
Is it true that the codeword lengths
l for individual
m symbols in an
1
optimal code are always less than log P(x) ? Answer: This is not
always true.
EC-413 23 / 33
Contd...

Example: Consider a random variable X with PMF

p(x) = 13 δ(x − 1) + 13 δ(x − 2) + 41 δ(x − 3) + 12
1
δ(x − 4).
The Huffman coding procedure results in codeword lengths of
(2, 2, 2, 2) or (1, 2, 3, 3) (depending on where one puts the merged
probabilities). Both these codes achieve the same expected codeword
length. In the second set of codeword lengths,
l the mthird symbol has
1
codeword length 3, which is greater than log P(3) = 2. So, we can
say that for individual symbols, either the Shannon code or Huffman
code can be shorter. But the Huffman code is shorter on average.
The Shannon code and Huffman code differ by less than 1 bit in
expected codeword length since both lie between H(X ) and H(X ) + 1.

EC-413 24 / 33
D-adic Distribution

Definition: A probability distribution is called D-adic w.r.t. D, if each

of the probabilities is equal to D1n , for some integer n
Consider a random variable X with PMF
p(x) = 14 δ(x − 1) + 12 δ(x − 2) + 81 δ(x − 3) + 18 δ(x − 4).
This is an example of 2-adic (dyadic) distribution since each of the
probabilities is equal to 21n , for some integer n, i.e.
P(1) = 212 , P(2) = 12 , P(3) = 213 , P(4) = 213
It is possible to find a code defined on this distribution, which has an
average code length that is equal to the entropy

EC-413 25 / 33
Shannon-Fano-Elias Coding Scheme
l m
1
We showed that Shannon codeword lengths l(x) = log P(x) satisfy
the Kraft inequality and can be used to construct a uniquely
decodable code.
Shannon-Fano-Elias coding scheme is a simple method for
constructing uniquely decodable code. It uses the modified
cumulative distribution function
l (CDF)
m to allot codewords C (x) with
1
codeword lengths l(x) = log P(x) + 1.
The CDF, F (x) of a random variable X is defined as
X
F (x) = P{X ≤ x} = P(z)
z≤x

The modified CDF, F (x) of a random variable X is defined as

X 1
F (x) = P(z) + P(x)
z<x
2

EC-413 26 / 33
Contd...

l m
1
In this scheme, we use l(x) = log P(x) + 1 bits to represent x, the
expected length of this code C is
X X l 1 m 
LC = P(x)l(x) = P(x) log +1
x x
P(x)
X  1 
< P(x) log +1+1 , use ⌈x⌉ < x + 1
x
P(x)
< H(X ) + 2

Thus, this coding scheme achieves an average codeword length that is

within 2 bits of the entropy H(X ).

EC-413 27 / 33
Contd...

Example: Consider a random variable X with PMF

p(x) = 14 δ(x − 1) + 12 δ(x − 2) + 81 δ(x − 3) + 18 δ(x − 4). Find the
Shannon-Fano-Elias code. Determine its average codeword length and
entropy.

EC-413 28 / 33
Contd...

X =x P(x) F (x) F (x) F (x) (in binary) l(x) Code

1 0.25 0.25 0.125 0.001 3 001
2 0.50 0.75 0.5 0.10 2 10
3 0.125 0.875 0.8125 0.1101 4 1101
4 0.125 1 0.9375 0.1111 4 1111
l m
P 1 1
where F (x) = z<x P(z) + 2 P(x) and l(x) = log P(x) + 1
F (1) = Pz<1 P(z) + 21 P(1) = 0 + 0.125 = 0.125
P
F (2) = Pz<2 P(z) + 21 P(2) = F (1) + 12 P(2) = 0.25 + 0.25 = 0.50
F (3) = Pz<3 P(z) + 21 P(3) = F (2) + 12 P(3) = 0.75 + 0.0625 = 0.8125 =
F (4) = z<4 P(z) + 12 P(4) = F (3) + 12 P(4) = 0.875 + 0.0625 = 0.9375 =

EC-413 29 / 33
Contd...

The average codeword length

X
LC = P(x)l(x)
x
= 2.75 bits

The entropy
X
H(X ) = − P(x) log2 P(x)
x
= 1.75 bits

The Huffman code for this distribution (dyadic) achieves the entropy
bound.

EC-413 30 / 33
References

T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons, 1991.

B. P. Lathi, Modern Digital and Analog Communication Systems, 3rd ed. Oxford University Press, 2002.

EC-413 31 / 33
QUESTIONS ?

EC-413 32 / 33
THANK YOU

EC-413 33 / 33