Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

24.3 Bounds on General Codes

We have shown that an $(n, M, d)$ $(n, M, d)$ code can correct $t$ $t$ errors if $d \geq 2 t + 1$ $d \geq 2 t + 1$ . Hence, we would like the minimum distance $d$ $d$ to be large so that we can correct as many errors as possible. But we also would like for $M$ $M$ to be large so that the code rate $R$ $R$ will be as close to $1$ $1$ as possible. This would allow us to use bandwidth efficiently when transmitting messages over noisy channels. Unfortunately, increasing $d$ $d$ tends to increase $n$ $n$ or decrease $M$ $M$ .

In this section, we study the restrictions on $n$ $n$ , $M$ $M$ , and $d$ $d$ without worrying about practical aspects such as whether the codes with good parameters have efficient decoding algorithms. It is still useful to have results such as the ones we’ll discuss since they give us some idea of how good an actual code is, compared to the theoretical limits.

First, we treat upper bounds for $M$ $M$ in terms of $n$ $n$ and $d$ $d$ . Then we show that there exist codes with $M$ $M$ larger than certain lower bounds. Finally, we see how some of our examples compare with these bounds.

24.3.1 Upper Bounds

Our first result was given by R. Singleton in 1964 and is known as the Singleton bound.

Theorem

Let $C$ $C$ be a $q$ $q$ -ary $(n, M, d)$ $(n, M, d)$ code. Then

M \leq q^{n - d + 1} .

$M \leq q^{n - d + 1} .$

Proof. For a codeword $c = (a_{1}, \dots, a_{n})$ $c = (a_{1}, \dots, a_{n})$ , let $c^{'} = (a_{d}, \dots, a_{n})$ $c^{'} = (a_{d}, \dots, a_{n})$ . If $c_{1} \neq c_{2}$ $c_{1} \neq c_{2}$ are two codewords, then they differ in at least $d$ $d$ places. Since ${c_{1}}^{'}$ ${c_{1}}^{'}$ and ${c_{2}}^{'}$ ${c_{2}}^{'}$ are obtained by removing $d - 1$ $d - 1$ entries from $c_{1}$ $c_{1}$ and $c_{2}$ $c_{2}$ , they must differ in at least one place, so ${c_{1}}^{'} \neq {c_{2}}^{'}$ ${c_{1}}^{'} \neq {c_{2}}^{'}$ . Therefore, the number $M$ $M$ of codewords $c$ $c$ equals the number of vectors $c^{'}$ $c^{'}$ obtained in this way. There are at most $q^{n - d + 1}$ $q^{n - d + 1}$ vectors $c^{'}$ $c^{'}$ since there are $n - d + 1$ $n - d + 1$ positions in these vectors. This implies that $M \leq q^{n - d + 1}$ $M \leq q^{n - d + 1}$ , as desired.

Corollary

The code rate of a $q$ $q$ -ary $(n, M, d)$ $(n, M, d)$ code is at most $1 - \frac{d - 1}{n}$ $1 - \frac{d - 1}{n}$ .

Proof. The corollary follows immediately from the definition of code rate.

The corollary implies that if the relative minimum distance $d / n$ $d / n$ is large, the code rate is forced to be small.

A code that satisfies the Singleton bound with equality is called an MDS code (maximum distance separable). The Singleton bound can be rewritten as $q^{d} \leq q^{n + 1} / M$ $q^{d} \leq q^{n + 1} / M$ , so an MDS code has the largest possible value of $d$ $d$ for a given $n$ $n$ and $M$ $M$ . The Reed-Solomon codes (Section 24.9) are an important class of MDS codes.

Before deriving another upper bound, we need to introduce a geometric interpretation that is useful in error correction. A Hamming sphere of radius $t$ $t$ centered at a codeword $c$ $c$ is denoted by $B (c, t)$ $B (c, t)$ and is defined to be all vectors that are at most a Hamming distance of $t$ $t$ from the codeword $c$ $c$ . That is, a vector $u$ $u$ belongs to the Hamming sphere $B (c, t)$ $B (c, t)$ if $d (c, u) \leq t$ $d (c, u) \leq t$ . We calculate the number of vectors in $B (c, t)$ $B (c, t)$ in the following lemma.

Lemma

A sphere $B (c, r)$ $B (c, r)$ in $n$ $n$ -dimensional $q$ $q$ -ary space has

(\binom{n}{0}) + (\binom{n}{1}) (q - 1) + (\binom{n}{2}) (q - 1)^{2} + \dots + (\binom{n}{r}) (q - 1)^{r}

$(\binom{n}{0}) + (\binom{n}{1}) (q - 1) + (\binom{n}{2}) (q - 1)^{2} + \dots + (\binom{n}{r}) (q - 1)^{r}$

elements.

Proof. First we calculate the number of vectors that are a distance $1$ $1$ from $c$ $c$ . These vectors are the ones that differ from $c$ $c$ in exactly one location. There are $n$ $n$ possible locations and $q - 1$ $q - 1$ ways to make an entry different. Thus the number of vectors that have a Hamming distance of $1$ $1$ from $c$ $c$ is $n (q - 1)$ $n (q - 1)$ . Now let’s calculate the number of vectors that have Hamming distance $m$ $m$ from $c$ $c$ . There are $(\binom{n}{m})$ $(\binom{n}{m})$ ways in which we can choose $m$ $m$ locations to differ from the values of $c$ $c$ . For each of these $m$ $m$ locations, there are $q - 1$ $q - 1$ choices for symbols different from the corresponding symbol from $c$ $c$ . Hence, there are

(\binom{n}{m}) (q - 1)^{m}

$(\binom{n}{m}) (q - 1)^{m}$

vectors that have a Hamming distance of $m$ $m$ from $c$ $c$ . Including the vector $c$ $c$ itself, and using the identity $(\binom{n}{0}) = 1$ $(\binom{n}{0}) = 1$ , we get the result:

(\binom{n}{0}) + (\binom{n}{1}) (q - 1) + (\binom{n}{2}) (q - 1)^{2} + \dots + (\binom{n}{r}) (q - 1)^{r} .

$(\binom{n}{0}) + (\binom{n}{1}) (q - 1) + (\binom{n}{2}) (q - 1)^{2} + \dots + (\binom{n}{r}) (q - 1)^{r} .$

We may now state the Hamming bound, which is also called the sphere packing bound.

Theorem

Let $C$ $C$ be a $q$ $q$ -ary $(n, M, d)$ $(n, M, d)$ code with $d \geq 2 t + 1$ $d \geq 2 t + 1$ . Then

M \leq \frac{q^{n}}{\sum_{j = 0}^{t} (\begin{matrix} n \\ j \end{matrix}) {(q - 1)}^{j}} .

$M \leq \frac{q^{n}}{\sum_{j = 0}^{t} (\begin{matrix} n \\ j \end{matrix}) {(q - 1)}^{j}} .$

Proof. Around each codeword $c$ $c$ we place a Hamming sphere of radius $t$ $t$ . Since the minimum distance of the code is $d \geq 2 t + 1$ $d \geq 2 t + 1$ , these spheres do not overlap. The total number of vectors in all of the Hamming spheres cannot be greater than $q^{n}$ $q^{n}$ . Thus, we get

\begin{matrix} (number of codewords) \times (number of elements per sphere) \\ = M \sum_{j = 0}^{t} (\begin{matrix} n \\ j \end{matrix}) {(q - 1)}^{j} \leq q^{n} . \end{matrix}

$\begin{matrix} (number of codewords) \times (number of elements per sphere) \\ = M \sum_{j = 0}^{t} (\begin{matrix} n \\ j \end{matrix}) {(q - 1)}^{j} \leq q^{n} . \end{matrix}$

This yields the desired inequality for $M$ $M$ .

An $(n, M, d)$ $(n, M, d)$ code with $d = 2 t + 1$ $d = 2 t + 1$ that satisfies the Hamming bound with equality is called a perfect code. A perfect $t$ $t$ -error correcting code is one such that the $M$ $M$ Hamming spheres of radius $t$ $t$ with centers at the codewords cover the entire space of $q$ $q$ -ary $n$ $n$ -tuples. The Hamming codes (Section 24.5) and the Golay code $G_{23}$ $G_{23}$ (Section 24.6) are perfect. Other examples of perfect codes are the trivial $(n, q^{n}, 1)$ $(n, q^{n}, 1)$ code obtained by taking all $n$ $n$ -tuples, and the binary repetition codes of odd length (Exercise 15).

Perfect codes have been studied a lot, and they are interesting from many viewpoints. The complete list of perfect codes is now known. It includes the preceding examples, plus a ternary $[11, 6, 5]$ $[11, 6, 5]$ code constructed by Golay. We leave the reader a caveat. A name like perfect codes might lead one to assume that perfect codes are the best error correcting codes. This, however, is not true, as there are error correcting codes, such as Reed-Solomon codes, that are not perfect codes yet have better error correcting capabilities for certain situations than perfect codes.

24.3.2 Lower Bounds

One of the problems central to the theory of error correcting codes is to find the largest code of a given length and given minimum distance $d$ $d$ . This leads to the following definition.

Definition

Let the alphabet $A$ $A$ have $q$ $q$ elements. Given $n$ $n$ and $d$ $d$ with $d \leq n$ $d \leq n$ , the largest $M$ $M$ such that an $(n, M, d)$ $(n, M, d)$ code exists is denoted $A_{q} (n, d)$ $A_{q} (n, d)$ .

We can always find at least one $(n, M, d)$ $(n, M, d)$ code: Fix an element $a_{0}$ $a_{0}$ of $A$ $A$ . Let $C$ $C$ be the set of all vectors $(a, a, \dots, a, a_{0}, \dots, a_{0})$ $(a, a, \dots, a, a_{0}, \dots, a_{0})$ (with $d$ $d$ copies of $a$ $a$ and $n - d$ $n - d$ copies of $a_{0}$ $a_{0}$ ) with $a \in A$ $a \in A$ . There are $q$ $q$ such vectors, and they are at distance $d$ $d$ from each other, so we have an $(n, q, d)$ $(n, q, d)$ code. This gives the trivial lower bound $A_{q} (n, d) \geq q$ $A_{q} (n, d) \geq q$ . We’ll obtain much better bounds later.

It is easy to see that $A_{q} (n, 1) = q^{n}$ $A_{q} (n, 1) = q^{n}$ : When a code has minimum distance $d = 1$ $d = 1$ , we can take the code to be all $q$ $q$ -ary $n$ $n$ -tuples. At the other extreme, $A_{q} (n, n) = q$ $A_{q} (n, n) = q$ (Exercise 7).

The following lower bound, known as the Gilbert-Varshamov bound, was discovered in the 1950s.

Theorem

Given $n, d$ $n, d$ with $n \geq d$ $n \geq d$ , there exists a $q$ $q$ -ary $(n, M, d)$ $(n, M, d)$ code with

M \geq \frac{q^{n}}{\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}} .

$M \geq \frac{q^{n}}{\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}} .$

This means that

A_{q} (n, d) \geq \frac{q^{n}}{\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}} .

$A_{q} (n, d) \geq \frac{q^{n}}{\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}} .$

Proof. Start with a vector $c_{1}$ $c_{1}$ and remove all vectors in $A^{n}$ $A^{n}$ (where $A$ $A$ is an alphabet with $q$ $q$ symbols) that are in a Hamming sphere of radius $d - 1$ $d - 1$ about that vector. Now choose another vector $c_{2}$ $c_{2}$ from those that remain. Since all vectors with distance at most $d - 1$ $d - 1$ from $c_{1}$ $c_{1}$ have been removed, $d (c_{2}, c_{1}) \geq d$ $d (c_{2}, c_{1}) \geq d$ . Now remove all vectors that have distance at most $d - 1$ $d - 1$ from $c_{2}$ $c_{2}$ , and choose $c_{3}$ $c_{3}$ from those that remain. We cannot have $d (c_{3}, c_{1}) \leq d - 1$ $d (c_{3}, c_{1}) \leq d - 1$ or $d (c_{3}, c_{2}) \leq d - 1$ $d (c_{3}, c_{2}) \leq d - 1$ , since all vectors satisfying these inequalities have been removed. Therefore, $d (c_{3}, c_{i}) \geq d$ $d (c_{3}, c_{i}) \geq d$ for $i = 1, 2$ $i = 1, 2$ . Continuing in this way, choose $c_{4}, c_{5}, \dots$ $c_{4}, c_{5}, \dots$ , until there are no more vectors.

The selection of a vector removes at most

\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}

$\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}$

vectors from the space. If we have chosen $M$ $M$ vectors $c_{1}, \dots, c_{M}$ $c_{1}, \dots, c_{M}$ , then we have removed at most

M \sum_{j = 1}^{d - 1} (\binom{n}{j}) (q - 1)^{j}

$M \sum_{j = 1}^{d - 1} (\binom{n}{j}) (q - 1)^{j}$

vectors, by the preceding lemma. We can continue until all $q^{n}$ $q^{n}$ vectors are removed, which means we can continue at least until

M \sum_{j = 1}^{d - 1} (\binom{n}{j}) (q - 1)^{j} \geq q^{n} .

$M \sum_{j = 1}^{d - 1} (\binom{n}{j}) (q - 1)^{j} \geq q^{n} .$

Therefore, there exists a code ${c_{1}, \dots, c_{M}}$ ${c_{1}, \dots, c_{M}}$ with $M$ $M$ satisfying the preceding inequality.

Since $A_{q} (n, d)$ $A_{q} (n, d)$ is the largest such $M$ $M$ , it also satisfies the inequality.

There is one minor technicality that should be mentioned. We actually have constructed an $(n, M, e)$ $(n, M, e)$ code with $e \geq d$ $e \geq d$ . However, by modifying a few entries of $c_{2}$ $c_{2}$ if necessary, we can arrange that $d (c_{2}, c_{1}) = d$ $d (c_{2}, c_{1}) = d$ . The remaining vectors are then chosen by the above procedure. This produces a code where the minimal distance is exactly $d$ $d$ .

If we want to send codewords with $n$ $n$ bits over a noisy channel, and there is a probability $p$ $p$ that any given bit will be corrupted, then we expect the number of errors to be approximately $p n$ $p n$ when $n$ $n$ is large. Therefore, we need an $(n, M, d)$ $(n, M, d)$ code with $d > 2 p n$ $d > 2 p n$ . We therefore need to consider $(n, M, d)$ $(n, M, d)$ codes with $d / n \approx x > 0$ $d / n \approx x > 0$ , for some given $x > 0$ $x > 0$ . How does this affect $M$ $M$ and the code rate?

Here is what happens. Fix $q$ $q$ and choose $x$ $x$ with $0 < x < 1 - 1 / q$ $0 < x < 1 - 1 / q$ . The asymptotic Gilbert-Varshamov bound says that there is a sequence of $q$ $q$ -ary $(n, M, d)$ $(n, M, d)$ codes with $n \to \infty$ $n \to \infty$ and $d / n \to x$ $d / n \to x$ such that the code rate approaches a limit $\geq H_{q} (x)$ $\geq H_{q} (x)$ , where

H_{q} (x) = 1 - x {log}_{q} (q - 1) + x {log}_{q} (x) + (1 - x) {log}_{q} (1 - x) .

$H_{q} (x) = 1 - x {log}_{q} (q - 1) + x {log}_{q} (x) + (1 - x) {log}_{q} (1 - x) .$

The graph of $H_{2} (x)$ $H_{2} (x)$ is as in Figure 24.2. Of course, we would like to have codes with high error correction (that is, high $x$ $x$ ), and with high code rate ( $= k / n$ $= k / n$ ). The asymptotic result says that there are codes with error correction and code rate good enough to lie arbitrarily close to, or above, the graph.

A graph of y versus x shows the graph of H subscript 2 left parenthesis x right parenthesis.

Figure 24.2 Full Alternative Text

The existence of certain sequences of codes having code rate limit strictly larger than $H_{q} (x)$ $H_{q} (x)$ (for certain $x$ $x$ and $q$ $q$ ) was proved in 1982 by Tsfasman, Vladut, and Zink using Goppa codes arising from algebraic geometry.

Examples

Consider the binary repetition code $C$ $C$ of length $3$ $3$ with the two vectors $(0, 0, 0)$ $(0, 0, 0)$ and $(1, 1, 1)$ $(1, 1, 1)$ . It is a $(3, 2, 3)$ $(3, 2, 3)$ code. The Singleton bound says that $2 = M \leq 2$ $2 = M \leq 2$ , so $C$ $C$ is an MDS code. The Hamming bound says that

2 = M \leq \frac{2^{3}}{(\binom{3}{0}) + (\binom{3}{1})} = 2,

$2 = M \leq \frac{2^{3}}{(\binom{3}{0}) + (\binom{3}{1})} = 2,$

so $C$ $C$ is also perfect. The Gilbert-Varshamov bound says that there exists a $(3, M, 3)$ $(3, M, 3)$ binary code with

M \geq \frac{2^{3}}{(\binom{3}{0}) + (\binom{3}{1}) + (\binom{3}{2})} = \frac{8}{7},

$M \geq \frac{2^{3}}{(\binom{3}{0}) + (\binom{3}{1}) + (\binom{3}{2})} = \frac{8}{7},$

which means $M \geq 2$ $M \geq 2$ .

The Hamming $[7, 4]$ $[7, 4]$ code has $M = 16$ $M = 16$ and $d = 3$ $d = 3$ , so it is a $(7, 16, 3)$ $(7, 16, 3)$ code. The Singleton bound says that $16 = M \leq 2^{5}$ $16 = M \leq 2^{5}$ , so it is not an MDS code. The Hamming bound says that

16 = M \leq \frac{2^{7}}{(\binom{7}{0}) + (\binom{7}{1})} = 16,

$16 = M \leq \frac{2^{7}}{(\binom{7}{0}) + (\binom{7}{1})} = 16,$

so the code is perfect. The Gilbert-Varshamov bound says that there exists a $(7, M, 3)$ $(7, M, 3)$ code with

M \geq \frac{2^{7}}{(\binom{7}{0}) + (\binom{7}{1}) + (\binom{7}{2})} = \frac{128}{29} \approx 4.4,

$M \geq \frac{2^{7}}{(\binom{7}{0}) + (\binom{7}{1}) + (\binom{7}{2})} = \frac{128}{29} \approx 4.4,$

so the Hamming code is much better than this lower bound. Codes that have efficient error correction algorithms and also exceed the Gilbert-Varshamov bound are currently relatively rare.

The Hadamard code from Section 24.1 is a binary (because there are two symbols) $(32, 64, 16)$ $(32, 64, 16)$ code. The Singleton bound says that $64 = M \leq 2^{17}$ $64 = M \leq 2^{17}$ , so it is not very sharp in this case. The Hamming bound says that

64 = M \leq \frac{2^{32}}{\sum_{j = 0}^{7} (\binom{32}{j})} \approx 951.3.

$64 = M \leq \frac{2^{32}}{\sum_{j = 0}^{7} (\binom{32}{j})} \approx 951.3.$

The Gilbert-Varshamov bound says there exists a binary $(32, M, 16)$ $(32, M, 16)$ code with

M \geq \frac{2^{32}}{\sum_{j = 0}^{15} (\binom{32}{j})} \approx 2.3.

$M \geq \frac{2^{32}}{\sum_{j = 0}^{15} (\binom{32}{j})} \approx 2.3.$

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for
24.3 Bounds on General Codes

24.3 Bounds on General Codes

24.3.1 Upper Bounds

Theorem

Corollary

Lemma

Theorem

24.3.2 Lower Bounds

Definition

Theorem

Figure 24.2 The Graph of $H_{2} (x)$ $H_{2} (x)$

Examples

Table of Contents for 24.3 Bounds on General Codes

Create new playlist

Sign In

Sign Up

Table of Contents for
24.3 Bounds on General Codes