Module: sage.coding.code_bounds
Bounds for Parameters of Codes
Author Log:
This module provided some upper and lower bounds for the parameters of codes.
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
to be the Hamming distance between
A linear code with length
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.
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:
(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), which use GUAVA's UpperBound( n, d, q )
This module implements:
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.
Module-level Functions
n, d, q) |
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 methods of Singleton, Hamming, Johnson, Plotkin
and Elias. If the code is binary,
, so the function takes
the minimum of the values obtained from all methods for the parameters
and
.
Wraps GUAVA's UpperBound( n, d, q ).
sage: codesize_upper_bound(10,3,2) 85
n, d, q) |
Returns an upper bound
for the dimension of a linear code of length n,
minimum distance d over a field of size q.
sage: dimension_upper_bound(10,3,2) 6
delta, q) |
Computes the asymptotic Elias bound for the information rate, provided 0 < delta < 1-1/q.
sage: elias_bound_asymp(1/4,2) 0.39912396330...
n, q, d) |
Returns the Elias upper bound for number of elements in
the largest code of minimum distance d in
. Wraps GAP's
UpperBoundElias.
sage: elias_upper_bound(10,2,3) 232
x, q) |
Computes the entropy on the q-ary symmetric channel.
n, q, d) |
Returns lower bound for number of elements in
the largest code of minimum distance d in
.
sage: gilbert_lower_bound(10,2,3) 128/7
n, q, d) |
Returns the Griesmer upper bound for number of elements in
the largest code of minimum distance d in
. Wraps GAP's
UpperBoundGriesmer.
sage: griesmer_upper_bound(10,2,3) 128
delta, q) |
Computes the asymptotic GV bound for the information rate, R.
sage: f = lambda x: gv_bound_asymp(x,2) sage: P = plot(f,0,1) sage: P.save()
n, delta, q) |
GV lower bound for information rate of a q-ary code of length n minimum distance delta*n
sage: gv_info_rate(100,1/4,3) 0.367049926083
delta, q) |
Computes the asymptotic Hamming bound for the information rate.
sage: f = lambda x: hamming_bound_asymp(x,2) sage: P = plot(f,0,1) sage: P.save()
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 maxmimum 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.
sage: hamming_upper_bound(10,2,3) 93
delta, q) |
Computes the ``first asymptotic McEliese-Rumsey-Rodemich-Welsh bound for the information rate, provided 0 < delta < 1-1/q.
sage: mrrw1_bound_asymp(1/4,2) 0.354578902665
delta, q) |
Computes the asymptotic Plotkin bound for the information rate, provided 0 < delta < 1-1/q.
sage: plotkin_bound_asymp(1/4,2) 1/2
n, q, d) |
Returns Plotkin upper bound for number of elements in
the largest code of minimum distance d in
. Wraps GAP's
UpperBoundPlotkin.
sage: plotkin_upper_bound(10,2,3) 192
delta, q) |
Computes the asymptotic Singleton bound for the information rate.
sage: f = lambda x: singleton_bound_asymp(x,2) sage: P = plot(f,0,1) sage: P.save()
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).
sage: singleton_upper_bound(10,2,3) 256
n, q, r) |
Returns number of elements in a Hamming ball of radius r in
.
sage: volume_hamming(10,2,3) 176
See About this document... for information on suggesting changes.