2022/06/08 by Sagi Marcovich, Tuvi Etzion, Marcovich, Sagi +3
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.2206.03711
arxiv created 2022/06/08 · arxiv updated 2022/06/09
de Bruijn sequences of order ℓ, i.e., sequences that contain each ℓ-tuple as a window exactly once, have found many diverse applications in information theory and most recently in DNA storage. This family of binary sequences has rate of 1/2. To overcome this low rate, we study ℓ-tuples covering sequences, which impose that each ℓ-tuple appears at least once as a window in the sequence. The cardinality of this family of sequences is analyzed while assuming that ℓ is a function of the sequence length n. Lower and upper bounds on the asymptotic rate of this family are given. Moreover, we study an upper bound for ℓ such that the redundancy of the set of ℓ-tuples covering sequences is at most a single symbol. Lastly, we present efficient encoding and decoding schemes for ℓ-tuples covering sequences that meet this bound.