EN|RU
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:2, 280-289

Volume 26, No 2, 2019, P. 98-114

UDC 519.14+519.71
D. A. Makarov and A. D. Yashunsky
On a construction of easily decodable sub-de Bruijn arrays

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.

DOI: 10.33048/daio.2019.26.637

Dmitry A. Makarov 1
Alexey D. Yashunsky 1,2

1. Keldysh Institute of Applied Mathematics,
4 Miusskaya Square, 125047 Moscow, Russia
2. Lomonosov Moscow State University,
1 Leninskie gory, 119991 Moscow, Russia
e-mail: m8er_ed@mail.ru, yashunsky@keldysh.ru

Received October 30, 2018
Revised February 14, 2019
Accepted February 27, 2019

References

[1] D. A. Makarov, Construction of easily decodable sub-de Bruijn matrices with a 2 × 2 window, in Materialy X molodyozhnoi nauchnoi shkoly po diskretnoi matematike i eyo prilozheniyam (Proc. 10th Young Scientists’ School on Discrete Mathematics and Its Applications) Moscow, Russia, Oct. 5–11, 2015, pp. 47–50, Keldysh Inst. Appl. Math., Moscow, 2015 [Russian]. Available at http://keldysh.ru/dmschool/datastore/media/sbornikX.pdf (accessed Feb. 25, 2019).

[2] R. Berkowitz and S. Kopparty, Robust positioning patterns, in Proc. 27th Ann. ACM-SIAM Symp. Discrete Algorithms, Arlington, VA, USA, Jan. 10–12, 2016, pp. 1937–1951, SIAM, Philadelphia, PA, 2016.

[3] A. M. Bruckstein, T. Etzion, R. Giryes, N. Gordon, R. J. Holt, and D. Shuldiner, Simple and robust binary self-location patterns, IEEE Trans. Inf. Theory, 58, No. 7, 4884–4889, 2012.

[4] N. G de Bruijn, A combinatorial problem, Proc. Nederl. Akad. Wet., 49, No. 7, 758–764, 1946.

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

[6] J. Dénes and A. D. Keedwell, A new construction of two-dimensional arrays with the window property, IEEE Trans. Inf. Theory, 36, No. 4, 873–876, 1990.

[7] T. Etzion, Sequence folding, lattice tiling, and multidimensional coding, 2009 (Cornell Univ. Libr. e-Print Archive, arXiv:0911.1745).

[8] V. Horan and B. Stevens, Locating patterns in the de Bruijn torus, Discrete Math., 339, No. 4, 1274–1282, 2016.

[9] G. Hurlbert and G. Isaak, On the de Bruijn torus problem, J. Comb. Theory, Ser. A, 64, No. 1, 50–62, 1993.

[10] S. A. Lloyd and J. Burns, Finding the position of a subarray in a pseudorandom array, in Cryptography and Coding III, Clarendon Press, Oxford, 1993.

[11] C. J. Mitchell and K. G. Paterson, Decoding perfect maps, Des. Codes Cryptogr., 4, No. 1, 11–30, 1994.

[12] C. J. Mitchell, Aperiodic and semi-periodic perfect maps, IEEE Trans. Inf. Theory, 41, No. 1, 88–95, 1995.

[13] K. G. Paterson, New classes of perfect maps I, J. Comb. Theory, Ser. A, 73, No. 2, 302–334, 1996.

[14] K. G. Paterson, New classes of perfect maps II, J. Comb. Theory, Ser. A, 73, No. 2. 335–345, 1996.

[15] W. C. Shiu, Decoding de Bruijn arrays constructed by FFMS method, Ars Comb., 47, 33–48, 1997.

[16] J. Tuliani, De Bruijn sequences with efficient decoding algorithms, Discrete Math., 226, No. 1–3, 313–336, 2001.
 © Sobolev Institute of Mathematics, 2015