Gilbert–Varšamov Bound for OOAs

The Gilbert-Varšamov bound for OOAs [1, Theorem 6.1] gives a sufficient condition for finding s vectors from Fbm that can be used for embedding a linear ordered orthogonal array OOA(bm, s,Fb, T −1, k) in a linear OOA(bm, s,Fb, T , k), i.e., for increasing the depth of the original OOA from T −1 to T . The condition is

Vb(T ,s−1)(kT ) < bm−T+1,

where Vb(T , σ)(r) is the volume of a ball with radius r in the NRT-space Fb(T , σ).

The proof uses a counting argument, ensuring that for each missing column in the generator matrix the number of vectors that cause prohibited linear dependencies is always strictly less than the number of vectors available in Fbm. Thus, codes obtained from this method are non-constructive.

A weaker result (corresponding to the Gilbert bound in coding theory) was obtained earlier in [2, Theorem 4]. It states that a linear OOA with parameters as above exists, provided that

Vb(T ,s)(k) < bm+1.

Applications

If the condition is satisfied for all depths T = Tbegin,…, Tend, an OOA(bm, s,Fb, Tend, k) can be obtained from an OOA(bm, s,Fb, Tbegin − 1, k). The extremal cases for Tbegin and Tend are particularly important:

The following combinations for Tbegin and Tend are noteworthy:

See Also

References

[1]Jürgen Bierbrauer, Yves Edel, and Wolfgang Ch. Schmid.
Coding-theoretic constructions for (t, m, s)-nets and ordered orthogonal arrays.
Journal of Combinatorial Designs, 10(6):403–418, 2002.
doi:10.1002/jcd.10015
[2]Michael Yu. Rosenbloom and Michael A. Tsfasman.
Codes for the m-metric.
Problems of Information Transmission, 33:55–63, 1997.
[3]Andrew T. Clayman, Kenneth Mark Lawrence, Gary L. Mullen, Harald Niederreiter, and Neil J. A. Sloane.
Updated tables of parameters of (t, m, s)-nets.
Journal of Combinatorial Designs, 7(5):381–393, 1999.
doi:10.1002/(SICI)1520-6610(1999)7:5<381::AID-JCD7>3.0.CO;2-S MR1702298 (2000d:05014)

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 OOAs.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2008-04-04. http://mint.sbg.ac.at/desc_OGV.html

Show usage of this method