Repairing Reed-Solomon Codes with Side Information
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_ | 1866913347872489472 |
|---|---|
| author | Dinh, Thi Xinh Le, Ba Thong Dau, Son Hoang Boztas, Serdar Kruglik, Stanislav Kiah, Han Mao Viterbo, Emanuele Etzion, Tuvi Chee, Yeow Meng |
| author_facet | Dinh, Thi Xinh Le, Ba Thong Dau, Son Hoang Boztas, Serdar Kruglik, Stanislav Kiah, Han Mao Viterbo, Emanuele Etzion, Tuvi Chee, Yeow Meng |
| contents | We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set $S$ of linearly independent combinations of the sub-symbols of the lost symbol. When $S = \varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When $S$ is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on $|S|$ and not the content of $S$ and construct a lower bound on the repair bandwidth of a linear repair scheme with side information $S$. We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_07180 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Repairing Reed-Solomon Codes with Side Information Dinh, Thi Xinh Le, Ba Thong Dau, Son Hoang Boztas, Serdar Kruglik, Stanislav Kiah, Han Mao Viterbo, Emanuele Etzion, Tuvi Chee, Yeow Meng Information Theory 94B05, 94B60 E.4 We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set $S$ of linearly independent combinations of the sub-symbols of the lost symbol. When $S = \varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When $S$ is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on $|S|$ and not the content of $S$ and construct a lower bound on the repair bandwidth of a linear repair scheme with side information $S$. We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes. |
| title | Repairing Reed-Solomon Codes with Side Information |
| topic | Information Theory 94B05, 94B60 E.4 |
| url | https://arxiv.org/abs/2405.07180 |