Repeat-Free Codes

In this paper we consider the problem of encoding data into 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 , 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.