Past exam of the communication Theory course of the University of Oxford / 2010 (B11a, DMAB 2650, DMCN 2650, DMPB 2650, DMST 2650)

Communication Theory, Thursday 17 June 2010, 9.30am–11.00am. The complete four-page source was supplied through the past-papers disclosure, in original Part B bundle pages 244–247. The private editable transcription retains the complete cover and all three questions. No exact worked-answer advertisement was found in the bounded availability check.

A binary code assigns a finite bit string to each source symbol. Use nonempty codewords for an unframed variable-length stream. The code is uniquely decodable if no two distinct finite sequences of source symbols produce the same concatenated bit string. It is a prefix-free code if no codeword is an initial segment of a different codeword.

To prove unique decoding of a prefix code, suppose two concatenations agree. Their first codewords both begin the same bit string, so the shorter is a prefix of the longer. The prefix condition forces the first codewords to be equal. Cancel them and repeat. Since the codewords are nonempty, this process ends with both symbol sequences exhausted at the same time; otherwise a nonempty remainder could not equal the empty string. Hence the source sequences agree.

The code $\{0,01\}$ is not a prefix code, since $0$ is a prefix of $01$. Nevertheless it is uniquely decodable: decode from the right. A final $1$ forces the last codeword to be $01$, whereas a final $0$ forces it to be $0$. Removing that final word recursively gives a unique parsing. Thus the converse fails.

Put $S={\sum }_{k=1}^a{2}^{-l_k}$ and let $l_{\max }$ be the largest length. Expanding $S^n$ sums $2^{-L}$ over all strings of $n$ source symbols, where $L$ is the total code length. By unique decodability, the concatenations of length $r$ in this sum are all distinct, so there are at most $2^r$ of them. Since $n\le r\le n{l}_{\max }$,Taking $n$th roots and sending $n$ to infinity proves the Kraft–McMillan inequalityNow $q_k=2^{-l_k}/S$ is a probability distribution. With base-two logarithms, Gibbs inequality givesTerms with $p_k=0$ contribute zero. ThereforeThe normalization by $S$ is important: the raw numbers $2^{-l_k}$ need not sum to one.

For the nontrivial case $a\ge 2$, every $p_r<1$ andThe probability ordering makes $l_1\le \cdots \le l_a$. At a dyadic number, choose the terminating binary expansion followed by zeros. Let $c_r$ be the first $l_r$ bits of $t_r$, and letbe its binary cylinder interval.

Suppose $r<s$ and $c_r$ were a prefix of $c_s$. Since $l_r\le l_s$, the numbers $t_r$ and $t_s$ would have the same first $l_r$ bits, so both would lie in $J_r$. In particular $t_s-t_r<2^{-l_r}$. Buta contradiction. A later word cannot be a shorter prefix of an earlier word because the lengths are nondecreasing; equal-length coincidences were also excluded. Thus the cumulative Shannon code is a prefix code.

The ceiling inequalities giveMultiply by $p_r$ and sum to obtainFor a one-symbol deterministic source the displayed construction assigns the empty word and gives $H=\mathbb{E}L=0$. This zero-bit convention is valid when the number of source emissions is supplied separately. It is not an unframed uniquely decodable code: concatenating different numbers of empty words gives the same bit string. If positive-length unframed words are required, the shortest deterministic code has length $1$, so the strict upper bound $\mathbb{E}L<H+1$ requires the nontrivial-source assumption.

For finite-valued random vectors, write $p(x,y)=P(X=x,Y=y)$ and $p_Y(y)=P(Y=y)$. The conditional entropy is the average entropy of the posterior distributions:Equivalently, $H(X\mid Y)=-{\sum }_{x,y:p(x,y)>0}p(x,y){\log }_{2}p(x\mid y)$. Since $p(x,y)=p_Y(y)p(x\mid y)$, splitting the logarithm givesUse the usual convention $0{\log }_{2}0=0$ and omit conditionals at zero-probability outputs. The same identities hold for countable alphabets whenever the entropy sums are well-defined, without subtracting two infinite quantities.

Set $Z=g(X)$. Given $X$, the value of $Z$ is certain, so $H(Z\mid X)=0$. Applying the entropy identity in the two orders givesbecause conditional entropy is nonnegative. ConsequentlyA deterministic coarsening can merge distinguishable source outcomes, but cannot create additional Shannon entropy.

Choose a most probable symbol $x_{\ast }$, and let $B=1_{\{X=x_{\ast }\}}$. Its binary entropy isSince $B$ is a function of $X$, part (a)(ii) gives $H(X)\ge h_2(\Pi )$. On $[1/2,1]$, the concave function $h_2$ lies above the chord joining $(1/2,1)$ and $(1,0)$. That chord has height $2(1-\Pi )$. ThereforeThe endpoint $\Pi =1$ is included by continuity and corresponds to a deterministic source.

Every positive atom has probability at most $\Pi$, so $-{\log }_{2}p(x)\ge -{\log }_2\Pi$. Averaging yieldsFor $0<\Pi \le 1/2$, the supplied inequality $4\Pi \le 4^{\Pi }$ gives $2+{\log }_2\Pi \le 2\Pi$. Rearranging provesThe two regimes combine into the entropy lower bound from the largest atom, valid for every finite probability distribution.

Given an output $y$ of positive probability, the ideal observer chooses a symbol maximizing the posterior:Ties may be broken arbitrarily, and the choice at an impossible output does not matter. This is maximum a posteriori decoding. It minimizes conditional error at each $y$, because a deterministic decision $x$ is correct with probability $P(X=x\mid Y=y)$; a randomized decision is a weighted average of these success probabilities and cannot exceed their maximum.

Write ${\Pi }_y={\max }_{x}P(X=x\mid Y=y)$. Then $w(y)=1-{\Pi }_y$. Applying the two cases from part (b) to the posterior distribution givesAverage with respect to the output law to obtain the conditional entropy upper bound on minimum decoding error:This is an upper bound on the optimum error probability; it does not hold for arbitrary deliberately poor decoding rules.

For a finite joint distribution, the mutual information isZero-probability terms contribute zero. It measures the reduction in uncertainty about one variable upon observing the other.

A discrete memoryless channel has discrete input/output alphabets and a fixed transition matrix $W(y\mid x)$. Over successive uses it obeysThus the output at a use depends on that input and no other channel history. Its channel capacity isin bits per use for base-two logarithms. On finite alphabets the maximum exists by continuity on the probability simplex; for more general discrete alphabets one uses a supremum.

Fix the channel matrix $W$. The mixed input induces the mixed output $q_3=\lambda q_1+(1-\lambda )q_2$. The concavity of information entropy impliesFor completeness, the difference is $\lambda D(q_1\Vert q_3)+(1-\lambda )D(q_2\Vert q_3)\ge 0$ by Gibbs inequality, including zero coordinates with the usual conventions.

On the other hand, conditional output entropy is linear in the input law:Subtracting gives the concavity of mutual information in the input distribution:This makes maximizing mutual information over the input probability simplex a concave optimization problem: a local maximum is global. It also justifies averaging input distributions over channel symmetries when searching for an optimum, since symmetry averaging cannot lower the achieved mutual information. The channel itself is held fixed throughout.

Let the input probabilities be $(s,t,u)$ and put $v=s+u=1-t$. The output distribution and conditional entropy areFor fixed $v$, the first and third output masses sum to $v/2$. Their entropy is maximized when they are equal, so $s=u=v/2$. Equivalently, if $v>0$,The same bound holds at $v=0$ by continuity. Therefore $I(X;Y)\le h_2(v/2)-v/2$, with equality for symmetric outer input probabilities. Writing $z=v/2\in [0,1/2]$, differentiate:The unique zero is $z=1/3$; strict concavity makes it the global maximum. Thus $v=2/3$ andThe optimum output is $(1/6,2/3,1/6)$.

Every row has Shannon entropy $1$, so $H(Y\mid X)=1$ for every input law. Since the output alphabet has three symbols, Gibbs inequality gives $H(Y)\le {\log }_{2}3$. The uniform input givesso it attains the upper bound. ThereforeUniform output is necessary for equality in the entropy bound, and the three displayed equations then force the uniform input, so this optimum input law is unique.

Let the input law again be $(s,t,u)$. The second output symbol has probability $1/2$ regardless of the input, and the two remaining output probabilities sum to $1/2$. Hencewith equality when the first and third output symbols each have probability $1/4$. The row entropies are $1,3/2,1$, soTake $t=0$ and $s=u=1/2$. The output is $(1/4,1/2,1/4)$ and both bounds are attained. ThereforeThe equality conditions also show uniqueness of the optimum input law. The middle row is the average of the outer rows and carries extra conditional entropy without introducing a new output law; removing a redundant input symbol from a channel explains why it need not be used.