New constructions for De Bruijn tori
type: Item
instance of: scholarly article
title: New constructions for De Bruijn tori
zbMATH Open document ID: 0826.05017
DOI: 10.1007/BF01390770
author: Garth Isaak
author: Glenn H. Hurlbert
published in: Designs, Codes and Cryptography
publication date: 1995-11-26T00:00:00Z
review text: 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)].
reviewed by: Jack van Lint
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 94A99
zbMATH DE Number: 777668
zbMATH Keywords: De Bruijn torus
zbMATH Keywords: infinite periodic array
zbMATH Keywords: matrix
MaRDI profile type: Publication
cites work: Toroidal tilings from de Bruijn-Good cyclic sequences
cites work: Constructions for perfect maps and pseudorandom arrays
cites work: Q3686626
cites work: A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
cites work: On the de Bruijn torus problem
cites work: A note on binary arrays with a certain window property (Corresp.)
cites work: Decoding perfect maps
cites work: Perfect maps
description: scientific article; zbMATH DE number 777668