Two-Step Decoding of Binary $2\times2$ Sum-Rank-Metric Codes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917365305835520 |
|---|---|
| author | Wu, Hao Chen, Bocong Zhang, Guanghui Liu, Hongwei |
| author_facet | Wu, Hao Chen, Bocong Zhang, Guanghui Liu, Hongwei |
| contents | We address an open problem posed by Chen-Cheng-Qi (IEEE Trans.\ Inf.\ Theory, 2025): can the decoding of binary sum-rank-metric codes $\SR(C_1,C_2)$ with $2\times2$ matrix blocks be reduced entirely to decoding the constituent Hamming-metric codes $C_1$ and $C_2$ without the additional requirement $d_1\ge\tfrac{2}{3}d_{\mathrm{sr}}$ used in their fast decoder? We answer this in the affirmative by exhibiting a simple two-step procedure: first uniquely decode $C_2$, then apply a single error-erasure decoding for $C_1$. This shows that the restrictive hypothesis $d_1\ge\tfrac{2}{3}d_{\mathrm{sr}}$ is theoretically unnecessary. The resulting decoder achieves unique decoding up to $\lfloor (d_{\mathrm{sr}}-1)/2\rfloor$ with overall cost $T_2+T_1$, where $T_2$ and $T_1$ are the complexities of the Hamming decoders for $C_2$ and $C_1$, respectively. We further show that this reduction is asymptotically optimal in a black-box model, as any sum-rank decoder must inherently decode the constituent Hamming codes. For BCH or Goppa instantiations over $\F_4$, the decoder runs in $O(\ell^2)$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_19812 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-Step Decoding of Binary $2\times2$ Sum-Rank-Metric Codes Wu, Hao Chen, Bocong Zhang, Guanghui Liu, Hongwei Information Theory 94B05, 94B35 We address an open problem posed by Chen-Cheng-Qi (IEEE Trans.\ Inf.\ Theory, 2025): can the decoding of binary sum-rank-metric codes $\SR(C_1,C_2)$ with $2\times2$ matrix blocks be reduced entirely to decoding the constituent Hamming-metric codes $C_1$ and $C_2$ without the additional requirement $d_1\ge\tfrac{2}{3}d_{\mathrm{sr}}$ used in their fast decoder? We answer this in the affirmative by exhibiting a simple two-step procedure: first uniquely decode $C_2$, then apply a single error-erasure decoding for $C_1$. This shows that the restrictive hypothesis $d_1\ge\tfrac{2}{3}d_{\mathrm{sr}}$ is theoretically unnecessary. The resulting decoder achieves unique decoding up to $\lfloor (d_{\mathrm{sr}}-1)/2\rfloor$ with overall cost $T_2+T_1$, where $T_2$ and $T_1$ are the complexities of the Hamming decoders for $C_2$ and $C_1$, respectively. We further show that this reduction is asymptotically optimal in a black-box model, as any sum-rank decoder must inherently decode the constituent Hamming codes. For BCH or Goppa instantiations over $\F_4$, the decoder runs in $O(\ell^2)$ time. |
| title | Two-Step Decoding of Binary $2\times2$ Sum-Rank-Metric Codes |
| topic | Information Theory 94B05, 94B35 |
| url | https://arxiv.org/abs/2511.19812 |