Coding Constructions with Hamming Codes

Why Use Binary Codes in Lower Bounds?

A metric lower bound often needs many parameter values that are well separated from one another. A binary cube supplies a convenient finite set of candidates, but using the entire cube does not ensure a large minimum separation: two cube points may differ in only one coordinate. A code is a subset chosen to avoid such close pairs. The key fact is that a simple greedy selection produces a code whose size can be bounded from below by counting how many cube points each selected codeword can exclude.

The construction is purely combinatorial. It does not by itself say that the corresponding statistical experiments are difficult to distinguish. For a statistical lower bound, one must separately control the distributions associated with the selected parameters, as in Fano’s method for metric estimation.

Hamming Distance and Codes

Definition: For $u,v\in\{0,1\}^m$, their Hamming distance is $$ d_H(u,v)=\sum_{i=1}^m \mathbf{1}\{u_i\ne v_i\}. $$ A binary code $C$ of length $m$ is any subset of $\{0,1\}^m$. Its minimum distance is $\min_{u\ne v,\;u,v\in C}d_H(u,v)$, when $C$ has at least two elements. Saying that $C$ has minimum distance at least $d$ means every two distinct codewords differ in at least $d$ coordinates.

A Hamming ball of radius $t$, centered at $u$, contains the cube points at distance at most $t$ from $u$. Its size does not depend on the center: to make a point at distance $j$, choose the $j$ coordinates to flip. Thus the volume is

V(m,t)=\sum_{j=0}^{t}\binom{m}{j}.

The central idea is to choose one point, exclude all points too close to it, and repeat. Each choice removes at most one Hamming ball’s worth of candidates.

The Greedy Packing Bound

Theorem (Greedy Hamming packing bound): For integers $m\ge 1$ and $1\le d\le m+1$, there exists a binary code $C\subseteq\{0,1\}^m$ such that every two distinct codewords are at distance at least $d$, and $$ |C|\ge \frac{2^m}{\displaystyle\sum_{j=0}^{d-1}\binom{m}{j}}. $$ Since $|C|$ is an integer, this also gives $|C|\ge \left\lceil 2^m/V(m,d-1)\right\rceil$.

Proof. Begin with all $2^m$ cube points available. While any points remain, select one as a codeword and remove it and every still-available point within Hamming distance $d-1$ of it. Because the cube is finite, this procedure stops. Let $M$ be the number of selected points. When a point is selected, every point removed at that step lies in a ball of radius $d-1$, so at most $V(m,d-1)$ points are removed. At termination every cube point has been removed. Therefore

2^m\le M V(m,d-1), \qquad M\ge \frac{2^m}{V(m,d-1)}.

If two selected points were at distance at most $d-1$, the later one would have been removed when the earlier one was selected. This contradicts the fact that it was selected. Thus every distinct pair is at distance at least $d$, and the selected set has the claimed size. $\square$

This proof gives a bound for a code that the algorithm constructs; it does not claim that the code is the largest possible. The bound can be conservative, but it requires no search for an optimal code.

Worked Example: A Small Code of Length Five

Take $m=5$ and require minimum distance $d=3$. Each selected word removes a ball of radius $d-1=2$, with volume

V(5,2)=\binom{5}{0}+\binom{5}{1}+\binom{5}{2} =1+5+10=16.

There are $2^5=32$ words in total, so the greedy bound guarantees

|C|\ge \left\lceil \frac{32}{16}\right\rceil=2.

For instance, the words $00000$ and $11111$ differ in all five positions, so their distance is $5$, which is at least $3$. This verifies directly that a two-word code with the required separation exists.

Worked Example: Length Eight and Distance Three

For $m=8$ and $d=3$, again use balls of radius $2$. Their volume is

V(8,2)=\binom{8}{0}+\binom{8}{1}+\binom{8}{2} =1+8+28=37.

The cube has $2^8=256$ words. The packing bound therefore gives

|C|\ge \left\lceil \frac{256}{37}\right\rceil =\lceil 6.9189\ldots\rceil=7.

Thus a greedy procedure is guaranteed to select at least seven words, any two of which differ in at least three coordinates. The conclusion is a guarantee, not a claim that seven is the maximum possible code size.

An Entropy Bound for Hamming-Ball Volume

For larger $m$, evaluating every term of the ball-volume sum may be inconvenient. The binary entropy function gives a compact upper bound on that volume.

Definition: For $q\in(0,1)$, the binary entropy is $$ h_2(q)=-q\log_2 q-(1-q)\log_2(1-q), $$ with $h_2(0)=h_2(1)=0$ by continuity.

Theorem (Entropy bound for Hamming balls): If $t$ is an integer with $0\le t\le m/2$, then $$ \sum_{j=0}^{t}\binom{m}{j}\le 2^{m h_2(t/m)}. $$ Consequently, if $d-1\le m/2$, there is a binary code of length $m$, minimum distance at least $d$, and size at least $$ 2^{m\left[1-h_2((d-1)/m)\right]}. $$

Proof. If $t=0$, the sum is $1$, and the bound holds because $h_2(0)=0$. Now suppose $1\le t\le m/2$, and put $q=t/m$. For every $j\le t$, since $0<q\le 1/2$,

q^j(1-q)^{m-j}\ge q^t(1-q)^{m-t}.

Indeed, the ratio of the left side to the right side is $\big((1-q)/q\big)^{t-j}$, which is at least $1$. Multiply the inequality by $\binom{m}{j}$, sum over $j=0,\ldots,t$, and use the binomial theorem:

q^t(1-q)^{m-t}\sum_{j=0}^{t}\binom{m}{j} \le \sum_{j=0}^{t}\binom{m}{j}q^j(1-q)^{m-j} \le \sum_{j=0}^{m}\binom{m}{j}q^j(1-q)^{m-j} =1.

Rearranging gives

\sum_{j=0}^{t}\binom{m}{j} \le \frac{1}{q^t(1-q)^{m-t}} =2^{m h_2(q)}.

The last equality follows by substituting $q=t/m$ into the definition of $h_2$. Combining this ball-volume bound with the greedy packing bound at $t=d-1$ gives the stated code-size bound. $\square$

Worked Example: Length One Hundred and Distance Twenty-One

Let $m=100$ and require distance $d=21$, so the relevant ball radius is $t=20$, with $t/m=1/5$. The entropy bound yields

|C|\ge 2^{100[1-h_2(1/5)]}.

Using

h_2(1/5) =-\frac15\log_2(1/5)-\frac45\log_2(4/5) \approx 0.7219280949,

the exponent is $100[1-h_2(1/5)]\approx 27.80719051$. The rigorous bound is therefore

|C|\ge \left\lceil 2^{100[1-h_2(1/5)]}\right\rceil,

which is approximately $2.35\times 10^8$ codewords. The exact expression inside the ceiling is the bound; the decimal exponent and code size are only approximations. In particular, rounding the exponent upward before applying the power would not preserve a lower bound.

Turning Codewords into Separated Parameters

The reason these codes are useful in metric estimation is that Hamming distance can translate directly into distance between parameter values. For example, for a fixed $a>0$, associate to each $u\in\{0,1\}^m$ the vector $\theta_u=a u\in\mathbb{R}^m$. For $1\le p<\infty$, the usual $\ell_p$ distance satisfies

\|\theta_u-\theta_v\|_p =\left(\sum_{i=1}^m |a u_i-a v_i|^p\right)^{1/p} =a\,d_H(u,v)^{1/p}.

Consequently, if $C$ has minimum Hamming distance at least $d$, then the parameter set $\{\theta_u:u\in C\}$ is separated by at least $a d^{1/p}$ in $\ell_p$ distance. For example, in $\ell_2$, that separation is at least $a\sqrt d$. This supplies a large finite collection of well-separated candidates, the geometric ingredient used in packing-based lower bounds.

A code’s cardinality and separation address only the geometry of the parameter set. To apply a testing inequality, one must also verify that the data distributions indexed by those parameters are sufficiently similar under the divergence or information measure being used. A large code alone cannot establish that statistical condition.

Common Pitfalls

Using the wrong ball radius. To guarantee minimum distance at least $d$, delete points within radius $d-1$, not radius $d$. Deleting radius $d$ would give the stronger separation $d+1$, but a weaker size guarantee.
Confusing a lower bound with an optimum. The greedy argument guarantees at least the stated number of codewords; it does not determine the maximum possible code size.
Rounding an exponent upward in a lower bound. If the derived bound is $2^A$ and $A$ is approximated by a decimal, replacing $A$ by a rounded-up value can increase the claimed lower bound. Keep the exact exponent inside the ceiling, and label decimal evaluations as approximations.
Assuming separation proves a statistical lower bound. Separation makes estimation errors distinguishable geometrically, but the associated distributions must also satisfy the required testing or information bound.

Key takeaway: Greedy selection produces a code with minimum distance $d$ by removing Hamming balls of radius $d-1$. Counting those balls gives a finite-volume bound, and binary entropy gives a convenient exponential version when the radius is at most half the code length.

Check Your Understanding

Use the definitions and arguments above to answer the following.

For length $m=6$ and required distance $d=3$, what radius is deleted at each greedy step, and what is the corresponding ball volume?
Why does selecting a point and deleting its radius-$(d-1)$ ball ensure that later selected points are at distance at least $d$?
For $m=40$ and $d=9$, state the entropy exponent in the code-size bound, and check that the theorem’s radius condition holds.
If binary codewords index vectors $a u$ in $\ell_2$, what separation follows from minimum Hamming distance at least $d$?
What additional statistical property, beyond code size and parameter separation, is needed to use the code in a Fano lower bound?