Constructions and bounds for codes with restricted overlaps

Simon Blackburn; Navid Esfahani; Donald Kreher; Douglas R. Stinson

doi:10.1109/TIT.2023.3304712

Constructions and bounds for codes with restricted overlaps

Simon Blackburn
, Navid Esfahani
, Donald Kreher
, Douglas R. Stinson

Research output: Contribution to journal › Article › peer-review

93 Downloads (Pure)

Abstract

Non-overlapping codes have been studied for almost 60 years. In such a code, no proper, non-empty prefix of any codeword is a suffix of any codeword.
In this paper, we study codes in which overlaps of certain specified sizes are forbidden. We prove some general bounds and we give several constructions in the case of binary codes. Our techniques also allow us to provide an alternative, elementary proof of a lower bound on non-overlapping codes due to Levenshtein in 1964.

Original language	English
Number of pages	17
Journal	IEEE Transactions on Information Theory
DOIs	https://doi.org/10.1109/TIT.2023.3304712
Publication status	Published - 14 Aug 2023

Access to Document

10.1109/TIT.2023.3304712

Accepted ManuscriptAccepted author manuscript, 610 KB

Cite this

@article{de7f1b4282d74817b8a4fc320b59e6c8,

title = "Constructions and bounds for codes with restricted overlaps",

abstract = "Non-overlapping codes have been studied for almost 60 years. In such a code, no proper, non-empty prefix of any codeword is a suffix of any codeword. In this paper, we study codes in which overlaps of certain specified sizes are forbidden. We prove some general bounds and we give several constructions in the case of binary codes. Our techniques also allow us to provide an alternative, elementary proof of a lower bound on non-overlapping codes due to Levenshtein in 1964.",

author = "Simon Blackburn and Navid Esfahani and Donald Kreher and Stinson, \{Douglas R.\}",

year = "2023",

month = aug,

day = "14",

doi = "10.1109/TIT.2023.3304712",

language = "English",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Constructions and bounds for codes with restricted overlaps

AU - Blackburn, Simon

AU - Esfahani, Navid

AU - Kreher, Donald

AU - Stinson, Douglas R.

PY - 2023/8/14

Y1 - 2023/8/14

N2 - Non-overlapping codes have been studied for almost 60 years. In such a code, no proper, non-empty prefix of any codeword is a suffix of any codeword. In this paper, we study codes in which overlaps of certain specified sizes are forbidden. We prove some general bounds and we give several constructions in the case of binary codes. Our techniques also allow us to provide an alternative, elementary proof of a lower bound on non-overlapping codes due to Levenshtein in 1964.

AB - Non-overlapping codes have been studied for almost 60 years. In such a code, no proper, non-empty prefix of any codeword is a suffix of any codeword. In this paper, we study codes in which overlaps of certain specified sizes are forbidden. We prove some general bounds and we give several constructions in the case of binary codes. Our techniques also allow us to provide an alternative, elementary proof of a lower bound on non-overlapping codes due to Levenshtein in 1964.

U2 - 10.1109/TIT.2023.3304712

DO - 10.1109/TIT.2023.3304712

M3 - Article

SN - 0018-9448

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

ER -