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

Use a fixed logarithm base $b>1$, and write $c={\log }_{b}e=1/\ln b$. All relative entropies below use this same base. Adopt $0\log (0/q)=0$ and $p\log (p/0)=+\infty$ for $p>0$.

For Gibbs inequality, if $q(x)=0<p(x)$ at some point, the relative entropy is infinite and the required conclusion is immediate. Otherwise let $S=\{x:p(x)>0\}$. The elementary inequality $\ln u\le u-1$, with equality only at $u=1$, gives, for every $x\in S$,ConsequentlyThis argument applies to a countable discrete probability distribution too: the difference between the two sides of the pointwise inequality is nonnegative, and the negative part of the entropy summand is bounded by $cq(x)$, hence summable. Thus no subtraction of divergent series is involved. Equality forces both ${\sum }_{S}q=1$ and equality in every pointwise inequality; hence $q(x)=p(x)$ on $S$ and $q=0=p$ off $S$. Conversely $p=q$ plainly gives zero. Therefore $\boxed{D(p\Vert q)\ge 0,D(p\Vert q)=0⟺p=q}$.

For the log-sum inequality, set $F={\sum }_{A}f$, $G={\sum }_{A}g$, and normalize to the probability distributions $p_A=f/F$, $q_A=g/G$. When $A$ is nonempty, positivity ensures $F,G>0$, and direct expansion givesThus normalization reduces the log-sum inequality to Gibbs inequality. Equality holds exactly when $f/F=g/G$. The empty-set case is the zero identity under the usual zero-mass convention.

For the final bound, partition the alphabet using $A=\{x:p(x)>q(x)\}$ and put $a=p(A)$, $d=q(A)$. Since the total signed difference is zero,Apply the log-sum inequality separately to $A$ and its complement. The same normalization argument works for countable sets of finite total mass, using the countable Gibbs inequality just proved. It yields the binary partition bound for relative entropyZero block masses are interpreted by the stated conventions; a positive mass divided by zero makes the bound infinite. The given binary estimate now impliesThis is Pinsker's inequality. Equivalently, for the total variation distance $\Vert p-q{\Vert }_{\mathrm{TV}}=\frac{1}{2}{\sum }_x|p(x)-q(x)|$, the bound is $D(p\Vert q)\ge 2{\log }_{b}e\Vert p-q{\Vert }_{\mathrm{TV}}^2$. The factor ${\log }_{b}e$ keeps the statement valid for either bits or natural-logarithm units.

For discrete random variables, write $p(u,v)$ for the joint probability mass function and $p_U(u)$ for its marginal. The conditional entropy is the average of the entropies of the conditional distributions:Conditional distributions at zero-probability values of $u$ can be chosen arbitrarily; they contribute nothing. Here $h$ denotes Shannon entropy, with one common logarithm base and $0\log 0=0$.

For $p(u,v)>0$, use $\log p(u,v)=\log p_U(u)+\log p(v\mid u)$ and sum with weight $-p(u,v)$. Summing out $v$ in the first term givesFor countable alphabets, the entropy contributions are nonnegative, so the equality remains valid with extended values by summing nonnegative terms. Applying this identity successively to the prefix $(X_1,\dots ,X_{i-1})$ and $X_i$ proves the chain rule for information entropy:For $i=1$, the conditioning tuple is empty and the term is $h(X_1)$.

For the subset inequalities, first suppose the marginal entropies are finite, so all joint entropies below are finite by the chain rule and the assumed conditioning reduces entropy property. Put $H=h(X_1,\dots ,X_n)$, and let $H_{-i}$ be the joint entropy with coordinate $i$ omitted. Apply the two-variable chain rule in the order $(X_{[n]\setminus \{i\}},X_i)$ to getThe inequality holds because the prefix conditioning set is contained in the set of all other coordinates. Summing over $i$ and using the chain rule givesThis proves Han's entropy inequality. In terms of the normalized subset entropy, $h_n^{(n)}=H/n$ and $h_{n-1}^{(n)}={\sum }_i{H}_{-i}/[n(n-1)]$, hence $\boxed{h_n^{(n)}\le h_{n-1}^{(n)}}$ for $n\ge 2$.

Apply the same result to each $k$-element coordinate set $S$. It givesWhen this is summed over all $k$-subsets, each fixed $(k-1)$-subset $T$ occurs once for each possible added coordinate, namely $n-k+1$ times. ThereforeSubstitute ${\sum }_{|S|=k}h(X_S)=k\left(\genfrac{}{}{0ex}{}{n}{k}\right)h_k^{(n)}$ and the analogous identity at $k-1$. The binomial coefficient identity $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=(n-k+1)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$ cancels the common positive factor and givesThis is the monotonicity of normalized subset entropies, obtained from the local $k$-coordinate inequality by explicit counting.

If some marginal entropy is infinite, each subset average contains at least one subset including that coordinate. The entropy of such a subset is at least that marginal entropy, by the nonnegative conditional-entropy chain rule, so every $h_k^{(n)}$ is infinite. The inequalities then hold in the extended sense. Otherwise the finite-entropy proof applies. For independent random variables the averages are all $n^{-1}{\sum }_{i}h(X_i)$; repeated copies of one variable instead give $h_k^{(n)}=h(X_1)/k$, illustrating the entropy reduction caused by redundancy.

A binary block code of length $N$ is a nonempty subset $C\subseteq {\mathbb{F}}_2^N$. Its size is $|C|$, the number of distinct codewords. The Hamming distance $d(x,y)$ counts coordinates at which two words differ. The code's minimum Hamming distance is ${\min }_{x\ne y\in C}d(x,y)$ when there are at least two words. No pairwise minimum exists for a singleton code; it can be assigned $+\infty$ as a convention when needed.

A binary linear code is a vector subspace of ${\mathbb{F}}_2^N$. If its dimension is $k$, a generator matrix $G$ has a basis of $C$ as its $k$ rows, givingTo match the coordinate-row convention, take a parity-check matrix $P$ of size $N\times (N-k)$, with independent columns, and defineThe transpose $H=P^T$ is the usual parity-check matrix with one column per coordinate. By rank-nullity theorem, the displayed kernel has dimension $k$. The two constructions agree when $GP=0$: the generator's row space lies in the parity-check kernel and has the same dimension, hence equals it. Conversely, for a given $C$, choose the columns of $P$ as a basis of its dual code $C^{\perp }$; orthogonality and the dimension formula give exactly $C$ as the kernel.

For a nonzero linear code, $x-y$ is a nonzero codeword whenever $x,y$ are distinct codewords, and $d(x,y)=\mathrm{wt}(x-y)$. Conversely compare any nonzero codeword with zero. Thus the minimum Hamming distance of a linear code is the least nonzero Hamming weight.

Write $P_i$ for the row associated with coordinate $i$. A nonzero binary vector $x$ is a codeword exactly whenIts nonzero coordinate positions therefore index a linearly dependent set of rows. Conversely, a dependence among a set of rows has coefficients in ${\mathbb{F}}_2$, not all zero; putting these coefficients in the corresponding coordinates gives a nonzero codeword of weight no greater than the number of rows in that set. Taking minima in both directions proves the parity-check dependencies determine minimum distance criterion:Rows here are indexed by positions: equal row vectors at different positions are two distinct members of the indexed family. In the usual matrix convention, the same result refers to columns of $H=P^T$. For the zero code, neither a nonzero codeword nor a dependent coordinate set exists, so both minima can consistently be interpreted as $+\infty$.

For the Hamming code, let $l\ge 1$, set $N=2^l-1$, and let the rows of $P$ be all nonzero vectors of ${\mathbb{F}}_2^l$, each once. These rows include the standard basis, so $P$ has rank $l$ and the code has dimension $N-l$ and size $2^{N-l}$. There is no dependence involving one row, because no row is zero, or two rows, because no rows are equal. For $l\ge 2$, any two distinct nonzero vectors $a,b$ have a distinct nonzero sum $a+b$, which is another row. These three rows sum to zero. Thus $d(C)=3$ for $l\ge 2$.

The perfectness of a Hamming code also has a direct decoding proof. Given any received word $y$, its syndrome is $yP\in {\mathbb{F}}_2^l$. A zero syndrome means $y\in C$. Otherwise it equals exactly one row $P_i$. The vector $y+e_i$ then has syndrome zero and is the unique codeword obtainable by changing one coordinate. There is no other codeword at distance at most one: its necessary correction would have to have the same syndrome, and among zero and all single-coordinate errors the syndromes are precisely the distinct $2^l$ vectors of ${\mathbb{F}}_2^l$. Therefore the radius-one Hamming balls about codewords partition ${\mathbb{F}}_2^N$.

Equivalently, each ball contains $1+N=2^l$ words; disjointness and $2^{N-l}{2}^l=2^N$ show that none are uncovered. Hence every nondegenerate binary Hamming code is a perfect single-error-correcting code. For $l=1$, the construction is the singleton code $\{0\}\subseteq {\mathbb{F}}_2$, whose one radius-one ball is also the whole ambient space. This deals with the degenerate boundary without falsely claiming its minimum distance is three.

Let the $r$ distinct codewords be $x^{(1)},\dots ,x^{(r)}\in {\mathbb{F}}_2^N$. No linearity assumption is needed. Sum their Hamming distances over unordered distinct pairs:Each summand is at least the minimum Hamming distance $\delta$, so $S\ge \delta r(r-1)/2$.

For coordinate $a$, let $m_a$ be the number of codewords whose $a$th bit is $1$. Exactly $m_a(r-m_a)$ unordered pairs differ at that coordinate. Summing coordinate contributions givessince $m_a(r-m_a)=r^2/4-(m_a-r/2{)}^2$. Combining the two bounds and dividing by $r>0$ gives $2\delta (r-1)\le Nr$, hence $r(2\delta -N)\le 2\delta$. Under $2\delta >N$, division is legitimate, proving the Plotkin boundBecause $r$ is an integer, it also satisfies the floor of the right-hand side. The binary alphabet is essential to the coordinate count; this proof applies to arbitrary binary block codes, not just linear ones.

Use the homogeneous weight enumerator conventionThus $s$ records ones, $t$ records zeros, and the ordinary weight enumerator is $W_C(z,1)$. For a binary linear code $C$ of dimension $k$ and its dual code $C^{\perp }$, the MacWilliams identity isor, equivalently, $W_C(s,t)=|C^{\perp }{|}^{-1}{W}_{C^{\perp }}(t-s,t+s)$. The second form applies the first to the dual and uses $(C^{\perp }{)}^{\perp }=C$.

One can verify the variable order directly from the character identity $1_{C^{\perp }}(y)=|C{|}^{-1}{\sum }_{x\in C}(-1{)}^{x\cdot y}$. If $y$ is not orthogonal to $C$, translation by a codeword having odd inner product pairs positive and negative terms, giving zero; otherwise all terms are one. After multiplying by $s^{\mathrm{wt}(y)}{t}^{N-\mathrm{wt}(y)}$ and summing over $y$, coordinate $j$ contributes $t+s$ when $x_j=0$, and $t-s$ when $x_j=1$. Their product is exactly the stated substitution.

For a Hamming code with $N=2^l-1$, its dual is the binary simplex code, generated by the $l$ rows of the usual parity-check matrix $H=P^T$. There are $2^l$ dual words. A nonzero message $a\in {\mathbb{F}}_2^l$ produces the evaluations $a\cdot v$ as $v$ runs over all nonzero vectors of ${\mathbb{F}}_2^l$. Exactly $2^{l-1}$ of them are one: the nonzero linear functional $v\mapsto a\cdot v$ takes each value equally often on the whole vector space, and removing zero removes a zero value only. This proves the constant weight of a binary simplex code.

Put $m=2^{l-1}$, so $N-m=m-1$. The dual enumerator is therefore $t^N+(2^l-1)s^m{t}^{m-1}$. Applying the MacWilliams identity gives the Hamming code weight enumeratorIn one variable this isFor example, $l=3$ gives $1+7z^3+7z^4+z^7$; $l=2$ gives $1+z^3$. For $l=1$, the expression is $1$, agreeing with the singleton code. Setting $s=t=1$ in the homogeneous formula gives $2^{N-l}$, the correct number of codewords.