论文标题
覆盖$ \ ell $ -tuples的序列
Covering Sequences for $\ell$-Tuples
论文作者
论文摘要
de bruijn序列$ \ ell $的序列，即包含每个$ \ ell $ tuple作为一个窗口的序列，它们在信息理论和最近的DNA存储中发现了许多不同的应用程序。这个二进制序列的家族的价格为$ 1/2 $。为了克服这种低率，我们研究了涵盖序列的$ \ ell $ tuplass，这些序列强烈认为每个$ \ ell $ -tuple至少出现一次作为序列中的窗口。假设$ \ ell $是序列长度$ n $的函数，分析了该序列家族的基数。给出了该家族渐近率的下限和上限。此外，我们研究了$ \ ell $的上限，以使$ \ ell $ - 覆盖序列的集合的冗余最多是一个符号。最后，我们为$ \ ell $的$ \ ell $ - 涵盖符合此界限的序列提出有效的编码和解码方案。
de Bruijn sequences of order $\ell$, i.e., sequences that contain each $\ell$-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 $\ell$-tuples covering sequences, which impose that each $\ell$-tuple appears at least once as a window in the sequence. The cardinality of this family of sequences is analyzed while assuming that $\ell$ 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 $\ell$ such that the redundancy of the set of $\ell$-tuples covering sequences is at most a single symbol. Lastly, we present efficient encoding and decoding schemes for $\ell$-tuples covering sequences that meet this bound.
