Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
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,[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.
