Communication Theory course of the University of Oxford (B11a, B11)

Source paper: FOI request thread. The cover identifies Communication Theory, B11a, Friday 24 June 2011, 2.30pm to 4.00pm. Its four readable pages are original private Part B bundle pages 312–315.

Use the continuous convention $0{\log }_2(0/q)=0$. Let $S=\{r:p_r>0\}$. Applying the allowed logarithm inequality to $q_r/p_r$ for $r\in S$ givesHence $d(p,q)\ge 0$. Equality forces ${\sum }_{r\in S}{q}_r=1$. Since every $q_r$ is strictly positive, this makes $S$ the entire alphabet. Equality in every weighted logarithm inequality then forces $q_r/p_r=1$ for every $r$. Conversely $p=q$ makes every summand zero. ThusThis is Gibbs inequality for relative entropy, with zero probabilities in the first argument handled explicitly.

For the uniform distribution $u_r=1/n$, direct expansion givesPart (a) therefore proveswith equality exactly for $p_X(r)=1/n$ for every $r$. Thus the uniform distribution is the unique entropy maximizer.

Normalize the candidate distribution by settingThe supplied finite sum gives its meanThus it meets the constraint. Since ${\log }_2{q}_r={\log }_{2}c-r$, every other distribution $p$ with mean $m$ satisfiesNonnegativity and the equality case in part (a) proveThe maximum is unique; the entropy comparison uses the fixed mean rather than an unconstrained optimization.

The given logarithmic moment iswhere the $r=1$ term is zero. It is attained by the positive distributionwhose probabilities sum to one. Write $A=2/[n(n+1)]$, so ${\log }_2{q}_r={\log }_{2}A+{\log }_{2}r$. For any distribution $p$ with the required logarithmic moment,Consequently the unique maximizer and its entropy areThe increasing weights are consistent with the prescribed moment; they need not be a decreasing power law.

Write $w_i=(Aq{)}_i$. For each row put $S_i=\{j:a_{ij}>0\}$; the positive row entries ${\alpha }_i=(a_{ij}{)}_{j\in S_i}$ form a probability distribution because the row sum is one. When $w_i>0$, define the probability distributionPart (a), applied on this row support, gives $d(r_i,{\alpha }_i)\ge 0$. Its weighted sum expands asRows with $w_i=0$ contribute zero, since all $a_{ij}{q}_j$ in such a row vanish. Using the convention that zero-weight logarithmic terms are zero, the result isBoth stochasticity conditions have a role: row sums normalize the comparison distributions, while column sums preserve the total contribution from $q$.

This is entropy increase under doubly stochastic mixing.

A binary code assigns a finite binary word $c_k$ to each source symbol $x_k$. In the ordinary unframed convention these codewords are nonempty. It is uniquely decodable when concatenation gives an injective map from finite symbol strings to bit strings:The decoder can recover the entire symbol sequence without being told where codewords end. This is stronger than merely assigning distinct words to individual symbols.

An instantaneous code can decode each symbol as soon as its final bit arrives, without waiting for later bits. Equivalently it is prefix-free: no codeword is a proper prefix of another, and different symbols receive different codewords.

For nonempty codewords, decoding greedily from the start of the bit string identifies the first codeword unambiguously; repeating identifies the whole sequence. Thus an instantaneous code is uniquely decodable under the ordinary nonempty-word convention.

The codeword lengths are integers. For necessity, take $L={\max }_k{l}_k$ and view codewords as nodes of the binary tree. A codeword of length $l_k$ has $2^{L-l_k}$ descendant words at depth $L$. Prefix-freeness makes these descendant sets disjoint, soFor sufficiency, reorder the lengths nondecreasingly. Assign words successively. At depth $l_k$, words extending previously assigned codewords numberThe asserted inequality, even after dropping the later nonnegative terms, givesThus at least one depth-$l_k$ word does not extend an earlier word. Choose it. Since lengths are nondecreasing, it cannot be a proper prefix of a shorter earlier word, and equal-length duplicates have been excluded. Induction constructs the required code. Therefore Kraft inequality is necessary and sufficient:

First consider any instantaneous code. Put $K_0={\sum }_k{2}^{-l_k}\le 1$ and $q_k=2^{-l_k}/K_0$. Part 1(a) givesso $\mathbb{E}L\ge H(X)-{\log }_2{K}_0\ge H(X)$.

For the construction, take the Shannon lengths $l_k=\lceil -{\log }_2{p}_k\rceil$. Then $2^{-l_k}\le p_k$, so Kraft's condition holds. Also $l_k<-{\log }_2{p}_k+1$ for every $k$. Averaging givesFor a nontrivial alphabet all $p_k<1$, so these lengths are positive and the ordinary code convention applies. For a deterministic one-symbol source, the usual zero-bit convention uses $l_1=0$ when the number of source symbols is externally known. If strictly nonempty codewords and arbitrary unframed message lengths are required instead, that degenerate case has $\mathbb{E}L\ge 1$ and cannot satisfy the printed strict upper bound. This convention issue does not affect sources with at least two symbols.

Let $F_k={\sum }_{r<k}{p}_r$ and let $J_k=[F_k,F_k+p_k)$ be the probability cell of symbol $k$. Its midpoint is $G_k=F_k+p_k/2$. Use the binary expansion terminating in zeros at a dyadic rational, so truncation to $l_k$ bits givesThe chosen codeword corresponds to the dyadic interval $D_k=[a_k,a_k+2^{-l_k})$. It contains $G_k$, and its width satisfies $2^{-l_k}\le p_k/2$. ConsequentlyThus $D_k\subseteq J_k$. The probability cells are disjoint, so the code intervals are disjoint. If one binary codeword were a prefix of another, its dyadic interval would contain the other's interval, contradicting this disjointness. Hence the code is instantaneous.

Finally, $l_k=\lceil -{\log }_2{p}_k\rceil +1<-{\log }_2{p}_k+2$. Multiplying by $p_k$ and summing yieldsThis is the Shannon-Fano-Elias code: the extra bit makes the dyadic interval narrow enough to remain inside the cell around its midpoint.

For finite-valued random variables, their mutual information isEquivalently,with zero joint-probability terms omitted. It is the relative entropy of the joint law from the product of its marginals and is nonnegative, with equality exactly when the two variables are independent.

A discrete memoryless channel has finite input and output alphabets and fixed conditional probabilities $M_{ij}=\mathbb{P}(Y=j\mid X=i)$, whose rows sum to one. Memorylessness means that for successive uses, conditional on the input sequence, the output probabilities factor as the product of these one-use conditional probabilities.

Its information capacity in bits per use isThe maximization varies the input distribution while keeping the channel matrix fixed. The output distribution is $p_{X}M$ in the row-vector convention.

Let $B$ be the selected block, and write $\alpha =\mathbb{P}(B=1)$. Because both the input and output alphabets are disjoint across blocks, $B$ is determined by either the input or the output. The mutual-information chain rule therefore givesFor any fixed $\alpha$, equality is achievable by using a capacity-achieving distribution inside each block. It remains to maximize this binary expression.

Put $S=2^{C_1}+2^{C_2}$ and $r=2^{C_1}/S$. A direct expansion of binary relative entropy yieldsPart 1(a) makes the maximum ${\log }_{2}S$, uniquely at $\alpha =r$. HenceThe block choice itself communicates information, in addition to any information sent within the selected block.

This is capacity of a disjoint sum of channels.

There are three distinguishable output groups: columns $\{1,2\}$ can arise only from input one; column $\{3\}$ can arise from inputs two or three, whose rows are identical; and columns $\{4,5\}$ can arise only from input four.

Each group has zero internal channel capacity. A block with one input cannot carry a variable input choice, and the middle block has identical output laws for both of its inputs. Combining the three disjoint zero-capacity blocks therefore givesEquivalently, the output identifies exactly which of these three groups was used, so mutual information is the entropy of that group label. It is maximized when all group probabilities are one third. The capacity-achieving input distributions are preciselySplitting the middle probability arbitrarily cannot communicate an extra distinction because its two channel rows agree.

For any chosen input distribution, the chain rule and nonnegativity of conditional mutual information giveand likewise $I(U;V,W)\ge I(U;W)$. Choosing an input distribution attaining either marginal capacity proves $K\ge \max \{K_1,K_2\}$.

For the upper bound, conditional independence implies $H(V,W\mid U)=H(V\mid U)+H(W\mid U)$, while entropy subadditivity gives $H(V,W)\le H(V)+H(W)$. ThereforeMaximizing over the input law givesMore precisely, under the conditional-independence assumption,The outputs may be dependent through the common input, and this final term measures the information they share rather than add independently.

This is information from two conditionally independent observations.

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.