Repeat-Free Codes

DOI10.1109/TIT.2021.3092056zbMATH Open1486.94182arXiv1909.05694OpenAlexW3175471354MaRDI QIDQ4958262FDOQ4958262

Authors: Ohad Elishco, Ryan Gabrys, Eitan Yaakobi, Muriel Médard 

Publication date: 7 September 2021

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper we consider the problem of encoding data into extit{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+2log(n)$. This algorithm is then improved to support any value of $k$ of the form $k=alog(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.

Full work available at URL: https://arxiv.org/abs/1909.05694

zbMATH Keywords

capacityencoding data into repeat-free sequencesmultidimensional repeat-free codes

Mathematics Subject Classification ID

Other types of codes (94B60)

Cited In (2)

• Cut-down de Bruijn sequences
• Non-Overlapping Codes

This page was built for publication: Repeat-Free Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958262)