Coding-theoretic constructions for (t,m,s)-nets and ordered orthogonal arrays

coauthors Jürgen Bierbrauer and Wolfgang Ch.Schmid

Journal of Combinatorial Designs, 10 (2002), 403-418.

doi:10.1002/jcd.10015


Abstract:

(t,m,s)-nets were defined by Niederreiter in the context of quasi-Monte Carlo methods of numerical integration. Niederreiter pointed out close connections to certain combinatorial and algebraic structures. This was made precise in the work of Lawrence, Mullen and Schmid. These authors introduce a large class of finite combinatorial structures, which we will call ordered orthogonal arrays OOA. These OOA contain orthogonal arrays as a subclass. (t,m,s)-nets are equivalent to another parametric subclass of OOA. Loosely speaking a (t,m,s)_q-net is linear if it is vectorspace over the field GF(q) with q elements. The duality between linear codes and linear orthogonal arrays carries over to the more general setting of linear OOA. This has been described by Rosenbloom-Tsfasman.
Our main results are generalizations of coding-theoretic construction techniques from Hamming space to RT-space, most notably concatenation (equivalently: Kronecker products), the (u,u+v)-construction and the Gilbert-Varshamov bound.
Let k=m-t denote the strength of a net. If a linear (t,m,s)_q-net exists, where m‹s, then a linear code [s,s-m,k+1]_q exists. From this point of view it is a basic problem (the problem of net-embeddability) to decide when a code [s,s-m,k+1]_q can be completed to a linear net (m-k,m,s)_q. More generally we ask when a linear OOA with certain parameters can be embedded in a larger OOA. We speak of a theorem of Gilbert-Varshamov type if the existence of the larger OOA can be guaranteed whenever the parameters satisfy a certain numerical condition. In the final section we apply our theoretical construction techniques as well as computer-generated net embeddings of error-correcting codes to improve upon net-parameters for nets of moderate strength and dimension defined over small fields.

Errata:
In the tables of the printed version are wrong entries. The entry for
q=2, k=5, m=25, s=2503, should replaced by s=2053.
q=3, k=7, m=18, s=53, should replaced by s=51.
q=4, k=3, m=3, s=6, should replaced by s=5.
q=4, k=4, m=10, s=373, should replaced by s=341.
q=4, k=13, m=34, s=98, should replaced by s=96.
q=4, k=13, m=35, s=112, should replaced by s=107.
q=4, k=13, m=36, s=128, should replaced by s=119.
q=4, k=14, m=37, s=106, should replaced by s=104.
q=4, k=13, m=38, s=119, should replaced by s=115.
q=5, k=9, m=21, s=80, should replaced by s=79.

An up to date and more comfortable online version of the tables is the MinT data base of tms-nets.

The computer results mentioned in the paper can be found here.

Download the preprint as pdf.


| home | List of publications |