On a Construction of Easily Decodable Sub-de Bruijn Arrays
- 作者: Makarov D.1, Yashunsky A.1,2
-
隶属关系:
- Keldysh Institute of Applied Mathematics
- Lomonosov Moscow State University
- 期: 卷 13, 编号 2 (2019)
- 页面: 280-289
- 栏目: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213176
- DOI: https://doi.org/10.1134/S1990478919020091
- ID: 213176
如何引用文章
详细
We consider the two-dimensional generalizations of de Bruijn sequences; i.e., the 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.
作者简介
D. Makarov
Keldysh Institute of Applied Mathematics
编辑信件的主要联系方式.
Email: m8er_ed@mail.ru
俄罗斯联邦, Miusskaya pl. 4, Moscow, 125047
A. Yashunsky
Keldysh Institute of Applied Mathematics; Lomonosov Moscow State University
编辑信件的主要联系方式.
Email: yashunsky@keldysh.ru
俄罗斯联邦, Miusskaya pl. 4, Moscow, 125047; Leninskie gory 1, Moscow, 119991