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.
- Dima Pasechnik (2012-10): added LP bounds.
Let be a finite field (we denote the finite field with
elements by
). A subset
of
is called a code of length
. A subspace
of
(with the standard basis) is called a linear code of length
. If its
dimension is denoted
then we typically store a basis of
as a
matrix (the rows are the basis vectors). If
then
is called a
binary code. If
has
elements then
is called a
-ary code. The
elements of a code
are called codewords. The information rate of
is
where denotes the number of elements of
. If
,
are vectors in
then
we define
to be the Hamming distance between and
. The function
is called the Hamming metric. The weight of a
vector (in the Hamming metric) is
. The minimum distance of
a linear code is the smallest non-zero weight of a codeword in
. The
relatively minimum distance is denoted
A linear code with length , dimension
, and minimum distance
is
called an
-code and
are called its parameters. A (not
necessarily linear) code
with length
, size
, and minimum
distance
is called an
-code (using parentheses instead of square
brackets). Of course,
for linear codes.
What is the “best” code of a given length? Let be a finite field with
elements. Let
denote the largest
such that there exists a
code in
. Let
(also denoted
) denote
the largest
such that there exists a
code in
. (Of course,
.) Determining
and
is one of the
main problems in the theory of error-correcting codes. For more details see [HP]
and [vL].
These quantities related to solving a generalization of the childhood game of “20 questions”.
GAME: Player 1 secretly chooses a number from to
(
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
times
(
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 .
Lemma: For fixed and
,
is
the smallest
such that
.
Thus, solving the solving a generalization of the game of “20
questions” is equivalent to determining ! Using
Sage, you can determine the best known estimates for this number in
2 ways:
- Indirectly, using best_known_linear_code_www(n, k, F),
- which connects to the website http://www.codetables.de by Markus Grassl;
- codesize_upper_bound(n,d,q), dimension_upper_bound(n,d,q),
- and best_known_linear_code(n, k, F).
The output of best_known_linear_code()
,
best_known_linear_code_www()
, or dimension_upper_bound()
would
give only special solutions to the GAME because the bounds are applicable
to only linear codes. The output of codesize_upper_bound()
would give
the best possible solution, that may belong to a linear or nonlinear code.
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
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
.
- gv_info_rate(n,delta,q),
, 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.
- Delsarte (a.k.a. Linear Programming (LP)) upper bounds.
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.
-
sage.coding.code_bounds.
codesize_upper_bound
(n, d, q, algorithm=None)¶ This computes the minimum value of the upper bound using the methods of Singleton, Hamming, Plotkin, and Elias.
If algorithm=”gap” then this returns the best known upper bound
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 algorithms of Singleton, Hamming, Johnson, Plotkin and Elias. If the code is binary,
, so the function takes the minimum of the values obtained from all algorithms for the parameters
and
. This wraps GUAVA’s (i.e. GAP’s package Guava) UpperBound( n, d, q ).
If algorithm=”LP” then this returns the Delsarte (a.k.a. Linear Programming) upper bound.
EXAMPLES:
sage: codes.bounds.codesize_upper_bound(10,3,2) 93 sage: codes.bounds.codesize_upper_bound(24,8,2,algorithm="LP") 4096 sage: codes.bounds.codesize_upper_bound(10,3,2,algorithm="gap") # optional - gap_packages (Guava package) 85 sage: codes.bounds.codesize_upper_bound(11,3,4,algorithm=None) 123361 sage: codes.bounds.codesize_upper_bound(11,3,4,algorithm="gap") # optional - gap_packages (Guava package) 123361 sage: codes.bounds.codesize_upper_bound(11,3,4,algorithm="LP") 109226
-
sage.coding.code_bounds.
dimension_upper_bound
(n, d, q, algorithm=None)¶ Returns an upper bound
for the dimension of a linear code of length n, minimum distance d over a field of size q. Parameter “algorithm” has the same meaning as in
codesize_upper_bound()
EXAMPLES:
sage: codes.bounds.dimension_upper_bound(10,3,2) 6 sage: codes.bounds.dimension_upper_bound(30,15,4) 13 sage: codes.bounds.dimension_upper_bound(30,15,4,algorithm="LP") 12
-
sage.coding.code_bounds.
elias_bound_asymp
(delta, q)¶ Computes the asymptotic Elias bound for the information rate, provided
.
EXAMPLES:
sage: codes.bounds.elias_bound_asymp(1/4,2) 0.39912396330...
-
sage.coding.code_bounds.
elias_upper_bound
(n, q, d, algorithm=None)¶ Returns the Elias upper bound for number of elements in the largest code of minimum distance d in
. Wraps GAP’s UpperBoundElias.
EXAMPLES:
sage: codes.bounds.elias_upper_bound(10,2,3) 232 sage: codes.bounds.elias_upper_bound(10,2,3,algorithm="gap") # optional - gap_packages (Guava package) 232
-
sage.coding.code_bounds.
entropy
(x, q=2)¶ Computes the entropy at
on the
-ary symmetric channel.
INPUT:
x
- real number in the interval.
q
- (default: 2) integer greater than 1. This is the base of the logarithm.
EXAMPLES:
sage: codes.bounds.entropy(0, 2) 0 sage: codes.bounds.entropy(1/5,4) 1/5*log(3)/log(4) - 4/5*log(4/5)/log(4) - 1/5*log(1/5)/log(4) sage: codes.bounds.entropy(1, 3) log(2)/log(3)
Check that values not within the limits are properly handled:
sage: codes.bounds.entropy(1.1, 2) Traceback (most recent call last): ... ValueError: The entropy function is defined only for x in the interval [0, 1] sage: codes.bounds.entropy(1, 1) Traceback (most recent call last): ... ValueError: The value q must be an integer greater than 1
-
sage.coding.code_bounds.
entropy_inverse
(x, q=2)¶ Find the inverse of the
q
-ary entropy function at the pointx
.INPUT:
x
– real number in the interval.
q
- (default: 2) integer greater than 1. This is the base of the logarithm.
OUTPUT:
Real number in the interval
. The function has multiple values if we include the entire interval
; hence only the values in the above interval is returned.
EXAMPLES:
sage: from sage.coding.code_bounds import entropy_inverse sage: entropy_inverse(0.1) 0.012986862055848683 sage: entropy_inverse(1) 1/2 sage: entropy_inverse(0, 3) 0 sage: entropy_inverse(1, 3) 2/3
-
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
.
EXAMPLES:
sage: codes.bounds.gilbert_lower_bound(10,2,3) 128/7
-
sage.coding.code_bounds.
griesmer_upper_bound
(n, q, d, algorithm=None)¶ Returns the Griesmer upper bound for number of elements in the largest code of minimum distance d in
. Wraps GAP’s UpperBoundGriesmer.
EXAMPLES:
sage: codes.bounds.griesmer_upper_bound(10,2,3) 128 sage: codes.bounds.griesmer_upper_bound(10,2,3,algorithm="gap") # optional - gap_packages (Guava package) 128
-
sage.coding.code_bounds.
gv_bound_asymp
(delta, q)¶ Computes the asymptotic GV bound for the information rate, R.
EXAMPLES:
sage: RDF(codes.bounds.gv_bound_asymp(1/4,2)) 0.18872187554086... sage: f = lambda x: codes.bounds.gv_bound_asymp(x,2) sage: plot(f,0,1) Graphics object consisting of 1 graphics primitive
-
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(codes.bounds.gv_info_rate(100,1/4,3)) # abs tol 1e-15 0.36704992608261894
-
sage.coding.code_bounds.
hamming_bound_asymp
(delta, q)¶ Computes the asymptotic Hamming bound for the information rate.
EXAMPLES:
sage: RDF(codes.bounds.hamming_bound_asymp(1/4,2)) 0.456435556800... sage: f = lambda x: codes.bounds.hamming_bound_asymp(x,2) sage: plot(f,0,1) Graphics object consisting of 1 graphics primitive
-
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
. 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
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.
where M is the maximum number of codewords and
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: codes.bounds.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
.
EXAMPLES:
sage: codes.bounds.mrrw1_bound_asymp(1/4,2) # abs tol 4e-16 0.3545789026652697
-
sage.coding.code_bounds.
plotkin_bound_asymp
(delta, q)¶ Computes the asymptotic Plotkin bound for the information rate, provided
.
EXAMPLES:
sage: codes.bounds.plotkin_bound_asymp(1/4,2) 1/2
-
sage.coding.code_bounds.
plotkin_upper_bound
(n, q, d, algorithm=None)¶ Returns Plotkin upper bound for number of elements in the largest code of minimum distance d in
.
The algorithm=”gap” option wraps Guava’s UpperBoundPlotkin.
EXAMPLES:
sage: codes.bounds.plotkin_upper_bound(10,2,3) 192 sage: codes.bounds.plotkin_upper_bound(10,2,3,algorithm="gap") # optional - gap_packages (Guava package) 192
-
sage.coding.code_bounds.
singleton_bound_asymp
(delta, q)¶ Computes the asymptotic Singleton bound for the information rate.
EXAMPLES:
sage: codes.bounds.singleton_bound_asymp(1/4,2) 3/4 sage: f = lambda x: codes.bounds.singleton_bound_asymp(x,2) sage: plot(f,0,1) Graphics object consisting of 1 graphics primitive
-
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
. Wraps GAP’s UpperBoundSingleton.
This bound is based on the shortening of codes. By shortening an
code d-1 times, an
code results, with
. Thus
Codes that meet this bound are called maximum distance separable (MDS).
EXAMPLES:
sage: codes.bounds.singleton_upper_bound(10,2,3) 256
-
sage.coding.code_bounds.
volume_hamming
(n, q, r)¶ Returns number of elements in a Hamming ball of radius r in
. Agrees with Guava’s SphereContent(n,r,GF(q)).
EXAMPLES:
sage: codes.bounds.volume_hamming(10,2,3) 176