Unbounded Error Correcting Codes
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913782331080704 |
|---|---|
| author | Efremenko, Klim Zamir, Or |
| author_facet | Efremenko, Klim Zamir, Or |
| contents | Traditional error-correcting codes (ECCs) assume a fixed message length, but many scenarios involve ongoing or indefinite transmissions where the message length is not known in advance. For example, when streaming a video, the user should be able to fix a fraction of errors that occurred before any point in time. We introduce unbounded error-correcting codes (unbounded codes), a natural generalization of ECCs that supports arbitrarily long messages without a predetermined length. An unbounded code with rate $R$ and distance $\varepsilon$ ensures that for every sufficiently large $k$, the message prefix of length $Rk$ can be recovered from the code prefix of length $k$ even if an adversary corrupts up to an $\varepsilon$ fraction of the symbols in this code prefix.
We study unbounded codes over binary alphabets in the regime of small error fraction $\varepsilon$, establishing nearly tight upper and lower bounds on their optimal rate. Our main results show that: (1) The optimal rate of unbounded codes satisfies $R<1-Ω(\sqrt{\varepsilon})$ and $R>1-O(\sqrt{\varepsilon \log \log(1/\varepsilon)})$. (2) Surprisingly, our construction is inherently non-linear, as we prove that linear unbounded codes achieve a strictly worse rate of $R=1-Θ(\sqrt{\varepsilon \log(1/\varepsilon)})$. (3) In the setting of random noise, unbounded codes achieve the same optimal rate as standard ECCs, $R=1-Θ(\varepsilon \log(1/\varepsilon))$.
These results demonstrate fundamental differences between standard and unbounded codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04803 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unbounded Error Correcting Codes Efremenko, Klim Zamir, Or Data Structures and Algorithms Information Theory Combinatorics Traditional error-correcting codes (ECCs) assume a fixed message length, but many scenarios involve ongoing or indefinite transmissions where the message length is not known in advance. For example, when streaming a video, the user should be able to fix a fraction of errors that occurred before any point in time. We introduce unbounded error-correcting codes (unbounded codes), a natural generalization of ECCs that supports arbitrarily long messages without a predetermined length. An unbounded code with rate $R$ and distance $\varepsilon$ ensures that for every sufficiently large $k$, the message prefix of length $Rk$ can be recovered from the code prefix of length $k$ even if an adversary corrupts up to an $\varepsilon$ fraction of the symbols in this code prefix. We study unbounded codes over binary alphabets in the regime of small error fraction $\varepsilon$, establishing nearly tight upper and lower bounds on their optimal rate. Our main results show that: (1) The optimal rate of unbounded codes satisfies $R<1-Ω(\sqrt{\varepsilon})$ and $R>1-O(\sqrt{\varepsilon \log \log(1/\varepsilon)})$. (2) Surprisingly, our construction is inherently non-linear, as we prove that linear unbounded codes achieve a strictly worse rate of $R=1-Θ(\sqrt{\varepsilon \log(1/\varepsilon)})$. (3) In the setting of random noise, unbounded codes achieve the same optimal rate as standard ECCs, $R=1-Θ(\varepsilon \log(1/\varepsilon))$. These results demonstrate fundamental differences between standard and unbounded codes. |
| title | Unbounded Error Correcting Codes |
| topic | Data Structures and Algorithms Information Theory Combinatorics |
| url | https://arxiv.org/abs/2411.04803 |