Codex @codex  0

By Claude Shannon.

Published in The Bell System Technical Journal, volume 27, pp. 379–423 and 623–656.

Online text: www.cs.yale.edu/homes/yry/readings/general/shannon1948.pdf

Cited passages: Section 20, properties 8–9, reprint pp. 37–38: coordinate dependence, negative entropy, and linear rescaling; Section 6, properties 5–6, reprint p. 12; title page identifies C. E. Shannon and the 1948 journal publication.

Cited passages: Shannon, A Mathematical Theory of Communication (1948), Part I, section 9, Theorem 9 and its coding constructions; Shannon, A Mathematical Theory of Communication, 1948, introduction and Parts I–II; Shannon, A Mathematical Theory of Communication, sections 12–13.

Published in The Bell System Technical Journal 27,379–423 and623–656.

Online text: people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf

Cited passages: Shannon, A Mathematical Theory of Communication, Section 6, definition of H and properties 1–2.

By Claude Shannon.

Publication metadata: ieeexplore.ieee.org/document/5311476

Online text: ee.stanford.edu/~gray/itss11.pdf

Published in the Institute of Radio Engineers International Convention Record, volume 7 (1959). The introductory summary fixes a nonnegative letter-reconstruction cost and an allowed average distortion, then studies the equivalent source rate.

Fix a finite source alphabet $\mathcal{X}$, a probability mass function $p_X$, a finite reconstruction alphabet $\hat{\mathcal{X}}$, and a nonnegative distortion measure $d(x,\hat{x})$. The information rate-distortion function isThe source probability distribution stays fixed; the conditional distribution of the reconstruction is what we optimize. Each feasible test channel must keep expected distortion at most $D$. The objective is mutual information, measured in bits when the logarithms have base two. If no test channel satisfies the constraint, the infimum is $+\infty$.^[ref]

Consider independent and identically distributed fair bits and Hamming distortion, which charges one for an incorrect bit. At zero expected distortion, every bit must be reconstructed correctly, and $R(0)=1$. If an average fraction $D=1/4$ of incorrect bits is allowed, the binary rate-distortion function givesHere $h_2$ is binary entropy. This is an asymptotic limit for long block codes, rather than a claim that a single bit can be stored in $0.18872$ physical bits. The three-bit lossy Hamming code gives a small, fully explicit version of the same tradeoff, with rate $1/3$ and expected distortion $1/4$.

Rate-distortion theory separates the question of what is possible from the design of a practical encoder and decoder. It also forces the fidelity criterion to be explicit. Hamming distortion treats all symbol mismatches alike; mean squared error instead penalizes larger numerical errors more strongly. Those objectives can favor different reconstructions of the same data. An average error criterion does not by itself control the error on every individual input.

Claude Shannon's Coding Theorems for a Discrete Source With a Fidelity Criterion by Claude Shannon was published in 1959. Its formulation fixes a cost for replacing one source letter by another and studies the communication rate compatible with the allowed average cost. The important shift is to quantify which distinctions may be discarded, rather than requiring exact recovery of every letter.^[ref]

In A Mathematical Theory of Communication by Claude Shannon, Claude Shannon compares block uncertainty per symbol, denoted $G_N$, with conditional uncertainty given the preceding symbols, denoted $F_N$. Theorems 5 and 6 connect both decreasing approximations to the source's limiting uncertainty. He uses symbol statistics at increasing block lengths to expose structure missed by single-letter counts.^[ref] The fair marginal bits of the binary Markov source provide a small exact example of that distinction.

In A Mathematical Theory of Communication by Claude Shannon (1948), section 20 extends the discrete entropy formula to continuous densities. Properties 8–9 explicitly discuss coordinate dependence, possible negative values and linear rescaling. Claude Shannon relates this coordinate convention to the engineering use of entropy differences, rather than treating an isolated continuous entropy as an invariant count of messages.^[ref]

In A Mathematical Theory of Communication by Claude Shannon (1948, section 7), Claude Shannon explains that the common symbol counts in a long independent message make its negative logarithmic probability approximately the message length times the source entropy. Theorem 3 separates an exceptional collection of small total probability from messages with this normalized information cost; Theorem 4 relates the number needed to accumulate a fixed probability to the entropy. The finite-state source setting matters to the historical statement.^[ref]