Geodesic
On a construction of easily decodable sub-de~Bruijn arrays
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 2, pp. 98-114.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : de Bruijn sequence, de Bruijn array
Keywords: decoding, complexity. 
@article{DA_2019_26_2_a4,
     author = {D. A. Makarov and A. D. Yashunsky},
     title = {On a construction of easily decodable {sub-de~Bruijn} arrays},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {98--114},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_2_a4/}
}
TY  - JOUR
AU  - D. A. Makarov
AU  - A. D. Yashunsky
TI  - On a construction of easily decodable sub-de~Bruijn arrays
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 98
EP  - 114
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_2_a4/
LA  - ru
ID  - DA_2019_26_2_a4
ER  - 
%0 Journal Article
%A D. A. Makarov
%A A. D. Yashunsky
%T On a construction of easily decodable sub-de~Bruijn arrays
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 98-114
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_2_a4/
%G ru
%F DA_2019_26_2_a4
D. A. Makarov; A. D. Yashunsky. On a construction of easily decodable sub-de~Bruijn arrays. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 2, pp. 98-114. http://geodesic.mathdoc.fr/item/DA_2019_26_2_a4/

[1] D. A. Makarov, “Construction of easily decodable sub-de Bruijn matrices with a $2\times 2$ window”, Proc. 10th Young Scientists' School on Discrete Mathematics and Its Applications (Moscow, Russia, Oct. 5–11, 2015), Keldysh Inst. Appl. Math., M., 2015, 47–50 (in Russian) (accessed Feb. 25, 2019)

[2] Berkowitz R., Kopparty S., “Robust positioning patterns”, Proc. 27th Annu. ACM-SIAM Symp. Discrete Algorithms SODA'16 (Arlington,VA, Jan. 10–12, 2016), SIAM, Philadelphia, PA, 2016, 1937–1951 | DOI | MR | Zbl

[3] Bruckstein A. M., Etzion T., Giryes R., Gordon N., Holt R. J., Shuldiner D., “Simple and robust binary self-location patterns”, IEEE Trans. Inf. Theory, 58:7 (2012), 4884–4889 | DOI | MR | Zbl

[4] De Bruijn N. G., “A combinatorial problem”, Proc. Nederl. Akad. Wet., 49:7 (1946), 758–764 | MR

[5] Burns J., Mitchell C. J., Coding schemes for two-dimensional position sensing, Res. Rep. HPL-92-19, HP Lab, Bristol, 1992 (accessed Feb. 25, 2019) http://www.hpl.hp.com/techreports/92/HPL-92-19.pdf

[6] Dénes J., Keedwell A. D., “A new construction of two-dimensional arrays with the window property”, IEEE Trans. Inf. Theory, 36:4 (1990), 873–876 | DOI | MR | Zbl

[7] Etzion T., Sequence folding, lattice tiling, and multidimensional coding, Cornell Univ. Libr., 2009, arXiv: 0911.1745 | MR

[8] Horan V., Stevens B., “Locating patterns in the de Bruijn torus”, Discrete Math., 339:4 (2016), 1274–1282 | DOI | MR | Zbl

[9] Hurlbert G., Isaak G., “On the de Bruijn torus problem”, J. Comb. Theory, Ser. A, 64:1 (1993), 50–62 | DOI | MR | Zbl

[10] Lloyd S. A., Burns J., “Finding the position of a subarray in a pseudo-random array”, Cryptography and Coding III, Clarendon Press, Oxford, 1993 | Zbl

[11] Mitchell C. J., Paterson K. G., “Decoding perfect maps”, Des. Codes Cryptogr., 4:1 (1994), 11–30 | DOI | MR | Zbl

[12] Mitchell C. J., “Aperiodic and semi-periodic perfect maps”, IEEE Trans. Inf. Theory, 41:1 (1995), 88–95 | DOI | MR | Zbl

[13] Paterson K. G., “New classes of perfect maps I”, J. Comb. Theory, Ser. A, 73:2 (1996), 302–334 | DOI | MR | Zbl

[14] Paterson K. G., “New classes of perfect maps II”, J. Comb. Theory, Ser. A, 73:2 (1996), 335–345 | DOI | MR | Zbl

[15] Shiu W. C., “Decoding de Bruijn arrays constructed by FFMS method”, Ars Comb., 47 (1997), 33–48 | MR | Zbl

[16] Tuliani J., “De Bruijn sequences with efficient decoding algorithms”, Discrete Math., 226:1–3 (2001), 313–336 | DOI | MR | Zbl