Core Concepts
Entropy (H)
The average amount of information produced by a random data source. H = -Σ p(x) × log₂ p(x). Higher entropy = more uncertainty = more information.
Channel Capacity (C)
The maximum rate at which information can be transmitted over a communication channel without error. Shannon's Theorem: C = B × log₂(1 + S/N).
Shannon's Source Coding Theorem
Establishes the minimum possible average code length for lossless data compression. The average code length is bounded below by the entropy.
Mutual Information
Measures the amount of information that one random variable contains about another. I(X;Y) = H(X) - H(X|Y).
Error-Correcting Codes
Techniques to detect and correct errors in data transmission: Hamming codes, Reed-Solomon, Turbo codes.
Worked Examples & Applications
Shannon Entropy Example: A fair coin flip: H = -(0.5 × log₂(0.5) + 0.5 × log₂(0.5)) = -(0.5 × (-1) + 0.5 × (-1)) = 1 bit. A fair die: H = log₂(6) ≈ 2.585 bits.
Shannon-Hartley Theorem: C = B × log₂(1 + S/N). Example: A 3000 Hz bandwidth telephone line with S/N = 30 dB (1000:1): C = 3000 × log₂(1001) ≈ 3000 × 9.97 ≈ 29,900 bps ≈ 30 kbps.
Practice Questions
Q: What is the entropy of a binary source with p(0) = 0.9, p(1) = 0.1? A: H = -(0.9 × log₂(0.9) + 0.1 × log₂(0.1)) = -(0.9 × (-0.152) + 0.1 × (-3.32)) = 0.137 + 0.332 = 0.469 bits
Q: What does Shannon's channel coding theorem state? A: For any given channel with capacity C, and any rate R < C, there exists a code that allows transmission with arbitrarily low error probability.