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.
Best Known Bounds for Linear Codes
A Magma database allows the user access to tables giving the best known upper and lower bounds of the Length, Dimension, and MinimumWeight of linear codes. Tables are currently available relating to codes over \(GF(2)\) and \(GF(4)\) with \(1 \le\) Length \(\le 256\), over \(GF(3)\) with \(1 \le\) Length \(\le 243\), over \(GF(5), GF(8)\), and \(GF(9)\) with \(1 \le\) Length \(\le 130\), and over \(GF(7)\) with \(1 \le\) Length \(\le 100\).
- 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 required length is out of the range of the database then no bound is available and -1 is 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 required length is out of the range of the database then no bound is available and -1 is returned.
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 on the cardinality of a (possibly non-linear) code of length \(n\) and minimum distance \(d\) over the field \(K\). The bound is formed by calculating the maximal possible average distance between codewords.
For binary codes the bound exists for \(n \le 2d\), (\(d\) even), or \(n \le 2d + 1\) (\(d\) odd). For codes over general fields the bound exists for \(d > (1-1/\#K)*n\).
- 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: Computed and Stored Cardinality Bounds (ex-89ddc1)
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 \({\bf F}_{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
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.