On Unique Error Patterns in the Levenshtein's Sequence Reconstruction Model
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917699693576192 |
|---|---|
| author | Junnila, Ville Laihonen, Tero Lehtilä, Tuomo |
| author_facet | Junnila, Ville Laihonen, Tero Lehtilä, Tuomo |
| contents | In the Levenshtein's sequence reconstruction problem a codeword is transmitted through $N$ channels and in each channel a set of errors is introduced to the transmitted word. In previous works, the restriction that each channel provides a unique output word has been essential. In this work, we assume only that each channel introduces a unique set of errors to the transmitted word and hence some output words can also be identical. As we will discuss, this interpretation is both natural and useful for deletion and insertion errors. We give properties, techniques and (optimal) results for this situation.
Quaternary alphabets are relevant due to applications related to DNA-memories. Hence, we introduce an efficient Las Vegas style decoding algorithm for simultaneous insertion, deletion and substitution errors in $q$-ary Hamming spaces for $q \geq 4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_14125 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Unique Error Patterns in the Levenshtein's Sequence Reconstruction Model Junnila, Ville Laihonen, Tero Lehtilä, Tuomo Information Theory 68P20, 68P30, 94B35 In the Levenshtein's sequence reconstruction problem a codeword is transmitted through $N$ channels and in each channel a set of errors is introduced to the transmitted word. In previous works, the restriction that each channel provides a unique output word has been essential. In this work, we assume only that each channel introduces a unique set of errors to the transmitted word and hence some output words can also be identical. As we will discuss, this interpretation is both natural and useful for deletion and insertion errors. We give properties, techniques and (optimal) results for this situation. Quaternary alphabets are relevant due to applications related to DNA-memories. Hence, we introduce an efficient Las Vegas style decoding algorithm for simultaneous insertion, deletion and substitution errors in $q$-ary Hamming spaces for $q \geq 4$. |
| title | On Unique Error Patterns in the Levenshtein's Sequence Reconstruction Model |
| topic | Information Theory 68P20, 68P30, 94B35 |
| url | https://arxiv.org/abs/2406.14125 |