Codes with restricted overlaps : expandability, constructions, and bounds

Stanovnik, Lidija (author)

onsider a q-ary block code satisfying the property that no ℓ-letters long code-word’s prefix occurs as a suffix of any codeword for ℓ inside some interval. We determine a general upper bound on the maximum size of these codes and a tighter bound for codes where overlaps with lengths not exceeding k are prohibited. We then provide constructions for codes with various restrictions on overlap lengths and use them to determine lower bounds on the maximum sizes. In particular, we construct (1, k)-overlap-free codes where k ≥ n/2 and n denotes the block size, expand a known construction of (k, n − 1)-overlap-free codes, and combine the ideas behind both constructions to obtain (t$_1$, t$_2$)-overlap-free codes and codes that are simultaneously (1, k)- and (n − k, n − 1)-overlap-free for some k < n/2. In the case when overlaps of lengths between 1 and k are prohibited, we complete the characterisation of non-expandable codes initiated by Cai, Wang, and Feng (IEEE Trans Inf Theory, 2023).

• Language: English
• Keywords: overlap-free code, non-overlapping code, weakly mutually uncorrelated code
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: 26 str.
• Numbering: Vol. , no.
• PID: 20.500.12556/RUL-168872
• UDC: 51:004
• ISSN on article: 1598-5865
• DOI: 10.1007/s12190-025-02441-z
• COBISS.SI-ID: 234691843
• Publication date in RUL: 05.05.2025

Record is a part of a journal

• Title: Journal of Applied Mathematics and Computing : International Journal
• Shortened title: J. Appl. Math. Comput., Int. J.
• Publisher: Springer, Korean Society for Computational and Applied Mathematics
• ISSN: 1598-5865
• COBISS.SI-ID: 10636310

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Projects

• Funder: ARIS - Slovenian Research and Innovation Agency
• Project number: P2-0359
• Name: Vseprisotno računalništvo