Том 26, номер 2, 2019 г., Стр. 98-114

УДК 519.14+519.71
Макаров Д. А., Яшунский А. Д.
Об одной конструкции легко декодируемых субдебрёйновых массивов

Аннотация:
Рассматриваются двумерные обобщения последовательностей де Брёйна — целочисленные массивы, в которых требуется, чтобы все фрагменты заданного размера (окна) были различны. Для таких массивов, называемых субдебрёйновыми, рассматривается сложность задачи декодирования — определения положения в массиве окна с заданным содержимым. Предложена конструкция массивов произвольного размера с произвольными окнами, для которых число различных элементов в массиве по порядку оптимально, а сложность декодирования окон линейна.
Библиогр. 16.

Ключевые слова: последовательность де Брёйна, массив де Брёйна, декодирование, сложность.

DOI: 10.33048/daio.2019.26.637

Макаров Дмитрий Александрович ¹
Яшунский Алексей Дмитриевич ^1,2
1. Институт прикладной математики им. М. В. Келдыша РАН,
Миусская пл., 4, 125047 Москва, Россия
2. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 1, 119991 Москва, Россия
е-mail: m8er_ed@mail.ru, yashunsky@keldysh.ru

Статья поступила 30 октября 2018 г.
После доработки — 14 февраля 2019 г.
Принята к публикации 27 февраля 2019 г.

Литература

[1] Макаров Д. А. Построение легко декодируемых субдебрёйновых матриц с окном 2 × 2 // Материалы X молодёж. науч. школы по дискрет. математике и её прил. (Москва, 5–11 октября 2015 г.) ИПМ им. М. В. Келдыша, 2015. С. 47–50. http://keldysh.ru/dmschool/datastore/media/sbornikX.pdf

[2] Berkowitz R., Kopparty S. Robust positioning patterns // Proc. 27th Annu. ACM-SIAM Symp. Discrete Algorithms SODA’16 (Arlington,VA, Jan. 10–12, 2016). Philadelphia, PA: SIAM, 2016. P. 1937–1951.

[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. 2012. Vol. 58, No. 7. P. 4884–4889.

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

[5] Burns J., Mitchell C. J. Coding schemes for two-dimensional position sensing. Res. Rep. HPL-92-19, Bristol: HP Lab., 1992. 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. 1990. Vol. 36, No. 4. P. 873–876.

[7] Etzion T. Sequence folding, lattice tiling, and multidimensional coding // arXiv:0911.1745. http://arxiv.org/abs/0911.1745v1 (2009)

[8] Horan V., Stevens B. Locating patterns in the de Bruijn torus // Discrete Math. 2016. Vol. 339, No. 4. P. 1274–1282. doi: 10.1016/j.disc.2015.11.015

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

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

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

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

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

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

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

[16] Tuliani J. De Bruijn sequences with efficient decoding algorithms // Discrete Math. 2001. Vol. 226, No 1–3. P. 313–336.