Repeat-Free Codes
© 2019 IEEE. 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 and redundancy of the repeat-free constraint are calculated. Then, an efficient algorithm, which u...
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
Online Access: | https://hdl.handle.net/1721.1/137690.2 |
_version_ | 1811069291591630848 |
---|---|
author | Elishco, Ohad Gabrys, Ryan Yaakobi, Eitan Medard, Muriel |
author2 | Massachusetts Institute of Technology. Research Laboratory of Electronics |
author_facet | Massachusetts Institute of Technology. Research Laboratory of Electronics Elishco, Ohad Gabrys, Ryan Yaakobi, Eitan Medard, Muriel |
author_sort | Elishco, Ohad |
collection | MIT |
description | © 2019 IEEE. 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 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 a ≤ 2, while its redundancy is o(n). Lastly, we also calculate the capacity of this constraint when combined with local constraints which are given by a constrained system. |
first_indexed | 2024-09-23T08:08:46Z |
format | Article |
id | mit-1721.1/137690.2 |
institution | Massachusetts Institute of Technology |
language | English |
last_indexed | 2024-09-23T08:08:46Z |
publishDate | 2021 |
publisher | Institute of Electrical and Electronics Engineers (IEEE) |
record_format | dspace |
spelling | mit-1721.1/137690.22022-04-01T17:27:47Z Repeat-Free Codes Elishco, Ohad Gabrys, Ryan Yaakobi, Eitan Medard, Muriel Massachusetts Institute of Technology. Research Laboratory of Electronics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 2019 IEEE. 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 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 a ≤ 2, while its redundancy is o(n). Lastly, we also calculate the capacity of this constraint when combined with local constraints which are given by a constrained system. 2021-11-08T16:46:03Z 2021-11-08T15:54:53Z 2021-11-08T16:46:03Z 2019-07 2021-03-09T17:04:26Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137690.2 2019. "Repeat-Free Codes." IEEE International Symposium on Information Theory - Proceedings, 2019-July. en 10.1109/ISIT.2019.8849483 IEEE International Symposium on Information Theory - Proceedings Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/octet-stream Institute of Electrical and Electronics Engineers (IEEE) arXiv |
spellingShingle | Elishco, Ohad Gabrys, Ryan Yaakobi, Eitan Medard, Muriel Repeat-Free Codes |
title | Repeat-Free Codes |
title_full | Repeat-Free Codes |
title_fullStr | Repeat-Free Codes |
title_full_unstemmed | Repeat-Free Codes |
title_short | Repeat-Free Codes |
title_sort | repeat free codes |
url | https://hdl.handle.net/1721.1/137690.2 |
work_keys_str_mv | AT elishcoohad repeatfreecodes AT gabrysryan repeatfreecodes AT yaakobieitan repeatfreecodes AT medardmuriel repeatfreecodes |