Glossary

(tms)-Net

Let 0 ≤ tm and s ≥ 1 be integers. A (t, m, s)-net in base b is a set of bm points in the s-dimensional half-open unit cube [0, 1)s such that every elementary interval in base b with volume btm contains exactly bt points [1, Definition 2.2]. An elementary interval in base b is an interval of the form

$\displaystyle \prod_{{i=1}}^{{s}}$[ai/bki,(ai +1)/bki)

with integers ki ≥ 0 and 0 ≤ ai < bki [1, Definition 2.1].

An (mk, m, s)-net N in base b is equivalent to an OOA (bm, s, Sb,∞, k) (cf. propagation rule extracting embedded OOA). The OOA A is derived from the b-adic expansion of the coordinates of the points of N as follows:

A = {(ηi,j−1(⌊bjxi⌋ modb))(i, j) ∈ {1,…, s}×ℕ  :  xN},

with ηi,j : Sb↔{0,…, b – 1} denoting arbitrary bijections.

A (t, m, s)-net N is called digital over the field Fb if there exist bijections ηi,j : Fb→{0,…, b – 1} such that the corresponding OOA is linear over Fb.

References

[1]Harald Niederreiter.
Point sets and sequences with small discrepancy.
Monatshefte für Mathematik, 104(4):273–337, December 1987.
doi:10.1007/BF01294651 MR918037 (89c:11120)

(ts)-Sequence

Let b ≥ 2 and let Sb denote a set with cardinality b. A (t, s)-sequence S in base b is a sequence

x0,x1,… ∈ Sb(s,∞)

such that the OOAs containing the runs xi with jbmi < (j + 1)bm are OOA(bm, s, Sb,∞, mt) for all mt and all j ≥ 0. Thus the point sets defined by these OOAs are (t, m, s)-nets in base b for all mt and all j ≥ 0.

A (t, s)-sequence S is called digital over the finite field Fb if there exists a sequence c1,c2,… ∈ Fb(s,∞) such that c1,…,cm is a basis of the linear OOA {x0,x1,…,xbm−1} for all mt. The ∞×(s,∞)-matrix (c1,c2,…)T is called the generator matrix of S.

The definition given here is equivalent to the one in [1]. The original definition of (t, s)-sequences given in [2, Definition 2.4] defines (t, s)-sequences in terms of the points

($\displaystyle \sum_{{j=1}}^{{\infty}}$$\displaystyle {\frac{{\eta_{i,j}(x_{(i,j)})}}{{b^{j}}}}$)i=1,…, s

in [0, 1]s. Therefore it cannot distinguish between different digit expansions resulting in the same coordinates.

References

[1]Harald Niederreiter and Chaoping Xing.
Low-discrepancy sequences and global function fields with many rational places.
Finite Fields and Their Applications, 2(3):241–273, July 1996.
doi:10.1006/ffta.1996.0016 MR1398076 (97h:11080)
[2]Harald Niederreiter.
Point sets and sequences with small discrepancy.
Monatshefte für Mathematik, 104(4):273–337, December 1987.
doi:10.1007/BF01294651 MR918037 (89c:11120)

Hamming Space

Let S := Sb denote an abelian group with cardinality b. The s-dimensional Hamming space over S is the metric, s-dimensional product space Ss with weight function

w(x) = |{i ∈ {1,…, s}  :  xi ≠ 0}|

and a metric defined as

d (x,y) := w(xy).

In other words, two vectors x,y have distance d = d (x,y) if they differ in exactly d positions.

Usually S is a finite field Fb, which makes Ss = Fbs an s-dimensional vector space.

Hamming space is the ambient space for codes as well as orthogonal arrays.

Ordered Space or NRT-Space

Let S := Sb denote an abelian group with cardinality b. The ordered space or NRT-space of dimension s and depth T over S, denoted by S(s,T ), is the metric, sT -dimensional product space of S with coordinates indexed by the elements of {1,…, s}×{1,…, T }. The metric d : S(s,T )×S(s,T )→ℕ0 is defined as

d (x,y) := w(xy),

where w : S(s,T )→ℕ0 is a weight function defined as

w(x) := $\displaystyle \sum_{{i=1}}^{{s}}$max{j ∈ {1,…, T }  :  x(i,j) ≠ 0}.

The depth T can also be unbounded. In this case we write T = ∞, denote the space by S(s,∞), use {1,…, s}×ℕ as the set of coordinates and define w : S(s,∞)→ℕ0∪{∞} by

w(x) := $\displaystyle \sum_{{i=1}}^{{s}}$max{j ∈ ℕ  :  x(i,j) ≠ 0}.

NRT-space is the ambient space for NRT-codes as well as ordered orthogonal arrays. For T = 1 NRT-space is equivalent to Hamming space.

In MinT the elements of S(s,T ) are usually written in the form

x = (x(1,1),…, x(1,T) |  ⋯  | x(s,1),…, x(s,T)) = (x(i,1),…, x(i,T))i=1,…, s

or

x = (x(1,1), x(1,2),… |  ⋯  | x(s,1), x(s,2),…) = (x(i,1), x(i,2),…)i=1,…, s

if T = ∞.

Ordered Orthogonal Array

Let M, s, T , and ksT be integers. An ordered orthogonal array OOA(M, s, Sb, T , k) is a multi set of M elements of the NRT-space S(s,T ) such that each possible projection on k coordinates of the form

(1, 1),…,(1, k1) |  ⋯  | (s, 1),…,(s, ks)

with k1 + … + ks = k is balanced, i.e., each of the bk possible k-tuples over S appears the same number of times in such a projection.

An OOA(M, s, Sb, 1, k) is an orthogonal array OA(M, s, Sb, k). Thus OOAs are a generalization of OAs.

An OOA A is linear over the finite field Fb if S = Fb and if A is a linear subspace of Fb(s,T ).

If A is a linear OOA(bm, s,Fb, T , k), its dual C := A is a linear [(s, T ), sT m, k + 1]-NRT-code over Fb and vice versa [1]. Therefore, linear NRT-codes and linear OOAs are equivalent objects and MinT does not distinguish between them.

Every OOA A defines a point set N in [0, 1)s using the mapping

N = {($\displaystyle \sum_{{j=1}}^{{T}}$$\displaystyle {\frac{{\eta_{i,j}(x_{i,j})}}{{b^{j}}}}$)i=1,…, s  :  xA},

where ηi,j : Sb→{0,…, b – 1} are arbitrary bijections for i = 1,…, s and j = 1,…, T . If T k, N is a (mk, m, s)-net in base b.

References

[1]Harald Niederreiter and Gottlieb Pirsic.
Duality for digital nets and its applications.
Acta Arithmetica, 97(2):173–182, 2001.
MR1824983 (2001m:11130)

Orthogonal Array

Let M, s, and ks be integers. An orthogonal array OA(M, s, Sb, k) is a multiset of M s-tuples in the Hamming space Ss, with S := Sb denoting a set of cardinality b. An OA has strength k if each possible projection on k coordinates is balanced, i.e., each of the bk possible k-tuples over S appears the same number of times in such a projection.

An orthogonal array A is called linear over the finite field Fb if S = Fb and if A is a linear subspace of Fbs. In this case, the parameters are usually written in the form OA(bm, s,Fb, k) with m denoting the Fb-dimension of A.

If A is a linear OA(bm, s,Fb, k), its dual C := A is a linear [s, sm, k + 1]-code over Fb and vice versa [1]. Therefore, linear codes and linear orthogonal arrays are equivalent objects and MinT does not distinguish between them.

References

[1]Raj Chandra Bose.
On some connections between the design of experiments and information theory.
Bulletin de l’Institut International de Statistique, 38(4):257–271, 1961.
MR0148190 (26 #5698)

Code

An (s, N, d)-code C over a finite field Fb is a non-empty subset of the s-dimensional Hamming space Fbs with cardinality N such that any two code words of C have Hamming distance at least d, i.e., they differ in at least d positions.

If C is an Fb-linear subspace of Fbs, C is called linear and is denoted as [s, n, d]-code with N = bn, i.e., n is the dimension of C.

If C is a linear [s, n, d]-code over Fb, its dual A := C is a linear orthogonal array OA(bsn, s,Fb, d−1) and vice versa [1]. Therefore, linear codes and linear orthogonal arrays are equivalent objects and MinT does not distinguish between them.

References

[1]Raj Chandra Bose.
On some connections between the design of experiments and information theory.
Bulletin de l’Institut International de Statistique, 38(4):257–271, 1961.
MR0148190 (26 #5698)

NRT-Code

An ((s, T ), N, d)-NRT-code C over a finite field Fb is a subset of the s-dimensional NRT space Fb(s,T ) with cardinality N such that any two code words of C have NRT-distance at least d. NRT-codes were first studied in detail in [1].

An ((s, 1), N, d)-NRT-code is also an (s, N, d)-code. Thus NRT-codes are a generalization of normal codes.

If C is an Fb-linear subspace of Fb(s,T ), C is called linear and is denoted as [(s, T ), n, d]-code with N = bn, i.e., n is the dimension of C.

If C is a linear [(s, T ), n, d]-code over Fb, its dual A := C is a linear ordered orthogonal array OOA(bsT−n, s,Fb, T , d−1) and vice versa [2]. Therefore, linear NRT-codes and linear OOAs are equivalent objects and MinT does not distinguish between them.

References

[1]Michael Yu. Rosenbloom and Michael A. Tsfasman.
Codes for the m-metric.
Problems of Information Transmission, 33:55–63, 1997.
[2]Harald Niederreiter and Gottlieb Pirsic.
Duality for digital nets and its applications.
Acta Arithmetica, 97(2):173–182, 2001.
MR1824983 (2001m:11130)

Volume of Ball in Hamming Space

Let Sb denote a set with cardinality b and Sbs the s-dimensional Hamming space over Sb. The spherical shell C(r) in Sbs with center c and radius r ∈ ℕ0 is defined as

C(r) = {xSbs  :  d (x,c) = r}.

The ball B(r) in Sbr with center c and radius r is defined as

B(r) = $\displaystyle \bigcup_{{\rho=0}}^{{r}}$C(ρ) = {xSbs  :  d (x,c) ≤ r}.

It is easy to see that the volume of C(r) and B(r) is independent of c. It is denoted by vbs(r) and Vbs(r), respectively, and given by the formulas

vbs(r) = $\displaystyle \binom{s}{r}$(b – 1)r

and

Vbs(r) = $\displaystyle \sum_{{\rho=0}}^{{r}}$vbs(ρ) = $\displaystyle \sum_{{\rho=0}}^{{r}}$$\displaystyle \binom{s}{\rho}$(b – 1)ρ.

Volume of Ball in NRT Space

Let Sb denote a set with cardinality b and Sb(s,T ) the s-dimensional NRT-space with depth T . The ball B(r) in Sbs with center c and radius r ∈ ℕ0 is defined as

B(r) = {xSbs  :  d (x,c) ≤ r}.

It is easy to see that the volume of B(r) is independent of c. It is denoted by Vb(s,T )(r) and given by the formula

Vb(s,T )(r) = 1 + $\displaystyle \sum_{{\rho=1}}^{{r}}$$\displaystyle \sum_{{\pi}}^{}$(b – 1)hbρh$\displaystyle \binom{s}{c_{1},\ldots,c_{T},s-h}$,

with the second sum running over all partitions π of ρ with summands less or equal T , i.e., over all sums π : ρ = 1c1 +2c2 + ⋯ + TcT , where cj ∈ ℕ0 denotes the number of times the summand j appears in π for j = 1,…, T , and h = c1 + ⋯ + cT denotes the total number of summands. A more explicit formula for Vb(s,T ) is

Vb(s,T )(r) = 1 + $\displaystyle \sum_{{\rho=1}}^{{r}}$$\displaystyle \sum_{{h=1}}^{{\rho}}$$\displaystyle \binom{s}{h}$(b – 1)hbρh$\displaystyle \sum_{{j=0}}^{{\left\lfloor \frac{\rho-h}{T}\right\rfloor }}$( – 1)j$\displaystyle \binom{h}{j}$$\displaystyle \binom{\rho-Tj−1}{h−1}$.

For T = ∞ the formula simplifies to

Vb(s,∞)(r) = 1 + $\displaystyle \sum_{{\rho=1}}^{{r}}$$\displaystyle \sum_{{h=1}}^{{\rho}}$$\displaystyle \binom{s}{h}$$\displaystyle \binom{\rho−1}{h−1}$(b – 1)hbρh

and one has Vb(s,T )(r) = Vb(s,∞)(r) for all rT .

For T = 1 the formula simplifies to Vb(s,1) = Vbs, the volume of a ball in Hamming space.

Constant-Weigth Code

An (s, N, d)-code C over Fb is called a constant-weight code if all code words of C have the same Hamming weight, i.e., w(x) = w for all xC.

Note that a non-trivial linear code can never be a constant weight code, because it contains 0 with w( 0) = 0 as well as a non-zero code word x with w(x) > 0. However, linear codes C exist such that C ∖ { 0} is a constant-weight code.

Projective Code

A linear [s, n, d]-code C over Fb with n ≥ 2 and generator matrix G is called projective, if the s columns of G (interpreted as homogenous coordinates) form distinct points in the projective space PG(n−1, b). This is equivalent to C being a linear orthogonal array with strength at least 2.

Algebraic Function Field

Let Fb denote a finite field. An algebraic function field F with full constant field Fb, denoted by F/Fb is an algebraic extention of the rational function field Fb(x) such that the constant functions in F are exactly the elements of Fb.

Two important parameters of F are the genus, denoted by g(F/Fb), and the number of rational places, denoted by N(F/Fb). For a given field of constants Fb and genus g one is usually interested in finding a field F with g(F/Fb) = g such that N(F/Fb) is maximal. This number is denoted by

Nb(g) := $\displaystyle \max_{{\substack{F\\ g(F/\mathbf{F}_{b})=g} }}^{}$N(F/Fb).

Algebraic function fields F/Fb are in a certain sense equivalent to algebraic curves c over Fb. In this setting, the rational places of F correspond to the rational points of c and the genus of F is the same as the genus of c.

Finite Projective Space

Let u ≥ 1 and b a prime power. Then PG(u, b) denotes the u-dimensional projective space over Fb. The 2-dimensional projective space PG(2, b) is also known as projective plane. PG(u, b) is usually constructed as the set of all one-dimensional subspaces of Fbu+1 and a point x ∈ PG(u, b) is written in homogenous coordinates as

x = (x1 : … : xu+1).

The affine space AG(u, b) can be obtained from PG(u, b) by discarding a hyperplane.

Finite Affine Space

Let u ≥ 1 and b a prime power. Then AG(u, b) denotes the u-dimensional affine space over Fb, usually identified with the vector space Fbu. The 2-dimensional affine space AG(2, b) is also known as affine plane.

AG(u, b) can be embedded in the projective space PG(u, b) using

(x1,…, xu) $\displaystyle \mapsto$ (x1 : … : xu : 1).

Caps

Caps are sets of points in some space such that no triple of points is collinear, i.e., every line contains at most two points of the cap. A cap containing s points is called an s-cap.

s-caps in the u-dimensional projective space PG(u, b) form the generator matrix of linear orthogonal arrays OA(bu+1, s,Fb, 3) and vice versa. The dual of such an OA is a linear [s, s−(u + 1), 4]-code over Fb. The size of the largest possible cap in PG(u, b) is denoted by m2(u, b).

Arcs

Arcs in a u-dimensional space are sets of points such that every hyperplane contains at most u points of the arc. An arc containing s points is called an s-arc.

s-arcs in the projective space PG(u, b) form a generator matrix of a linear orthogonal array OA(bu+1, s,Fb, u + 1) with index unity and vice versa. The dual of such an OA is a a linear [s, s−(u + 1), u + 2]-MDS-code over Fb.

It follows from the duality of MDS codes that s-arcs in PG(u, b) are equivalent to s-arcs in PG(su, b).

See Also

What Makes an Existence Result Constructive?

MinT distinguishes between constructions and pure existence results:

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