Glossary

(t, m, s)-Net

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

$\displaystyle \prod_{{i=1}}^{{s}}$ [a_i/b^k_i,(a_i +1)/b^k_i)

with integers k_i ≥ 0 and 0 ≤ a_i < b^k_i [1, Definition 2.1].

An (m−k, m, s)-net N in base b is equivalent to an OOA (b^m, s, S_b,∞, 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⁻¹(⌊b^jx_i⌋ modb))_{(i, j) ∈ {1,…, s}×ℕ} : x ∈ N},

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

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

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)

(t, s)-Sequence

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

x₀,x₁,… ∈ S_b^(s,∞)

such that the OOAs containing the runs x_i with jb^m ≤ i < (j + 1)b^m are OOA(b^m, s, S_b,∞, m−t) for all m ≥ t and all j ≥ 0. Thus the point sets defined by these OOAs are (t, m, s)-nets in base b for all m ≥ t and all j ≥ 0.

A (t, s)-sequence S is called digital over the finite field F_b if there exists a sequence c₁,c₂,… ∈ F_b^(s,∞) such that c₁,…,c_m is a basis of the linear OOA {x₀,x₁,…,x_b^m−1} for all m ≥ t. The ∞×(s,∞)-matrix (c₁,c₂,…)^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 := S_b denote an abelian group with cardinality b. The s-dimensional Hamming space over S is the metric, s-dimensional product space S^s with weight function

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

and a metric defined as

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

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 F_b, which makes S^s = F_b^s 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 := S_b 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 )}→ℕ₀ is defined as

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

where w : S^{(s,T )}→ℕ₀ 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,∞)→ℕ₀∪{∞} 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}

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 k ≤ sT be integers. An ordered orthogonal array OOA(M, s, S_b, 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, k₁) | ⋯ | (s, 1),…,(s, k_s)

with k₁ + … + k_s = k is balanced, i.e., each of the b^k possible k-tuples over S appears the same number of times in such a projection.

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

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

If A is a linear OOA(b^m, s,F_b, T , k), its dual C := A^⊥ is a linear [(s, T ), sT −m, k + 1]-NRT-code over F_b 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} : x ∈ A},

where η_i,j : S_b→{0,…, b – 1} are arbitrary bijections for i = 1,…, s and j = 1,…, T . If T ≥ k, N is a (m−k, 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 k ≤ s be integers. An orthogonal array OA(M, s, S_b, k) is a multiset of M s-tuples in the Hamming space S^s, with S := S_b 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 b^k 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 F_b if S = F_b and if A is a linear subspace of F_b^s. In this case, the parameters are usually written in the form OA(b^m, s,F_b, k) with m denoting the F_b-dimension of A.

If A is a linear OA(b^m, s,F_b, k), its dual C := A^⊥ is a linear [s, s−m, k + 1]-code over F_b 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 F_b is a non-empty subset of the s-dimensional Hamming space F_b^s 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 F_b-linear subspace of F_b^s, C is called linear and is denoted as [s, n, d]-code with N = bⁿ, i.e., n is the dimension of C.

If C is a linear [s, n, d]-code over F_b, its dual A := C^⊥ is a linear orthogonal array OA(b^s−n, s,F_b, 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 F_b is a subset of the s-dimensional NRT space F_b^{(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 F_b-linear subspace of F_b^{(s,T )}, C is called linear and is denoted as [(s, T ), n, d]-code with N = bⁿ, i.e., n is the dimension of C.

If C is a linear [(s, T ), n, d]-code over F_b, its dual A := C^⊥ is a linear ordered orthogonal array OOA(b^sT−n, s,F_b, 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 S_b denote a set with cardinality b and S_b^s the s-dimensional Hamming space over S_b. The spherical shell C(r) in S_b^s with center c and radius r ∈ ℕ₀ is defined as

C(r) = {x ∈ S_b^s : d (x,c) = r}.

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

B(r) = $\displaystyle \bigcup_{{\rho=0}}^{{r}}$ C(ρ) = {x ∈ S_b^s : 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 v_b^s(r) and V_b^s(r), respectively, and given by the formulas

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

and

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

Volume of Ball in NRT Space

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

B(r) = {x ∈ S_b^s : d (x,c) ≤ r}.

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

V_b^{(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 π : ρ = 1c₁ +2c₂ + ⋯ + Tc_T, where c_j ∈ ℕ₀ denotes the number of times the summand j appears in π for j = 1,…, T , and h = c₁ + ⋯ + c_T denotes the total number of summands. A more explicit formula for V_b^{(s,T )} is

V_b^{(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

V_b^(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 V_b^{(s,T )}(r) = V_b^(s,∞)(r) for all r ≤ T .

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

Constant-Weigth Code

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

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 F_b 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 F_b denote a finite field. An algebraic function field F with full constant field F_b, denoted by F/F_b is an algebraic extention of the rational function field F_b(x) such that the constant functions in F are exactly the elements of F_b.

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

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

Algebraic function fields F/F_b are in a certain sense equivalent to algebraic curves c over F_b. 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 F_b. 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 F_b^u+1 and a point x ∈ PG(u, b) is written in homogenous coordinates as

x = (x₁ : … : x_u+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 F_b, usually identified with the vector space F_b^u. 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

(x₁,…, x_u) $\displaystyle \mapsto$ (x₁ : … : x_u : 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(b^u+1, s,F_b, 3) and vice versa. The dual of such an OA is a linear [s, s−(u + 1), 4]-code over F_b. The size of the largest possible cap in PG(u, b) is denoted by m₂(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(b^u+1, s,F_b, 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 F_b.

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

What Makes an Existence Result Constructive?

MinT distinguishes between constructions and pure existence results:

Existence Results provide proof of the existence of an object with certain parameters without giving an explicit method for its construction.
Constructions are explicit and effective methods for creating the object, i.e., the generator matrices for digital nets, orthogonal arrays, and linear codes, the point sets for nets, and the runs of an orthogonal array.
A method is considered constructive if a computer implementation or at least an algorithm allowing such an implementation is available. If generator matrices are available explicitly (tabulated in print or electronically), the method is also considered constructive.
A brute force search through the finite space of possible generator matrices for given parameters is not considered a constructive method.
Of course, a construction implies an existence result.

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: 2015-09-03. http://mint.sbg.ac.at/glossary.php

Glossary

(t, m, s)-Net

References

(t, s)-Sequence

References

Hamming Space

Ordered Space or NRT-Space

Ordered Orthogonal Array

References

Orthogonal Array

References

Code

References

NRT-Code

References

Volume of Ball in Hamming Space

Volume of Ball in NRT Space

Constant-Weigth Code

Projective Code

Algebraic Function Field

Finite Projective Space

Finite Affine Space

Caps

Arcs

See Also

What Makes an Existence Result Constructive?

Copyright