Sphere Packing Bound

We start to look at bounds on the size of codes.

Definition 1.11.1   We define $B_q(n,d)$ to be the maximum number of code words in a linear code over $\mathbb{F}_q^n$ of length $n$ and minimum weight $d$. $A_q(n,d)$ is the maximum number of code words in any arbitrary code over $\mathbb{F}_q^n$ of length $n$ and minimum weight $d$.

Theorem 1.11.2   Sphere Packing Bound

$$B_q(n,d) \leq A_q(n,d) \leq \frac{q^n}{\displaystyle \sum_{i=0}^t \left(\begin{array}{c} n i \end{array}\right) (q-1)^i }$$

where $t = \left\lfloor \frac{d-1}2 \right\rfloor$.

Proof. Let $\mathcal{C}$ be a code over $\mathbb{F}_q$ (possibly nonlinear) of length $n$ and minimum distance $d$ such that $\mathcal{C}$ contains $M$ codewords. By Theorem 1.11.2, the spheres of radius $t$ about these distinct codewords are disjoint. Define

$$\alpha := \sum_{i=0}^t \left(\begin{array}{c} n i \end{array}\right) (q-1)^i.$$

Then, $\alpha$ is the total number of vectors. Then, $M \alpha$ cannot be bigger than the number $q^n$ of vectors in $\mathbb{F}_q^n$. Hence, we must have

$$M \alpha \leq q^n$$

or

$$B_q(n,d) \leq A_q(n,d) \leq \frac{q^n}{\alpha}$$

which is precisely the sphere packing bound.
$\qedsymbol$

Definition 1.11.3   Let $\mathcal{C}$ be a $[n,k,d]_q$ code and $t = \left\lfloor \frac{d-1}2 \right\rfloor$. If the spheres of radius $t$ are pairwise disjoint and their union is the entire space $\mathbb{F}_q^n$, then the code $\mathcal{C}$ is said to be perfect.

Example: 1.12.2 in the book.
We know that $\mathcal{H}_{q,r}$ over $\mathbb{F}_q$ is an $[n,k,3]$ code where $n = (q^r - 1)/(q-1)$ and $k = n-r$ ($t = 1$). Then,

$$\frac{q^n}{\displaystyle \sum_{i=0}^t \left(\begin{array}{c} n i \end{array}\right) (q-i)^i} = \frac{q^n}{1 + n(q-1)} = \frac{q^n}{q^r} = q^k$$

Hence, the Hamming codes are perfect.

Theorem 1.11.4  

(i)

There exist perfect single error-correcting codes over $\mathbb{F}_q$ which are not linear and all codes have parameters corresponding to Hamming codes.

(ii)

The only non-trivial perfect multiple error-correcting codes have the same length, number of codewords, and minimum distance as either the $[23,12,7]$ Golay code or the $[11,6,5]$ ternary Golay code.

(iii)

Any binary possibly nonlinear code with $2^{12}$ (respectively $3^6$) vectors containing the $\textbf 0$ vector with length $23$ (resp. $11$) and minimum distance $7$ (resp. $5$) is equivalent to the [23,12,7] binary (resp. [11,6,5] ternary) Golay code.

Definition 1.11.5   The covering radius, $\rho(\mathcal{C})$ (linear code) is the smallest integer $s$ so that $\mathbb{F}_q^n$ is the union of spheres with radius $s$ centered at codewords. Equivalently,

$$\rho(\mathcal{C}) = \max_{\textbf x \in \mathbb{F}_q^n} \min_{\textbf c \in \mathcal{C}} d(\textbf x,\textbf c)$$

Note that $\rho(\mathcal{C}) \geq t$ and $\rho(\mathcal{C}) = t$ if and only if $\mathcal{C}$ is perfect

Definition 1.11.6   We say that $\mathcal{C}$ is quasi-perfect if $\rho(\mathcal{C}) = t+1$.

Theorem 1.11.7   Let $\mathcal{C}$ be linear and $H$ a parity check matrix.

(i)

$\rho(\mathcal{C})$ is the weight of the coset of largest weight.

(ii)

$\rho(\mathcal{C})$ is the smallest number such that every nonzero syndrome is a combination of $s$ or fewer columns of $H$, i.e., there exists a syndrome requiring $s$ columns.

Theorem 1.11.8   Let $\mathcal{C}= [n,k]_q$ code, $\hat \mathcal{C}$ the extension of $\mathcal{C}$, and $\mathcal{C}^*$ be the puncturing of $\mathcal{C}$ on any coordinate. Then,

(i)

$\mathcal{C}= \mathcal{C}\oplus \mathcal{C}_2 \Leftarrow \rho(\mathcal{C}) = \rho(\mathcal{C}_1) \rho(\mathcal{C}_2)$.

(ii)

$\rho(\mathcal{C}^*)$ is either $\rho(\mathcal{C})$ or $\rho(\mathcal{C})-1$.

(iii)

$\rho(\hat \mathcal{C})$ is either $\rho(\mathcal{C})$ or $\rho(\mathcal{C}) + 1$.

(iv)

If $q = 2$, then $\rho(\hat \mathcal{C}) = \rho(\mathcal{C}) + 1$.

(v)

Assume $\textbf x$ is a coset leader of $\mathcal{C}$. If $\textbf x' \in \mathbb{F}_q^n$, all of whose nonzero entries agree with $\textbf x$, then $\textbf x'$ is also a coset leader of $\mathcal{C}$. In particular, if there exists a coset with weight $s$, there exists a coset of any weight less than $s$.

Proof. Part $(iv)$. Let $\textbf x = (x_1, \ldots, x_n)$ be a coset leader; then define $\textbf x' = (x_1, \ldots, x_n, 1)$. It is enough to show that $\textbf x'$ is a coset leader. Let $\textbf c = (c_1, \ldots, c_n) \in \mathcal{C}$ and $\hat{\textbf c}$ be its extension.
If the weight of $\textbf c$ is even, then

$$\mathrm{wt}( \hat{\textbf c} + \textbf x') = \mathrm{wt}( \textbf c + \textbf x) + 1 \geq \mathrm{wt}(\textbf x) + 1$$

where the last inequality is because $\textbf x$ is a coset leader ( $\mathrm{wt}(\textbf x) \leq \mathrm{wt}(\textbf x + \textbf c)$ for all codewords).
If the weight of $\textbf c$ is odd, then

$$\mathrm{wt}( \hat{\textbf c} + \textbf x') = \mathrm{wt}(\textbf c + \textbf x)$$

By Theorem 1.4.3, we get that the $\mathrm{wt}(\textbf c + \textbf x)$ is odd if and only if $\mathrm{wt}(\textbf x )$ is even. In particular, the $\mathrm{wt}(\textbf c + \textbf x) \neq \mathrm{wt}(\textbf x)$. Therefore,

$$\mathrm{wt}(\textbf c + \textbf x) > \mathrm{wt}(\textbf x)$$

and

$$\mathrm{wt}(\hat{\textbf c} + \textbf x') = \mathrm{wt}(\textbf c + \textbf x) \geq \mathrm{wt}(\textbf x) + 1$$

Thus, the

$$\mathrm{wt}(\textbf x') = \mathrm{wt}(\textbf x) + 1 \leq \mathrm{wt}(\hat{\textbf c} + \textbf x')$$

for all $\hat{ \textbf c } \in \hat \mathcal{C}$. Hence, $\textbf x'$ is a coset leader. $\qedsymbol$

Example 1.12.7: Let $\mathcal{C}$ be generated by $G = [1,1,2]$. Then,

$$\mathcal{C}= \{ 000, 112, 221 \}$$

$d = 3$, $t = 1$.

$$\vert B_1(\textbf c) \vert = \sum_0^1 \left(\begin{array}{c} 3 \\ i \end{array}\right) 2^i = 1 + 6 = 7$$

However, let $(x_1, x_2, x_3) \in \mathbb{F}_3^3$. Note that each vector is less than two away from an element of $\mathcal{C}$, so $\rho(\mathcal{C}) = 2$.
Now, let's consider the extension of $\mathcal{C}$, $\hat \mathcal{C}$. This is generated by $\hat G = [1122]$:

$$\mathcal{C}= \{ 0000, 1122, 2211 \}$$

Here, $d = 4$ and $t = 1$. We can tell that $\rho(\hat \mathcal{C}) > 1$ because $\rho(\mathcal{C}) = 2$. Suppose that $(x_1, x_2, x_3, x_4)$ is not within $2$ of $0000$ and $1122$. By exhaustion, we can see that this cannot happen.

Wednesday, 6-15-2005: