On List-Decodability of Random Rank Metric Codes and Subspace Codes
Codes in rank metric have a wide range of applications. To construct such codes with better list-decoding performance explicitly, it is of interest to investigate the listdecodability of random rank metric codes. It is shown that if n/m = b is a constant, then for every rank metric code in Fm×n q wi...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2016
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/82171 http://hdl.handle.net/10220/41145 |
| _version_ | 1824454249663168512 |
|---|---|
| author | Ding, Yang |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Ding, Yang |
| author_sort | Ding, Yang |
| collection | NTU |
| description | Codes in rank metric have a wide range of applications. To construct such codes with better list-decoding performance explicitly, it is of interest to investigate the listdecodability of random rank metric codes. It is shown that if n/m = b is a constant, then for every rank metric code in Fm×n q with rate R and list-decoding radius ρ must obey the Gilbert-Varshamov bound, that is, R ≤ (1-ρ)(1-bρ). Otherwise, the list size can be exponential and hence no polynomial-time list decoding is possible. On the other hand, for arbitrary 0 <; ρ <; 1 and E > 0, with E and ρ being independent of each other, with high probability, a random rank metric code with rate R = (1 - ρ)(1 - bρ) - can be efficiently list-decoded up to a fraction ρ of rank errors with constant list size O(1/E). We establish similar results for constant-dimension subspace codes. Moreover, we show that, with high probability, the list-decoding radius of random Fq-linear rank metric codes also achieve the Gilbert-Varshamov bound with constant list size O(exp(1/E)). |
| first_indexed | 2025-02-19T03:19:19Z |
| format | Journal Article |
| id | ntu-10356/82171 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:19:19Z |
| publishDate | 2016 |
| record_format | dspace |
| spelling | ntu-10356/821712020-03-07T12:31:32Z On List-Decodability of Random Rank Metric Codes and Subspace Codes Ding, Yang School of Physical and Mathematical Sciences Gilbert-Varshamov bound Constant-dimension subspace codes Codes in rank metric have a wide range of applications. To construct such codes with better list-decoding performance explicitly, it is of interest to investigate the listdecodability of random rank metric codes. It is shown that if n/m = b is a constant, then for every rank metric code in Fm×n q with rate R and list-decoding radius ρ must obey the Gilbert-Varshamov bound, that is, R ≤ (1-ρ)(1-bρ). Otherwise, the list size can be exponential and hence no polynomial-time list decoding is possible. On the other hand, for arbitrary 0 <; ρ <; 1 and E > 0, with E and ρ being independent of each other, with high probability, a random rank metric code with rate R = (1 - ρ)(1 - bρ) - can be efficiently list-decoded up to a fraction ρ of rank errors with constant list size O(1/E). We establish similar results for constant-dimension subspace codes. Moreover, we show that, with high probability, the list-decoding radius of random Fq-linear rank metric codes also achieve the Gilbert-Varshamov bound with constant list size O(exp(1/E)). ASTAR (Agency for Sci., Tech. and Research, S’pore) 2016-08-16T09:07:38Z 2019-12-06T14:47:57Z 2016-08-16T09:07:38Z 2019-12-06T14:47:57Z 2015 Journal Article Ding, Y. (2014). On List-Decodability of Random Rank Metric Codes and Subspace Codes. IEEE Transactions on Information Theory, 61(1), 51-59. 0018-9448 https://hdl.handle.net/10356/82171 http://hdl.handle.net/10220/41145 10.1109/TIT.2014.2371915 en IEEE Transactions on Information Theory © 2014 IEEE. |
| spellingShingle | Gilbert-Varshamov bound Constant-dimension subspace codes Ding, Yang On List-Decodability of Random Rank Metric Codes and Subspace Codes |
| title | On List-Decodability of Random Rank Metric Codes and Subspace Codes |
| title_full | On List-Decodability of Random Rank Metric Codes and Subspace Codes |
| title_fullStr | On List-Decodability of Random Rank Metric Codes and Subspace Codes |
| title_full_unstemmed | On List-Decodability of Random Rank Metric Codes and Subspace Codes |
| title_short | On List-Decodability of Random Rank Metric Codes and Subspace Codes |
| title_sort | on list decodability of random rank metric codes and subspace codes |
| topic | Gilbert-Varshamov bound Constant-dimension subspace codes |
| url | https://hdl.handle.net/10356/82171 http://hdl.handle.net/10220/41145 |
| work_keys_str_mv | AT dingyang onlistdecodabilityofrandomrankmetriccodesandsubspacecodes |