Gilbert–Varšamov Bound for Nets
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
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
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:
For Tbegin = 1, the existence of the final OOA is established without relying on any previously known OOA.
If Tend = k, an OOA(bm, s,Fb, k, k) is obtained. The net defined by this OOA is a digital (m−k, m, s)-net over Fb. Thus, for Tend = k the Gilbert-Varšamov bound for OOAs can be used for establishing the existence of a net.
The following combinations for Tbegin and Tend are noteworthy:
For Tbegin = Tend = 1, this method reduces to the well known Gilbert-Varšamov bound from coding theory.
For Tbegin = 1 and Tend = k, the existence of a digital (m−k, m, s)-net is shown without relying on any OOA. This is known as the “Gilbert-Varšamov bound for nets” [1, Theorem 6.2].
For Tbegin = 2 and Tend = k, the existence of a digital (m−k, m, s)-net is shown based on a linear orthogonal array OA(bm, s,Fb, k), i.e., on an OOA with depth 1. Since this OA is the dual of a linear [s, s−m, k + 1]-code, this procedure is known as “embedding a linear code in a net using the Gilbert-Varšamov bound” [1, Theorem 7.1].
See Also
For T = 1 the normal Gilbert-Varšamov bound for OAs and codes is obtained.
This procedure can always be reversed using depth reduction
The case with Tbegin = 1 and Tend = k is Construction “g” in [1].
The case with Tbegin = 2 and Tend = k is Construction “h” in [1].
The cases with Tbegin = 2, Tend = k, and k ∈ {3, 4} are listed in [3] as Construction 17 and 20, respectively.
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 Nets.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2015-09-03.
http://mint.sbg.ac.at/desc_OGV-net.html