## 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: 2024-09-05.
http://mint.sbg.ac.at/desc_CGV.html