Information Theory Basics

Information theory, founded by Claude Shannon in 1948, provides the mathematical framework for understanding the fundamental limits of data compression and reliable communication. It answers two crucial questions: How much can data be compressed? And at what rate can we communicate reliably over a noisy channel?

The Concept of Information

In information theory, "information" has a precise mathematical meaning — it quantifies the surprise or uncertainty associated with an event.

Information Content of an event with probability p:

I(x) = -log₂(p) = log₂(1/p) bits

Key properties:

• Certain event (p=1): I = 0 bits (no surprise)
• Impossible event (p→0): I → ∞ bits (maximum surprise)
• Independent events: I(x,y) = I(x) + I(y)

Example:

• Fair coin: I(head) = -log₂(0.5) = 1 bit
• Biased coin (p=0.9): I(head) = -log₂(0.9) = 0.152 bits
• Roll of 6 on fair die: I(6) = -log₂(1/6) = 2.585 bits

Entropy

Entropy is the average information content (average surprise) of a source:

H(X) = -Σ P(xᵢ) × log₂[P(xᵢ)] bits/symbol

Properties of Entropy:

1. H(X) ≥ 0 (entropy is non-negative)
2. H(X) ≤ log₂(M) for M possible outcomes (maximum = uniform distribution)
3. H(X) = 0 only if one outcome has probability 1
4. Maximum entropy means maximum uncertainty/randomness

Binary Entropy Function:

For binary source with P(0) = p, P(1) = 1-p:

H(p) = -p×log₂(p) - (1-p)×log₂(1-p)

Joint and Conditional Entropy

Joint Entropy: H(X,Y) = -Σ Σ P(x,y) × log₂[P(x,y)]

Conditional Entropy: H(X|Y) = -Σ Σ P(x,y) × log₂[P(x|y)]

Chain Rule: H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)

Mutual Information

Measures how much knowing Y tells us about X:

I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)

Also: I(X;Y) = H(X) + H(Y) - H(X,Y)

Shannon's Source Coding Theorem

First Theorem: A source with entropy H can be encoded with average code length L satisfying:

H ≤ L < H + 1 bits/symbol

This means we cannot compress below the entropy rate, and we can always get within 1 bit of it.

Implications:

• Entropy sets the compression limit
• Huffman coding achieves L ≤ H + 1
• Arithmetic coding can approach H arbitrarily closely

Shannon's Channel Coding Theorem

Second Theorem: For a channel with capacity C:

• If transmission rate R < C: there exist codes achieving arbitrarily low error probability
• If R > C: reliable communication is impossible

Channel Capacity:

C = max{p(x)} I(X;Y) bits/channel use

The maximum is over all possible input distributions.

For AWGN: C = B × log₂(1 + SNR) bits/second

Source-Channel Separation Theorem

Theorem: Source coding and channel coding can be designed independently (separated) without loss of optimality.

This justifies the modern approach of:

1. First compress (source coding)
2. Then add redundancy for error protection (channel coding)

Practical Applications

Solved Example

Problem: A source produces 5 symbols with probabilities: P(A)=0.4, P(B)=0.2, P(C)=0.2, P(D)=0.1, P(E)=0.1. Calculate: (a) information content of each symbol, (b) source entropy, (c) can the source be represented with average < 2 bits/symbol?

Solution:

(a) Information content:

• I(A) = -log₂(0.4) = 1.322 bits
• I(B) = -log₂(0.2) = 2.322 bits
• I(C) = -log₂(0.2) = 2.322 bits
• I(D) = -log₂(0.1) = 3.322 bits
• I(E) = -log₂(0.1) = 3.322 bits

(b) Source entropy: H = 0.4(1.322) + 0.2(2.322) + 0.2(2.322) + 0.1(3.322) + 0.1(3.322) H = 0.529 + 0.464 + 0.464 + 0.332 + 0.332 H = 2.122 bits/symbol

(c) Since entropy H = 2.122 bits/symbol, by the source coding theorem, the minimum average code length cannot be less than 2.122 bits/symbol. Therefore, NO, we cannot represent this source with average less than 2 bits/symbol.

With Huffman coding, we can achieve approximately 2.2 bits/symbol.

Interview Questions

Q1: What is the physical meaning of entropy in information theory?

Entropy represents the average uncertainty or average information content of a source. Higher entropy means more randomness (harder to predict, more bits needed to encode). A source with maximum entropy (uniform distribution) is completely random and incompressible. A source with zero entropy is completely predictable and needs no bits.

Q2: Why is Shannon's channel coding theorem considered revolutionary?

Before Shannon, engineers believed that reducing error rate required reducing transmission rate. Shannon proved that error-free communication at rates up to channel capacity is achievable with appropriate coding. He showed the existence of codes without constructing them — it took 45+ years to find practical capacity-approaching codes (turbo codes in 1993, LDPC rediscovery in 1996).

Q3: Explain the relationship between entropy and data compression.

Entropy is the fundamental limit of lossless compression. A source with entropy H bits/symbol cannot be compressed below H bits/symbol on average without losing information. Compression algorithms like Huffman approach this limit. The redundancy R = L - H represents the remaining compressibility. Maximum compression = entropy.

Q4: What is mutual information and how does it relate to channel capacity?

Mutual information I(X;Y) measures the information shared between input X and output Y of a channel. Channel capacity C = max I(X;Y) over all input distributions. It quantifies how much the output tells us about the input. A perfect channel has I(X;Y) = H(X), while a completely noisy channel has I(X;Y) = 0 (output is independent of input).