Count selections before interpreting messages

Shannon begins with a communication system containing a source, transmitter, channel, receiver and destination. The source chooses one message from a set. The transmitter turns that message into a signal suitable for the channel. Noise perturbs the signal. The receiver reconstructs a message for the destination. Telegraphy, speech, images and control signals differ physically, yet all can be treated as selections transformed under constraints.

The word selection is load-bearing. If a source can only emit a fixed sentence, receiving it removes no uncertainty. If it may emit one of eight equiprobable sentences, learning which was chosen resolves three binary choices. The meanings could be profound or trivial without changing that count. Conversely, a meaningless random string may be highly unpredictable and therefore costly to reproduce. Shannon’s information is a measure of resolved uncertainty within a specified ensemble, not a score for truth, usefulness or significance.

Hartley’s logarithm, then Shannon’s probabilities

Ralph Hartley’s 1928 precursor measured the information associated with choosing among s equally distinguishable alternatives as a logarithm of s.² Logarithms make independent choices add. Two choices among eight alternatives produce 64 joint possibilities; log₂ 8 + log₂ 8 = log₂ 64 = 6. The base fixes the unit. Base two gives bits.

Equal alternatives are only a beginning. Natural sources are uneven. In English, some letters and sequences occur far more often than others. Shannon seeks a function H of the probabilities that is continuous, grows with the number of equiprobable alternatives, and respects grouping a choice into successive choices. These conditions force the form H(X) = −K Σ pᵢ log pᵢ. With base-two logarithms and K equal to one, entropy is measured in bits.

The quantity −log₂ p(x) is the surprise or self-information of outcome x. A rare outcome resolves more uncertainty than a common one. Entropy averages this quantity over the source. It is therefore a property of a random variable under a probability model. It is not a substance stored inside a symbol, and it can change when the ensemble changes even if the observed symbol does not.

Why the grouping rule determines the formula

Imagine choosing one of four equiprobable cards. The choice can be made at once, or in two stages: first choose red versus blue, then choose one of the two cards of that colour. A coherent uncertainty measure must give the same total either way. One four-way choice has H(¼,¼,¼,¼). The staged version has one bit for the colour plus, with probability one, one further bit for the card. Both equal two bits.

Unequal groups reveal the probability weights. Suppose three outcomes have probabilities one half, one quarter and one quarter. Group the latter two. The first choice is between groups of probability one half each, which costs one bit. Only when the second group is selected, on half the trials, is another equally likely choice required. Average uncertainty is therefore 1 + ½×1 = 1.5 bits. The formula gives the same answer: −½log₂½ − ¼log₂¼ − ¼log₂¼ = 1.5.

Continuity prevents tiny probability changes from causing jumps in measured uncertainty. Monotonicity for equally likely alternatives ensures that more available choices do not count as less uncertainty. The grouping rule then links compound choices to weighted conditional choices. Shannon’s Appendix II proves that these requirements leave only a positive constant times −Σpᵢlogpᵢ. The proof earns a uniqueness claim relative to its axioms. It does not prove that every ordinary use of the word information must obey them.

The expectation form also explains why surprise alone is not a source measure. A distress message with probability one in a million carries about 19.9 bits of self-information when it occurs, but its contribution to average entropy is weighted by one millionth. Engineering a code for long-run traffic needs the average. Engineering a safety response to the rare event may care about consequences instead. Shannon’s measure does not turn low probability into low importance.

A source is a process, not a bag of letters

Shannon does not stop at independent symbols. He models a discrete source as a stochastic process, often a finite-state graph whose transition probabilities generate symbol sequences. The entropy rate is the growth rate of uncertainty across long sequences. Dependence matters. If every q must be followed by u, the second letter adds little uncertainty after the first. A code that ignores such structure wastes capacity.

For an ergodic source, sufficiently long sequences divide into a high-probability group with roughly 2ⁿᴴ members and a low-total-probability remainder. Modern texts call this the typical set. Shannon’s paper develops the essential counting idea: although all length-n strings may number 2ⁿ, most probability concentrates on exponentially fewer sequences when the entropy rate H is below one bit per symbol. Compression assigns short channel descriptions to this probable region.

Consider independent biased bits with probability 0.1 of a one. A length-100 block is not typically all zeros, even though all zeros is the single most probable exact block. Typical blocks contain roughly ten ones. There are many such blocks, and their individual probabilities are similar on a logarithmic scale. Together they hold nearly all probability. This corrects a common mistake: “typical” does not mean “most probable individual outcome”. It means belonging to a set whose total probability approaches one and whose log-size per symbol approaches the entropy.

The count supplies the compression argument. If roughly 2ⁿᴴ source blocks matter, then about nH binary digits can index them. Add a small overhead to mark or handle the atypical remainder. As n grows, the overhead divided by n vanishes. Attempt fewer than nH bits and there are too few binary names for the probable blocks without collisions. Achievability and converse meet at the entropy rate.

Ergodicity is doing real work. It lets long time samples exhibit the source’s ensemble statistics. A mixture of persistent regimes may be stationary but not ergodic. Imagine selecting one of two coins once, then tossing only that coin for ever. Across the ensemble, half the worlds use each coin; within one realised world, the long-run frequency reflects only the selected coin. Treating the mixture as one ergodic source can misstate which sequences are typical for an observed run.

Compression is probability made spatial

A noiseless channel has constraints on which signal sequences are possible and how long they take. Its capacity is the logarithmic growth rate of distinguishable signals per unit time. A source can be transmitted efficiently when its likely message sequences are matched to available channel sequences of suitable duration. This is source coding: remove predictable structure before spending scarce signalling resources.

Shannon’s Theorem 9 states, in his notation, that a source of entropy H bits per symbol can be encoded over a noiseless channel of capacity C bits per second at an average symbol rate arbitrarily close to C/H, and no higher rate is possible.³ The converse follows from an accounting constraint. A non-singular encoder must preserve the source’s distinctions, while the channel cannot carry more entropy per second than its capacity.

The achievable direction uses long blocks. Group many source symbols, order or partition their sequences by probability, and assign efficient channel strings to the high-probability group. As blocks grow, the overhead per source symbol shrinks. The price is delay and complexity. Shannon explicitly notes that ideal or nearly ideal encoding generally requires long delay at transmitter and receiver.

Non-singularity matters because compression is not licensed to merge messages that the destination must distinguish. A mapping that sends both A and B to the same codeword is short, but it has discarded the choice. Lossless source coding requires unique recovery. If approximation is permitted, the distortion rule becomes part of the problem. Shannon later treats fidelity criteria for continuous sources, but a lower bit count is meaningful only after specifying which distinctions may be surrendered.

Instantaneous prefix codes are one convenient construction, not the whole theorem. Their tree leaves obey a counting constraint: codewords of lengths lᵢ must fit without any word being a prefix of another. Short leaves occupy more of the tree, so they should be assigned to common outcomes. For ideal dyadic probabilities, lᵢ = −log₂pᵢ is an integer and expected length equals entropy. General probabilities create rounding overhead of less than one bit per coded symbol for a standard one-symbol construction. Blocking many symbols spreads this bounded overhead across the block.

The theorem is asymptotic and statistical. It does not claim that every individual file compresses to its entropy, because entropy belongs to a source distribution. Nor does it make a compressor that is best for every unknown source. A code optimised for one model can expand data drawn from another. The model, code and evaluation population form one claim; reporting only the compressed size hides the assumed ensemble.

Redundancy is not merely waste

For a source with maximum possible entropy H_max and actual entropy H, Shannon defines relative redundancy as 1 − H/Hmax. Redundancy makes compression possible because the source does not occupy all nominal sequences equally. Yet redundancy also supports reconstruction after damage. English spelling and syntax let a reader infer missing letters. A code designer may first compress away source redundancy, then add controlled channel redundancy whose pattern helps separate corrupted codewords.

These operations serve different models. Source coding exploits known dependence in messages. Channel coding introduces dependence in transmitted signals to resist a known confusion process. Calling all repetition waste overlooks this distinction. Unstructured repetition may be inefficient, but structured redundancy can enlarge distances between valid codewords and make noise detectable or correctable.

Noise creates equivocation, coding creates distance

A noisy channel is described by conditional probabilities linking input symbols or sequences to outputs. Send x; observe y. The receiver’s remaining uncertainty about what was sent is the conditional entropy H(X|Y), which Shannon calls equivocation. The information transmitted is I(X;Y) = H(X) − H(X|Y). Equivalent forms subtract output uncertainty due to noise from total output entropy, or compare marginal entropies with joint entropy.

This quantity is mutual. It measures statistical dependence between sent and received variables. If output perfectly identifies input, equivocation is zero and mutual information equals source entropy. If output is independent of input, observing it resolves nothing and mutual information is zero. A channel’s capacity is the maximum mutual information over permitted input distributions. The source must be matched to the channel because a non-uniform input may fail to exploit all distinguishable output patterns.

Shannon gives equivocation an operational interpretation through a correction channel. An observer sees both the original and recovered messages, notes the errors, and sends enough side information for the receiver to correct them. The necessary correction-channel rate is the conditional entropy H(X|Y). If that auxiliary capacity is smaller, some uncertainty about the input must remain. This turns a formal subtraction into a task: equivocation is the average extra description needed after the noisy observation is known.

Mutual information can therefore be read as saved description. Before seeing Y, the receiver faces H(X) bits of uncertainty on average. After seeing Y, it faces H(X|Y). Their difference is how much the observation helped. This account prevents two errors. Output entropy alone is not transmitted information because some output variation may be noise. Input entropy alone is not transmitted information because some distinctions may be lost.

The maximisation in capacity is equally important. Consider a noiseless channel with three permitted symbols but a source that emits only one of them. The physical alphabet can support log₂3 bits per use under an equal input distribution, but the constant source transmits zero. Capacity describes the best admissible use of the channel, not the rate of every configured source. Costs or power constraints restrict the distributions over which the maximum is taken.

The binary symmetric channel

The smallest useful noisy channel sends bits. Each bit flips independently with probability q. With equally likely input bits, output bits are also balanced. The remaining uncertainty about the input after seeing the output is the binary entropy H₂(q). Capacity per channel use is therefore C = 1 − H₂(q). At q equal to zero, capacity is one bit. At q equal to one half, output is independent of input and capacity is zero. A flip probability above one half is not worse than one half because the receiver can invert every output and obtain a channel with error 1 − q.

The theorem’s surprising half

A naive strategy repeats symbols until each is nearly certain. As the target error approaches zero, repetition grows and rate collapses. Shannon’s Theorem 11 says this collapse is not necessary. For a discrete source of entropy rate H and a discrete noisy channel of capacity C, if H is below C, there exist coding systems with arbitrarily small error frequency or equivocation.⁴ Above capacity, unresolved uncertainty cannot be driven below the excess rate.

The proof is an existence argument over long codebooks. Long input sequences form a high-probability set. Each possible transmitted sequence produces a cloud of likely received sequences. Select codewords so that their likely clouds overlap little. Shannon averages performance over a class of codes and shows the average error can be made small. If the average is small, at least one code is good. This establishes existence without identifying a convenient encoder or decoder.

Follow the counting more slowly. For a long duration T, a source of rate H produces about 2ᵀᴴ probable input messages. The channel’s received space also has an exponential scale. Conditioned on one sent codeword, noise spreads probability over a typical output cloud whose size is governed by conditional entropy. The number of distinguishable clouds that fit is controlled by the difference between total output uncertainty and noise uncertainty, which is mutual information. Maximising that difference yields capacity.

Random coding supplies a way to reason without first solving code construction. Draw many codewords according to a capacity-approaching input distribution. Decode a received block to the uniquely compatible codeword, or declare an error when none or several fit. Two bad events remain: the true sent-output pair may be atypical, and some competing codeword may also look compatible. The first probability shrinks for long blocks. The second stays small when the codebook rate is below the mutual-information exponent. Above it, competitors crowd the received space.

The converse is more than pessimism. Capacity was defined as the maximum mutual information per channel use. Processing cannot create additional dependence between the original message and the observation. If source uncertainty enters faster than the channel can preserve it, the excess remains as equivocation. Clever naming, a more powerful decoder or a different diagram cannot remove the accounting deficit without changing the channel, the input constraint or the permitted error.

Shannon’s original proof uses the typical-sequence language available in the paper and openly acknowledges practical shortcomings. It shows that good codes must exist in a class by bounding their average performance. The step from existence to usable construction became a long research programme involving algebraic codes, convolutional codes, turbo codes, low-density parity-check codes and polar codes. Those later techniques vindicate the boundary without being contained in the 1948 paper.

Three qualifications prevent overstatement. First, “arbitrarily small” is not “zero”. For any target error above zero, sufficiently long blocks can meet it under the theorem’s assumptions. Second, long blocks bring delay and computational demands. Third, the discrete theorem relies on a specified statistical channel. If errors have memory, drift adversarially or depend on the code, the memoryless calculation may not apply.

What the measure leaves outside

The most quoted boundary appears at the paper’s opening. Messages often have meaning, Shannon writes, but semantic aspects are irrelevant to the engineering problem as formulated. The sentence defines a scope, not a metaphysics. To reproduce a message selected at one point, an engineer needs a model of alternatives, probabilities, signals and distortions. Whether the selected sentence is true, valuable, understood or felt does not enter those equations.

Warren Weaver’s 1949 exposition made the distinction explicit: two messages, one meaningful and one nonsensical, may be equivalent in Shannon information, though engineering constraints can still matter to semantics.⁵ Bar-Hillel and Carnap later pursued a quantitative theory of semantic information using logical probability over possible worlds.⁶ That project answers another question. It does not refute channel capacity; it changes the object being measured.

Algorithmic information changes the object again. Kolmogorov’s 1965 approach asks for the length of a shortest effective description of an individual finite object.⁷ Shannon entropy averages uncertainty under a distribution; Kolmogorov complexity concerns one string relative to a description language, up to an additive constant. A thousand fair coin tosses have high expected Shannon entropy before observation. Once a particular string exists, its algorithmic complexity may be high if no short program generates it. A thousand zeros are improbable under the fair-coin model but have a short description. Neither measure is simply “the true amount of information” without a question and model.

The distinction also matters in studies of intelligence and consciousness. A system may emit text with high token entropy while lacking stable goals, world-directed understanding or experience. Another system may communicate a low-entropy alarm whose meaning is decisive to an agent. Shannon variables can measure dependence between a stimulus and a report, between neural states, or between components of a machine. Such results establish statistical constraint. They do not by themselves establish representation, agency, awareness or phenomenal character.

A claim about “information integration” requires more than adding entropy terms. One must specify the variables, interventions, grain and comparison. High mutual information may arise from a common driver without either subsystem controlling the other. Low mutual information may result from a poor measurement scale. If a theory identifies consciousness with an informational quantity, that identification is an additional bridge principle. Shannon’s equations can serve the calculation while leaving the bridge unproved.

Zero error is a different demand

Shannon’s noisy-channel theorem drives average error probability as low as desired below capacity. Some systems demand no confusion whatsoever. Shannon’s 1956 paper defines zero-error capacity as the supremum of rates achievable with exactly zero error and represents symbol confusability through a graph.⁸ Ordinary capacity may be positive while zero-error capacity is smaller or even zero. The difference matters whenever a rare error cannot be averaged away.

This later result is a correction to careless language, not a reversal of 1948. The original theorem says what it says: arbitrarily small error or equivocation for long codes below capacity. It does not license “perfectly reliable” if perfect means a finite code with no possible error. The 1956 question changes the admissible event from low probability to impossibility.

Continuous entropy needs a coordinate warning

Part III extends the theory from discrete symbols to continuous signals. Shannon defines differential entropy using a density, then states an important difference: unlike discrete entropy, it changes under coordinate transformation and may be negative. Information rates and capacities depend on differences of entropies in which the coordinate terms cancel. Treating differential entropy as an absolute count of bits in a real-valued sample is therefore unsafe.

A scaling example makes the warning visible. Let X be a continuous measurement in metres and define Y=100X in centimetres. No new physical distinction has appeared, yet differential entropy changes by log₂100 because the density is expressed against smaller coordinate units. Mutual information with another consistently transformed variable remains invariant when the Jacobian terms cancel. The absolute differential value is coordinate-relative; the transmitted dependence can still be well defined.

For a band-limited Gaussian channel with bandwidth W, signal power S and noise power N, the famous capacity form is C = W log₂(1 + S/N) bits per second under the stated model. The logarithm means power must grow exponentially for linear gains in rate at fixed bandwidth. The formula is not a universal law for every physical link. It assumes the channel and noise structure used in the derivation.

Why Gaussian noise? Among distributions with fixed variance, the Gaussian has maximum differential entropy. In a worst-case sense for the stated power constraint, it spreads uncertainty most broadly. Band limitation gives roughly 2WT real degrees of freedom over duration T. Signal and noise then occupy high-dimensional regions. Capacity compares the volume available to received signal-plus-noise with the volume consumed by noise. The familiar logarithm is the per-second growth rate of distinguishable regions.

Shannon says that the continuous treatment takes some liberties with limiting processes and avoids the full abstraction that complete rigour would demand. That candour sets an editorial boundary. The geometric derivation illuminates practical cases; it should not be presented as a measure-theoretic theorem covering every continuous process without qualifications. The paper’s strength includes its explicit statement of where generality was traded for a visible main thread.

Recover the theory without slogans

Compact glossary

From computable symbols to measurable uncertainty

Paper 0003 sits in Stage S0, First principles, Module S0M1, Computability, algorithms and information theory. Church and Turing established limits on uniform symbolic procedures. Shannon changes the axis. Given a source and channel that are already describable, he asks how statistical alternatives can be represented and transported. Computability says which transformations a procedure can perform; information theory prices distinctions under probability and noise.

The professional question this paper genuinely illuminates is: how should a system separate content volume from uncertainty, recoverability and channel limits? The diagnostic is to demand four ledgers before using the word information: the ensemble, the probability model, the channel law and the error criterion. Without them, an “information bottleneck” may refer to bandwidth, semantics, memory, attention or governance while measuring none precisely.

For machine systems, the distinction changes evaluation. Token count measures physical or economic volume. Cross-entropy evaluates a probability model against observed symbols. Mutual information can quantify dependence between defined variables. Task utility measures consequences under an objective. None substitutes automatically for another. A compressed representation may preserve predictive information while discarding rare safety-relevant distinctions. Capacity tells what a channel could preserve under a distribution, not which distinctions an institution ought to protect.

The original thesis of this companion is a boundary rule: before treating an information measure as evidence about intelligence, require an explicit account of selection, observer access and recoverable distinction. Selection identifies the alternatives and probabilities. Observer access identifies the conditioning variable. Recoverable distinction identifies the permitted error or distortion. If one ledger is missing, the number may still be computed, but its interpretation outruns the model.

The threshold Shannon actually earned

The paper’s lasting move is not the loose claim that everything is information. It is a disciplined conversion: selections become probability distributions, probability distributions become typical volumes, noisy transformations become conditional distributions, and reliable rate becomes a packing boundary. That conversion lets engineers prove both possibility and impossibility without interpreting each message.

The discipline survives only if its boundary survives. Meaning, truth, value and experience are not secretly measured by bits. A physical channel may violate the assumed noise model. A finite system may be unable to realise the existence proof. Exact zero error demands another capacity. Shannon’s theory remains powerful because it says less than the word “information” often suggests, and proves far more within that carefully chosen scope.