Calculating the I/O Cost of Linear Repair Schemes for RS Codes Evaluated on Subspaces via Exponential Sums
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_ | 1866915078399328256 |
|---|---|
| author | Liu, Zhongyan Xu, Jingke Zhang, Zhifang |
| author_facet | Liu, Zhongyan Xu, Jingke Zhang, Zhifang |
| contents | The I/O cost, defined as the amount of data accessed at helper nodes during the repair process, is a crucial metric for repair efficiency of Reed-Solomon (RS) codes. Recently, a formula that relates the I/O cost to the Hamming weight of some linear spaces was proposed in [Liu\&Zhang-TCOM2024]. In this work, we introduce an effective method for calculating the Hamming weight of such linear spaces using exponential sums. With this method, we derive lower bounds on the I/O cost for RS codes evaluated on a $d$-dimensional subspace of $\mathbb{F}_{q^\ell}$ with $r=2$ or $3$ parities. These bounds are exactly matched in the cases $r=2,\ell-d+1\mid\ell$ and $r=3,d=\ell$ or $\ell-d+2\mid\ell$, via the repair schemes designed in this work. We refer to schemes that achieve the lower bound as I/O-optimal repair schemes. Additionally, we characterize the optimal repair bandwidth of I/O-optimal repair schemes for full-length RS codes with two parities, and build an I/O-optimal repair scheme for full-length RS codes with three parities, achieving lower repair bandwidth than previous schemes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_18430 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Calculating the I/O Cost of Linear Repair Schemes for RS Codes Evaluated on Subspaces via Exponential Sums Liu, Zhongyan Xu, Jingke Zhang, Zhifang Information Theory The I/O cost, defined as the amount of data accessed at helper nodes during the repair process, is a crucial metric for repair efficiency of Reed-Solomon (RS) codes. Recently, a formula that relates the I/O cost to the Hamming weight of some linear spaces was proposed in [Liu\&Zhang-TCOM2024]. In this work, we introduce an effective method for calculating the Hamming weight of such linear spaces using exponential sums. With this method, we derive lower bounds on the I/O cost for RS codes evaluated on a $d$-dimensional subspace of $\mathbb{F}_{q^\ell}$ with $r=2$ or $3$ parities. These bounds are exactly matched in the cases $r=2,\ell-d+1\mid\ell$ and $r=3,d=\ell$ or $\ell-d+2\mid\ell$, via the repair schemes designed in this work. We refer to schemes that achieve the lower bound as I/O-optimal repair schemes. Additionally, we characterize the optimal repair bandwidth of I/O-optimal repair schemes for full-length RS codes with two parities, and build an I/O-optimal repair scheme for full-length RS codes with three parities, achieving lower repair bandwidth than previous schemes. |
| title | Calculating the I/O Cost of Linear Repair Schemes for RS Codes Evaluated on Subspaces via Exponential Sums |
| topic | Information Theory |
| url | https://arxiv.org/abs/2412.18430 |