In search of maximum non-overlapping codes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911753007267840 |
|---|---|
| author | Stanovnik, Lidija Moškon, Miha Mraz, Miha |
| author_facet | Stanovnik, Lidija Moškon, Miha Mraz, Miha |
| contents | Non-overlapping codes are block codes that have arisen in diverse contexts of computer science and biology. Applications typically require finding non-overlapping codes with large cardinalities, but the maximum size of non-overlapping codes has been determined only for cases where the codeword length divides the size of the alphabet, and for codes with codewords of length two or three. For all other alphabet sizes and codeword lengths no computationally feasible way to identify non-overlapping codes that attain the maximum size has been found to date. Herein we characterize maximal non-overlapping codes. We formulate the maximum non-overlapping code problem as an integer optimization problem and determine necessary conditions for optimality of a non-overlapping code. Moreover, we solve several instances of the optimization problem to show that the hitherto known constructions do not generate the optimal codes for many alphabet sizes and codeword lengths. We also evaluate the number of distinct maximum non-overlapping codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_12593 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | In search of maximum non-overlapping codes Stanovnik, Lidija Moškon, Miha Mraz, Miha Information Theory Discrete Mathematics Combinatorics 94B50, 90C10 Non-overlapping codes are block codes that have arisen in diverse contexts of computer science and biology. Applications typically require finding non-overlapping codes with large cardinalities, but the maximum size of non-overlapping codes has been determined only for cases where the codeword length divides the size of the alphabet, and for codes with codewords of length two or three. For all other alphabet sizes and codeword lengths no computationally feasible way to identify non-overlapping codes that attain the maximum size has been found to date. Herein we characterize maximal non-overlapping codes. We formulate the maximum non-overlapping code problem as an integer optimization problem and determine necessary conditions for optimality of a non-overlapping code. Moreover, we solve several instances of the optimization problem to show that the hitherto known constructions do not generate the optimal codes for many alphabet sizes and codeword lengths. We also evaluate the number of distinct maximum non-overlapping codes. |
| title | In search of maximum non-overlapping codes |
| topic | Information Theory Discrete Mathematics Combinatorics 94B50, 90C10 |
| url | https://arxiv.org/abs/2307.12593 |