Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 31 (Information and Coding)

Take $m\ge 2$, as required for the lower bound in this part. A binary Huffman code has a full binary tree: every merge has two children, and all codewords are leaves. More generally an optimal prefix code for positive-probability symbols cannot have an internal vertex with only one child, since suppressing that vertex shortens its descendant codewords and reduces the expected length.

Choose a leaf of maximum depth $s$. Its sibling must also be a leaf, since an internal sibling would have a descendant deeper than $s$. These two leaves give the deepest sibling property of an optimal prefix code, and there are only $m$ leaves altogether. ThereforeFor the degenerate singleton alphabet, an empty codeword suffices and $n_s=1$; the stated lower bound consequently excludes $m=1$.

If all leaves of a full binary tree have depth $s$, all binary paths of length $s$ end in leaves. Thus it has exactly $2^s$ leaves and $m=2^s$. Equivalently, equality in the Kraft inequality gives $m{2}^{-s}=1$.

Conversely, when $m=2^k$ a complete depth-$k$ tree is a prefix code with mean length $k$. For any prefix lengths $s_i$, convexity givesso $L\ge {\log }_{2}m=k$. The complete tree is optimal. A Huffman code attains this optimum, and equality in the strictly convex first inequality forces all its lengths to equal $k$. Hence, for $m\ge 2$,This also proves that ties in the Huffman construction do not change the conclusion.

Use the balancing fact proved by the exchange argument in part d: every leaf of an optimal tree has depth $s-1$ or $s$. A full binary tree with this property has all $2^{s-1}$ possible vertices at level $s-1$; at least one of these is split into two deepest leaves. ThusThese inequalities characterize the maximum codeword length exactly:In the suggested notation $m=a{2}^k$, $1\le a<2$, this is $s=k$ for $a=1$ and $s=k+1$ for $1<a<2$. The distinction at a power of two is important.

Suppose a leaf has depth $t\le s-2$. By part a there is a sibling pair of leaves at depth $s$. These leaves are disjoint from the shallow leaf and its descendants, since a leaf has no descendants. Modify the prefix tree of a code by splitting the shallow leaf into two leaves at depth $t+1$ and replacing the deepest sibling pair by their parent as one leaf at depth $s-1$. The number of leaves remains $m$, so assign the equiprobable source letters bijectively to the new leaves.

The sum of depths for the three affected leaves changes from $t+2s$ to $2(t+1)+(s-1)$. The change isAll other depths are unchanged. Since probabilities are equal, this strictly decreases the expected codeword length, contradicting the optimality of the Huffman code. This is the balancing exchange for a uniform optimal prefix code. There is therefore no leaf of depth at most $s-2$, provingThe argument applies to every optimal binary prefix tree for the uniform source, independently of how Huffman ties are resolved.

A full binary tree has Kraft sum one. For example, place mass one at the root and divide each internal vertex's mass equally between its children; a leaf at depth $l$ receives $2^{-l}$, and the total mass on leaves remains one. Using part d gives the two equationsMultiplying the second equation by $2^s$ and subtracting the first gives the uniform-source Huffman length distributionIf $m=2^s$, the first number is zero and every codeword has length $s$. Otherwise both levels occur. The corresponding mean length is $L=s-(2^s-m)/m$.

For the uniform 27-symbol model, $s=\lceil {\log }_{2}27\rceil =5$. The uniform-source Huffman length distribution givesThus five symbols receive four-bit codewords and the other 22 receive five-bit codewords. To realize these lengths, start with all 32 binary words of length five and collapse any five disjoint sibling pairs into their four-bit parents. This leaves exactly five leaves at depth four and 22 at depth five. All source letters have the same probability, so which five letters receive the shorter codewords is arbitrary.

The expected codeword length isThe 27 symbols may represent 26 letters and a space, but this idealization keeps them equiprobable; it is not an empirical frequency model of English.

Use base-two logarithms and put $H=H(U_1)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Zero-probability letters can be omitted. The random variables $I_j=-{\log }_2{p}_{U_j}$ are self-information values, are IID, and have finite mean $H$ because the alphabet is finite. Independence givesFor an arbitrary $\delta >0$, define the typical setThe weak law of large numbers implies $P(T_{n,\delta })\to 1$. Every string in this set satisfiesThis is the asymptotic equipartition property for the given finite IID source, here obtained directly from the weak law of large numbers.

For the upper bound, summing the lower bound on typical-string probabilities yields $|T_{n,\delta }|\le 2^{n(H+\delta )}$. For sufficiently large $n$, its probability is at least $1-\epsilon$, so it is an admissible set in the definition of $M(n,\epsilon )$. HenceFor the lower bound, let $A$ be any admissible set and write ${\eta }_n=P(T_{n,\delta }^c)\to 0$. ThenEach member of this intersection has probability at most $2^{-n(H-\delta )}$. Therefore, for all sufficiently large $n$,This applies in particular to a minimum-size admissible set, giving a liminf at least $H-\delta$. Letting $\delta \downarrow 0$ proves both existence and the value of the minimal high-probability source-set exponent:For a deterministic source, $H=0$ and $M(n,\epsilon )=1$, consistent with the formula.

For coding, label the strings in an admissible set with distinct binary indices of length $\lceil {\log }_{2}M(n,\epsilon )\rceil$. A decoder reconstructs those strings exactly and may fail outside the set. Thus asymptotically $H$ bits per source symbol describe any fixed fraction $1-\epsilon$ of the probability mass. More strongly, every rate $R>H$ permits block codes with error tending to zero: choose $\delta <R-H$, encode the typical strings individually and reserve one index for all other strings. The required number of indices is at most $2^{n(H+\delta )}+1\le 2^{nR}$ for large $n$.

Conversely, a block encoder with at most $2^{nR}$ outputs can reconstruct at most that many distinct input strings correctly. If $R<H$, choose $0<\delta <H-R$. Its success probability is at mostThis gives the strong converse for fixed-rate source coding. It is the operational significance of the information entropy limit for reliable source encoding at a rate. The allowance of a small reconstruction error matters: a fixed-length code that must encode every possible string without error generally needs the larger rate ${\log }_2|\{i:p_i>0\}|$.

We give the bounds for an alphabet of size $q\ge 2$, including the binary case $q=2$. Let $C$ be a length-$n$ code with $M$ codewords and minimum Hamming distance at least $d$, where $1\le d\le n$. Write $A_q(n,d)$ for the maximum code size at a given distance andfor the number of words in a Hamming ball of radius $t$. The $j$th term chooses the changed coordinates and the $q-1$ alternative symbols in each.

For the Hamming bound, put $t=\lfloor (d-1)/2\rfloor$. Balls of radius $t$ around distinct codewords are disjoint: a common point would, by the triangle inequality, make their distance at most $2t<d$. Counting those balls inside the $q^n$ ambient words provesNo linearity is needed. For a linear code of dimension $k$ over ${\mathbb{F}}_q$, replace $M$ by $q^k$.

For the Gilbert–Varshamov bound, construct a code greedily, adding any word at distance at least $d$ from all previously selected words, until none remains. The process terminates because the space is finite. Its maximality implies that the radius-$(d-1)$ balls around its codewords cover the whole space: an uncovered word could have been added. These balls may overlap, but the size of their union is at most the sum of their sizes. Hence the constructed code has $M{V}_q(n,d-1)\ge q^n$, proving the existence boundOne may take the ceiling on the right because code size is integral.

For completeness, the sharper linear version is the Varshamov bound for linear codes. When $q$ is a prime power and $d\ge 2$, an $[n,k,\ge d]$ linear code exists providedSet $r=n-k$ and choose $n$ columns of an $r\times n$ parity-check matrix in order. When choosing column $l$, exclude all combinations of at most $d-2$ earlier columns, including the zero combination. There are at most ${\sum }_{j=0}^{d-2}\left(\genfrac{}{}{0ex}{}{l-1}{j}\right)(q-1{)}^j$ forbidden vectors, smaller than $q^r$ by the assumed inequality. A column can therefore be chosen. Inductively every set of at most $d-1$ chosen columns is independent: a relation involving the newest one would express it as a combination of at most $d-2$ earlier columns. The kernel has dimension at least $n-r=k$ and minimum Hamming distance at least $d$, since a low-weight kernel vector would be such a column relation. If its dimension is larger than $k$, take a $k$-dimensional subspace. This proves the stated linear existence claim; it does not assume the greedy nonlinear code was linear.

To derive the asymptotic bounds, define the q-ary entropywith the continuous endpoint conventions. Its derivative is ${\log }_q((q-1)(1-x)/x)$, so it is increasing on $[0,1-1/q]$ and has maximum one at $1-1/q$. Stirling's formula gives, uniformly for integer $0\le j\le n$,The sum defining $V_q$ is between its largest summand and $(n+1)$ times that summand. For radius fractions tending to $\rho \le 1-1/q$, monotonicity of $H_q$ makes the largest exponent tend to $H_q(\rho )$. Consequently the Hamming ball volume exponent isFor $\rho >1-1/q$, the exponent is one: use a radius fraction just below $1-1/q$ for a lower bound and $V_q\le q^n$ for an upper bound.

Set $d_n=\max \{1,\lceil \delta n\rceil \}$ and define the asymptotic rate-distance function byThe code rate is $n^{-1}{\log }_{q}M$ and the relative minimum distance is $d/n$. A limsup suffices; no unproved existence of a limit for optimal code sizes is required. The packing radii have fraction tending to $\delta /2$, so the finite Hamming bound and the volume exponent give the asymptotic Hamming boundThe covering radii have fraction tending to $\delta$, giving the asymptotic Gilbert–Varshamov boundFor larger $\delta$, this covering argument gives only the trivial lower bound zero, not the expression obtained by extending the decreasing information entropy function beyond its maximum.

The asymptotic lower bound is also achievable by linear codes over a finite field. For $\delta >0$ and sufficiently large $n$, take redundancy $r_n=\lfloor {\log }_q{V}_q(n-1,d_n-2)\rfloor +1$, so $q^{r_n}>V_q(n-1,d_n-2)$. The linear existence condition produces dimension at least $n-r_n$; its rate has liminf at least $1-H_q(\delta )$. At $\delta =0$, use the whole space, of rate one. In particular, for binary codes the bounds reduce towhere $h_2$ is the binary entropy function.

Use binary codes, so the polynomial modulus is $f(X)=X^N+1=X^N-1$ in ${\mathbb{F}}_2[X]$. A cyclic code $C$ is a linear subspace of ${\mathbb{F}}_2^N$ invariant under the cyclic shift $(a_0,\dots ,a_{N-1})\mapsto (a_{N-1},a_0,\dots ,a_{N-2})$. Identify a word with $a(X)={\sum }_{i=0}^{N-1}{a}_i{X}^i$. Addition is coefficientwise, and multiplication is polynomial multiplication reduced modulo $f$. In the quotient ringmultiplication by $X$ is exactly that cyclic shift. Closure under this map and linear combinations gives closure under multiplication by every polynomial, so a cyclic code is an ideal of $R$. Conversely, an ideal is a linear subspace closed under multiplication by $X$, proving the correspondence.

Take the inverse image of $C$ in ${\mathbb{F}}_2[X]$. This is an ideal containing $(f)$. The polynomial division algorithm shows directly that it has a unique monic generator $g$: choose a nonzero polynomial of least polynomial degree and divide any other member by it; the remainder is in the ideal and has smaller polynomial degree, so must vanish. If two monic generators existed, mutual divisibility would make them equal. Because $f$ belongs to the ideal, $g\mid f$. Conversely every monic divisor of $f$ defines an ideal of $R$. Thus the generator polynomial of a cyclic code satisfiesFor a nonzero code, $g$ is its nonzero polynomial representative of least polynomial degree. For the zero code, use $g=f$, whose residue in $R$ is zero; this standard convention covers that endpoint despite its having no nonzero codeword.

Let $r=\mathrm{deg}g$ and $k=N-r$, and put $h=f/g$. Every codeword has a unique representation $bg$ with $\mathrm{deg}b<k$: dividing an arbitrary multiplier by $h$ does not change its product with $g$ modulo $f$. The words $g,Xg,\dots ,X^{k-1}g$ have distinct leading degrees below $N$ and are independent. ConsequentlyThe statement remains valid for the zero code, with an empty basis, and the full code, with $g=1$.

For length 16, characteristic two gives $X^{16}+1=(X+1{)}^{16}$. Its only monic divisors are $(X+1{)}^j$ for $0\le j\le 16$. Hence all binary cyclic codes of length a power of two in this case areThere are exactly 17 codes, forming the chain $C_{16}\subset C_{15}\subset \cdots \subset C_0$. This is a repeated-root cyclic code situation, so it would be incorrect to count just square-free factors. Their canonical check polynomials of a cyclic code are $(X+1{)}^{16-j}$. An explicit expansion of each generator is ${\prod }_{b:\text{bit }b\text{ of }j\text{ is }1}(1+X^{2^b})$.

The canonical check polynomial of a cyclic code isIndeed $ah\equiv 0(\mathrm{mod}f)$ means $f\mid ah$. Since $f=gh$, cancellation in the polynomial ring gives $g\mid a$, exactly code membership. No coprimality of $g$ and $h$ is needed, including for length 16.

There is a normalization qualification in the printed definition. The kernel condition alone does not force the supplied polynomial $\tilde{h}$ to equal this canonical $h$. If $d=\gcd (f,\tilde{h})$, write $f=d{f}_1$ and $\tilde{h}=d{h}_1$ with $\gcd (f_1,h_1)=1$. Then $f\mid a\tilde{h}$ holds exactly when $f_1\mid a$, so its kernel is the ideal generated by $f/d$. ThereforeEquivalently $\tilde{h}=hu$ with $\gcd (u,g)=1$. Requiring the monic divisor of $f$ selects the canonical check polynomial of a cyclic code. For example $Xh$ gives the same kernel as $h$, since $X$ is a unit modulo $f$, but is generally a different polynomial. Given any permitted $\tilde{h}$, taking $\gcd (f,\tilde{h})$ recovers the canonical $h$.

To construct a parity-check matrix, write the canonical $h={\sum }_{l=0}^k{h}_l{X}^l$ and its reciprocal polynomial $h^{\ast }(X)=X^{k}h(X^{-1})$. Take coefficient vectors, padded to length $N$, ofas the $r$ rows of $H$. Here $h_0=1$ because $h\mid f$, so these rows have successive leading degrees $k,k+1,\dots ,N-1$ and are independent. For a word $a$, row $j$ has dot product ${\sum }_{l=0}^k{h}_{k-l}{a}_{j+l}$, the coefficient of $X^{k+j}$ in the ordinary product $ah$. If $a\in C$, then $ah=bf$ with $\mathrm{deg}b<k$. This product has no terms in degrees $k,\dots ,N-1$, so $H{a}^T=0$. The kernel of $H$ has dimension $N-r=k$, the same as $C$, proving $\ker H=C$. This proves the reciprocal-polynomial parity-check matrix construction and identifies its rows as a basis for the dual of a cyclic code.

Alternatively, a supplied check polynomial of a cyclic code reduced modulo $f$, $\tilde{h}={\sum }_{l=0}^{N-1}{\tilde{h}}_l{X}^l$, gives the polynomial multiplication parity-check matrixThis circulant matrix represents multiplication by $\tilde{h}$ modulo $f$, so its kernel is $C$ and its matrix rank is $r$. Selecting independent rows yields a rank-$r$ parity-check matrix even without initially normalizing the supplied polynomial.

The syndrome $s(y)=H{y}^T$ labels the coset $C+y$. Indeed $s(y)=s(z)$ if and only if $H(y-z{)}^T=0$, equivalently $y-z\in C$. There are $2^r$ cosets, each with $2^k$ words, and the syndrome classification of code cosets gives a bijection between them and ${\mathbb{F}}_2^r$. If $y=c+e$ is a transmitted codeword plus an error, then $s(y)=s(e)$: the syndrome determines the error coset. Choosing a minimum-weight coset leader and subtracting it performs minimum-distance decoding. The error itself need not be uniquely identified, but it is unique when its weight is at most $\lfloor (d-1)/2\rfloor$, since the corresponding error-correction balls are disjoint.

For the repetition code, the nonzero codeword is the all-ones word, soTheir product is $X^N+1$, and the generator polynomial degree $N-1$ gives dimension one. For the single parity-check code, membership is $a(1)=0$, equivalent to divisibility by $X+1$. ThusIts dimension is $N-1$; it is the even-weight code.

Finally, factor the binary length-seven modulus:A standard cyclic realization of the Hamming code of length seven usesIts dimension is four. The reciprocal-check construction givesIts columns are exactly the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$, so no word of weight one or two is in its kernel. The generator itself has weight three, so the minimum Hamming distance is exactly three; this is the $[7,4,3]$ Hamming code. Reversing the cyclic coordinate order gives the equally valid reciprocal choiceThe polynomial answer therefore depends on the cyclic coordinate convention, while the resulting codes are equivalent.