A new class of rank-metric codes and their list decoding beyond the unique decoding radius
Compared with classical block codes, list decoding rank-metric codes efficiently seems more difficult. The evidences to support this view include: 1) so far the only known efficient list decoding of rank-metric codes C gives decoding radius beyond (1 - R)/2 with positive rate R when the ratio of the...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/145452 |
| _version_ | 1811684988084551680 |
|---|---|
| author | Xing, Chaoping Yuan, Chen |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Xing, Chaoping Yuan, Chen |
| author_sort | Xing, Chaoping |
| collection | NTU |
| description | Compared with classical block codes, list decoding rank-metric codes efficiently seems more difficult. The evidences to support this view include: 1) so far the only known efficient list decoding of rank-metric codes C gives decoding radius beyond (1 - R)/2 with positive rate R when the ratio of the number of rows over the number of columns is extremely small, 2) the Johnson bound for rank-metric codes does not exist as opposed to classical codes, and 3) the Gabidulin codes of square matrices cannot be list decoded beyond half of the minimum distance. Although the list decodability of random rank-metric codes and the limits to the list decodability have been determined completely, little work on efficient list decoding of rank-metric codes has been done. The only known efficient list decoding of rank-metric codes C gives decoding radius up to the singleton bound 1-R-e with positive rate R when ρ(C) is extremely small, i.e., O(ε 2 ), where ρ(C) denotes the ratio of the number of rows over the number of columns of C. It is commonly believed that it is difficult to list decode rank-metric codes C with the ratio ρ(C) close to 1. The main purpose of this paper is to explicitly construct a class of rank-metric codes C with the ratio ρ(C) up to 1/2 and efficiently list decode these codes beyond unique decoding radius (1 - R)/2. Furthermore, encoding and list decoding algorithms run in polynomial time poly(n, exp(1/e)). The list size can be reduced to O(1/e) by randomizing the algorithm. Our key idea is to employ bivariate polynomials f (x, y), where f is linearized in variable y and the variable x is used to “fold” the code. In other words, the rows are used to correct rank errors and the columns are used to “fold” the code to enlarge the decoding radius. Apart from the above algebraic technique, we have to prune down the list. The algebraic idea enables us to pin down the messages into a structured subspace whose dimension is linear in the number n of columns. This “periodic” structure allows us to pre-encode the messages to prune down the list. More precisely, we use subspace design introduced by Guruswami and Xing to obtain a deterministic algorithm with a larger constant list size and employ hierarchical subspace-evasive sets introduced by Guruswami et al. to obtain a randomized algorithm with a smaller constant list size. |
| first_indexed | 2024-10-01T04:37:22Z |
| format | Journal Article |
| id | ntu-10356/145452 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:37:22Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1454522020-12-22T03:07:59Z A new class of rank-metric codes and their list decoding beyond the unique decoding radius Xing, Chaoping Yuan, Chen School of Physical and Mathematical Sciences Engineering::Computer science and engineering Code Decoding Compared with classical block codes, list decoding rank-metric codes efficiently seems more difficult. The evidences to support this view include: 1) so far the only known efficient list decoding of rank-metric codes C gives decoding radius beyond (1 - R)/2 with positive rate R when the ratio of the number of rows over the number of columns is extremely small, 2) the Johnson bound for rank-metric codes does not exist as opposed to classical codes, and 3) the Gabidulin codes of square matrices cannot be list decoded beyond half of the minimum distance. Although the list decodability of random rank-metric codes and the limits to the list decodability have been determined completely, little work on efficient list decoding of rank-metric codes has been done. The only known efficient list decoding of rank-metric codes C gives decoding radius up to the singleton bound 1-R-e with positive rate R when ρ(C) is extremely small, i.e., O(ε 2 ), where ρ(C) denotes the ratio of the number of rows over the number of columns of C. It is commonly believed that it is difficult to list decode rank-metric codes C with the ratio ρ(C) close to 1. The main purpose of this paper is to explicitly construct a class of rank-metric codes C with the ratio ρ(C) up to 1/2 and efficiently list decode these codes beyond unique decoding radius (1 - R)/2. Furthermore, encoding and list decoding algorithms run in polynomial time poly(n, exp(1/e)). The list size can be reduced to O(1/e) by randomizing the algorithm. Our key idea is to employ bivariate polynomials f (x, y), where f is linearized in variable y and the variable x is used to “fold” the code. In other words, the rows are used to correct rank errors and the columns are used to “fold” the code to enlarge the decoding radius. Apart from the above algebraic technique, we have to prune down the list. The algebraic idea enables us to pin down the messages into a structured subspace whose dimension is linear in the number n of columns. This “periodic” structure allows us to pre-encode the messages to prune down the list. More precisely, we use subspace design introduced by Guruswami and Xing to obtain a deterministic algorithm with a larger constant list size and employ hierarchical subspace-evasive sets introduced by Guruswami et al. to obtain a randomized algorithm with a smaller constant list size. 2020-12-22T03:07:59Z 2020-12-22T03:07:59Z 2018 Journal Article Xing, C., & Yuan, C. (2018). A new class of rank-metric codes and their list decoding beyond the unique decoding radius. IEEE Transactions on Information Theory, 64(5), 3394-3402. doi:10.1109/TIT.2017.2780848 1557-9654 https://hdl.handle.net/10356/145452 10.1109/TIT.2017.2780848 5 64 3394 3402 en IEEE Transactions on Information Theory © 2018 Institute of Electrical and Electronics Engineers (IEEE). All rights reserved. |
| spellingShingle | Engineering::Computer science and engineering Code Decoding Xing, Chaoping Yuan, Chen A new class of rank-metric codes and their list decoding beyond the unique decoding radius |
| title | A new class of rank-metric codes and their list decoding beyond the unique decoding radius |
| title_full | A new class of rank-metric codes and their list decoding beyond the unique decoding radius |
| title_fullStr | A new class of rank-metric codes and their list decoding beyond the unique decoding radius |
| title_full_unstemmed | A new class of rank-metric codes and their list decoding beyond the unique decoding radius |
| title_short | A new class of rank-metric codes and their list decoding beyond the unique decoding radius |
| title_sort | new class of rank metric codes and their list decoding beyond the unique decoding radius |
| topic | Engineering::Computer science and engineering Code Decoding |
| url | https://hdl.handle.net/10356/145452 |
| work_keys_str_mv | AT xingchaoping anewclassofrankmetriccodesandtheirlistdecodingbeyondtheuniquedecodingradius AT yuanchen anewclassofrankmetriccodesandtheirlistdecodingbeyondtheuniquedecodingradius AT xingchaoping newclassofrankmetriccodesandtheirlistdecodingbeyondtheuniquedecodingradius AT yuanchen newclassofrankmetriccodesandtheirlistdecodingbeyondtheuniquedecodingradius |