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

Communication Theory, Mathematics Part B and the corresponding joint schools; Thursday 12 June 2008, 9.30am–11.15am. The complete three-page source and intact cover are preserved in a private editable transcription from original Part B bundle pages 127–129, supplied through the past-papers disclosure. No exact worked-answer advertisement was found in the bounded availability check. All logarithms in these solutions are to base two unless another base is shown.

Write $p_{xy}=\mathbb{P}(X=x,Y=y)$, $p_x={\sum }_y{p}_{xy}$, and $q_y={\sum }_x{p}_{xy}$. In bits the mutual information isTerms with zero joint probability contribute zero. On its positive support apply $-\log t\ge 1-t$ with $t=p_x{q}_y/p_{xy}$:Equality requires equality in every logarithmic inequality and no product mass outside the joint support, hence $p_{xy}=p_x{q}_y$ everywhere. Conversely that factorization makes every term zero. Thus mutual information is nonnegative and vanishes exactly for independence. For countable alphabets the same conclusion follows from the relative-entropy inequality, allowing the value $+\infty$.

The entropy chain rule givesConditional entropy is nonnegative, so $I(X;Y)\le \min (H(X),H(Y))$. For finite entropies, if $H(X)\le H(Y)$, equality holds exactly when $H(X\mid Y)=0$, meaning $X$ is a function of $Y$ almost surely. If $H(Y)\le H(X)$, interchange the variables. When their entropies are equal, equality requires both functional relations. Zero conditional entropy has this characterization because each conditional probability distribution must be a point mass.

The conditional output distributions are permutations of the same triple, so both conditional entropies equalWith input probability $p$, the three output probabilities are $q_1=(2-p)/6$, $q_2=(1+2p)/6$, and $q_3=(3-p)/6$. ThereforeDifferentiating, the constant terms cancel because $\sum q_j^{\prime }=0$:Thus there is a unique maximum. Its stationary equation reduces to $3p^2+9p-5=0$, whose root in $[0,1]$ isThe other root is negative; strict concavity proves this is the global maximum.

For a finite probability distribution,with $0{\log }_{2}0=0$. If the positive support has size $s\le n$, apply the given strict Jensen inequality to the random variable $Z=1/p_X$:Equality requires $s=n$ and $Z$ constant almost surely, so all probabilities are $1/n$. Conversely the uniform distribution attains this bound. Thus $\boxed{H(X)\le {\log }_{2}n}$, with exactly that equality case.

Define $H(X\mid Y)={\sum }_y\mathbb{P}(Y=y)H(X\mid Y=y)$. The joint entropy identity $H(X,Y)=H(Y)+H(X\mid Y)$ follows by writing $p_{xy}=q_y{p}_{x\mid y}$ and expanding its logarithm. If $Y=g(X)$, then $H(Y\mid X)=0$ and $H(X,Y)=H(X)$, giving the desired decomposition.

Group the first two symbols together and keep the third separate. If $c<1$, the identity becomeswhere $h(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$. Binary entropy is at most one, with equality precisely at $1/2$. HenceEquality holds exactly when $a=b=(1-c)/2$. When $c=1$, $a=b=0$, so the same conclusion holds at the boundary.

The capacity of a discrete memoryless channel is $C={\max }_{P_X}I(X;Y)$, in bits per channel use. For the binary symmetric channel with crossover probability $p$, $H(Y\mid X)=h(p)$ and $H(Y)\le 1$. A uniform input makes the output uniform, attainingFor the binary erasure channel, let $E$ be its erasure indicator. This flag is visible in the output and independent of the input. If there is no erasure, the output reveals the input; otherwise it reveals nothing. Consequentlyagain attained by a uniform input. These formulas include crossover probabilities zero and one, and complete erasure.

Let $X$ be the original input, $U$ the output of the first channel, and $Y$ the final output. The independent erasure flag is observable from $Y$. The mutual information chain rule, conditioning on that flag, givesThe same uniform input maximizes $I(X;U)$ as in the binary symmetric channel. ThusThis scaling works because the erasure event is independent of both the input and the first channel noise.

Unique decipherability makes the map from $(X_1,\dots ,X_m)$ to the concatenated binary string $M$ injective. Entropy is unchanged by an injective relabelling, and memorylessness gives independence, henceGiven $L=\ell$, the string has at most $2^{\ell }$ possibilities. The entropy bound for finite alphabets therefore gives $H(M\mid L=\ell )\le \ell$. Averaging,The random length cannot simply be discarded: it can also carry information. Let ${\ell }_{\max }$ be the maximum codeword length, finite since the alphabet is finite. Since $L$ is a function of $M$ and takes at most $m{\ell }_{\max }+1$ values,Divide by $m$ and let $m\to \infty$. This proves $\boxed{\mathbb{E}|c(X)|\ge H(X)}$. The conclusion also covers a deterministic source; the source's lowercase $x$ in its final expectation denotes the random source letter.

The entropy isTo construct a Huffman code, work with integer weights $2,2,3,4,5$. Merge the two twos to make four. Of the remaining weights $3,4,4,5$, merge three with the original four to make seven, and merge the new four with five to make nine. Finally merge seven with nine. Resolving the tie in this way gives, for example,This is a prefix code and Huffman's optimality theorem makes it optimal. Its expected length isDifferent choices at a tied merge can give different optimal codewords with the same expected length.

Let $\bar{\ell }=\mathbb{E}|c(X)|$. The Huffman encoder emits an average of $w\bar{\ell }$ binary digits per minute. Shannon's noisy-channel coding theorem states that for a discrete memoryless channel of capacity $K$, every information rate strictly below $K$ bits per use is achievable with error probability tending to zero as block length grows; rates above $K$ are not achievable for unrestricted messages.

Thus a channel code carrying the Huffman bitstream reliably with buffering and arbitrarily long blocks can be chosen wheneverThe strict inequality supplies positive coding and buffering slack. Huffman's expected-length bound is $H(X)\le \bar{\ell }<H(X)+1$ for a nontrivial finite source. Therefore the simpler bound $r>w(H(X)+1)/K$ is sufficient without knowing its exact Huffman lengths.

Distinguish this bitstream construction from the absolute source-channel limit. The noiseless source coding theorem permits long source blocks to be compressed to any rate above $H(X)$ bits per source symbol, with arbitrarily small overhead. Together with channel coding, this gives the sharper limiting requirement $rK>wH(X)$; $rK<wH(X)$ is impossible by the source-channel converse. Further compression can exploit redundancy remaining in a single-symbol Huffman stream, so $w\bar{\ell }/K$ need not be the universal minimum channel symbol rate. At $K=0$ a positive-entropy source cannot be sent reliably at a finite rate.

A binary prefix code assigns each source symbol a distinct finite binary word, with no assigned word a prefix of another. It is instantaneous because a decoder can identify the symbol as soon as its last digit arrives, without reading digits from the next word. Such a code is optimal when it minimizesamong all binary prefix codes for that source distribution. Symbols of zero probability may be removed from the optimization.

Make a rooted binary tree with an edge labelled zero for the first branch and one for the second branch at each interior node. Put each source symbol at the leaf reached by following the successive digits of its codeword. The prefix property ensures no assigned word ends at an ancestor of another assigned word.

The route of a codeword is its root-to-leaf path; its length is the number of edges on that path, equal to the number of binary digits in the word. For an optimal tree with positive leaf probabilities, every interior node has two children: a node with just one child could be contracted, shortening all words below it and strictly reducing the expected length. The diagram in the earlier Huffman calculation is one such full binary tree.

The redundancy is $R=\bar{\ell }-H(X)$, measured in bits per source symbol. Write $s_v={\sigma }_0(v)+{\sigma }_1(v)$ for the total mass passing through interior node $v$. Counting each codeword's length as one for each interior node its route visits givesThe entropy can be split into the conditional binary decisions along that route. Algebraically each node contributesSumming telescopes: each non-root interior mass appears once positively as a parent and once negatively as a child. The root term is $1{\log }_{2}1=0$ and the remaining leaf terms sum to $-{\sum }_x{p}_x{\log }_2{p}_x=H(X)$. HenceSubtracting this identity from the expected-length identity provesThus redundancy is the sum of the probability-weighted imbalances of the binary branch decisions. Nodes with no mass contribute zero by continuity. The formula holds for every full prefix tree, even without optimality.