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

Use base-two logarithms and the convention $0{\log }_{2}0=0$. Write $p_y=\mathbb{P}(Y=y)$ and $q_y(x)=\mathbb{P}(X=x\mid Y=y)$ for $p_y>0$. The conditional entropy is the average of the information entropies of these conditional laws:The careful form of Gibbs inequality is that, for two probability mass functions $q,p$ on a common countable set,where a term with $q(x)>0=p(x)$ gives $+\infty$. Equality holds exactly when $q=p$. This is the nonnegativity of relative entropy.

First suppose $H(X)<\infty$. For every $y$ of positive probability, $q_y(x)>0$ implies $p_X(x)>0$. Averaging the cross-entropies givesAll the summands here are nonnegative, so interchanging the sums is valid, and each conditional cross-entropy is finite. Applying Gibbs inequality to each $q_y,p_X$ shows that $H(q_y)$ is at most its cross-entropy. Subtracting and averaging therefore givesEvery term on the right is nonnegative. The equality in the entropy conditioning inequality is thus equivalent to $q_y=p_X$ for all $p_y>0$, which is exactly factorization of the joint probability mass function. Consequently

For arbitrary countable discrete random variables, the inequality remains valid in $[0,\infty ]$: the case $H(X)=\infty$ is immediate. The finite-entropy condition is necessary for the usual equality characterization. For example, let $\mathbb{P}(A=n)=c/(n(\ln n{)}^2)$ for $n\ge 2$, with $c$ the normalizing constant, and let $B$ be an independent fair bit. The series defining the probability mass function converges, whereas its information entropy diverges like ${\sum }_{n}1/(n\ln n)$. Then $X=(A,B)$ and $Y=B$ are dependent, but $H(X)=H(X\mid Y)=\infty$. In the infinite case, equality means precisely that the conditional entropy is also infinite; it does not imply independent random variables.

Introduce a selector $B$ with Bernoulli distribution of parameter $\alpha$, and construct $W$ by taking its conditional law given $B=1$ to be $p_U$, and its conditional law given $B=0$ to be $p_V$. No prescribed joint law of $U,V$ is needed. Summing over the selector gives the desired mixture probability mass function. The conditional entropy isSince conditioning cannot increase information entropy,This proves the concavity of information entropy. The argument also covers infinite information entropies with the convention that a zero mixing weight contributes zero. At $\alpha =0$ or $1$, the mixture is the corresponding original law and equality is immediate.

For $N\sim \mathrm{Pois}(\lambda )$, the Poisson distribution givesThis information entropy is finite: ${\log }_2(n!)\le n^2$ for integer $n\ge 0$, while $\mathbb{E}{N}^2=\lambda +{\lambda }^2$.

Fix $0<{\lambda }_1<{\lambda }_2$. Take independent random variables $U\sim \mathrm{Pois}({\lambda }_1)$ and $V\sim \mathrm{Pois}({\lambda }_2-{\lambda }_1)$. Their convolution isby the binomial theorem. Thus $U+V$ has Poisson distribution with parameter ${\lambda }_2$. Conditioning on $V=v$ only translates $U$, so $H(U+V\mid V)=H(U)=F({\lambda }_1)$. The entropy monotonicity under independent addition yields $F({\lambda }_2)\ge F({\lambda }_1)$.

In fact the inequality is strict. The covariance $\mathrm{Cov}(U+V,V)=\mathrm{Var}(V)={\lambda }_2-{\lambda }_1$ is positive, so $U+V$ and $V$ are not independent random variables. Their information entropies are finite, and the equality criterion from part (a) excludes equality. Therefore the Poisson entropy monotonicity gives the stronger conclusion

For an $n$-dimensional random vector with a density and finite differential entropy in bits, define its entropy power by $N(X)=(2\pi e{)}^{-1}{2}^{2h(X)/n}$. The entropy power inequality states that for independent such random vectors,Here the sum's differential entropy must be defined, with $+\infty$ permitted.

Since $g^{\prime }(x)>0$, the mean value theorem makes $g$ strictly increasing. Its image is an interval $I$, and its inverse on $I$ has derivative $1/g^{\prime }(g^{-1}(y))$. The density change of variables givesThis does not require $g$ to map onto all of $\mathbb{R}$. Taking logarithms at $y=g(X)$ and then expected values proves the differential entropy under an increasing transformation:The two finite expectations in the assumptions justify splitting the expectation and imply that the transformed differential entropy is finite.

To derive the product inequality, assume that $h(Y_i)$ and ${\mu }_i=\mathbb{E}{\log }_2{Y}_i$ are finite and that the differential entropy of the logarithmic sum is defined. Set $Z_i=\ln Y_i$, using natural logarithms for this transformation while measuring differential entropy in bits. On the positive half-line the derivative of $\ln y$ is $1/y$, so the same density argument givesThe $Z_i$ are independent random variables, and the one-dimensional entropy power inequality yieldsSince $Y_1{Y}_2=\exp (Z_1+Z_2)$, another change of variables givesMultiplying the entropy power inequality by $2^{2({\mu }_1+{\mu }_2)}$ proves the multiplicative entropy power inequality:

The printed positivity and density assumptions alone do not ensure that the quantities in this last formula exist. For a concrete example, let $T$ have the standard Cauchy distribution and put $Y=e^T$. Thenis a density, but $\mathbb{E}{\log }_{2}Y=({\log }_{2}e)\mathbb{E}T$ is undefined because its positive and negative parts both diverge. Two independent copies satisfy the printed hypotheses but leave ${\alpha }_1,{\alpha }_2$ undefined. The product inequality therefore needs the finiteness or well-definedness conditions used above.

Write $A_2(N,\delta )$ for the largest number of codewords in a binary length-$N$ code with minimum Hamming distance at least $\delta$. The volume of a Hamming ball does not depend on its centre and isFor the Hamming bound, put $r=\lfloor (\delta -1)/2\rfloor$. The radius-$r$ Hamming balls around distinct codewords are disjoint: a point belonging to two such balls would, by the triangle inequality for Hamming distance, put their centres at distance at most $2r<\delta$. Counting points in the binary cube therefore gives

For the Gilbert–Varshamov bound, choose a code maximal under inclusion among those with minimum Hamming distance at least $\delta$, for example by successively adding any allowable word. Its radius-$(\delta -1)$ Hamming balls cover the cube. Otherwise an uncovered word would be at distance at least $\delta$ from every codeword and could be added, contradicting maximality. ThusThe lower bound is an existence assertion about a suitable code, while the upper bound holds for every such code. Together they give

Let $h_2(x)=-x{\log }_{2}x-(1-x){\log }_2(1-x)$ be the binary entropy. For $\delta =\lfloor \lambda N\rfloor$,The assumed Hamming ball volume exponent applies also to any integer radii $d_N$ with $d_N/N\to \theta \in (0,1/2)$. Indeed, for each small $\epsilon >0$ these radii eventually lie between $\lfloor (\theta -\epsilon )N\rfloor$ and $\lfloor (\theta +\epsilon )N\rfloor$. monotonicity of $v_N$ sandwiches its normalized logarithm between limits $h_2(\theta -\epsilon )$ and $h_2(\theta +\epsilon )$; continuity then lets $\epsilon$ tend to zero. Consequently the asymptotic Gilbert–Varshamov bound and asymptotic Hamming bound have respective exponential scalesEquivalently, the optimal code rate satisfiesThese are bounds on the rate, not a claim that the optimal rate has a known limit or equals either endpoint.

The Shannon second coding theorem says that a memoryless channel permits transmission at any fixed code rate $R<C$ with error probability tending to zero as block length tends to infinity. Conversely, a sequence of codes with error probability tending to zero cannot have a limiting rate above $C$. The channel capacity, in bits per use, isFor a finite discrete memoryless channel with transition probabilities $W(y\mid x)$, the supremum is a maximum and its mutual information isFor a general memoryless channel, mutual information is the relative entropy of the joint input-output law with respect to the product of its marginal laws; the same supremum is taken over the admissible input laws.

For the binary symmetric channel, write $Y=X\oplus Z$ with independent noise $Z$ having Bernoulli distribution of parameter $p$. Given either input bit, the output conditional entropy is $h_2(p)$. ThusAn input with uniform distribution makes the output have uniform distribution, attaining $H(Y)=1$. The binary symmetric channel capacity is therefore

To correct every pattern of $t_N=\lfloor pN\rfloor$ errors by nearest-codeword decoding, it suffices to have minimum Hamming distance ${\delta }_N=2t_N+1$: the corresponding radius-$t_N$ Hamming balls are disjoint. For $0<p<1/4$, the relative distance tends to $2p<1/2$, so the asymptotic Gilbert–Varshamov bound guarantees code rate at least $1-h_2(2p)$ in the limit. Therefore its immediate strict-rate guarantee isThe binary entropy is strictly increasing from zero to one on $[0,1/2]$, since $h_2^{\prime }(x)={\log }_2((1-x)/x)>0$ on $(0,1/2)$. Let $a=h_2^{-1}(1-R)$ denote the inverse on this interval. The asymptotic condition becomes

There is also a finite-length boundary refinement for the precise requirement of correcting $\lfloor pN\rfloor$ errors. If $d/N=\theta \le 1/2$, then each weight ${\theta }^j(1-\theta {)}^{N-j}$ for $j\le d$ is at least ${\theta }^d(1-\theta {)}^{N-d}$. Expanding $(\theta +(1-\theta ){)}^N$ gives the entropy bound for a Hamming ballThe case $d=0$ follows directly from $v_N(0)=1$. Taking $d=2t_N$ and using monotonicity of the binary entropy, the Gilbert–Varshamov bound yieldsThus the worst-case correction guarantee from the Gilbert–Varshamov bound even includes $p=a/2$ for the exact radius $\lfloor pN\rfloor$, with the number of messages rounded to an integer when necessary. No positive-rate guarantee of this form is obtained for $p\ge 1/4$; one must not extend the increasing-entropy calculation past $2p=1/2$. Failure of this sufficient bound does not rule out better codes.

By contrast, the Shannon second coding theorem gives vanishing error probability on the binary symmetric channel wheneverThe factor of two comes from demanding disjoint correction balls for every error pattern of a prescribed weight. This is a worst-case distance requirement, and the Gilbert–Varshamov bound is itself only a sufficient existence bound. The Shannon second coding theorem controls the probability of decoding failure for the random channel; rare bad patterns may remain.

Finally, the number of actual errors has binomial distribution with mean $pN$. Correcting exactly its mean does not itself imply error probability tending to zero. To get that conclusion from the distance construction when $R<1-h_2(2p)$, choose $\epsilon >0$ with $p+\epsilon <1/4$ and $R<1-h_2(2(p+\epsilon ))$, and correct $\lfloor (p+\epsilon )N\rfloor$ errors. The weak law of large numbers then makes the probability of exceeding the correction radius tend to zero.

Work over the finite field ${\mathbb{F}}_2$. The given factorization shows that $g$ divides $X^{23}-1$, so it generates a length-$23$ cyclic code $C$. Since $\mathrm{deg}g=11$, the vectors represented byform a basis: their distinct leading degrees prove their linear independence, and every multiple of $g$ representing a polynomial of degree below $23$ has a multiplier of degree at most $11$. Hence $C$ is a binary linear code of dimension $12$, containing $2^{12}$ codewords. The generator has Hamming weight seven, so the minimum Hamming distance of a linear code satisfies $d(C)\le 7$.

The BCH bound used here is the following consecutive-root theorem. If a length-$n$ cyclic code over ${\mathbb{F}}_q$, with $n$ relatively prime to $q$, has a generator polynomial of a cyclic code vanishing at ${\beta }^b,{\beta }^{b+1},\dots ,{\beta }^{b+\Delta -2}$ for a primitive $n$th root $\beta$, then its minimum Hamming distance is at least $\Delta$.

Choose a root $\beta$ of $g$ in an algebraic closure of ${\mathbb{F}}_2$. The factorization implies ${\beta }^{23}=1$, while $g(1)=1$ in ${\mathbb{F}}_2$, so $\beta \ne 1$. As $23$ is prime, $\beta$ has order $23$. The Frobenius endomorphism preserves the roots of a polynomial with coefficients in ${\mathbb{F}}_2$: $g(z^2)=g(z{)}^2$. Thus every ${\beta }^{2^j}$ is a root. In particular, $2^8=256\equiv 3(\mathrm{mod}23)$ shows thatare roots of $g$. These four consecutive roots give $d(C)\ge 5$ by the BCH bound. A further argument is needed to exclude weights five and six.

Put $S(X)=1+X+\cdots +X^{22}$. Cancelling $X+1$ in the supplied factorization gives $g(X)g^{\mathrm{rev}}(X)=S(X)$. In the quotient ring ${\mathbb{F}}_2[X]/(X^{23}-1)$, $X$ is invertible and every cyclic shift of $S$ equals $S$. Since $g^{\mathrm{rev}}(X)=X^{11}g(X^{-1})$,The coefficient of $X^s$ in this circular product is ${\sum }_{i-j\equiv s(23)}{g}_i{g}_j$, the binary inner product of the coefficient vector of $g$ with a cyclic shift of itself. Every coefficient of $S$ is one. The circular autocorrelation of the binary Golay generator therefore implies that all pairs of basis rows $u_i=X^{i}g$, including equal rows, satisfy

Each $u_i$ has Hamming weight seven. Append its parity bit, which is one, and write ${\hat{u}}_i=(u_i,1)$. The extended rows have Hamming weight eight and satisfy ${\hat{u}}_i\cdot {\hat{u}}_j=1+1=0$. Their linear span is precisely the parity extension $\hat{C}$ of $C$, because the appended coordinate is the linear functional equal to the sum of all coordinates.

These extended generators produce a doubly even code. To prove this rather than assume it, useAll the extended generators have weights divisible by four. A sum of previous generators is orthogonal to the next generator, so the intersection size in this identity is even. Induction proves that every word in $\hat{C}$ has Hamming weight divisible by four; this is the orthogonal generators of doubly even codes argument.

An original word of weight five acquires a parity bit and has extended weight six, while a word of weight six acquires a zero parity bit and still has extended weight six. Both contradict divisibility by four. Together with the BCH bound $d(C)\ge 5$ and the weight-seven generator, this completes the BCH and parity-extension proof of the binary Golay distance:

Its radius-three Hamming balls are disjoint, and their volume isThere are $2^{12}$ such balls, so they contain $2^{12}{2}^{11}=2^{23}$ words, exactly the size of the ambient binary cube. They therefore cover the cube, with every word in exactly one ball. Hence