Repeat-Free Codes

DOI10.1109/TIT.2021.3092056MaRDI QIDQ4958262zbMATH OpenOpenAlexFDO

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)

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)

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.

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)