In this paper we consider the problem of encoding data into \textit{repeat-free} sequences in which sequences are imposed to contain any $k$-tuple at most once (for predefined $k$). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length-$n$ sequences for $k=2+2\log (n)$. This algorithm is then improved to support any value of $k$ of the form $k=a\log (n)$, for $1<a$, while its redundancy is $o(n)$. We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes.
翻译:在本文中,我们考虑了将数据编码为\ textit{ repeat-freet} 序列的问题,在这种序列中,要求序列最多包含一次任何k$-tuple(对于预先定义的美元) 。首先,计算了重复无限制的能力。然后,使用两位冗余的高效算法,用2k=2+2=log(n)美元来编码长度-n美元序列。然后,这一算法得到改进,以支持1美元=a美元表1k=alog(n)美元的任何价值,而其冗余为$o(n)美元。当与受限制的系统所设定的本地限制相结合时,我们还计算了重复无限制序列的能力,以及多维的重复代码的能力。