Classical Information Review

Classical information theory explains how predictable data can be compressed and how messages can survive a noisy channel. These are different tasks: compression removes redundancy, while error correction adds carefully chosen redundancy. This review develops both for finite alphabets, independent identically distributed (iid) sources, and discrete memoryless channels, then explains what changes when secrecy or computational cost matters.

Helpful background. Probability spaces and conditional probability supply the distributions used below. The mathematical derivations of entropy and relative entropy give a fuller account of the information measures.

Sources, Alphabets, and Distributions

Let a discrete source produce a random variable $X$ taking values in a finite alphabet $\mathcal X$ with probability mass function

$$p_X(x)\ge 0, \qquad \sum_{x\in\mathcal X}p_X(x)=1.$$

The alphabet lists possible symbols; the distribution gives their ensemble frequencies. Neither specifies what the symbols mean. A binary alphabet could encode logical values, detector clicks, source labels, error flags, or decisions. Semantic importance must enter through the task or loss function rather than being inferred from probability alone.

For an iid source block $X^n=(X_1,\ldots,X_n)$,

$$p_{X^n}(x^n) = \prod_{i=1}^{n}p_X(x_i).$$

This factorization is an assumption. A stationary source need not be independent, a device can drift, and a channel can have memory. When correlations matter, reporting only the one-symbol marginal $p_X$ discards operationally relevant structure.

The realized sequence $x^n$ is not the distribution $p_{X^n}$. Entropy is an ensemble average, while the information content $-\log_2p_{X^n}(x^n)$ varies from one realization to another. Likewise, an empirical frequency observed in one finite block is an estimator of a source parameter, not automatically the parameter itself.

Entropy, Divergence, and Mutual Information

This page uses base-$2$ logarithms, so entropies and divergences are reported in bits, with $0\log_2 0=0$ by continuity. For $X\sim p_X$, the Shannon entropy is

$$H(X) = -\sum_{x\in\mathcal X}p_X(x)\log_2p_X(x).$$

For a pair $(X,Y)$, the compact dictionary is

$$H(X,Y) = -\sum_{x,y}p_{XY}(x,y)\log_2p_{XY}(x,y),$$ $$H(Y\mid X) = \sum_xp_X(x)H(Y\mid X=x),$$

and

$$\begin{aligned} I(X{:}Y) &=H(X)+H(Y)-H(X,Y)\\ &=H(Y)-H(Y\mid X). \end{aligned}$$

Entropy measures average uncertainty under a declared ensemble. Conditional entropy measures the uncertainty remaining after the conditioning variable is known. Mutual information measures statistical dependence: it is zero exactly when $P_{XY}=P_XP_Y$ for finite alphabets. It does not by itself establish causation, usefulness, secrecy, or an achievable communication rate.

For distributions $P=(p_x)$ and $Q=(q_x)$ on the same alphabet,

$$D(P\|Q) = \sum_{x:p_x>0}p_x\log_2\frac{p_x}{q_x}.$$

If $p_x>0$ for some $x$ with $q_x=0$, then $D(P\|Q)=+\infty$. The divergence is directed and is not a metric. The identity

$$I(X{:}Y) = D\!\left(P_{XY}\middle\|P_XP_Y\right)$$

connects dependence to distinguishability from the product model. For example, a perfectly copied random bit has $I(X:Y)=H(X)$, while independent bits have zero mutual information. These statements concern correlation, not a causal direction.

Stochastic Channels and Data Processing

A finite classical channel is a conditional distribution $W(y\mid x)$ from an input alphabet $\mathcal X$ to an output alphabet $\mathcal Y$. This page writes inputs as columns and outputs as rows, so every input column is normalized:

$$\sum_{y\in\mathcal Y}W(y\mid x)=1.$$

For an input law $p_X$, the channel induces

$$p_{XY}(x,y)=p_X(x)W(y\mid x),$$

and

$$p_Y(y)=\sum_xW(y\mid x)p_X(x).$$

The conditional law is not a complete communication system. It does not specify the input distribution, encoder, decoder, blocklength, assistance, cost, or criterion for success.

If $X\to Y\to Z$ is a Markov chain, so that $Z$ is produced from $Y$ without additional access to $X$, then the data-processing inequality gives

$$I(X{:}Z)\le I(X{:}Y).$$

Postprocessing can preserve or discard information about $X$, but it cannot create dependence on $X$ that was absent from $Y$. This statement assumes the declared Markov structure; hidden side information can invalidate an informal application of the inequality.

Worked example: a binary symmetric channel

Take a uniform binary input and a binary symmetric channel with crossover probability $\epsilon=0.11$. With rows indexed by output $y$ and columns by input $x$,

$$W = \begin{pmatrix} 0.89&0.11\\ 0.11&0.89 \end{pmatrix}.$$

Each column sums to one. Symmetry and the uniform input make $Y$ uniform, so $H(Y)=1$ bit. Given either input, the output flips with probability $0.11$, hence

$$H(Y\mid X) = h_2(0.11) = 0.499915958 \quad\text{bits},$$

where

$$h_2(p) = -p\log_2p-(1-p)\log_2(1-p).$$

Therefore

$$\begin{aligned} I(X{:}Y) &=H(Y)-H(Y\mid X)\\ &=1-h_2(0.11)\\ &=0.500084042 \quad\text{bits per channel use}. \end{aligned}$$

For a BSC, symmetry makes the uniform input capacity achieving, so this value also equals

$$C=\max_{p_X}I(X{:}Y).$$

The capacity is an optimized asymptotic limit for this memoryless channel. It is not an achieved finite-block rate, a gate rate, or hardware throughput.

Source Coding and Compression

A lossless source code represents a source block by a bit string from which the decoder can reconstruct that block. For a one-symbol binary prefix code with codeword lengths $\ell(x)$, the Kraft inequality requires

$$\sum_x2^{-\ell(x)}\le 1,$$

and the mean length is

$$L=\sum_xp_X(x)\ell(x).$$

For any binary prefix code, $L\ge H(X)$. Conversely, one can choose integer lengths $\ell(x)=\lceil-\log_2p_X(x)\rceil$ on the source support and construct a prefix code with $L<H(X)+1$. Coding blocks of $n$ iid symbols gives $H(X)\le L_n/n<H(X)+1/n$. These are expected lengths for lossless variable-length coding, not the lengths of every realized string. The code must also be known to the decoder.

Compression changes the representation of source data. It does not protect the resulting bits against a noisy channel. Conversely, adding redundancy for error correction generally increases the transmitted blocklength. Keeping these two operations separate prevents the common claim that “coding” must either always compress or always expand data.

Worked example: a biased Bernoulli source

Let $p_X(1)=0.1$ and $p_X(0)=0.9$. Then

$$\begin{aligned} H(X) &=h_2(0.1)\\ &=0.468995594 \quad\text{bits per source symbol}. \end{aligned}$$

For $10{,}000$ iid symbols, the first-order entropy benchmark is

$$10{,}000H(X) = 4{,}689.955936 \approx 4{,}690 \quad\text{bits}.$$

This can be compared with the $10{,}000$ bits needed by the raw one-bit-per-symbol representation. It is not the encoded length of every realized block. A binary single-symbol prefix code still needs one bit for each of the two symbols and therefore has mean length one bit per symbol. Approaching the entropy requires block or arithmetic-style coding, together with finite-block, model, header, and implementation overhead.

Channel Coding and Reliable Decoding

A channel code uses redundancy to convey one of $M$ messages through $n$ channel uses. For a discrete memoryless channel,

$$W^n(y^n\mid x^n) = \prod_{i=1}^{n}W(y_i\mid x_i).$$

An encoder maps each message $m\in\{1,\ldots,M\}$ to a codeword $x^n(m)$. A decoder maps the received word $y^n$ to an estimate $\widehat m$ or, when allowed, an erasure or abort. If $M=2^k$, the code rate is

$$R = \frac{k}{n} = \frac{\log_2M}{n} \quad\text{message bits per channel use}.$$

For a discrete memoryless channel, the Shannon capacity is

$$C = \max_{p_X}I(X{:}Y) \quad\text{bits per channel use}.$$

In its asymptotic form, the noisy-channel coding theorem separates rates below capacity, for which sequences of codes can drive error toward zero, from rates above capacity, which are not reliably achievable under the theorem’s assumptions. The theorem does not select a practical code, fix a decoder’s computational cost, or give the latency and throughput of a finite device.

Source and channel rates use different denominators. A source code reports bits per source symbol; a channel code reports message bits per channel use. Connecting them requires an explicit interface. Under the assumptions of a source–channel separation theorem, one may compress and then protect the compressed bits, but those assumptions and both blocklengths must be declared rather than hidden in a single “compression rate.”

Finite Blocks, Error Criteria, and Rates

For $M$ equiprobable messages, the average decoding error is

$$P_{\mathrm e}^{\mathrm{avg}} := \frac1M \sum_{m=1}^{M} \Pr\!\left[\widehat M\ne m\mid M=m\right],$$

whereas the maximal error is

$$P_{\mathrm e}^{\max} := \max_m \Pr\!\left[\widehat M\ne m\mid M=m\right].$$

Always $P_{\mathrm e}^{\mathrm{avg}}\le P_{\mathrm e}^{\max}$ for equiprobable messages. A code can protect common or easy messages well while leaving one message much less reliable, so an unqualified “error rate” is insufficient. A one-shot or selected finite-block result must also remain distinct from an asymptotic sequence-of-codes claim.

For a BSC with fixed crossover $0<p<1/2$, the normal approximation to the best achievable rate at blocklength $n$ and fixed error target $0<\varepsilon<1$ is

$$R^*(n,\varepsilon) =C-\sqrt{\frac{V}{n}}\,Q^{-1}(\varepsilon) +O\!\left(\frac{\log n}{n}\right),$$

where $Q$ is the upper tail probability of a standard normal variable and

$$V=p(1-p)\left[\log_2\frac{1-p}{p}\right]^2$$

is the channel dispersion. For $p=0.11$, $n=1000$, and $\varepsilon=0.01$, the first two terms give approximately $0.431$ message bits per channel use, below the capacity $0.5001$. This estimates the optimal finite-block rate; it neither constructs a code nor guarantees that a chosen practical code achieves the estimate. Polyanskiy, Poor, and Verdú develop the bounds and asymptotics behind this approximation.

To convert a rate into delivered bits per second, we also need the channel-use rate, decoding time, and any retries or discarded blocks. Capacity, finite-block coding performance, and hardware throughput answer different questions.

Keys, Randomness, and Security Boundaries

A key can have high Shannon entropy and still be known to an adversary. Security requires a relation among the key, adversarial information, protocol transcript, and intended ideal resource—not merely a marginal distribution for $K$.

For a classical key $K$ and adversarial record $E$, marginal uniformity is represented by $P_K=U_K$. Independence would additionally require $P_{KE}=P_KP_E$. A useful classical distance from an ideal uniform independent key is

$$d_{\mathrm{TV}}\!\left(P_{KE},U_KP_E\right) := \frac12 \sum_{k,e} \left| P_{KE}(k,e)-U_K(k)P_E(e) \right|.$$

If this distance is large, an adversary can distinguish the real joint distribution from the ideal resource even when $H(K)$ is maximal. A nominal key length also says nothing by itself about freshness, authentication, leakage during reconciliation, implementation compromise, or safe composition with another protocol.

The one-time pad illustrates the boundary sharply: information-theoretic secrecy needs a uniform secret key independent of the message and adversary, at least as long as the message, and never reused. Quantum key distribution develops security against quantum side information, finite-key effects, and authentication assumptions.

Comparing classical and quantum computations

A comparison must ask both algorithms to solve the same problem with comparable input access and accuracy. Producing an entire vector, estimating one scalar, and drawing one sample are different tasks. An already prepared quantum state and an explicit classical data file also expose different information; preparing the state may itself be costly.

For example, an algorithm that processes an amplitude-encoded vector using few gates need not load an arbitrary classical vector equally quickly. Include the state or data-structure construction, repeated preparations, measurements, and classical processing when assessing total cost. A separation in oracle queries remains a result about that oracle model until these other costs have been analyzed.

Continue to quantum oracles for access models, query complexity for query bounds, and algorithmic benchmarking for comparisons of complete implementations. Communication with quantum systems develops the quantum counterparts of the channel-coding questions above.

Exercises

1. Decoding an erased bit

Let $P_X(1)=0.3$. Use a binary erasure channel with erasure probability $\delta=0.2$, the identity encoder, blocklength one, output alphabet $\{0,1,?\}$, and a decoder that maps an erasure to $0$. Write the channel probabilities and compute the average and maximal decoding errors under this source distribution.

Solution

The source alphabet is $\mathcal X=\{0,1\}$ with

$$P_X(0)=0.7, \qquad P_X(1)=0.3.$$

With outputs ordered as $0,1,?$ and inputs ordered as $0,1$, the nonzero channel probabilities are

$$W(0\mid0)=W(1\mid1)=0.8, \qquad W(?\mid0)=W(?\mid1)=0.2,$$

with $W(1\mid0)=W(0\mid1)=0$. For each fixed input $x$, summing over the three outputs gives one, consistent with the page’s output-row/input-column orientation. The identity encoder sends $x$ itself in one channel use. The decoder is

$$g(0)=0, \qquad g(1)=1, \qquad g(?)=0.$$

If $X=0$, both a received $0$ and an erasure decode to $0$, so the conditional error is zero. If $X=1$, an erasure is decoded incorrectly, so the conditional error is $0.2$. Therefore

$$P_{\mathrm e}^{\mathrm{avg}} = 0.7(0)+0.3(0.2) = 0.06,$$

and

$$P_{\mathrm e}^{\max} = \max\{0,0.2\} = 0.2.$$

The nominal uncoded rate is one source symbol per channel use, but that statement is meaningful only with the declared blocklength, decoder, source distribution, and error criterion.

2. Relative entropy and support

For $P=(1,0)$ and $Q=(1/2,1/2)$, compute $H(P)$, $H(Q)$, $D(P\|Q)$, and $D(Q\|P)$ using base-$2$ logarithms.

Solution

Using $0\log_2 0=0$,

$$H(P) = -1\log_2 1-0\log_2 0 = 0,$$

whereas

$$H(Q) = -2\left(\frac12\log_2\frac12\right) = 1 \quad\text{bit}.$$

Only the first component contributes to $D(P\|Q)$:

$$D(P\|Q) = 1\log_2\frac{1}{1/2} = 1 \quad\text{bit}.$$

For the reverse divergence, $Q$ assigns positive probability $1/2$ to the second symbol while $P$ assigns it probability zero. The support condition therefore gives

$$D(Q\|P)=+\infty.$$

The last result is not obtained by treating division by zero informally; it follows from the extended-value definition when the support of the first distribution is not contained in the support of the second.

3. Exact dyadic prefix code

For symbol probabilities

$$p=\left(\frac12,\frac14,\frac18,\frac18\right),$$

consider the codewords $0$, $10$, $110$, and $111$. Check directly that no word is a prefix of another, calculate the Kraft sum, and compare mean length with entropy. Does a Kraft sum at most one prove that an arbitrary supplied code is prefix free?

Solution

The codeword lengths are $(1,2,3,3)$. The Kraft sum is

$$2^{-1}+2^{-2}+2^{-3}+2^{-3} = \frac12+\frac14+\frac18+\frac18 = 1.$$

The displayed code is prefix free: no listed codeword is the beginning of another. Its mean length is

$$\begin{aligned} L &=\frac12(1)+\frac14(2)+\frac18(3)+\frac18(3)\\ &=\frac74\\ &=1.75 \quad\text{bits per symbol}. \end{aligned}$$

Because each probability is dyadic and $\ell_i=-\log_2p_i$, the entropy is

$$H(X) = \sum_i p_i\ell_i = 1.75 \quad\text{bits per symbol}.$$

Exact equality is possible here because the ideal lengths are integers satisfying Kraft equality. A general one-symbol distribution has noninteger ideal lengths and need not admit $L=H(X)$.

The Kraft inequality guarantees that some prefix code with the specified lengths exists. It does not prove that a particular set of strings is prefix free: the strings $0$ and $00$ have Kraft sum $1/2+1/4=3/4$, yet the first is a prefix of the second.

4. Three-fold repetition at finite blocklength

Send one message bit through three independent uses of a BSC with crossover probability $0.1$, and decode by majority vote. Compute the block error and code rate, then compare the result with uncoded transmission.

Solution

Majority decoding fails when exactly two or all three channel outputs flip. Independence gives

$$\begin{aligned} P_{\mathrm e} &=\binom32(0.1)^2(0.9)+(0.1)^3\\ &=3(0.01)(0.9)+0.001\\ &=0.028. \end{aligned}$$

One message bit uses three channel uses, so

$$R=\frac13 \quad\text{message bit per channel use}.$$

Uncoded transmission has error $0.1$ at rate one message bit per channel use. Repetition lowers the error to $0.028$ but also lowers the rate by a factor of three and increases latency. This one finite code does not establish capacity or an asymptotic optimum.

5. Cascaded BSC and data processing

Cascade BSCs with crossover probabilities $0.1$ and $0.2$. For a uniform input, compute the effective crossover and the mutual information before and after the second channel.

Solution

The final bit differs from the input exactly when one of the two channels flips and the other does not. Thus

$$\epsilon_{\mathrm{eff}} = 0.1(1-0.2)+(1-0.1)0.2 = 0.26.$$

For a uniform input to a BSC,

$$I=1-h_2(\epsilon).$$

After the first channel,

$$I(X{:}Y) = 1-h_2(0.1) = 0.531004406 \quad\text{bits}.$$

After the second channel,

$$I(X{:}Z) = 1-h_2(0.26) = 0.173253628 \quad\text{bits}.$$

The variables form the Markov chain $X\to Y\to Z$, and the numerical result explicitly satisfies

$$I(X{:}Z)\le I(X{:}Y).$$

The second channel has discarded information about $X$; it has not created a new observation of $X$.

6. Uniform but completely leaked key

Let $K$ be a uniform bit and let an adversary hold $E=K$. Compute $H(K)$ and the total-variation distance from the ideal independent distribution $U_KP_E$.

Solution

The marginal key distribution is uniform, so

$$H(K)=1 \quad\text{bit}.$$

The real joint distribution has

$$P_{KE}(0,0)=P_{KE}(1,1)=\frac12,$$

and zero probability on $(0,1)$ and $(1,0)$. Because $E$ is also marginally uniform, the ideal product distribution $U_KP_E$ assigns probability $1/4$ to each of the four pairs. Therefore

$$\begin{aligned} d_{\mathrm{TV}}(P_{KE},U_KP_E) &=\frac12\sum_{k,e} \left|P_{KE}(k,e)-\frac14\right|\\ &=\frac12\left(4\cdot\frac14\right)\\ &=\frac12. \end{aligned}$$

The key has maximal marginal entropy but is completely known to the adversary. The marginal entropy ignores the adversary’s information; secrecy requires a joint-state criterion.

References

• Cover, T. M., and J. A. Thomas. Elements of Information Theory, 2nd edition. Wiley, 2006. doi:10.1002/047174882X.
• MacKay, D. J. C. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003. Chapters 4–11.
• Polyanskiy, Y., H. V. Poor, and S. Verdú. “Channel coding rate in the finite blocklength regime.” IEEE Transactions on Information Theory 56, 2307–2359 (2010). doi:10.1109/TIT.2010.2043769; author’s manuscript.
• Shannon, C. E. “A mathematical theory of communication.” Bell System Technical Journal 27, 379–423 and 623–656 (1948). Part I, doi:10.1002/j.1538-7305.1948.tb01338.x; Part II, doi:10.1002/j.1538-7305.1948.tb00917.x.
• Shannon, C. E. “Communication theory of secrecy systems.” Bell System Technical Journal 28, 656–715 (1949). doi:10.1002/j.1538-7305.1949.tb00928.x.