## Gilbert–Varšamov Bound for OAs

The Gilbert bound and the Varšamov bound are existence results for linear codes and linear orthogonal arrays, respectively. Since both methods use a counting argument, the resulting codes and OAs are non-constructive.

### The Varšamov Bound

The Varšamov bound [1] guarantees the existence of a linear OA(*b*^{m}, *s*,**F**_{b}, *k*), provided that

*b*

^{m}>

*V*

_{b}

^{s−1}(

*k*−1),

where *V*_{b}^{σ}(*r*) denotes the volume of a ball with radius *r* in the Hamming space **F**_{b}^{σ}. The existence of a linear [*s*, *s*−*m*, *k* + 1]-code over **F**_{b} follows by duality.

The validity of this statement is easy to see: Let * H* denote the generator matrix of a linear OA(

*b*

^{m},

*s*– 1,

**F**

_{b},

*k*). The maximum number of possible linear combinations of at most

*k*−1 column vectors of

*is less or equal to*

**H***V*

_{b}

^{s−1}(

*k*−1). If this number is less than

*b*

^{m}, then there exists a vector

*∈*

**x****F**

_{b}

^{m}that is linearly independent of any

*k*−1 columns in

*. Thus (*

**H***|*

**H***) is the generator matrix of a linear OA(*

**x***b*

^{m},

*s*,

**F**

_{b},

*k*). Obviously, the existence of the original OA follows also from the Varšamov bound, allowing the construction of the final generator matrix by iteratively appending columns to the

*m*× 0 matrix.

### The Gilbert Bound

The Gilbert bound [2] is a similar, but slightly weaker result, stating that a linear [*s*, *n*, *d*]-code over **F**_{b} exists provided that

*b*

^{n−1}

*V*

_{b}

^{s}(

*d*– 1) <

*b*

^{s}.

The existence of a linear OA(*b*^{s−n}, *s*,**F**_{b}, *d*−1) follows by duality.

The result follows from the fact that the *b*^{n−1} balls of radius *d*−1 centered at the *b*^{n−1} code words of an [*s*, *n*−1, *d*]-code C cannot cover more than *b*^{n−1}*V*_{b}^{s}(*d*−1) vectors in **F**_{b}^{s}. Thus, there is at lest one vector * x* ∈

**F**

_{b}

^{s}with

*d*(

*,*

**x***) ≥*

**y***d*for all

*∈ C left, such that [C,*

**y***] is an [*

**x***s*,

*n*,

*d*]-code.

Asymptotically the Gilbert bound and the Varšamov bound are equivalent.

### See also

Generalization for arbitrary OOAs

The Varšamov bound can be strengthened to the Varšamov-Edel bound.

If the Varšamov bound is used for lengthening an existing code, a pair of nested codes is obtained, such that construction X can be applied.

[3, Theorem 1.12 and Problem (1.45)], [4, Theorem 9.12 and Exercise 9.11]

### References

[1] | Rom Rubenovich Varšamov. Estimate of the number of signals in error correcting codes. Doklady Akademii Nauk SSSR, 17:739–741, 1957. |

[2] | Edgar N. Gilbert. A comparison of signalling alphabets. Bell System Technical Journal, 31:504–522, 1952. |

[3] | F. Jessie MacWilliams and Neil J. A. Sloane.The Theory of Error-Correcting Codes.North-Holland, Amsterdam, 1977. |

[4] | 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. “Gilbert–Varšamov Bound for OAs.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2008-04-04.
http://mint.sbg.ac.at/desc_CGV.html