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

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 H is less or equal to 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 H. Thus (H|x) is the generator matrix of a linear OA(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

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−1V_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 y ∈ C left, such that [C,x] is an [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]

• Gilbert-Varshamov bound at

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