Decoding Algorithms for Twisted GRS 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_ | 1866915428762124288 |
|---|---|
| author | Zhang, Guanghui Lin, Liren Chen, Bocong |
| author_facet | Zhang, Guanghui Lin, Liren Chen, Bocong |
| contents | Twisted generalized Reed-Solomon (TGRS) codes were introduced to extend the algebraic capabilities of classical generalized Reed-Solomon (GRS) codes. This extension holds the potential for constructing new non-GRS maximum distance separable (MDS) codes and enhancing cryptographic security. It is known that TGRS codes with $1$ twist can either be MDS or near-MDS. In this paper, we employ the Gaussian elimination method to propose new decoding algorithms for MDS TGRS codes with parameters $[n,k,n-k+1]$. The algorithms can correct up to $\lfloor \frac{n-k}{2}\rfloor$ errors when $n-k$ is odd, and $\lfloor \frac{n-k}{2}\rfloor-1$ errors when $n-k$ is even. The computational complexity for both scenarios is $O(n^3)$. %, where $ω\approx 2.37286$ is the matrix multiplication exponent. Our approach diverges from existing methods based on Euclidean algorithm and addresses situations that have not been considered in the existing literature \cite{SYJL}. Furthermore, this method is also applicable to decoding near-MDS TGRS codes with parameters $[n, k, n-k]$, enabling correction of up to $\lfloor \frac{n-k-1}{2} \rfloor$ errors, while maintaining polynomial time complexity in $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_03552 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decoding Algorithms for Twisted GRS Codes Zhang, Guanghui Lin, Liren Chen, Bocong Information Theory 94B05, 94B65 Twisted generalized Reed-Solomon (TGRS) codes were introduced to extend the algebraic capabilities of classical generalized Reed-Solomon (GRS) codes. This extension holds the potential for constructing new non-GRS maximum distance separable (MDS) codes and enhancing cryptographic security. It is known that TGRS codes with $1$ twist can either be MDS or near-MDS. In this paper, we employ the Gaussian elimination method to propose new decoding algorithms for MDS TGRS codes with parameters $[n,k,n-k+1]$. The algorithms can correct up to $\lfloor \frac{n-k}{2}\rfloor$ errors when $n-k$ is odd, and $\lfloor \frac{n-k}{2}\rfloor-1$ errors when $n-k$ is even. The computational complexity for both scenarios is $O(n^3)$. %, where $ω\approx 2.37286$ is the matrix multiplication exponent. Our approach diverges from existing methods based on Euclidean algorithm and addresses situations that have not been considered in the existing literature \cite{SYJL}. Furthermore, this method is also applicable to decoding near-MDS TGRS codes with parameters $[n, k, n-k]$, enabling correction of up to $\lfloor \frac{n-k-1}{2} \rfloor$ errors, while maintaining polynomial time complexity in $n$. |
| title | Decoding Algorithms for Twisted GRS Codes |
| topic | Information Theory 94B05, 94B65 |
| url | https://arxiv.org/abs/2508.03552 |