Technical Program

Paper Detail

Paper Title Repeat-Free Codes
Paper IdentifierTU2.R5.4
Authors Ohad Elishco, Massachusetts Institute of Technology, United States; Ryan Gabrys, Spawar Systems center, United States; Muriel Médard, Massachusetts Institute of Technology, United States; Eitan Yaakobi, Technion - Israel Institute of Technology, Israel
Session Information Theory in Biology II
Location Saint Victor, Level 3
Session Time Tuesday, 09 July, 11:40 - 13:00
Presentation Time Tuesday, 09 July, 12:40 - 13:00
Manuscript  Click here to download the manuscript
Abstract 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 and redundancy of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses a single bit 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