Entropy, Information & Coding

Information theory measures information in bits. Learn self-information, Shannon entropy, joint and conditional entropy, mutual information, the source-coding theorem, Huffman coding, the binary symmetric channel and how these ideas set the limits of compression and communication — with Python entropy calculations.

How many yes/no questions do you need to identify an outcome? That number, averaged over outcomes, is the entropy. A fair coin needs one bit; a heavily biased coin needs less because the answer is usually predictable.

Claude Shannon's 1948 theory showed entropy is the minimum average number of bits for lossless compression, and mutual information bounds how fast data can pass through a noisy channel. Every ZIP file, video codec, 5G link and deep-space probe is designed with these limits in mind.

An analogy

Entropy is surprise. A weather forecast of 'sunny' in the desert carries little information because you expected it; 'snow' in the desert is very informative. Entropy is the average surprise of a source.

Bits as answers to yes/no questions

With M equally likely outcomes you need log₂M bits: 8 outcomes → 3 bits. When outcomes are unequal, ask about likely ones first — the average number of questions drops, and its minimum is exactly the entropy.

Compression and Huffman codes

Give short codewords to frequent symbols and long ones to rare symbols. Huffman's algorithm (repeatedly merge the two least likely symbols) builds an optimal prefix code. For p = {½, ¼, ⅛, ⅛} the codes 0, 10, 110, 111 give average length 1.75 bits = H exactly, because the probabilities are powers of ½.

Mutual information

I(X; Y) is how much knowing Y reduces uncertainty about X. It is symmetric, never negative, and zero only when X and Y are independent. For a channel, maximising I over input distributions gives the capacity C.

Channel coding theorem

Shannon proved that for any rate R < C there exist codes with arbitrarily small error probability, and none for R > C. Modern LDPC and polar codes (5G) operate within a fraction of a dB of this limit. For an AWGN channel the capacity is C = B log₂(1 + S/N) — covered in the next lesson.

Relative entropy (Kullback–Leibler divergence) and cross-entropy extend these ideas to machine learning loss functions.

Formulas

Worked example: Entropy of a sensor alphabet

Given: States with p = ½, ¼, ⅛, ⅛

Find: H.

Answer: H = 1.75 bits/symbol

Worked example: Huffman code

Given: Same source

Find: Code and efficiency.

Answer: L̄ = 1.75 bits, η = 100%

Worked example: BSC capacity

Given: Bit-flip probability ε = 0.1

Find: C.

Answer: C = 0.531 bits/use

Entropy of sources, text and a noisy channel

import math
from collections import Counter

def H(p):
    """Shannon entropy in bits."""
    return -sum(pi * math.log2(pi) for pi in p if pi > 0)

print(f"fair coin   H = {H([0.5, 0.5]):.4f} bits")
print(f"biased 0.9  H = {H([0.9, 0.1]):.4f} bits")
print(f"fair die    H = {H([1/6]*6):.4f} bits")

text = "ENGINEERING MATHEMATICS"
freq = Counter(text)
p = [c / len(text) for c in freq.values()]
print(f"text entropy = {H(p):.3f} bits/symbol vs {math.log2(len(freq)):.3f} max")

# Binary symmetric channel with crossover probability e
e = 0.1
Hb = H([e, 1 - e])
print(f"BSC e=0.1: capacity C = 1 - H(e) = {1 - Hb:.4f} bits/use")
# fair coin   H = 1.0000 bits
# biased 0.9  H = 0.4690 bits
# fair die    H = 2.5850 bits
# text entropy = 3.414 bits/symbol vs 3.585 max
# BSC e=0.1: capacity C = 1 - H(e) = 0.5310 bits/use

Uneven letter frequencies make text compressible (3.41 < 3.585 bits). A channel that flips 10% of bits can still carry 0.531 reliable bits per use — with good enough coding.

Common mistakes

Applications

Key takeaways

Going further