Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Về một cấu trúc của các mảng sub-de Bruijn dễ giải mã
Tóm tắt
Chúng tôi xem xét các khái niệm tổng quát hai chiều của chuỗi de Bruijn; tức là, các mảng giá trị nguyên mà tất cả các đoạn của một kích thước cố định (cửa sổ) là khác nhau. Đối với các mảng này, được gọi là sub-de Bruijn, chúng tôi xem xét độ phức tạp của việc giải mã; tức là, xác định vị trí của một cửa sổ với nội dung nhất định trong một mảng. Chúng tôi đề xuất một cấu trúc của các mảng có kích thước tùy ý với các cửa sổ tùy ý, trong đó số lượng các phần tử khác nhau trong mảng là tối ưu và độ phức tạp của việc giải mã một cửa sổ là tuyến tính.
Từ khóa
#mảng de Bruijn #giải mã #độ phức tạp #cấu trúc mảngTài liệu tham khảo
N. G de Bruijn, “A Combinatorial Problem,” Proc. Nederl. Akad. Wet. 49 (7), 758–764 (1946).
J. Burns and C. J. Mitchell, “Coding Schemes for Two-Dimensional Position Sensing,” Res. Rep. HPL-92–19 (HP Lab., Bristol, 1992). Available at http://www.hpl.hp.com/techreports/92/HPL-92-19.pdf (accessed February 25, 2019).
J. Dénes and A. D. Keedwell, “A New Construction of Two-Dimensional Arrays with the Window Property,” IEEE Trans. Inform. Theory 36 (4), 873–876 (1990).
G. Hurlbert and G. Isaak, “On the de Bruijn Torus Problem,” J. Combin. Theory Ser. A 64 (1), 50–62 (1993).
K. G. Paterson, “New Classes of Perfect Maps I,” J. Combin. Theory Ser. A 73 (2), 302–334 (1996).
K. G. Paterson, “New Classes of Perfect Maps II,” J. Combin. Theory Ser. A 73 (2), 335–345 (1996).
C. J. Mitchell, “Aperiodic and Semi-Periodic Perfect Maps,” IEEE Trans. Inform. Theory 41 (1), 88–95 (1995).
T. Etzion, Sequence Folding, Lattice Tiling, and Multidimensional Coding (Cornell Univ. Libr. e-Print Archive, arXiv:0911.1745, 2009).
R. Berkowitz and S. Kopparty, “Robust Positioning Patterns,” in Proceedings of 27th Annual ACM-SIAM Symposium on Discrete Algorithms SODA’16, Arlington, VA, USA, January 10–12, 2016 (SIAM, Philadelphia, PA, 2016), pp. 1937–1951.
A. M. Bruckstein, T. Etzion, R. Giryes, N. Gordon, R. J. Holt, and D. Shuldiner, “Simple and Robust Binary Self-Location Patterns,” IEEE Trans. Inform. Theory 58 (7), 4884–4889 (2012).
S. A. Lloyd and J. Burns, “Finding the Position of a Subarray in a Pseudo-Random Array,” in Cryptography and Coding III (Clarendon Press, Oxford, 1993).
C. J. Mitchell and K. G. Paterson, “Decoding Perfect Maps,” Des. Codes Cryptogr. 4 (1), 11–30 (1994).
W. C. Shiu, “Decoding de Bruijn Arrays Constructed by FFMS Method,” Ars Combin. 47, 33–48 (1997).
J. Tuliani, “De Bruijn Sequences with Efficient Decoding Algorithms,” Discrete Math. 226 (1–3), 313–336 (2001).
V. Horan and B. Stevens, “Locating Patterns in the de Bruijn Torus,” Discrete Math. 339 (4), 1274–1282 (2016).
D. A. Makarov, “Construction of Easily Decodable Sub-de Bruijn Matrices with a 2 × 2 Window,” in Proceedings of 10th Young Scientists’ School on Discrete Mathematics and Its Applications Moscow, Russia, October 5–11, 2015 (Keldysh Inst. Appl. Math., Moscow, 2015), pp. 47–50. Available at http://keldysh.ru/dmschool/datastore/media/sbornikX.pdf (accessed Feb. 25, 2019).