The Volume of Hamming Ball

Given a finite set $\Sigma$ with size $q = |\Sigma|$, and a integer $n \in \mathbb{N}_+$, a code $C \subseteq \Sigma^n$ is a set of strings that are far apart. The set $\Sigma$ is called the alphabet of the code, and $n$ is called the block length of the code. Strings in $C$ are called codewords.

For $x, y \in \Sigma^n$, define their Hamming distance as

The distance $\Delta(C)$ (or $d$ for a shorthand) of $C$, is defined as the minimum distance between two different codes words in $C$:

If we store a code $x \in C$, and up to $(d - 1) / 2$ bits of $x$ are corrupted, then we can still recover $x$. Denote the ball centered at $x$ with radius $r \in \mathbb{R}_+$ as

Fact. For $x \in \Sigma^n$, $r \in \mathbb{R}_+$, the size (volume) of the ball $\mathcal{B}(x, r)$ is independent of $x$ and is given by

$$\mathbb{Vol}(r) \doteq | \mathcal{B}(x, r) | = \sum_{i = 0}^{ \lfloor r \rfloor } \binom{n}{i} (q - 1)^i.$$

If the code $C$ has distance $\Delta(C) = d$, then the balls $\{ \mathcal{B}(x, (d - 1) / 2) : x \in C \}$ should be disjoint. Therefore, we can upper bound the size $|C|$ in terms of the size of $\Sigma^n$, and the volume of the balls.

Theorem (Hamming Bound). Let $C$ be a code with distance $d \ge 3$. Then

$$|C| \le \frac{q^n }{ \mathbb{Vol} \Big( (d - 1) / 2 \Big) }.$$

We are going to prove an estimate of the volume.

Theorem (Estimate of Volume). Let $r \in \mathbb{R}_+$. When $r \le n - n / q$,

$$q^{ n h_q ( r / n) - O( \log n) } \le \mathbb{Vol} (r) \le q^{ n h_q ( \lfloor r \rfloor / n)},$$

where

$$\begin{aligned} h_q (\epsilon) &\doteq (1 - \epsilon) \log_q \left( \frac{1}{1 - \epsilon} \right) + (q - 1) \frac{\epsilon}{q - 1} \log_q \left( \frac{q - 1}{ \epsilon } \right) \\ &= (1 - \epsilon) \log_q \left( \frac{1}{1 - \epsilon} \right) + \epsilon \log_q \left( \frac{q - 1}{ \epsilon } \right). \end{aligned}$$

When $q = 2$, we have the following corollary.

Corollary. Let $r \in \mathbb{R}_+$. When $r \le n / 2$,

$$2^{ n \cdot h_2 ( r / n) - O( \log n) } \le \sum_{i = 0}^{ \lfloor r \rfloor } \binom{n}{i} \le 2^{ n \cdot h_2 ( \lfloor r \rfloor / n)},$$

where $h_2( \cdot )$ is the Shannon's entropy function.

Observe that by concavity of $\log_q (\cdot)$, we have

The inequality holds with equality when $h_q(\epsilon)$ is maximized, i.e., when $1 - \epsilon = \epsilon / (q - 1)$, i.e., $1 - \epsilon = 1 / q$.

Rate of the Code

Based on the theorems of Hamming bound, and the estimate of the volume, we have

The last $\Longleftrightarrow$ holds, since

and

Define the rate of the code $R = \frac{ \log_q |C| }{ n }$, and relative distance of the code as $\delta = \frac{d}{n}$, we get

$$R + h_q( \delta / 2) \le 1 + O\left( \frac{\log_q n }{n} \right).$$

In what's follows, we prove the inequalities for volume estimation. WLOG, we assume that $r$ is an integer.

Upper Bound

Theorem. For $0 \le r \le n \cdot (1 - 1 / q)$, it holds that $\mathbb{Vol} (r) \le q^{n h_q(r / n)}$.

Algebraic Approach

where the last inequality follows from that

as $r / n \le 1 - 1 / q = q / (q - 1)$.

Finally, let $\epsilon \doteq \frac{r}{n}$, we have

which proves the claim.

Entropy

We rely on sub-additivity of entropy.

Let $X$ and $Y$ be discrete random variables, then

1. $H( X, Y ) \le H(X) + H(Y)$.
2. $H(X | Y) \le H(X)$.

Proof. Consider the ball $\mathcal{B}(1^n, r)$, and a uniform random point $X = (X_1, ..., X_n)$ in the ball $\mathcal{B}(1^n, r)$. Its entropy is

We write $Y = X_1$. By sub-additivity of entropy and by symmetry,

Let $\epsilon \doteq \Pr[ Y \neq 1]$ be the probability that $Y$ is not $1$. Further, by symmetry, $\Pr[Y = i]$ has equal probability for each $i \neq 1$. Hence,

where then entropy of $Y$ is maximized when $Y$ is uniform of the elements that are not 1. Further, it can be verified that $\epsilon < r / n$. As $h_q (\epsilon)$ increases for $\epsilon < 1 - 1 / q$, hence

$\square$

Lower Bound

Theorem. For $r \in \mathbb{R}_+$, it holds that $\mathbb{Vol} (r) \ge q^{ n h_q ( r / n) - O( \log n) }$.

We rely on the Stirling's approximation.

Fact. For $n \in \mathbb{N}_+$, $\sqrt{2 \pi n} \left(\frac{n}{e} \right)^n \le n! \le e \sqrt{n} \left(\frac{n}{e} \right)^n$.

Proof. First, assume that $r \in \mathbb{N}_+$. It holds that

Assume that $r \in \mathbb{R}_+$. Let $r' = \lfloor r \rfloor$. Then

But

$\square$

Hence, the upper bound is rather tight.

Reference

[1] Anup Rao, Coding Theory Lecture 3: The Volume Bound and Finite Fields