MinT - Linear Programming Bound

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 A₀,…, A_s denote the distance distribution of an (s, N, d)-code C, i.e.,

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

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

A_i^⊥ = $\displaystyle {\frac{{1}}{{N}}}$ $\displaystyle \sum_{{j=0}}^{{s}}$ A_jK_i(j)

for 0 ≤ i ≤ s, where

K_i(X) = $\displaystyle \sum_{{r=0}}^{{i}}$ ( – 1)^r(b – 1)^i−r $\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 A₀,…, A_s as well as A₀^⊥,…, A_s^⊥ are distance distributions of codes, the following constraints must be satisfied:

A_i ≥ 0 for i = 0,…, s.
A_i^⊥ ≥ 0 for i = 0,…, s, where A_i^⊥ can be replaced by a linear combination of A₀,…, A_s according to the Krawtchouk transformation, i.e., one actually requires that
$\displaystyle \sum_{{j=0}}^{{s}}$ A_jK_i(j) ≥ 0
for i = 0,…, s.

Furthermore, we have

A₀ = 1 and
A₁ = … = A_d−1 = 0 because C has minimum distance d.

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 = A₀ + A₁ + … + A_s = 1 + A_d + … + A_s 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 = b^s/N of any linear OA(M, s,F_b, d−1).

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

A_i^⊥ := $\displaystyle {\frac{{1}}{{N}}}$ $\displaystyle \sum_{{j=0}}^{{s}}$ A_jK_i(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 A_i^⊥ ≥ 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 F_b.

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 A_i^⊥ for i = 0,…, s. Define A_i as

A_i := $\displaystyle {\frac{{1}}{{M}}}$ $\displaystyle \sum_{{j=0}}^{{s}}$ A_j^⊥K_i(j)

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

A_i^⊥ = $\displaystyle {\frac{{1}}{{N}}}$ $\displaystyle \sum_{{j=0}}^{{s}}$ A_jK_i(j)

with N := b^s/M. The dual distance of A is defined as the largest integer d, such that A_i = 0 for i = 1,…, d−1. Based on this notation it is shown in [1] that A_i ≥ 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 = b^s/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}}$ c_iK_i(X)

such that c_i ≥ 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

N ≤ p(0)

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

M ≥ b^s/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:

The Rao and Hamming bound with
p(X) = $\displaystyle \sum_{{i=0}}^{{s}}$ $\displaystyle \left(\vphantom{\frac{\sum_{j=0}^{\left\lfloor k/2\right\rfloor }… …}(i)}{\sum_{j=0}^{\left\lfloor k/2\right\rfloor }\binom{s}{j}(b−1)^{j}}}\right.$ $\displaystyle {\frac{{\sum_{j=0}^{\left\lfloor k/2\right\rfloor }K_{j}(i)}}{{\sum_{j=0}^{\left\lfloor k/2\right\rfloor }\binom{s}{j}(b−1)^{j}}}}$ $\displaystyle \left.\vphantom{\frac{\sum_{j=0}^{\left\lfloor k/2\right\rfloor }… …m_{j=0}^{\left\lfloor k/2\right\rfloor }\binom{s}{j}(b−1)^{j}}}\right)^{{2}}_{}$ K_i(X).
The (dual) Plotkin bound with
p(X) = $\displaystyle {\frac{{b(k+1-X)}}{{b(k+1)-s(b−1)}}}$ = 1 + $\displaystyle {\frac{{1}}{{b(k+1)-s(b−1)}}}$ K₁(X).
The Bush bounds.
The Singleton bound with
p(X) = b^s−k $\displaystyle \binom{s-X}{s-k}$ / $\displaystyle \binom{s}{k}$ = $\displaystyle \sum_{{i=0}}^{{s}}$ $\displaystyle \binom{s-i}{k}$ $\displaystyle \binom{s}{k}$ K_i(X).

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: 2015-09-03. http://mint.sbg.ac.at/desc_CBoundLP.html

Show usage of this method

Linear Programming Bound

Bounds Established Using an LP-Solver

An Alternative Formulation of the LP Bound and Explicit Solutions

See also

References

Copyright