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.

  • Devansh Sehgal (2026-08-07): implemented the second MRRW asymptotic bound.

Let \(F\) be a finite set of size \(q\). A subset \(C\) of \(V=F^n\) is called a code of length \(n\). Often one considers the case where \(F\) is a finite field, denoted by \(\GF{q}\). Then \(V\) is an \(F\)-vector space. 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 elements of \(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 an element (in the Hamming metric) is \(d({\bf v},{\bf 0})\), where \(0\) is a distinguished element of \(F\); in particular it is \(0\) of the field if \(F\) is a field. The minimum distance of a linear code is the smallest nonzero 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 \(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. For more details see [HP2003] and [Lin1999].

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 this generalization of the game of “20 questions” is equivalent to determining \(A_2(n,d)\). In Sage, the function dimension_upper_bound() computes upper bounds for the dimension of linear codes, and therefore only concerns the linear-code analogue \(B_q(n,d)\). The function codesize_upper_bound() computes upper bounds for \(A_q(n,d)\), so it applies to arbitrary, possibly nonlinear, codes.

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.

  • mrrw2_bound_asymp(delta,q), “second” asymptotic McEliece-Rodemich-Rumsey-Welch bound for the information rate of binary codes.

  • 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.

sage.coding.code_bounds.codesize_upper_bound(n, d, q, algorithm=None)[source]

Return an upper bound on the number of codewords in a (possibly non-linear) code.

This function computes the minimum value of the upper bounds of Singleton, Hamming, Plotkin, and Elias.

If algorithm="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 algorithms 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 algorithms for the parameters \((n, 2\ell-1)\) and \((n+1, 2\ell)\). 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')               # needs sage.numerical.mip
4096
sage: codes.bounds.codesize_upper_bound(10, 3, 2, algorithm='gap')              # optional - gap_package_guava
85
sage: codes.bounds.codesize_upper_bound(11, 3, 4, algorithm=None)               # needs sage.symbolic
123361
sage: codes.bounds.codesize_upper_bound(11, 3, 4, algorithm='gap')              # optional - gap_package_guava
123361
sage: codes.bounds.codesize_upper_bound(11, 3, 4, algorithm='LP')               # needs sage.numerical.mip
109226

>>> from sage.all import *
>>> codes.bounds.codesize_upper_bound(Integer(10), Integer(3), Integer(2))
93
>>> codes.bounds.codesize_upper_bound(Integer(24), Integer(8), Integer(2), algorithm='LP')               # needs sage.numerical.mip
4096
>>> codes.bounds.codesize_upper_bound(Integer(10), Integer(3), Integer(2), algorithm='gap')              # optional - gap_package_guava
85
>>> codes.bounds.codesize_upper_bound(Integer(11), Integer(3), Integer(4), algorithm=None)               # needs sage.symbolic
123361
>>> codes.bounds.codesize_upper_bound(Integer(11), Integer(3), Integer(4), algorithm='gap')              # optional - gap_package_guava
123361
>>> codes.bounds.codesize_upper_bound(Integer(11), Integer(3), Integer(4), algorithm='LP')               # needs sage.numerical.mip
109226
sage.coding.code_bounds.dimension_upper_bound(n, d, q, algorithm=None)[source]

Return an upper bound for the dimension of a linear code.

Return 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\).

Parameter algorithm has the same meaning as in codesize_upper_bound()

EXAMPLES:

sage: codes.bounds.dimension_upper_bound(10,3,2)                                # needs sage.libs.pari sage.symbolic
6
sage: codes.bounds.dimension_upper_bound(30,15,4)                               # needs sage.libs.pari sage.symbolic
13
sage: codes.bounds.dimension_upper_bound(30,15,4,algorithm='LP')                # needs sage.libs.pari sage.numerical.mip
12

>>> from sage.all import *
>>> codes.bounds.dimension_upper_bound(Integer(10),Integer(3),Integer(2))                                # needs sage.libs.pari sage.symbolic
6
>>> codes.bounds.dimension_upper_bound(Integer(30),Integer(15),Integer(4))                               # needs sage.libs.pari sage.symbolic
13
>>> codes.bounds.dimension_upper_bound(Integer(30),Integer(15),Integer(4),algorithm='LP')                # needs sage.libs.pari sage.numerical.mip
12
sage.coding.code_bounds.elias_bound_asymp(delta, q)[source]

The asymptotic Elias bound for the information rate.

This only makes sense when \(0 < \delta < 1-1/q\).

EXAMPLES:

sage: codes.bounds.elias_bound_asymp(1/4,2)                                     # needs sage.symbolic
0.39912396330...

>>> from sage.all import *
>>> codes.bounds.elias_bound_asymp(Integer(1)/Integer(4),Integer(2))                                     # needs sage.symbolic
0.39912396330...
sage.coding.code_bounds.elias_upper_bound(n, q, d, algorithm=None)[source]

Return the Elias upper bound.

Return the Elias upper bound for number of elements in the largest code of minimum distance \(d\) in \(\GF{q}^n\), cf. [HP2003]. If algorithm="gap", it 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_package_guava
232

>>> from sage.all import *
>>> codes.bounds.elias_upper_bound(Integer(10),Integer(2),Integer(3))
232
>>> codes.bounds.elias_upper_bound(Integer(10),Integer(2),Integer(3),algorithm='gap')  # optional - gap_package_guava
232
sage.coding.code_bounds.entropy(x, q=2)[source]

Compute the entropy at \(x\) on the \(q\)-ary symmetric channel.

INPUT:

  • x – real number in the interval \([0, 1]\)

  • 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).factor()                                      # needs sage.symbolic
1/10*(log(3) - 4*log(4/5) - log(1/5))/log(2)
sage: codes.bounds.entropy(1, 3)                                                # needs sage.symbolic
log(2)/log(3)

>>> from sage.all import *
>>> codes.bounds.entropy(Integer(0), Integer(2))
0
>>> codes.bounds.entropy(Integer(1)/Integer(5),Integer(4)).factor()                                      # needs sage.symbolic
1/10*(log(3) - 4*log(4/5) - log(1/5))/log(2)
>>> codes.bounds.entropy(Integer(1), Integer(3))                                                # needs sage.symbolic
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
[Python] 
>>> from sage.all import *
>>> codes.bounds.entropy(RealNumber('1.1'), Integer(2))
Traceback (most recent call last):
...
ValueError: The entropy function is defined only for x in the interval [0, 1]
>>> codes.bounds.entropy(Integer(1), Integer(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)[source]

Find the inverse of the \(q\)-ary entropy function at the point x.

INPUT:

  • x – real number in the interval \([0, 1]\)

  • q – (default: 2) integer greater than 1; this is the base of the logarithm

OUTPUT:

Real number in the interval \([0, 1-1/q]\). The function has multiple values if we include the entire interval \([0, 1]\); hence only the values in the above interval is returned.

EXAMPLES:

sage: # needs sage.symbolic
sage: from sage.coding.code_bounds import entropy_inverse
sage: entropy_inverse(0.1)                                                      # needs scipy
0.012986862055...
sage: entropy_inverse(1)
1/2
sage: entropy_inverse(0, 3)
0
sage: entropy_inverse(1, 3)
2/3

>>> from sage.all import *
>>> # needs sage.symbolic
>>> from sage.coding.code_bounds import entropy_inverse
>>> entropy_inverse(RealNumber('0.1'))                                                      # needs scipy
0.012986862055...
>>> entropy_inverse(Integer(1))
1/2
>>> entropy_inverse(Integer(0), Integer(3))
0
>>> entropy_inverse(Integer(1), Integer(3))
2/3
sage.coding.code_bounds.gilbert_lower_bound(n, q, d)[source]

Return the Gilbert-Varshamov lower bound.

Return the Gilbert-Varshamov lower bound for number of elements in a largest code of minimum distance d in \(\GF{q}^n\). See Wikipedia article Gilbert-Varshamov_bound

EXAMPLES:

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

>>> from sage.all import *
>>> codes.bounds.gilbert_lower_bound(Integer(10),Integer(2),Integer(3))
128/7
sage.coding.code_bounds.griesmer_upper_bound(n, q, d, algorithm=None)[source]

Return the Griesmer upper bound.

Return the Griesmer upper bound for the number of elements in a largest linear code of minimum distance \(d\) in \(\GF{q}^n\), cf. [HP2003]. If the method is “gap”, it wraps GAP’s UpperBoundGriesmer.

The bound states:

\[`n\geq \sum_{i=0}^{k-1} \lceil d/q^i \rceil.`\]

EXAMPLES:

The bound is reached for the ternary Golay codes:

sage: codes.bounds.griesmer_upper_bound(12,3,6)                                 # needs sage.libs.pari
729
sage: codes.bounds.griesmer_upper_bound(11,3,5)                                 # needs sage.libs.pari
729

>>> from sage.all import *
>>> codes.bounds.griesmer_upper_bound(Integer(12),Integer(3),Integer(6))                                 # needs sage.libs.pari
729
>>> codes.bounds.griesmer_upper_bound(Integer(11),Integer(3),Integer(5))                                 # needs sage.libs.pari
729


sage: codes.bounds.griesmer_upper_bound(10,2,3)                                 # needs sage.libs.pari
128
sage: codes.bounds.griesmer_upper_bound(10,2,3,algorithm='gap')                 # optional - gap_package_guava, needs sage.libs.pari
128
[Python] 
>>> from sage.all import *
>>> codes.bounds.griesmer_upper_bound(Integer(10),Integer(2),Integer(3))                                 # needs sage.libs.pari
128
>>> codes.bounds.griesmer_upper_bound(Integer(10),Integer(2),Integer(3),algorithm='gap')                 # optional - gap_package_guava, needs sage.libs.pari
128
sage.coding.code_bounds.gv_bound_asymp(delta, q)[source]

The asymptotic Gilbert-Varshamov bound for the information rate, R.

EXAMPLES:

sage: # needs sage.symbolic
sage: RDF(codes.bounds.gv_bound_asymp(1/4,2))                                   # needs sage.libs.pari
0.18872187554086...
sage: f = lambda x: codes.bounds.gv_bound_asymp(x,2)
sage: plot(f,0,1)                                                               # needs sage.libs.pari sage.plot
Graphics object consisting of 1 graphics primitive

>>> from sage.all import *
>>> # needs sage.symbolic
>>> RDF(codes.bounds.gv_bound_asymp(Integer(1)/Integer(4),Integer(2)))                                   # needs sage.libs.pari
0.18872187554086...
>>> f = lambda x: codes.bounds.gv_bound_asymp(x,Integer(2))
>>> plot(f,Integer(0),Integer(1))                                                               # needs sage.libs.pari sage.plot
Graphics object consisting of 1 graphics primitive
sage.coding.code_bounds.gv_info_rate(n, delta, q)[source]

The Gilbert-Varshamov lower bound for information rate.

The Gilbert-Varshamov lower bound for information rate of a \(q\)-ary code of length \(n\) and minimum distance \(n\delta\).

EXAMPLES:

sage: RDF(codes.bounds.gv_info_rate(100,1/4,3))  # abs tol 1e-15                # needs sage.libs.pari sage.symbolic
0.36704992608261894

>>> from sage.all import *
>>> RDF(codes.bounds.gv_info_rate(Integer(100),Integer(1)/Integer(4),Integer(3)))  # abs tol 1e-15                # needs sage.libs.pari sage.symbolic
0.36704992608261894
sage.coding.code_bounds.hamming_bound_asymp(delta, q)[source]

The asymptotic Hamming bound for the information rate.

EXAMPLES:

sage: # needs sage.symbolic
sage: RDF(codes.bounds.hamming_bound_asymp(1/4,2))                              # needs sage.libs.pari
0.456435556800...
sage: f = lambda x: codes.bounds.hamming_bound_asymp(x,2)
sage: plot(f,0,1)                                                               # needs sage.libs.pari sage.plot
Graphics object consisting of 1 graphics primitive

>>> from sage.all import *
>>> # needs sage.symbolic
>>> RDF(codes.bounds.hamming_bound_asymp(Integer(1)/Integer(4),Integer(2)))                              # needs sage.libs.pari
0.456435556800...
>>> f = lambda x: codes.bounds.hamming_bound_asymp(x,Integer(2))
>>> plot(f,Integer(0),Integer(1))                                                               # needs sage.libs.pari sage.plot
Graphics object consisting of 1 graphics primitive
sage.coding.code_bounds.hamming_upper_bound(n, q, d)[source]

Return the Hamming upper bound.

Return the Hamming upper bound for number of elements in the largest code of length \(n\) and minimum distance \(d\) over alphabet of size \(q\).

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 an alphabet of size \(q\). The Hamming bound is obtained by dividing the contents of the entire Hamming space \(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 \frac{q^n}{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. See e.g. [HP2003].

EXAMPLES:

sage: codes.bounds.hamming_upper_bound(10,2,3)
93

>>> from sage.all import *
>>> codes.bounds.hamming_upper_bound(Integer(10),Integer(2),Integer(3))
93
sage.coding.code_bounds.mrrw1_bound_asymp(delta, q)[source]

The first asymptotic McEliese-Rumsey-Rodemich-Welsh bound.

This only makes sense when \(0 < \delta < 1-1/q\).

EXAMPLES:

sage: codes.bounds.mrrw1_bound_asymp(1/4,2)   # abs tol 4e-16                   # needs sage.symbolic
0.3545789026652697

>>> from sage.all import *
>>> codes.bounds.mrrw1_bound_asymp(Integer(1)/Integer(4),Integer(2))   # abs tol 4e-16                   # needs sage.symbolic
0.3545789026652697
sage.coding.code_bounds.mrrw2_bound_asymp(delta, q)[source]

Return the second asymptotic McEliece-Rodemich-Rumsey-Welch bound.

This is an upper bound for the information rate of a binary code with relative minimum distance delta. It is defined by

\[\min_{0 \leq u \leq 1 - 2\delta} \left(1 + g(u^2) - g(u^2 + 2\delta u + 2\delta)\right),\]

where

\[g(x) = H_2\left(\frac{1 - \sqrt{1-x}}{2}\right).\]

The returned RealDoubleElement is a numerical approximation obtained with SciPy’s bounded scalar minimizer and an explicit comparison with both endpoints.

INPUT:

  • delta – real number in \([0, 1/2]\); the relative minimum distance

  • q – integer equal to \(2\); the alphabet size

REFERENCES:

EXAMPLES:

sage: codes.bounds.mrrw2_bound_asymp(1/5, 2)  # abs tol 1e-12                   # needs scipy
0.461359603763518
sage: codes.bounds.mrrw2_bound_asymp(1/10, 2)  # abs tol 1e-12                  # needs scipy
0.692740743078879

>>> from sage.all import *
>>> codes.bounds.mrrw2_bound_asymp(Integer(1)/Integer(5), Integer(2))  # abs tol 1e-12                   # needs scipy
0.461359603763518
>>> codes.bounds.mrrw2_bound_asymp(Integer(1)/Integer(10), Integer(2))  # abs tol 1e-12                  # needs scipy
0.692740743078879

At delta=0.3, the right endpoint supplies the minimum:

sage: codes.bounds.mrrw2_bound_asymp(RDF('0.3'), 2)  # abs tol 1e-12             # needs scipy
0.2502249116110706
[Python] 
>>> from sage.all import *
>>> codes.bounds.mrrw2_bound_asymp(RDF('0.3'), Integer(2))  # abs tol 1e-12             # needs scipy
0.2502249116110706

At the endpoints the asymptotic bound is one and zero, respectively:

sage: codes.bounds.mrrw2_bound_asymp(0, 2)
1.0
sage: codes.bounds.mrrw2_bound_asymp(2^-60, 2)
1.0
sage: codes.bounds.mrrw2_bound_asymp(1/2, 2)
0.0

>>> from sage.all import *
>>> codes.bounds.mrrw2_bound_asymp(Integer(0), Integer(2))
1.0
>>> codes.bounds.mrrw2_bound_asymp(Integer(2)**-Integer(60), Integer(2))
1.0
>>> codes.bounds.mrrw2_bound_asymp(Integer(1)/Integer(2), Integer(2))
0.0

Values below the upper endpoint retain their numerical accuracy:

sage: # needs scipy
sage: codes.bounds.mrrw2_bound_asymp(RDF('0.499999994'), 2)  # abs tol 1e-27
2.018429124836941e-15
sage: codes.bounds.mrrw2_bound_asymp(1/2 - 2^-100, 2)  # abs tol 1e-70
1.2535809688529749e-58
sage: codes.bounds.mrrw2_bound_asymp(1/2 - 2^-538, 2) > 0
True
sage: all(codes.bounds.mrrw2_bound_asymp(1/2 - 2^-n, 2) > 0
....:     for n in range(539, 543))
True
[Python] 
>>> from sage.all import *
>>> # needs scipy
>>> codes.bounds.mrrw2_bound_asymp(RDF('0.499999994'), Integer(2))  # abs tol 1e-27
2.018429124836941e-15
>>> codes.bounds.mrrw2_bound_asymp(Integer(1)/Integer(2) - Integer(2)**-Integer(100), Integer(2))  # abs tol 1e-70
1.2535809688529749e-58
>>> codes.bounds.mrrw2_bound_asymp(Integer(1)/Integer(2) - Integer(2)**-Integer(538), Integer(2)) > Integer(0)
True
>>> all(codes.bounds.mrrw2_bound_asymp(Integer(1)/Integer(2) - Integer(2)**-n, Integer(2)) > Integer(0)
...     for n in range(Integer(539), Integer(543)))
True

The second bound is only known for binary codes:

sage: codes.bounds.mrrw2_bound_asymp(1/5, 3)
Traceback (most recent call last):
...
NotImplementedError: the second MRRW bound is only implemented for binary codes

>>> from sage.all import *
>>> codes.bounds.mrrw2_bound_asymp(Integer(1)/Integer(5), Integer(3))
Traceback (most recent call last):
...
NotImplementedError: the second MRRW bound is only implemented for binary codes

Relative minimum distances outside the binary range are rejected:

sage: codes.bounds.mrrw2_bound_asymp(-1/10, 2)
Traceback (most recent call last):
...
ValueError: the relative minimum distance must be between 0 and 1/2
sage: codes.bounds.mrrw2_bound_asymp(3/5, 2)
Traceback (most recent call last):
...
ValueError: the relative minimum distance must be between 0 and 1/2
sage: codes.bounds.mrrw2_bound_asymp(1/2 + 2^-100, 2)
Traceback (most recent call last):
...
ValueError: the relative minimum distance must be between 0 and 1/2
[Python] 
>>> from sage.all import *
>>> codes.bounds.mrrw2_bound_asymp(-Integer(1)/Integer(10), Integer(2))
Traceback (most recent call last):
...
ValueError: the relative minimum distance must be between 0 and 1/2
>>> codes.bounds.mrrw2_bound_asymp(Integer(3)/Integer(5), Integer(2))
Traceback (most recent call last):
...
ValueError: the relative minimum distance must be between 0 and 1/2
>>> codes.bounds.mrrw2_bound_asymp(Integer(1)/Integer(2) + Integer(2)**-Integer(100), Integer(2))
Traceback (most recent call last):
...
ValueError: the relative minimum distance must be between 0 and 1/2
sage.coding.code_bounds.plotkin_bound_asymp(delta, q)[source]

The asymptotic Plotkin bound for the information rate.

This only makes sense when \(0 < \delta < 1-1/q\).

EXAMPLES:

sage: codes.bounds.plotkin_bound_asymp(1/4,2)
1/2

>>> from sage.all import *
>>> codes.bounds.plotkin_bound_asymp(Integer(1)/Integer(4),Integer(2))
1/2
sage.coding.code_bounds.plotkin_upper_bound(n, q, d, algorithm=None)[source]

Return the Plotkin upper bound.

Return the Plotkin upper bound for the number of elements in a largest code of minimum distance \(d\) in \(\GF{q}^n\). More precisely this is a generalization of Plotkin’s result for \(q=2\) to bigger \(q\) due to Berlekamp.

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_package_guava
192

>>> from sage.all import *
>>> codes.bounds.plotkin_upper_bound(Integer(10),Integer(2),Integer(3))
192
>>> codes.bounds.plotkin_upper_bound(Integer(10),Integer(2),Integer(3),algorithm='gap')  # optional - gap_package_guava
192
sage.coding.code_bounds.singleton_bound_asymp(delta, q)[source]

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)                                                               # needs sage.plot
Graphics object consisting of 1 graphics primitive

>>> from sage.all import *
>>> codes.bounds.singleton_bound_asymp(Integer(1)/Integer(4),Integer(2))
3/4
>>> f = lambda x: codes.bounds.singleton_bound_asymp(x,Integer(2))
>>> plot(f,Integer(0),Integer(1))                                                               # needs sage.plot
Graphics object consisting of 1 graphics primitive
sage.coding.code_bounds.singleton_upper_bound(n, q, d)[source]

Return the Singleton upper bound.

Return the Singleton upper bound for number of elements in a largest code of minimum distance \(d\) in \(\GF{q}^n\).

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

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

Codes that meet this bound are called maximum distance separable (MDS).

EXAMPLES:

sage: codes.bounds.singleton_upper_bound(10,2,3)
256

>>> from sage.all import *
>>> codes.bounds.singleton_upper_bound(Integer(10),Integer(2),Integer(3))
256
sage.coding.code_bounds.volume_hamming(n, q, r)[source]

Return the number of elements in a Hamming ball.

Return the number of elements in a Hamming ball of radius \(r\) in \(\GF{q}^n\).

EXAMPLES:

sage: codes.bounds.volume_hamming(10,2,3)
176

>>> from sage.all import *
>>> codes.bounds.volume_hamming(Integer(10),Integer(2),Integer(3))
176