New constructions for De Bruijn tori (Q1894269)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New constructions for De Bruijn tori |
scientific article |
Statements
New constructions for De Bruijn tori (English)
0 references
26 November 1995
0 references
A \(d\)-dimensional De Bruijn torus \(B\) with base \(k\), order \(\vec N= \langle n_1, n_2,\dots, n_d\rangle\) and period \(\vec R= \langle r_1, r_2,\dots, r_d\rangle\) is an infinite periodic array with period \(\vec R\) and entries from \([k]= \{0, 1,\dots, k- 1\}\) (`\(k\)-ary') such that every \(k\)-ary matrix of size \(\vec N\) appears exactly once periodically with period \(\vec R\). Such an array is called a \((\vec R; \vec N)^d_k\) De Bruijn torus. The main result of the paper is a theorem stating that for all natural numbers \(n_1\), \(n_2\), \(k\) there exists a \((q, k^{n_1 n_2}/q; n_1, n_2)^2_k\) De Bruijn torus, where \(k\) has prime decomposition \[ k= \prod p_l^{\alpha_1}\quad \text{and} \quad q= k \prod p_l^{[\log_{p_l} n_1]}. \] The proof depends on two new construction methods for De Bruijn tori. The first is a type of product construction; the second uses a decomposition of a \(d\)- dimensional torus to produce a \(d+ 1\)-dimensional torus. These constructions are extensions of ideas used by \textit{J. C. Cock} [Toroidal tilings from De Bruijn-Good cyclic sequences, Discrete Math. 70, No. 2, 209-210 (1988; Zbl 0652.05013)] and \textit{T. Etzion} [Constructions for perfect maps and pseudorandom arrays, IEEE Trans. Inf. Theory 34, No. 5, 1308-1316 (1988; Zbl 0685.05011)].
0 references
De Bruijn torus
0 references
infinite periodic array
0 references
matrix
0 references