Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.10234 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929758140366848 |
|---|---|
| author | Liu, Yang Baumeister, Anna Wachter-Zeh, Antonia |
| author_facet | Liu, Yang Baumeister, Anna Wachter-Zeh, Antonia |
| contents | In this paper, we establish the list-decoding capacity theorem for sum-rank metric codes. This theorem implies the list-decodability theorem for random general sum-rank metric codes: Any random general sum-rank metric code with a rate not exceeding the list-decoding capacity is $\left(ρ,O\left(1/ε\right)\right)$-list-decodable with high probability, where $ρ\in\left(0,1\right)$ represents the error fraction and $ε>0$ is referred to as the capacity gap. For random $\mathbb{F}_q$-linear sum-rank metric codes by using the same proof approach we demonstrate that any random $\mathbb{F}_q$-linear sum-rank metric code with a rate not exceeding the list-decoding capacity is $\left(ρ,\exp\left(O\left(1/ε\right)\right)\right)$-list-decodable with high probability, where the list size is exponential at this stage due to the high correlation among codewords in linear codes. To achieve an exponential improvement on the list size, we prove a limited correlation property between sum-rank metric balls and $\mathbb{F}_q$-subspaces. Ultimately, we establish the list-decodability theorem for random $\mathbb{F}_q$-linear sum-rank metric codes: Any random $\mathbb{F}_q$-linear sum-rank metric code with rate not exceeding the list decoding capacity is $\left(ρ, O\left(1/ε\right)\right)$-list-decodable with high probability. For the proof of the list-decodability theorem of random $\mathbb{F}_q$-linear sum-rank metric codes our proof idea is inspired by and aligns with that provided in the works \cite{Gur2010,Din2014,Gur2017} where the authors proved the list-decodability theorems for random $\mathbb{F}_q$-linear Hamming metric codes and random $\mathbb{F}_q$-linear rank metric codes, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10234 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the List-Decodability of Random (Linear) Sum-Rank Metric Codes Liu, Yang Baumeister, Anna Wachter-Zeh, Antonia Information Theory In this paper, we establish the list-decoding capacity theorem for sum-rank metric codes. This theorem implies the list-decodability theorem for random general sum-rank metric codes: Any random general sum-rank metric code with a rate not exceeding the list-decoding capacity is $\left(ρ,O\left(1/ε\right)\right)$-list-decodable with high probability, where $ρ\in\left(0,1\right)$ represents the error fraction and $ε>0$ is referred to as the capacity gap. For random $\mathbb{F}_q$-linear sum-rank metric codes by using the same proof approach we demonstrate that any random $\mathbb{F}_q$-linear sum-rank metric code with a rate not exceeding the list-decoding capacity is $\left(ρ,\exp\left(O\left(1/ε\right)\right)\right)$-list-decodable with high probability, where the list size is exponential at this stage due to the high correlation among codewords in linear codes. To achieve an exponential improvement on the list size, we prove a limited correlation property between sum-rank metric balls and $\mathbb{F}_q$-subspaces. Ultimately, we establish the list-decodability theorem for random $\mathbb{F}_q$-linear sum-rank metric codes: Any random $\mathbb{F}_q$-linear sum-rank metric code with rate not exceeding the list decoding capacity is $\left(ρ, O\left(1/ε\right)\right)$-list-decodable with high probability. For the proof of the list-decodability theorem of random $\mathbb{F}_q$-linear sum-rank metric codes our proof idea is inspired by and aligns with that provided in the works \cite{Gur2010,Din2014,Gur2017} where the authors proved the list-decodability theorems for random $\mathbb{F}_q$-linear Hamming metric codes and random $\mathbb{F}_q$-linear rank metric codes, respectively. |
| title | On the List-Decodability of Random (Linear) Sum-Rank Metric Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2503.10234 |