Information theory: uncertainty, codes, and communication

Discover how information can be measured, represented, compressed, sent through noisy channels, and recovered using carefully designed codes.

What information theory measures

Information theory studies the representation, compression, and communication of information. It gives mathematical tools for asking how uncertain an outcome is, how many bits are needed to encode it, and how reliably a message can be sent through a noisy channel.

In everyday speech, information often means meaningful facts. In information theory, the measure is tied to probabilities: an outcome that was highly expected provides less surprise than an unlikely outcome. The theory does not determine whether a message is true, useful, or important to a person.

A bit represents one binary choice. A sequence of bits can encode numbers, text, images, sound, and instructions. The encoding convention determines how the sequence is interpreted.

Entropy and uncertainty

Entropy measures uncertainty in a random variable. For outcomes with probabilities p₁, p₂, ..., Shannon entropy is:

H(X) = -Σ p(x) log₂ p(x)

Entropy is measured in bits when the logarithm uses base 2. A fair coin has two equally likely outcomes and entropy of one bit. A coin that lands heads 99% of the time has lower entropy because its result is more predictable.

Source	Outcome probabilities	Intuition
Fair coin	Heads 0.5, tails 0.5	Maximum uncertainty for two outcomes
Biased coin	Heads 0.9, tails 0.1	Less uncertainty; heads is more predictable
Fixed result	One outcome has probability 1	No uncertainty; entropy is zero

Entropy depends on a probability model. If the true distribution is different from the one assumed, a code based on that model may be inefficient. Entropy is an average quantity; a particular message may require more or fewer bits than the average.

Conditional entropy and shared information

Conditional entropy measures remaining uncertainty about one variable after another is known. If knowing today's weather greatly helps predict whether people carry umbrellas, the uncertainty about umbrellas given weather is lower than the uncertainty without that information.

Mutual information measures how much knowing one variable reduces uncertainty about another. Association does not establish a causal relationship: two variables can share information because of a third factor, selection effects, or the way data was collected.

Entropy as an average code length

Entropy provides a lower bound on the average number of bits needed to represent outcomes from a known source when using an ideal lossless code. If common outcomes are frequent and rare outcomes are uncommon, a variable-length code can approach that average more closely than a fixed-length code.

For a fair coin, each outcome carries one bit of uncertainty. For a biased coin, a code can use a short representation for the common result and a longer one for the rare result across a sequence of tosses. A single isolated outcome cannot always be assigned a fractional bit; the bound describes the average over many symbols and a coding scheme that preserves unambiguous decoding.

In practical compression, the source distribution is not always known. A format may estimate symbol frequencies from the data itself, store that model, or use adaptive coding that updates estimates while encoding. Model information adds overhead, especially for short messages, so a theoretically efficient code can lose to a simpler one on small inputs.

Surprise is relative to the model

The self-information of an outcome with probability p is -log₂(p) bits. A rare outcome is more surprising under that model. If the model assigns zero probability to an outcome that occurs, the formula is undefined and a code based on that model cannot represent it without adaptation or a fallback. Robust systems leave room for unexpected data.

Represent information with codes

A code maps messages or symbols into codewords. A fixed-length code uses the same number of bits for each symbol. If there are eight possible symbols, three bits are sufficient because 2³ = 8. Fixed-length codes are simple to parse but may use more bits than necessary when some symbols occur much more often.

A variable-length code gives common symbols shorter codewords and rare symbols longer ones. For unambiguous decoding, a code can be prefix-free: no codeword is the prefix of another. Then a receiver can identify a symbol as soon as its complete codeword is read.

Huffman coding constructs a prefix-free code from symbol frequencies and minimizes the average codeword length among binary prefix codes for the assumed symbol probabilities. The best code depends on the data model; a different source distribution can change which representation is compact.

Lossless compression

Lossless compression reduces the size of data while allowing exact recovery. It exploits patterns and redundancy. Run-length encoding stores repeated values as a value and count; it works well for long repeated runs but can enlarge data with few repetitions.

Dictionary methods store repeated sequences once and refer to them by codes. Entropy coding assigns shorter representations to common patterns. Many practical formats combine several techniques, along with headers that describe how to decode the result.

Worked example: run-length encoding

Consider the string AAAAABB. A simple run-length representation might encode it as A5B2: five As followed by two Bs. The original can be reconstructed exactly. For a string such as ABABAB, the encoding may be no smaller or even larger after delimiters and metadata are included.

Compression has overhead: the decoder needs to know the method and often the original length or dictionary. Real-world formats balance compression ratio, encoding time, decoding time, memory, and error recovery. A compact format that is too expensive to decode may be a poor choice for a constrained device.

There is no lossless compressor that makes every possible input shorter. If every fixed-length input could always be shortened, the number of possible shorter outputs would be insufficient to represent all inputs uniquely. Compression succeeds by taking advantage of structure or assumptions in typical data.

Lossy compression and rate-distortion

Lossy compression discards information to reduce size. Image, audio, and video codecs may remove details that are less noticeable under a chosen perceptual model. Once discarded, those details cannot be exactly reconstructed.

Rate-distortion theory studies the trade-off between the number of bits used and the distortion introduced. The acceptable balance depends on the task. A photograph displayed at small size may tolerate some loss; a medical image or scientific measurement may require preserving details that appear visually subtle.

Repeatedly saving lossy data can compound degradation. Keep an original when fidelity matters, choose quality settings based on use, and avoid treating compressed output as a precise record of the source.

Channels and noise

A communication channel carries symbols from sender to receiver. Noise can flip bits, erase symbols, delay packets, or otherwise alter the message. Channel capacity describes the maximum rate at which information can be sent with arbitrarily low error under a specified channel model.

Shannon's channel coding theorem says reliable communication is possible below channel capacity with an appropriate coding scheme, while rates above capacity cannot achieve arbitrarily small error under the model. The theorem is a fundamental limit, not a specific practical protocol.

Real systems combine coding with physical transmission, framing, checksums, acknowledgments, or retransmission. The right mechanism depends on whether errors can be corrected locally, whether retransmission is possible, and how much delay is acceptable.

Detecting and correcting errors

Redundancy can help detect or correct errors. A parity bit adds one bit chosen to make the count of ones even or odd. It can detect any odd number of bit flips in a block, but it cannot identify which bit changed and misses an even number of flips.

More powerful error-correcting codes add structured redundancy. A receiver can use it to identify and correct some errors without asking the sender to retransmit. Error detection plus retransmission is common when a reliable reverse channel exists; forward error correction is useful when retransmission is costly or impossible.

Checksums and cryptographic hashes also detect changes, but their purpose and guarantees differ from error-correcting codes. A checksum is designed to catch accidental corruption; a cryptographic message authentication code can help detect intentional tampering when its secret key is protected.

Applications and limitations

Information theory informs data compression, digital communication, coding theory, storage, machine learning, and language processing. It helps engineers understand lower bounds and trade-offs, but does not choose an application's objective or decide which information deserves protection.

Compression can remove repeated patterns but may also remove context if the representation is lossy. A compact encoding is not automatically secure; encrypted data can still reveal size and timing. Systems handling private information should consider metadata and communication patterns, not only message contents.

Probabilities used in entropy calculations reflect assumptions. If a model is trained on incomplete or outdated data, its estimates can be misleading. Explain what source and distribution a result assumes, especially when using information measures to compare people or decisions.

A compact glossary

Entropy

A measure of uncertainty in a random variable under a probability distribution.

Codeword

A sequence assigned to represent a symbol or message.

Prefix-free code

A code in which no codeword is a prefix of another.

Lossless compression

Encoding that permits exact reconstruction of the original data.

Channel capacity

A theoretical upper rate for reliable information transmission under a channel model.

Redundancy

Additional structure or information that can support compression, detection, or recovery.

References and further reading

1. Claude E. Shannon. “A Mathematical Theory of Communication.” Bell System Technical Journal, 1948. Article DOI.
2. David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Free online book.
3. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory, 2nd edition. Wiley, 2006. Publisher information.
4. Stanford Engineering Everywhere. Information Theory. Course materials.

Try it yourself

1. How many bits are needed for a fixed-length code with 16 equally likely symbols?
2. Encode CCCCDDDAA with the simple run-length method and explain why it may not suit every string.
3. Why does a parity bit detect some errors but not all?
4. Give an example where lossy compression is acceptable and one where it may not be.
5. Explain why a domain-specific probability model can make a code more efficient.

Remember: information theory quantifies uncertainty and limits; practical encodings balance size, reliability, computation, and purpose.