ECE421 Digital Communication
Source Coding
Lecturer: Dr. Reham Samir
References
n K. Deergha Rao “Channel Coding Techniques for
Wireless Communications” Springer, 2015.
n Behrouz A. Forouzan “Data Communication and
Networking” (5th Edition), McGraw Hill, 2015.
n Behrouz A. Forouzan “Data Communication and
Networking” (3rd Edition), McGraw Hill, 2004.
n Peyton Z. Peebles, Jr., Ph.D “Digital Communication
Systems” Prentice-Hall, 1987.
Introduction
n Source coding means how to efficiently represent the symbols
generated by some source.
n Source coding applications
n Magnetic recording: cassette, hardrive, USB...
n Speech compression
n Compact disk (CD)
n Image compression: JPEG
Shannon’s Source Coding Theorem
n Shannon showed that “To encode a random information source X
into bits, we need at least H(X) bits”.
n Entropy is lower bound on expected code length.
Shannon’s Source Coding Theorem
n Example:
n If I toss a dice 1,000,000 times and record values from each trial
1,3,4,6,2,5,2,4,5,2,4,5,6,1,…….
n In principle, I need 3 bits for storing each outcome as 3 bits covers 1-
8. So I need 3,000,000 bits for storing the information.
n Using Extended ASCII representation, computer needs 8 bits = 1 byte
for storing each outcome. The resulting file has size 8,000,000 bits.
n But Shannon said you only need 2.585 bits for storing each outcome.
So, the file can be compressed to yield size 2585000 bits.
Shannon’s Source Coding Theorem
n Example:
Types of Information Source
n Zero Memory Source (ZMS)
n Current symbol is independent on the previous symbols.
n Source with Memory
n Current o/p symbol is dependent on M-previous symbols and it has M
memory locations for storing the previous symbols.
Zero Memory Source (ZMS)
n Codes Types
n Blocking and Non-Blocking
n Singular and Non-Singular
n Uniquely and Non-Uniquely Decodable
n Instantaneous and Non-Instantaneous
Codes Types
n Blocking and Non-Blocking
Codes Types
n Singular and Non-Singular
Code(A) = Code(C)
we will not be able to
distinguish between A
and C.
Codes Types
n Singular and Non-Singular
n Example: The following mapping is Singular or Non-Singular?
n Sol: Non-singular
Codes Types
n Uniquely and Non-Uniquely Decodable
n Uniquely decodable if only one possible source string producing it.
Codes Types
n Uniquely and Non-Uniquely Decodable
n Example: The following mapping is Uniquely Decodable or Non-
Uniquely Decodable?
n Sol: Non-Uniquely Decodable.
n For instance, the sequence 010 could represent either b, ca or ad
Codes Types
n Instantaneous (Prefix) and Non-Instantaneous
n In other words, a code is called a prefix code or an instantaneous code if no
codeword is a prefix of any other codeword (no symbol’s code is the
beginning of a code for a different symbol).
Codes Types
n Instantaneous (Prefix) and Non-Instantaneous
n Example: The following mapping is Instantaneous or Non-
Instantaneous?
n Sol: Instantaneous
Codes Types
n Example:
Optimum Codes
n The optimum codes have the following properties :
n Blocking
n Non-Singular
n Uniquely Decodable
n Instantaneous
Optimum Codes
Fixed Length Codes
n Consider encoding the N symbols { s i }, entropy H, as a fixed
length (L) block binary digits. To ensure we can decode these
symbols we need:
L=
n Where X is the largest integer less than X.
n H log 2 ( N ) then H L
n The efficiency of the coding is given by:
H
L
n When the N symbols are equiprobable, then H = L, and 1
Variable Length Codes
n In general we don’t have equiprobable symbols, and we would
hope to achieve some more compressed form of encoding by use of
variable length codes.
n Example: Consider four symbol alphabet and some possible
variable length codes:
Variable Length Codes
n Example:
n For code 1
n The coding rate, or average number of bits per symbol, is given by:
Lavg Li Pi
i
n The Entropy (H) is given by: -(1/2)log(1/2)-(1/4)log(1/4)-(1/8)log(1/8)-
(1/8)log(1/8) = 7/4
n The coding rate is less than the entropy (H = 7/4)
Variable Length Codes
n Example:
n For code 2
n This code is uniquely decodable; we can decode instantenously (no back
tracking is required); once we have the bits of the encoded symbol we
can decode without waiting for more.
n This code satisfies the prefix condition, that is there is no code word
which is prefix ( same bit pattern) of a longer code word.
1 1 1 1 7
L avg X1 X 2 X 3 X 3
2 4 8 8 4
n The coding rate is equal to the entropy (coding rate = H = 7/4) .
Variable Length Codes
n Example:
n For code 3
n This code is decodable.
n The code does not have the prefix property and is not an instantaneous
code.
1 1 1 1 7
L avg X1 X 2 X 3 X 3
2 4 8 8 4
n The coding rate is equal to the entropy (coding rate = H = 7/4) .
Variable Length Codes
n Note:
n The code is called optimally efficient when Lavg = H (the coding rate
equals the entropy of the source).
n Example:
n Whether this code is optimally efficient code or not?
Probability Code Letter
1/2 1 A
1/4 01 B
1/8 001 C
1/16 0000 D
1/16 0001 E
Variable Length Codes
n Sol:
n H = 1/2 + 2/4 + 3/8 + 4/16 + 4/16 = 1(7/8)
n Lavg = 1 x 1/2 + 2 x 1/4 + 3x 1/8 + 4x 1/16 + 4x 1/16 = 1(7/8)
n Then the code is optimally efficient.
Prefix Codes
n For a prefix code to exist, it must satisfy the Kraft-Mcmillan
inequality. That is a necessary condition for a code having binary
code words with length L1 L2 ..... LN to satisfy the prefix
condition is:
N
1
i1 2 L i
1
Prefix Codes
n Example: Consider code with five symbols as follows:
1. Does this code satisfy the Kraft-Mcmillan inequality?
2. Calculate the average code length.
3. Calculate the code efficiency.
Prefix Codes
n Sol:
1. Does this code satisfy the Kraft-Mcmillan inequality?
1. Calculate the average code length.
1. Calculate the code efficiency.
Prefix Codes
n To create instantaneous code we use tree method.
n Each codeword is represented by a leaf node.
n Path from the root traces out the symbol.
n No codeword is an ancestor of any other codeword on the tree.
Prefix Codes
n Example: Consider code with lengths given as follows:
n Does this code satisfy the Kraft-Mcmillan inequality?
n Create instantaneous binary code with lengths given in the table.
Prefix Codes
n Sol:
