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(bm, s,Fb, k), provided that

bm > Vbs−1(k−1),

where Vbσ(r) denotes the volume of a ball with radius r in the Hamming space Fbσ. The existence of a linear [s, sm, k + 1]-code over Fb follows by duality.

The validity of this statement is easy to see: Let H denote the generator matrix of a linear OA(bm, s – 1,Fb, k). The maximum number of possible linear combinations of at most k−1 column vectors of H is less or equal to Vbs−1(k−1). If this number is less than bm, then there exists a vector xFbm that is linearly independent of any k−1 columns in H. Thus (H|x) is the generator matrix of a linear OA(bm, s,Fb, 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 Fb exists provided that

bn−1Vbs(d – 1) < bs.

The existence of a linear OA(bsn, s,Fb, d−1) follows by duality.

The result follows from the fact that the bn−1 balls of radius d−1 centered at the bn−1 code words of an [s, n−1, d]-code C cannot cover more than bn−1Vbs(d−1) vectors in Fbs. Thus, there is at lest one vector xFbs with d (x,y) ≥ d for all yC left, such that [C,x] is an [s, n, d]-code.

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

See also

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

Show usage of this method