Introduction to Information Theory Study Guide

Explore the fundamental limits of data compression and reliable communication. From Claude Shannon's entropy to the noisy-channel coding theorem.

Entropy & Self-Information

Information theory quantifies the "surprise" of an event. Rare events carry more information than common ones.

Core Concepts

Self-Information

I(x) = -log2 P(x)

Measured in Bits. If P(x) = 0.5, I(x) = 1 bit.

Entropy (H)

H(X) = -Σ P(x) log2 P(x)

The average uncertainty or information content of a source.

Binary Entropy Simulator

Adjust the probability of a binary source (Coin Flip) to see how entropy changes.

P(Heads) 0.50
Entropy (H)
1.000
bits/symbol
Max Capacity
1.000
bits/symbol

Entropy is maximized when uncertainty is highest (p=0.5).

Source Coding

How do we represent data efficiently? Source coding removes redundancy to compress data.

Kraft Inequality

A necessary condition for the existence of an instantaneous (prefix-free) code.

Σ D-li ≤ 1

Where D is the size of the alphabet and li are code lengths.

Huffman Coding Algorithm

Optimal prefix code minimizing expected length.

Greedy Algorithm
1. Sort symbols by probability (descending).
2. Combine two lowest probabilities into a node.
3. Re-sort and repeat until one node remains.
4. Assign '0' to left branches, '1' to right.

Huffman Tree Builder

Enter symbol probabilities (sum does not need to be 1, will be normalized):

Resulting Codes

Click "Generate Code" to see results...

Channel Capacity

The maximum rate at which information can be transmitted over a noisy channel with arbitrarily low error.

Mutual Information

Measures the information that X (input) and Y (output) share. It quantifies the reduction in uncertainty of X given Y.

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

Information sent - Information lost to noise

  • • If channel is noiseless, H(X|Y) = 0, so I(X;Y) = H(X).
  • • If X and Y are independent, I(X;Y) = 0.

Binary Symmetric Channel (BSC)

A simple model where bits are flipped with probability p.

0
1
0
1
1-p
1-p
p
p

BSC Capacity Formula:

C = 1 - H(p)

Where H(p) is the binary entropy function.

The Shannon Limit

"It is possible to transmit information with arbitrarily low error probability over a noisy channel, provided the transmission rate is below the channel capacity."

— Claude Shannon, 1948

AWGN Channel Capacity

For a channel with Additive White Gaussian Noise (AWGN), the capacity is determined by the Signal-to-Noise Ratio (SNR).

C = B log2(1 + SNR)

C
Channel Capacity
bits per second (bps)
B
Bandwidth
Hz
SNR
Signal-to-Noise Ratio
Power ratio (S/N)

Capacity vs. SNR

Normalized for Bandwidth (B=1Hz). Capacity increases logarithmically with power.