Can the entropy be less than one bit per symbol?

Yes. It is an average information amount. Coding sequences allows a fractional average even though each complete stored bit is indivisible.

Does the theorem supply the best practical compressor?

No. It establishes limits and achievability under assumptions. Efficient code construction and accurate source modeling are additional problems.

Does dependence between symbols matter?

Yes. Predictable relationships can reduce entropy rate below the entropy calculated from single-symbol frequencies alone.

AI Glossary / MLOps and deployment / Intermediate

Shannon's source coding theorem

Definition

Shannon's source coding theorem establishes entropy as the fundamental rate limit for lossless compression under an appropriate source model. For independent, identically distributed discrete symbols, long-block coding can make the average number of bits per symbol approach the source entropy, but uniquely decodable lossless coding cannot beat that average limit.

What it means

Entropy measures average uncertainty under a probability distribution. A compressor can exploit predictability, assigning shorter descriptions to likely outcomes, while preserving enough information to distinguish every message it must decode.

The theorem concerns a statistical source and a specified coding setting. It does not claim that every individual file has the same compression limit, or that no particular file can be very small. It also differs from the noisy-channel coding theorem, which concerns reliable communication despite transmission errors.

How it works

For a discrete symbol X with probabilities p(x), entropy is H(X)=−Σp(x)log2 p(x). In binary uniquely decodable coding, the expected codeword length is at least H(X). Suitable prefix codes can approach this bound by coding groups of symbols.

For independent symbols grouped into blocks of n, block entropy is nH(X). A construction can achieve an expected length below nH(X)+1 bits per block. Dividing by n gives an overhead below 1/n bit per source symbol, before practical format costs.

For sources with dependence, the relevant asymptotic quantity is an entropy rate under suitable assumptions. Using only individual-symbol frequencies can miss predictability in relationships between successive symbols. The theorem identifies a limit; practical modeling, buffering and implementation determine how closely a real system approaches it.

Three practical examples

1. Sensor compression planning: strongly predictable state values may contain fewer bits of uncertainty than their fixed-width storage representation suggests. A source model helps estimate the opportunity before implementing a codec.

2. AI-based compression research: a predictive model assigns probabilities to data, and an entropy coder converts those probabilities into a description. Better predictive fit can reduce description length, subject to model and deployment costs.

3. Evaluating compression claims: a team checks whether a reported result includes all information needed for recovery and whether it generalizes to the stated source. A tiny description of a special file is not evidence of universal compression below entropy.

Think of it this way

Think of a quiz where some answers are easy to predict. A concise answer sheet can reserve longer descriptions for surprises and shorter ones for expected answers. On average, uncertainty determines how much information remains to be supplied.

The analogy stops at meaning: entropy is calculated from probabilities, not from intellectual difficulty or usefulness. A meaningful message can be statistically predictable, and apparently meaningless random data can have high entropy.

Worked example

Consider independent binary symbols with P(0)=0.9 and P(1)=0.1. Their entropy is −0.9log2(0.9)−0.1log2(0.1), approximately 0.469 bits per symbol.

A one-symbol binary prefix code still needs a bit for each of the two possibilities, so it uses one bit per symbol. The entropy is lower because long sequences can exploit the imbalance more effectively.

For blocks of ten independent symbols, the entropy is approximately 4.690 bits per block. A suitable prefix construction has expected block length less than 5.690 bits, or less than 0.569 bits per original symbol. For blocks of one hundred, the analogous upper bound is less than 0.479 bits per symbol.

These are existence bounds on expected lengths, not guaranteed lengths for every block or measurements of a particular compressor. A rare block may require many more bits. Headers, the probability model and practical constraints can add overhead. The larger block also increases the number of possible block values dramatically, so a literal table-based implementation may be impractical even though the theorem demonstrates the limit.

Illustrative case study

Fictional case: SignalLedger estimates compression potential from a stream in which one state is much more frequent than another. A prototype using one-bit state codes fails to approach the calculated entropy, and the team initially suspects the theory is wrong.

Review shows that the prototype encodes each symbol independently with a whole bit. The team explores sequence-aware coding and measures full-file size, including metadata. It also discovers that consecutive states are correlated, so an independent-symbol entropy estimate is not the final limit for the richer source model.

This fictional case distinguishes a theorem's assumptions, a model's statistical detail and an implementation's coding choices.

Common misconceptions and mistakes

“No file can compress below its empirical entropy.” The theorem is about specified sources and coding criteria. A particular file can have exploitable structure absent from a simple frequency estimate.

“Every file can become shorter.” A reversible code cannot map every possible input of a fixed length into a shorter distinct binary string. Some inputs must remain long or expand.

“Entropy measures semantic value.” It measures statistical uncertainty. It does not assess truth, importance or business relevance.

“Lossy compression violates the theorem.” Lossy coding changes the requirement by allowing reconstruction error. Its limits are studied using tools such as rate - distortion theory.

Business use

Use source coding theory to frame realistic expectations, compare modeling approaches and question incomplete accounting. Estimate uncertainty at the level of structure the proposed compressor actually uses, and validate the estimate on representative data rather than treating a training sample as the production distribution.

For model-based compression, include model storage or distribution, inference time, precision and synchronization requirements. Compare achieved rates with a stated baseline and reconstruction guarantee. A slightly larger representation can be operationally preferable when it improves decoding speed, random access or maintainability.

Check your understanding

A binary source has entropy 0.469 bits per symbol, but each symbol is stored in one bit. Does this contradict the source coding theorem?

Answer: No. The theorem permits coding approaches whose average rate approaches entropy over longer sequences. A one-symbol fixed-width representation need not attain that limit.

Related terms

Learn next

Calculate entropy for a biased binary source, then compare one-symbol and block-based codes. Study conditional entropy to understand dependence, and distinguish variable-length lossless coding from fixed-rate schemes that allow a small probability of decoding failure.

Sources

Primary foundation: Claude E. Shannon, “A Mathematical Theory of Communication,” Section 9 on the noiseless-channel theorem: https://www.princeton.edu/~wbialek/rome/refs/shannon_48.pdf . The biased-source calculations and fictional development case are original illustrations of the standard lossless block-coding interpretation.

Previous: Shannon - Fano - Elias coding Next: Shape