Bounds for Parameters of Codes¶

This module provided some upper and lower bounds for the parameters of codes.

AUTHORS:

David Joyner (2006-07): initial implementation.
William Stein (2006-07): minor editing of docs and code (fixed bug in elias_bound_asymp)
David Joyner (2006-07): fixed dimension_upper_bound to return an integer, added example to elias_bound_asymp.
” (2009-05): removed all calls to Guava but left it as an option.

Let $F$ be a finite field (we denote the finite field with $q$ elements by $\GF{q}$ ). A subset $C$ of $V=F^n$ is called a code of length $n$ . A subspace of $V$ (with the standard basis) is called a linear code of length $n$ . If its dimension is denoted $k$ then we typically store a basis of $C$ as a $k\times n$ matrix (the rows are the basis vectors). If $F=\GF{2}$ then $C$ is called a binary code. If $F$ has $q$ elements then $C$ is called a $q$ -ary code. The elements of a code $C$ are called codewords. The information rate of $C$ is

$R={\frac{\log_q\vert C\vert}{n}},$

where $\vert C\vert$ denotes the number of elements of $C$ . If ${\bf v}=(v_1,v_2,...,v_n)$ , ${\bf w}=(w_1,w_2,...,w_n)$ are vectors in $V=F^n$ then we define

$d({\bf v},{\bf w}) =\vert\{i\ \vert\ 1\leq i\leq n,\ v_i\not= w_i\}\vert$

to be the Hamming distance between ${\bf v}$ and ${\bf w}$ . The function $d:V\times V\rightarrow \Bold{N}$ is called the Hamming metric. The weight of a vector (in the Hamming metric) is $d({\bf v},{\bf 0})$ . The minimum distance of a linear code is the smallest non-zero weight of a codeword in $C$ . The relatively minimum distance is denoted

$\delta = d/n.$

A linear code with length $n$ , dimension $k$ , and minimum distance $d$ is called an $[n,k,d]_q$ -code and $n,k,d$ are called its parameters. A (not necessarily linear) code $C$ with length $n$ , size $M=|C|$ , and minimum distance $d$ is called an $(n,M,d)_q$ -code (using parentheses instead of square brackets). Of course, $k=\log_q(M)$ for linear codes.

What is the “best” code of a given length? Let $F$ be a finite field with $q$ elements. Let $A_q(n,d)$ denote the largest $M$ such that there exists a $(n,M,d)$ code in $F^n$ . Let $B_q(n,d)$ (also denoted $A^{lin}_q(n,d)$ ) denote the largest $k$ such that there exists a $[n,k,d]$ code in $F^n$ . (Of course, $A_q(n,d)\geq B_q(n,d)$ .) Determining $A_q(n,d)$ and $B_q(n,d)$ is one of the main problems in the theory of error-correcting codes.

These quantities related to solving a generalization of the childhood game of “20 questions”.

GAME: Player 1 secretly chooses a number from $1$ to $M$ ( $M$ is large but fixed). Player 2 asks a series of “yes/no questions” in an attempt to determine that number. Player 1 may lie at most $e$ times ( $e\geq 0$ is fixed). What is the minimum number of “yes/no questions” Player 2 must ask to (always) be able to correctly determine the number Player 1 chose?

If feedback is not allowed (the only situation considered here), call this minimum number $g(M,e)$ .

Lemma: For fixed $e$ and $M$ , $g(M,e)$ is the smallest $n$ such that $A_2(n,2e+1)\geq M$ .

Thus, solving the solving a generalization of the game of “20 questions” is equivalent to determining $A_2(n,d)$ ! Using Sage, you can determine the best known estimates for this number in 2 ways:

(1) Indirectly, using minimum_distance_lower_bound(n,k,F) and minimum_distance_upper_bound(n,k,F) (both of which which connect to the internet using Steven Sivek’s linear_code_bound(q,n,k)) (2) codesize_upper_bound(n,d,q), dimension_upper_bound(n,d,q).

This module implements:

codesize_upper_bound(n,d,q), for the best known (as of May, 2006) upper bound A(n,d) for the size of a code of length n, minimum distance d over a field of size q.
dimension_upper_bound(n,d,q), an upper bound $B(n,d)=B_q(n,d)$ for the dimension of a linear code of length n, minimum distance d over a field of size q.
gilbert_lower_bound(n,q,d), a lower bound for number of elements in the largest code of min distance d in $\GF{q}^n$ .
gv_info_rate(n,delta,q), $log_q(GLB)/n$ , where GLB is the Gilbert lower bound and delta = d/n.
gv_bound_asymp(delta,q), asymptotic analog of Gilbert lower bound.
plotkin_upper_bound(n,q,d)
plotkin_bound_asymp(delta,q), asymptotic analog of Plotkin bound.
griesmer_upper_bound(n,q,d)
elias_upper_bound(n,q,d)
elias_bound_asymp(delta,q), asymptotic analog of Elias bound.
hamming_upper_bound(n,q,d)
hamming_bound_asymp(delta,q), asymptotic analog of Hamming bound.
singleton_upper_bound(n,q,d)
singleton_bound_asymp(delta,q), asymptotic analog of Singleton bound.
mrrw1_bound_asymp(delta,q), “first” asymptotic McEliese-Rumsey-Rodemich-Welsh bound for the information rate.

PROBLEM: In this module we shall typically either (a) seek bounds on k, given n, d, q, (b) seek bounds on R, delta, q (assuming n is “infinity”).

TODO:

Johnson bounds for binary codes.
mrrw2_bound_asymp(delta,q), “second” asymptotic McEliese-Rumsey-Rodemich-Welsh bound for the information rate.

REFERENCES:

C. Huffman, V. Pless, Fundamentals of error-correcting codes, Cambridge Univ. Press, 2003.

sage.coding.code_bounds.codesize_upper_bound(n, d, q, method=None)¶

This computes the minimum value of the upper bound using the methods of Singleton, Hamming, Plotkin and Elias.

If method=”gap” then this returns the best known upper bound $A(n,d)=A_q(n,d)$ for the size of a code of length n, minimum distance d over a field of size q. The function first checks for trivial cases (like d=1 or n=d), and if the value is in the built-in table. Then it calculates the minimum value of the upper bound using the methods of Singleton, Hamming, Johnson, Plotkin and Elias. If the code is binary, $A(n, 2\ell-1) = A(n+1,2\ell)$ , so the function takes the minimum of the values obtained from all methods for the parameters $(n, 2\ell-1)$ and $(n+1, 2\ell)$ . This wraps GUAVA’s UpperBound( n, d, q ).

EXAMPLES::: sage: codesize_upper_bound(10,3,2) 93 sage: codesize_upper_bound(10,3,2,method=”gap”) # requires optional GAP package Guava 85

sage.coding.code_bounds.dimension_upper_bound(n, d, q)¶

Returns an upper bound $B(n,d) = B_q(n,d)$ for the dimension of a linear code of length n, minimum distance d over a field of size q.

EXAMPLES:

sage: dimension_upper_bound(10,3,2)
6

sage.coding.code_bounds.elias_bound_asymp(delta, q)¶

Computes the asymptotic Elias bound for the information rate, provided $0 < \delta 1-1/q$ .

EXAMPLES:

sage: elias_bound_asymp(1/4,2)
0.39912396330...

sage.coding.code_bounds.elias_upper_bound(n, q, d, method=None)¶

Returns the Elias upper bound for number of elements in the largest code of minimum distance d in $\GF{q}^n$ . Wraps GAP’s UpperBoundElias.

EXAMPLES:

sage: elias_upper_bound(10,2,3)
232
sage: elias_upper_bound(10,2,3,method="gap")  # requires optional GAP package Guava
232

sage.coding.code_bounds.entropy(x, q)¶: Computes the entropy on the q-ary symmetric channel.

sage.coding.code_bounds.gilbert_lower_bound(n, q, d)¶

Returns lower bound for number of elements in the largest code of minimum distance d in $\GF{q}^n$ .

EXAMPLES:

sage: gilbert_lower_bound(10,2,3)
128/7

sage.coding.code_bounds.griesmer_upper_bound(n, q, d, method=None)¶

Returns the Griesmer upper bound for number of elements in the largest code of minimum distance d in $\GF{q}^n$ . Wraps GAP’s UpperBoundGriesmer.

EXAMPLES::: sage: griesmer_upper_bound(10,2,3) 128 sage: griesmer_upper_bound(10,2,3,method=”gap”) # requires optional GAP package Guava 128

sage.coding.code_bounds.gv_bound_asymp(delta, q)¶

Computes the asymptotic GV bound for the information rate, R.

EXAMPLES::: sage: RDF(gv_bound_asymp(1/4,2)) 0.188721875541 sage: f = lambda x: gv_bound_asymp(x,2) sage: plot(f,0,1)

sage.coding.code_bounds.gv_info_rate(n, delta, q)¶

GV lower bound for information rate of a q-ary code of length n minimum distance delta*n

EXAMPLES:

sage: RDF(gv_info_rate(100,1/4,3))
0.367049926083

sage.coding.code_bounds.hamming_bound_asymp(delta, q)¶

Computes the asymptotic Hamming bound for the information rate.

EXAMPLES::: sage: RDF(hamming_bound_asymp(1/4,2)) 0.4564355568 sage: f = lambda x: hamming_bound_asymp(x,2) sage: plot(f,0,1)

sage.coding.code_bounds.hamming_upper_bound(n, q, d)¶

Returns the Hamming upper bound for number of elements in the largest code of minimum distance d in $\GF{q}^n$ . Wraps GAP’s UpperBoundHamming.

The Hamming bound (also known as the sphere packing bound) returns an upper bound on the size of a code of length n, minimum distance d, over a field of size q. The Hamming bound is obtained by dividing the contents of the entire space $\GF{q}^n$ by the contents of a ball with radius floor((d-1)/2). As all these balls are disjoint, they can never contain more than the whole vector space.

$M \leq {q^n \over V(n,e)},$

where M is the maximum number of codewords and $V(n,e)$ is equal to the contents of a ball of radius e. This bound is useful for small values of d. Codes for which equality holds are called perfect.

EXAMPLES:

sage: hamming_upper_bound(10,2,3) 
93

sage.coding.code_bounds.mrrw1_bound_asymp(delta, q)¶

Computes the first asymptotic McEliese-Rumsey-Rodemich-Welsh bound for the information rate, provided $0 < \delta < 1-1/q$ .

EXAMPLES:

sage: mrrw1_bound_asymp(1/4,2)
0.354578902665

sage.coding.code_bounds.plotkin_bound_asymp(delta, q)¶

Computes the asymptotic Plotkin bound for the information rate, provided $0 < \delta < 1-1/q$ .

EXAMPLES:

sage: plotkin_bound_asymp(1/4,2)
1/2

sage.coding.code_bounds.plotkin_upper_bound(n, q, d, method=None)¶

Returns Plotkin upper bound for number of elements in the largest code of minimum distance d in $\GF{q}^n$ .

The method=”gap” option wraps Guava’s UpperBoundPlotkin.

EXAMPLES::: sage: plotkin_upper_bound(10,2,3) 192 sage: plotkin_upper_bound(10,2,3,method=”gap”) # requires optional GAP package Guava 192

sage.coding.code_bounds.singleton_bound_asymp(delta, q)¶

Computes the asymptotic Singleton bound for the information rate.

EXAMPLES::: sage: singleton_bound_asymp(1/4,2) 3/4 sage: f = lambda x: singleton_bound_asymp(x,2) sage: plot(f,0,1)

sage.coding.code_bounds.singleton_upper_bound(n, q, d)¶

Returns the Singleton upper bound for number of elements in the largest code of minimum distance d in $\GF{q}^n$ . Wraps GAP’s UpperBoundSingleton.

This bound is based on the shortening of codes. By shortening an $(n, M, d)$ code d-1 times, an $(n-d+1,M,1)$ code results, with $M \leq q^n-d+1$ . Thus