Linear Programming Bound

The Linear Programming Bound (LP-bound), established by Delsarte in [1], is one of the strongest bounds on the number of codewords in a code as well as on the number of runs in an orthogonal array.

Let A0,…, As denote the distance distribution of an (s, N, d)-code C, i.e.,

Ai := $\displaystyle {\frac{{1}}{{N}}}$|{(x, y) ∈ C2  :  d (x, y) = i}|.

For linear codes the LP-bound can be established using the following result due to MacWilliams [2]: The distance distribution A0,…, As of the dual code C is always given by the Krawtchouk transformation

Ai = $\displaystyle {\frac{{1}}{{N}}}$$\displaystyle \sum_{{j=0}}^{{s}}$AjKi(j)

for 0 ≤ is, where

Ki(X) = $\displaystyle \sum_{{r=0}}^{{i}}$( – 1)r(b – 1)ir$\displaystyle \binom{X}{r}$$\displaystyle \binom{s-X}{i-r}$

are the Krawtchouk polynomials of degree i in base b, a family of orthogonal polynomials.

Since A0,…, As as well as A0,…, As are distance distributions of codes, the following constraints must be satisfied:

Furthermore, we have

Since any conceivable linear (s, N, d)-code has to satisfy the conditions given above, an upper bound on the number of its code words can be found by maximizing N = A0 + A1 + … + As = 1 + Ad + … + As subject to the stated linear constraints. Thus, solving this linear program yields an upper bound on the number of code words N of any linear (s, N, d)-code, or, equivalently, a lower bound on the number of runs M = bs/N of any linear OA(M, s,Fb, d−1).

For non-linear codes one defines the dual distance distribution by

Ai := $\displaystyle {\frac{{1}}{{N}}}$$\displaystyle \sum_{{j=0}}^{{s}}$AjKi(j)

for i = 0,…, s. Even though there is (in general) no dual code, it is shown in [1] that the dual distance distribution satisfies Ai ≥ 0 for all i = 0,…, s. So the same linear program as discussed above leads to an upper bound on the number of codewords N of an arbitrary (s, N, d)-code over Fb.

In order to establish a lower bound on the number of runs of an arbitrary orthogonal array, an additional result from [1] is required: Let A denote a (linear or non-linear) OA with M runs and weight distribution Ai for i = 0,…, s. Define Ai as

Ai := $\displaystyle {\frac{{1}}{{M}}}$$\displaystyle \sum_{{j=0}}^{{s}}$AjKi(j)

for i = 0,…, s, which can be shown to be equivalent to

Ai = $\displaystyle {\frac{{1}}{{N}}}$$\displaystyle \sum_{{j=0}}^{{s}}$AjKi(j)

with N := bs/M. The dual distance of A is defined as the largest integer d, such that Ai = 0 for i = 1,…, d−1. Based on this notation it is shown in [1] that Ai ≥ 0 for all i = 0,…, s and that A is an orthogonal array with strength d−1. Thus, the same linear program as discussed above can be used for obtaining an upper bound on N, which yields a lower bound on M = bs/N.

Bounds Established Using an LP-Solver

By solving the linear program (LP) described above, a lower bound on the number of runs of an OA with given base b, strength k, and number of factors s is obtained. Solving such an LP is a computationally involved process, especially if s is large, because this number determines the number of variables of the LP. A second problem is that the LP is numerically unstable, therefore arbitrary precision arithmetic has to be used in order to obtain reliable results.

Nevertheless, this LP can be solved if s is not too large. We use the computer algebra system Mathematica® with the built-in operation “LinearProgramming”. Currently, MinT contains all results up to s = 150 and k = 110 for all bases, as well as sporadic results for s up to 300. Most of our calculations have also been verified by using alternative formulations of the LP and by using a different LP-solver. Detailed information about these calculations can be found in [3].

An Alternative Formulation of the LP Bound and Explicit Solutions

An alternative formulation of the LP bound is as follows: Suppose we can find a polynomial p of the form

p(X) = 1 + $\displaystyle \sum_{{i=1}}^{{s}}$ciKi(X)

such that ci ≥ 0 for i = 1, 2,…, s and p(j) ≤ 0 for j = k + 1, k + 2,…, s. Then the number of code words in any (s, N, k + 1)-code satisfies

Np(0)

and the number of runs in any OA(M, s, Sb, k) satisfies

Mbs/p(0).

Thus, explicit bounds for OAs and codes can be obtained by finding suitable polynomials p and calculating p(0). The following bounds can be derived in this manner:

See also

References

[1]Philippe Delsarte.
An algebraic approach to the association schemes of coding theory.
Philips Research Reports Supplement, 10, 1973.
[2]F. Jessie MacWilliams.
A theorem on the distribution of weights in a systematic code.
Bell System Technical Journal, 42:79–94, 1963.
[3]Horst Trinker.
Linear programming bounds on ordered orthogonal arrays.
Master’s thesis, University of Salzburg, Austria, January 2007.
[4]A. S. Hedayat, Neil J. A. Sloane, and John Stufken.
Orthogonal Arrays.
Springer Series in Statistics. Springer-Verlag, 1999.
[5]Jürgen Bierbrauer.
Introduction to Coding Theory.
Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, London, New York, Washington D.C., 2004.
MR2079734 (2005f:94001)

Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Linear Programming Bound.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2008-04-04. http://mint.sbg.ac.at/desc_CBoundLP.html

Show usage of this method