References & Citations
Computer Science > Information Theory
Title: On de Bruijn Covering Sequences and Arrays
(Submitted on 21 Apr 2024 (v1), last revised 9 May 2024 (this version, v2))
Abstract: An $(m,n,R)$-de Bruijn covering array (dBCA) is a doubly periodic $M \times N$ array over an alphabet of size $q$ such that the set of all its $m \times n$ windows form a covering code with radius $R$. An upper bound of the smallest array area of an $(m,n,R)$-dBCA is provided using a probabilistic technique which is similar to the one that was used for an upper bound on the length of a de Bruijn covering sequence. A folding technique to construct a dBCA from a de Bruijn covering sequence or de Bruijn covering sequences code is presented. Several new constructions that yield shorter de Bruijn covering sequences and $(m,n,R)$-dBCAs with smaller areas are also provided. These constructions are mainly based on sequences derived from cyclic codes, self-dual sequences, primitive polynomials, an interleaving technique, folding, and mutual shifts of sequences with the same covering radius. Finally, constructions of de Bruijn covering sequences codes are also discussed.
Submission history
From: Hoang Ta [view email][v1] Sun, 21 Apr 2024 14:26:44 GMT (20kb)
[v2] Thu, 9 May 2024 09:22:36 GMT (21kb)
Link back to: arXiv, form interface, contact.