Publisher DOI: | 10.1016/j.jcta.2025.106030 10.48550/arXiv.2405.03309 |
Title: | On de Bruijn Rings and families of almost perfect maps | Other Titles: | Über de Bruijn Ringe und fast perfekte Karten | Language: | English | Authors: | Stelldinger, Peer ![]() |
Keywords: | De Bruijn torus; De Bruijn ring; Perfect map; Sub-perfect map | Issue Date: | 27-Feb-2025 | Publisher: | Elsevier | Journal or Series Name: | Journal of combinatorial theory : JCTA. Series A | Volume: | 214 | Abstract: | De Bruijn tori, also called perfect maps, are two-dimensional periodic arrays of letters drawn from a given finite alphabet, such that each possible pattern of a given shape (m,n) appears exactly once within one period of the torus. It is still unknown if de Bruijn tori of some certain size exist, like e.g. square shaped de Bruijn Tori with odd m=n in {3,5,7} and an even alphabet size k. However, in certain applications like positional coding, sub-perfect maps are sufficient, i.e. one does not need every possible (m,n)-pattern to appear, as long as a sufficient large number of such patterns is captured and every pattern occurs at most once. We show, that given any m=n and a square alphabet size k², one can efficiently construct a sub-perfect map which is almost perfect, i.e. of almost maximal size. We do this by introducing de Bruijn rings, i.e. sub-perfect maps of minimal height, and providing an efficient construction method for them. We extend our results to non-square torus shapes and arbitrary non-prime alphabet sizes. |
URI: | https://hdl.handle.net/20.500.12738/16530 | ISSN: | 0097-3165 | Review status: | This version was peer reviewed (peer review) | Institute: | Forschungs- und Transferzentrum Smart Systems Department Informatik Fakultät Technik und Informatik |
Type: | Article | Additional note: | Preprint: https://doi.org/10.48550/arXiv.2405.03309. Verlagsversion: https://doi.org/10.1016/j.jcta.2025.106030. |
Appears in Collections: | Publications without full text |
Show full item record
Add Files to Item
Note about this record
Export
This item is licensed under a Creative Commons License