Lecture 3: Source Coding
Topic: Data Compression and Efficiency
1 Introduction to Source Coding
The primary objective of Source Coding is to represent the output of a data source
(text, image, audio) as efficiently as possible. In simple terms, it is the process of con-
verting a sequence of symbols into a sequence of binary bits (0s and 1s) such that the
total number of bits is minimized. This is the foundation of Data Compression.
2 Variable Length vs. Fixed Length Coding
• Fixed-Length Code: Every symbol is represented by the same number of bits.
For example, if we have 4 symbols {A, B, C, D}, we might use 2 bits for each:
A = 00, B = 01, C = 10, D = 11.
• Variable-Length Code: Symbols that occur more frequently are assigned shorter
codes, while rare symbols get longer codes. This leads to a smaller average file size.
3 Important Coding Properties
To ensure the receiver can understand the message without ambiguity, a code must satisfy
specific properties:
3.1 Uniquely Decodable Codes
A code is uniquely decodable if every encoded string can be decomposed into a unique
sequence of source symbols.
3.2 Prefix Codes (Prefix-Free Codes)
A code is called a Prefix Code if no codeword is a prefix of any other codeword.
• Example of Invalid Prefix Code: A = 0, B = 01. (Here, 0 is a prefix of 01. If
the receiver sees 01, they won’t know if it is B or A followed by something else).
• Example of Valid Prefix Code: A = 0, B = 10, C = 11. (No code starts with
another code).
1
4 Average Code Length (L)
The performance of a source code is measured by its average length. If a source has
symbols xi with probabilities P (xi ) and assigned codeword lengths li , the average length
L is:
n
X
L= P (xi ) · li bits/symbol (1)
i=1
5 Source Coding Efficiency (η)
We compare our average length L with the theoretical limit, which is the Entropy H(X).
H(X)
Efficiency (η) = × 100% (2)
L
• A code is 100% efficient if L = H(X).
• The Redundancy (R) is defined as: R = 1 − η.
6 Numerical Example for the Class
Scenario: A source emits three symbols {S1 , S2 , S3 } with probabilities: P (S1 ) = 0.5, P (S2 ) =
0.25, P (S3 ) = 0.25.
Let’s assign a Prefix Code: S1 = 0, S2 = 10, S3 = 11.
Step 1: Calculate Entropy H(X)
H(X) = −[0.5 log2 (0.5) + 0.25 log2 (0.25) + 0.25 log2 (0.25)]
H(X) = −[0.5(−1) + 0.25(−2) + 0.25(−2)]
H(X) = 0.5 + 0.5 + 0.5 = 1.5 bits/symbol
Step 2: Calculate Average Length L
Lengths are l1 = 1 (for ’0’), l2 = 2 (for ’10’), l3 = 2 (for ’11’).
L = (0.5 × 1) + (0.25 × 2) + (0.25 × 2)
L = 0.5 + 0.5 + 0.5 = 1.5 bits/symbol
Step 3: Calculate Efficiency
1.5
η= × 100% = 100%
1.5
Source coding allows us to represent information at the edge of the Entropy limit. In
the next lecture, we will study specific algorithms like Huffman Coding to construct
these optimal codes systematically.