This article is cited in 2 papers

On a construction of easily decodable sub-de Bruijn arrays

D. A. Makarov^a, A. D. Yashunsky<sup>ab

a</sup> Keldysh Institute of Applied Mathematics, 4 Miusskaya Square, 125047 Moscow, Russia
^b Lomonosov Moscow State University, 1 Leninskie gory, 119991 Moscow, Russia

Abstract: We consider a two-dimensional generalization of de Bruijn sequences; i.e., integer-valued arrays whose all fragments of a fixed size (windows) are different. For these arrays, dubbed sub-de Bruijn, we consider the complexity of decoding; i.e., the determination of a position of a window with given content in an array. We propose a construction of arrays of arbitrary size with arbitrary windows where the number of different elements in the array is of an optimal order and the complexity of decoding a window is linear. Bibliogr. 16.

Keywords: de Bruijn sequence, de Bruijn array, decoding, complexity.

UDC: 519.14+519.71

Received: 30.10.2018
Revised: 14.02.2019
Accepted: 27.02.2019

DOI: 10.33048/daio.2019.26.637

 English version: Journal of Applied and Industrial Mathematics, 2019, 13:2, 280–289

Bibliographic databases:

•