Improved Construction of Robust Gray Code
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913212743548928 |
|---|---|
| author | Fathollahi, Dorsa Wootters, Mary |
| author_facet | Fathollahi, Dorsa Wootters, Mary |
| contents | A robust Gray code, formally introduced by (Lolck and Pagh, SODA 2024), is a Gray code that additionally has the property that, given a noisy version of the encoding of an integer $j$, it is possible to reconstruct $\hat{j}$ so that $|j - \hat{j}|$ is small with high probability. That work presented a transformation that transforms a binary code $C$ of rate $R$ to a robust Gray code with rate $Ω(R)$, where the constant in the $Ω(\cdot)$ can be at most $1/4$. We improve upon their construction by presenting a transformation from a (linear) binary code $C$ to a robust Gray code with similar robustness guarantees, but with rate that can approach $R/2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15291 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Construction of Robust Gray Code Fathollahi, Dorsa Wootters, Mary Information Theory A robust Gray code, formally introduced by (Lolck and Pagh, SODA 2024), is a Gray code that additionally has the property that, given a noisy version of the encoding of an integer $j$, it is possible to reconstruct $\hat{j}$ so that $|j - \hat{j}|$ is small with high probability. That work presented a transformation that transforms a binary code $C$ of rate $R$ to a robust Gray code with rate $Ω(R)$, where the constant in the $Ω(\cdot)$ can be at most $1/4$. We improve upon their construction by presenting a transformation from a (linear) binary code $C$ to a robust Gray code with similar robustness guarantees, but with rate that can approach $R/2$. |
| title | Improved Construction of Robust Gray Code |
| topic | Information Theory |
| url | https://arxiv.org/abs/2401.15291 |