= Information theory
{wiki}
Information theory quantifies how much uncertainty messages contain, how efficiently they can be represented, and how reliably they can pass through a noisy <channel>. Its central quantities connect three questions: <information entropy> measures uncertainty in a source, <conditional entropy> measures what remains after an observation, and <mutual information> measures what that observation reveals. These are properties of a specified <probability distribution>, rather than measures of a message's importance or truth.
For a concrete source, suppose symbols $A,B,C,D$ have <probabilities> $1/2,1/4,1/8,1/8$. A fixed-length binary representation needs two <bits> per symbol. Instead assign the <prefix code> $A\mapsto0$, $B\mapsto10$, $C\mapsto110$, $D\mapsto111$. Reading from left to right gives an unambiguous decoding because no codeword begins another. The <expected value> of the length is
$$
\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac18\cdot3=\frac74.
$$
This saves an average of $1/4$ of a <bit> per symbol, or $12.5\%$ of the fixed-length representation, with no loss of symbols. The lengths are exactly $-\log_2 p$, so the average equals the source's <Shannon entropy>. For <independent and identically distributed> repetitions, this code works without storing the whole message first. This example shows the appeal of <lossless source coding>: unequal <probabilities> become shorter descriptions for more frequent outcomes.
\Image[/entropy-prefix-code.png]
{title=A four-symbol source reaches its entropy with a binary prefix code}
<Channel coding> addresses a different problem: errors during transmission. A shorter representation removes predictable structure; an error-correcting representation adds carefully chosen structure that helps recover corrupted symbols. <Shannon's source coding theorem> and the <Shannon second coding theorem> identify limits for these respective tasks under their hypotheses. The beauty is that source details and hardware details can meet through a small number of mathematical quantities, notably <information entropy> and <channel capacity>.
Claude E. Shannon's \i[A Mathematical Theory of Communication] appeared in the \i[Bell System Technical Journal] in July and October 1948. Its introduction separates the engineering problem of reproducing messages from their semantic meaning; subsequent sections develop probabilistic source models, noiseless coding, and transmission with noise. It also acknowledges earlier work by Harry Nyquist and Ralph Hartley.<A Mathematical Theory of Communication by Claude Shannon>{ref}
Back to article page
