Past exam of the communication Theory course of the University of Oxford / 2007 (B11, DMAB 2650, DMPB 2650, DMST 2650)

Communication Theory, Mathematics Part B and the Mathematics and Philosophy and Mathematics and Statistics joint schools; Thursday 14 June 2007, 9.30am–11.15am. The complete four-page source is privately transcribed from original Part B bundle pages 61–64, supplied through the past-papers disclosure. No exact worked-answer advertisement was found in the bounded availability check. Source coding uses the positive-probability source support. Logarithms and information quantities are in base two unless indicated otherwise.

Use the convention $0{\log }_{2}0=0$. On the positive support of $p$, the given logarithm inequality givesThe logarithm is strictly concave, so its supporting line at one has equality only there. More explicitly, the given global bound forces $c=1/{\log }_{e}2$ by differentiation at one, and $x-1-{\log }_{e}x$ vanishes only at one. Equality above therefore requires $p_r=q_r$ on the positive support, and no mass of $q$ outside it. Thus equality holds exactly when $p=q$.

For the uniform distribution $q_r=1/n$, the divergence is $D(p,q)={\log }_{2}n-H(p)$. Its nonnegativity gives $\boxed{H(p)\le {\log }_{2}n}$, with equality precisely for the uniform law.

Conditional entropy is $H(U\mid V)={\sum }_{v}P(V=v)H(U\mid V=v)$. Factor the joint probabilities as $P(U=u,V=v)=P(V=v)P(U=u\mid V=v)$ and expand their logarithms. This gives $H(X,Y)=H(Y)+H(X\mid Y)$. Applying the same identity within each conditional law given $Z=z$ and averaging gives $H(X,Y\mid Z)=H(X\mid Z)+H(Y\mid X,Z)$.

Put $E=1_{\{X\ne Y\}}$ and $\epsilon =P(E=1)$. Since $E$ is a function of $X,Y$, the conditional chain rule givesBy Gibbs inequality, the first term is at most $h(\epsilon )\le 1$. When $E=0$, $Y$ determines $X$. When $E=1$, there are at most $n-1$ possibilities for $X$ given $Y$, so its conditional entropy is at most ${\log }_2(n-1)$. ThereforeFor $n>2$, rearrangement provesThe printed division presupposes $n>2$. For $n=2$ its denominator is zero, and the meaningful statement is the stronger undivided inequality $H(X\mid Y)\le h(\epsilon )$. For $n=1$ the variables agree surely.

Independence gives $P(X=Y)={\sum }_r{p}_r{q}_r={\mathbb{E}}_p[2^{{\log }_2{q}_X}]$. The given exponential convexity inequality therefore yieldsTaking complementary probabilities provesThe strict positivity of the entries of $q$ makes all logarithms appearing in this finite expectation well defined.

A binary prefix code assigns distinct finite binary strings to the source symbols, with no assigned string a prefix of another. It is instantaneous because a complete codeword is recognized without needing the next word's bits.

Associate a word of length $\ell$ with its dyadic subinterval of $[0,1)$ of length $2^{-\ell }$. A prefix relation corresponds to interval containment. Prefix-free words therefore give disjoint intervals, whose total length is at most one. This proves necessity of Kraft inequality.

For sufficiency, sort the requested nonnegative integer lengths increasingly and construct a code greedily in a binary tree. At depth ${\ell }_j$, the preceding codewords forbid exactly ${\sum }_{i<j}{2}^{{\ell }_j-{\ell }_i}$ nodes. The assumed inequality, retaining the positive contribution of the present word, bounds this integer by $2^{{\ell }_j}-1$. Thus at least one node is available; choose it. It is not below an earlier codeword, and the nondecreasing lengths prevent it from being a proper ancestor of an earlier word. Continue to obtain a prefix code of all the required lengths. Hence

Work on the source support, so its listed probabilities are positive; zero-probability symbols may be omitted. An optimal binary prefix code minimizes the expected codeword length for that distribution. The same optimal expected length is attained when optimization is over uniquely decipherable codes, by the converse and existence parts of Kraft–McMillan inequality.

Choose Shannon lengths ${\ell }_k=\lceil -{\log }_2{p}_k\rceil$. They satisfy $2^{-{\ell }_k}\le p_k$, so the preceding existence theorem gives a prefix code with those lengths. Also ${\ell }_k<-{\log }_2{p}_k+1$ for every symbol, including the integer cases. Thus its expected length is less than $H(X)+1$. An optimal code cannot have a larger expected length, provingFor a deterministic one-symbol source the empty word has length zero, consistent with this bound.

At an interior tree node write $A,B$ for the total masses in its two children, and $S=A+B$. Counting path lengths and telescoping the Shannon entropy over the binary decisions givesIndeed each symbol contributes its probability once per ancestral interior node to the first sum. In the second sum, expanding $Sh(A/S)=S{\log }_{2}S-A{\log }_{2}A-B{\log }_{2}B$ cancels the interior terms and leaves the source Shannon entropy. The supplied inequality now bounds redundancy byConsider the cut between adjacent symbols $k,k+1$ made at one node. If its left side is heavier, moving its last symbol to the right must not improve the chosen cut. Writing $\Delta =A-B\ge 0$, this says $|\Delta -2p_k|\ge \Delta$, which implies $\Delta \le p_k$; when the left side is a singleton the same bound is immediate. If the right side is heavier, the corresponding argument gives $|A-B|\le p_{k+1}$. In all casesRecursive subdivision of contiguous blocks uses each original gap exactly once. Summing over the $m-1$ gaps therefore givesproving $\bar{s}<H(X)+2$. If probabilities are already nonincreasing, each maximum is $p_k$ and the improved bound is $\bar{s}-H(X)\le 1-p_m<1$. Thus the sorted version has expected length less than $H(X)+1$, although it need not be optimal. For one symbol the assertions hold directly. This is the Fano slice code redundancy bound.

The channel matrix has entries $M_{xy}=P(Y=y\mid X=x)$, with nonnegative entries and each row summing to one. For an input distribution $\pi$, it induces the joint law $P(X=x,Y=y)={\pi }_x{M}_{xy}$. Its capacity in bits per use isOn finite alphabets the maximum exists by continuity on the compact probability simplex.

Gibbs inequality makes mutual information nonnegative, so $C\ge 0$. The two conditional-Shannon entropy expressions giveEach Shannon entropy is bounded by the base-two logarithm of its alphabet size. Maximizing over the input distribution therefore gives $\boxed{0\le C\le {\log }_{2}m}$ for the smaller size $m$.

Exchanging the first and third inputs, together with the corresponding outputs, leaves the channel unchanged. Concavity therefore shows that averaging an input distribution with its exchanged distribution cannot reduce mutual information. We may take input probabilities $(a,1-2a,a)$.

For $p<1$, put $b=1-p$ and $t=2ab$, so $0\le t\le b$. The output distribution is $(t/2,1-t,t/2)$ and the mean conditional output Shannon entropy is $2ah(p)=th(p)/b$. HenceIts strict concavity gives the unique stationary value $t_{\ast }=[1+2^{h(p)/b-1}{]}^{-1}$. This lies in the allowed interval: for $0<p<1$, the derivative at $t=b$ is $({\log }_{2}p+b)/b<0$, while it tends to positive infinity at zero. At $p=0$ the stationary value is $2/3<1$ directly. Consequently an achieving input distribution isThe resulting capacity is $C={\log }_2(1+2^{1-h(p)/(1-p)})$. In particular at $p=1/2$, $a=1/3$ andAt $p=1$ all outputs are the middle symbol, so $C=0$ and every input distribution achieves it; the divided formula is not used at that endpoint.

Maximum a posteriori decoding chooses an input with the largest posterior probability given the received word. By Bayes' theorem this maximizes $P(X=x)p(y\mid x)$ over candidate codewords, minimizing the average probability of a decoding error.

Maximum-likelihood decoding chooses a codeword maximizing $p(y\mid x)$ for the received word $y$. It uses the likelihood alone, without weighting by the prior probabilities of the codewords.

Minimum-distance decoding with Hamming distance chooses a codeword minimizing the number of positions in which it differs from the received word. Ties may be resolved by a fixed rule.

With equally likely codewords, the prior factor in the ideal-observer criterion is constant, so it agrees with maximum likelihood. On the binary symmetric channel,For $0<p<1/2$ this is strictly decreasing in Hamming distance, so the likelihood maximizers are precisely the nearest codewords. With the same tie convention all three decoders therefore agree. At $p=0$ every possible received word equals its transmitted codeword, and the rules agree on all positive-probability outputs; outputs having zero probability need no posterior assignment.

A radius-$r$ Hamming decoder outputs the unique codeword within distance $r$ of the received word, if there is one. Ambiguous cases and absent candidates can be declared errors, or assigned arbitrarily for an error bound. The average error is the mean of the conditional error probabilities over the equally likely transmitted messages.

Let $V_n(r)={\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ be the size of a Hamming ball. For any transmitted random codeword, the channel noise weight is $U\sim \mathrm{Bin}(n,p)$. Decoding can fail only if $U>r$ or another codeword lies within distance $r$ of the output. Conditional on the output, each independently sampled competing codeword is still uniform on the whole word space, so has probability $2^{-n}{V}_n(r)$ of lying in that ball. A union bound yieldsThis is an average over the random code construction as well as over messages and noise. It implies existence of at least one deterministic codebook with average error no greater than this bound, rather than asserting the same inequality for every randomly sampled book.

Choose a target rate $R<1-h(p)$ and a small $\delta >0$ such that $p+\delta <1/2$ and $R<1-h(p+\delta )$. Let $M_n=\lfloor 2^{nR}\rfloor$ and $r=\lfloor n(p+\delta )\rfloor$. The standard Hamming-volume estimate is $V_n(r)\le 2^{nh(r/n)}$: for $s=r/n\le 1/2$, each binomial probability term $s^j(1-s{)}^{n-j}$ with $j\le r$ is at least $s^r(1-s{)}^{n-r}$, and summing proves this bound. Thus the union-bound term decays exponentially, while $P(U>r)\to 0$ by the law of large numbers or a Chernoff bound.

There exists a $2M_n$-message book with average error ${\epsilon }_n\to 0$. At least half its messages have individual error at most $2{\epsilon }_n$, by Markov's inequality on the uniformly chosen message. Keep $M_n$ of these and discard the rest. Restricting the decoder's candidate set cannot spoil a previously unique successful decoding. The retained book therefore has maximum error at most $2{\epsilon }_n\to 0$. For large $n$ its retained codewords must be distinct: identical words could not both have conditional error below one half. This expurgation of a codebook proves reliable communication at every rate below $1-h(p)$, while converting an average-error estimate into the requested maximum-error conclusion.