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 |