Scribd
Upload
3 views2 pages

Variable Length Coding

Variable Length Coding (VLC) assigns codewords of varying lengths based on symbol frequency, optimizing data compression by reducing the Average Code Length to approach Entropy. Prefix Codes ensure that no codeword is a prefix of another, allowing for unambiguous decoding. Kraft's Inequality and Shannon's theorem provide the mathematical foundation for the feasibility and limits of VLC in data compression.

Uploaded by

meheraf.gsc2002
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views2 pages

Variable Length Coding

Variable Length Coding (VLC) assigns codewords of varying lengths based on symbol frequency, optimizing data compression by reducing the Average Code Length to approach Entropy. Prefix Codes ensure that no codeword is a prefix of another, allowing for unambiguous decoding. Kraft's Inequality and Shannon's theorem provide the mathematical foundation for the feasibility and limits of VLC in data compression.

Uploaded by

meheraf.gsc2002
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Lecture 4: Variable Length Coding (VLC)

Topic: Data Compression and Prefix Codes

1 Concept of Variable Length Coding


In previous lectures, we used the same number of bits for every symbol (Fixed Length
Coding). Variable Length Coding (VLC) is a strategy where different symbols are
assigned codewords of different lengths.
The fundamental principle is:

The VLC Rule


Assign shorter codewords to symbols that occur frequently (High Probability)
and longer codewords to symbols that occur rarely (Low Probability).

2 Why Use VLC?


VLC is the basis of almost all lossless data compression algorithms (like ZIP, JPEG, and
MP3). By matching the code length to the probability of the symbol, we can reduce the
Average Code Length (L) to be as close to the Entropy (H) as possible.

3 Prefix Codes (Instantaneous Codes)


A major challenge with variable lengths is knowing where one character ends and the
next begins. To solve this, we use Prefix Codes.

3.1 Definition
A code is called a Prefix Code (or Prefix-free code) if no codeword is a prefix of any
other codeword.

3.2 Example
Consider a source with symbols {A, B, C}.

• Non-Prefix Code: A = 0, B = 01, C = 11.


Problem: If the receiver gets ”011”, they don’t know if it is A followed by C, or
just B followed by something else.

• Prefix Code: A = 0, B = 10, C = 11.


Benefit: As soon as the receiver sees ”0”, they know it is A. If they see ”10”, they
know it is B. There is no ambiguity.

1
4 Kraft’s Inequality
How do we know if it is even possible to create a prefix code for a given set of lengths?
We use Kraft’s Inequality.
For a set of codeword lengths {l1 , l2 , ..., ln }, a prefix code exists if and only if:
n
X
2−li ≤ 1 (1)
i=1

Example: Can we have a prefix code with lengths {1, 2, 3, 3}?


Check: 2−1 + 2−2 + 2−3 + 2−3 = 0.5 + 0.25 + 0.125 + 0.125 = 1.0.
Since 1.0 ≤ 1, this set of lengths can form a prefix code.

5 The Entropy Bound


Shannon proved that for any source X, the average length L of an optimal variable length
code is bounded by:
H(X) ≤ L < H(X) + 1 (2)
This means we can never compress data smaller than its Entropy without losing infor-
mation.

6 Comparison Summary
Feature Fixed Length Variable Length
Bit Length Same for all symbols Different (based on prob.)
Efficiency Low (if probs vary) High (Optimized)
Complexity Simple to implement Requires specific algorithms
Usage ASCII, Basic structures Huffman, Shannon-Fano

Variable Length Coding is the key to efficient communication. By ensuring the Prefix
Property, we allow for instantaneous decoding while significantly reducing the amount
of data transmitted. In our next session, we will learn the Huffman Algorithm to
generate these codes automatically.

You might also like