[Next][Prev] [Right] [Left] [Up] [Index] [Root] 
Bounds








Magma supplies various functions for computing lower and upper bounds for
parameters associated with codes. It also contains tables of best known
bounds for linear codes.
The functions in this section only apply to codes over finite fields.




Subsections



Best Known Bounds for Linear Codes






A Magma database allows the user access  to tables giving upper and 
lower bounds of the Length, Dimension, and MinimumWeight.
Tables are currently available relating to codes over GF(2) with
1 <= Length <= 256.



BKLCLowerBound(F, n, k) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Returns the best known lower bound on the maximum possible 
minimum weight of a linear code over finite field F having length 
n and dimension k.



BKLCUpperBound(F, n, k) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Returns the best known upper bound on the minimum weight of a linear 
code over finite field F of length n and dimension k.





BLLCLowerBound(F, k, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Returns the best known lower bound on the minimum  possible length 
of a linear code over finite field F having dimension k and 
minimum weight at least d.  If the necessary length is greater
than 256, then it is not available, and so the value 0 will be 
returned.





BLLCUpperBound(F, k, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Returns the best known upper bound on the minimum possible length of
a linear code over finite field F of dimension k and minimum weight 
at least d.  If the necessary length is greater then 256, then it 
is not available, and so the value 0 will be returned.





BDLCLowerBound(F, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Returns the best known lower bound on the maximum possible 
dimension of a linear code over finite field F having length n
and minimum weight at least d.





BDLCUpperBound(F, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Returns the best known upper bound on the dimension of
a linear code over finite field F having length n
and minimum weight at least d.





Bounds on the Cardinality of a Largest Code





EliasBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Return the Elias upper bound of the cardinality of a largest code of
length n and minimum distance d over the field K.



GriesmerBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Return the Griesmer upper bound of the cardinality of a largest code of
length n and  minimum distance d over the field K.



JohnsonBound(n, d) : RngIntElt, RngIntElt -> RngIntElt



Return the Johnson upper bound of the cardinality of a largest binary code of
length n and minimum distance d.



LevenshteinBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Return the Levenshtein upper bound of the cardinality of a largest code of
length n and  minimum distance d over the field K.



PlotkinBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Return the Plotkin upper bound of the cardinality of a largest code of
length n and minimum distance d over the field K.



SingletonBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Return the Singleton upper bound of the cardinality of a largest code of
length n and minimum distance d over the field K.



SpherePackingBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Return the Hamming sphere packing upper bound on the cardinality of a
largest codes of length n and minimum distance d over the field K.



GilbertVarshamovBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Return the Gilbert--Varshamov lower bound of the cardinality of a largest code 
(possibly non-linear) of length n and minimum distance d over the field K.



GilbertVarshamovLinearBound(K, n, d) : FldFin,RngIntElt,RngIntElt -> RngIntElt



Return the Gilbert--Varshamov lower bound of the cardinality of a largest linear
code of length n and minimum distance d over the field K.



VanLintBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt



Return the Van Lint lower bound of the cardinality of a largest code of
length n and minimum distance d over the field K.





Example CodeFld_Card-Best-Comparison (H97E39)

We compare computed and stored values of best known upper 
bounds of the dimension
of binary linear codes of length 20. The cardinality of a linear code
of dimension k over GF(q) is q^k, and so the computed bounds on
cardinality are compared with the stored bounds on dimension by taking
logs.







> n:=20;
> K := GF(2);
> [ Ilog(#K, Minimum( { GriesmerBound(K,n,d) , EliasBound(K,n,d),
>                       JohnsonBound(n,d) , LevenshteinBound(K,n,d),
>                       SpherePackingBound(K,n,d) } )) : d in [1..n] ];
[ 20, 19, 15, 14, 12, 11, 9, 8, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1 ]
> [ BDLCUpperBound(K,n,d) : d in [1..n] ];
[ 20, 19, 15, 14, 11, 10, 9, 8, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1 ]













Bounds on the Minimum Distance





BCHBound(C) : Code -> RngIntElt, RngIntElt



Given a cyclic code C, return the BCH bound for C.  This a lower
bound on the minimum weight of C.



GriesmerMinimumWeightBound(K, n, k) : FldFin,RngIntElt,RngIntElt->RngIntElt



Return the Griesmer upper bound of the minimum weight of a linear code of
length n and dimension k over the field K.



Asymptotic Bounds on the Information Rate





EliasAsymptoticBound(K, delta) : FldFin, FldPrElt -> FldPrElt



Return the Elias asymptotic upper bound of the information rate for
delta in [0, 1] over the field K.



McElieceEtAlAsymptoticBound(delta) : FldPrElt -> FldPrElt



Return the McEliece--Rodemich--Rumsey--Welch asymptotic upper bound of the
binary information rate for delta in [0, 1].



PlotkinAsymptoticBound(K, delta) : FldFin, FldPrElt -> FldPrElt



Return the Plotkin asymptotic upper bound of the information rate for
delta in [0, 1] over the field K.



SingletonAsymptoticBound(delta) : FldPrElt -> FldPrElt



Return the Singleton asymptotic upper bound of the information rate for
delta in [0, 1] over any finite field.



HammingAsymptoticBound(K, delta) : FldFin, FldPrElt -> FldPrElt



Return the Hamming asymptotic upper bound of the information rate
for delta in [0, 1] over the field K.



GilbertVarshamovAsymptoticBound(K, delta) : FldFin, FldPrElt -> FldPrElt



Return the Gilbert--Varshamov asymptotic lower bound of the information rate
for delta in [0, 1] over the field K.



Other Bounds





GriesmerLengthBound(K, k, d) : FldFin,RngIntEt,RngIntElt -> RngIntElt



Return the Griesmer lower bound of the length of a linear code of
dimension k and minimum distance d over K.



 [Next][Prev] [Right] [Left] [Up] [Index] [Root]