What outcomes can occur?
Define the alphabet.
A source produces symbols or events according to some probability distribution.
Side 32
Information
Theory
A study of how uncertainty becomes information and how messages survive compression and noise. Information theory strips communication down to source, code, channel and limits.
source→uncertainty→encoding→channel→recovery
06core ideas
05coding problems
05channel limits
32Side
Information measures resolved uncertainty.
An event carries more information when it was less expected before it occurred.
How expected is each outcome?
Assign probabilities.
Rare outcomes are more surprising and carry more self-information.
How surprising was this symbol?
−log₂ p(x)
Using base 2 expresses information in bits.
How uncertain is the source on average?
Expected information.
Entropy is highest when outcomes are spread more evenly across possibilities.
Does one variable reduce uncertainty about another?
Mutual information.
Shared structure can be quantified without requiring a linear relationship.
Shannon entropyH(X) = −Σ p(x) log₂ p(x)
A code maps messages into transmissible symbols.
Good coding exploits probability structure while preserving enough distinction for decoding.
Represent one source symbol or block.
Messages are mapped into sequences from a code alphabet.
No codeword begins another.
This property enables instantaneous unambiguous decoding.
Short codes for common symbols.
Variable-length coding approaches the entropy limit for known symbol probabilities.
Encode sequences together.
Longer blocks can exploit dependencies that single-symbol codes miss.
Recover the intended message.
Decoding quality depends on code design and channel corruption.
How many bits per source symbol?
Compression performance is compared against the theoretical source entropy.
Compression removes predictable structure.
If data contain repetition or unequal symbol probabilities, they can often be represented with fewer bits than a naive encoding uses.
Lossless
Goal
Recover exactly.
No information needed for reconstruction may be discarded.
Structure
Exploit redundancy.
Repeated patterns and predictable symbols are represented more compactly.
Limit
Entropy sets the asymptotic floor.
Average code length cannot be driven arbitrarily below source entropy without losing information.
Lossy
Goal
Preserve what matters.
Some detail is intentionally discarded to achieve much larger compression.
Distortion
Define acceptable error.
Compression quality depends on which differences the application can tolerate.
Trade-off
Rate versus distortion.
Rate–distortion theory studies the minimum bitrate needed for a chosen fidelity level.
A channel limits how much information can pass reliably.
The central question is not whether noise exists, but how much reliable communication remains possible despite it.
What symbols are transmitted?
Input probabilities can be chosen to match channel characteristics.
How does the channel corrupt symbols?
Channel models specify probabilities of output given input.
What is observed?
The receiver sees a noisy version of the transmitted signal.
Maximum reliable information rate.
Channel capacity is the highest rate at which error probability can be made arbitrarily small with suitable coding.
Finite resources constrain rate.
Physical channels impose limits through bandwidth, signal power and noise.
How much input uncertainty survives?
It quantifies how much observing the output tells us about the input.
Redundancy can be waste or protection.
Compression removes predictable redundancy; error correction deliberately adds structured redundancy so damaged messages can be reconstructed.
Parity
Add a simple consistency check.
Extra bits can detect some transmission errors without identifying all of them.
Distance
Keep valid codewords far apart.
Hamming distance determines how many bit errors a code can detect or correct.
Correction
Infer the most plausible original.
Structured codes make certain corruption patterns recoverable.
Trade-off
Protection costs rate.
More redundancy generally reduces net information throughput while improving robustness.
Coding theorem
Reliable communication has a limit.
Below channel capacity, suitable codes can drive error probability very low; above it, reliability cannot be guaranteed.
Information theory travels.
Its mathematics connects communication, inference, learning, thermodynamics, biology and computation.
Information and likelihood connect.
Measures such as KL divergence quantify how one probability distribution differs from another.
Loss functions often encode information ideas.
Cross-entropy is central to classification and probabilistic learning.
Sequences carry constrained information.
Genetic and signaling systems can be studied through entropy and mutual information.
Signals encode uncertain states.
Neural coding asks how much information activity carries about stimuli or actions.
Entropy concepts intersect carefully.
Statistical mechanics and information theory share mathematical structure while describing different physical and informational contexts.
Predictability shapes coding efficiency.
Natural language contains redundancy, enabling both compression and error recovery.
A Mathematical Theory of CommunicationClaude Shannon · foundational paper
Elements of Information TheoryCover & Thomas · standard reference
Information Theory, Inference, and Learning AlgorithmsDavid MacKay · broad connections
Information Theory: A Tutorial IntroductionJames Stone · accessible foundation