List decoding of rank-metric and cover-metric codes
A fundamental challenge in coding theory is to efficiently decode the original transmitted message even when a few symbols of the received word are erroneous. Traditionally, unique decoding outputs a unique codeword and can only correct up to half the minimum distance of the code. An alternative not...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/74108 |
| _version_ | 1826121595874181120 |
|---|---|
| author | Liu, Shu |
| author2 | Wang Huaxiong |
| author_facet | Wang Huaxiong Liu, Shu |
| author_sort | Liu, Shu |
| collection | NTU |
| description | A fundamental challenge in coding theory is to efficiently decode the original transmitted message even when a few symbols of the received word are erroneous. Traditionally, unique decoding outputs a unique codeword and can only correct up to half the minimum distance of the code. An alternative notion of decoding called list decoding allows the decoder to output a list of all codewords and permits recovery from errors well beyond the unique decoding barrier. However, the study of list decoding of rank-metric and cover-metric codes has not been as extensive and complete as that of Hamming metric codes.
This thesis presents a detailed investigation of list decoding of rank-metric and cover-metric codes as well as constructions of some codes with good parameters. Our main results consist of four parts. Firstly, we reveal that a random subcode of a Gabidulin code can be list decoded with list decoding radius far beyond half of the minimum distance. Then, we show that the list decoding radius of $\F_q$-linear self-orthogonal rank-metric codes can attain the Gilbert-Varshamov bound with polynomial list size. Furthermore, we successfully construct a new family of $\F_q$-linear MRD codes of large dimension that is not equivalent to any other existing families. Finally, we present that a random cover-metric code can be list decoded up to the Singleton bound and provide explicit constructions attaining this bound. |
| first_indexed | 2024-10-01T05:34:47Z |
| format | Thesis |
| id | ntu-10356/74108 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:34:47Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/741082023-02-28T23:46:30Z List decoding of rank-metric and cover-metric codes Liu, Shu Wang Huaxiong Xing Chaoping School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Applied mathematics::Information theory A fundamental challenge in coding theory is to efficiently decode the original transmitted message even when a few symbols of the received word are erroneous. Traditionally, unique decoding outputs a unique codeword and can only correct up to half the minimum distance of the code. An alternative notion of decoding called list decoding allows the decoder to output a list of all codewords and permits recovery from errors well beyond the unique decoding barrier. However, the study of list decoding of rank-metric and cover-metric codes has not been as extensive and complete as that of Hamming metric codes. This thesis presents a detailed investigation of list decoding of rank-metric and cover-metric codes as well as constructions of some codes with good parameters. Our main results consist of four parts. Firstly, we reveal that a random subcode of a Gabidulin code can be list decoded with list decoding radius far beyond half of the minimum distance. Then, we show that the list decoding radius of $\F_q$-linear self-orthogonal rank-metric codes can attain the Gilbert-Varshamov bound with polynomial list size. Furthermore, we successfully construct a new family of $\F_q$-linear MRD codes of large dimension that is not equivalent to any other existing families. Finally, we present that a random cover-metric code can be list decoded up to the Singleton bound and provide explicit constructions attaining this bound. Doctor of Philosophy (SPMS) 2018-04-25T08:49:51Z 2018-04-25T08:49:51Z 2018 Thesis Liu, S. (2018). List decoding of rank-metric and cover-metric codes. Doctoral thesis, Nanyang Technological University, Singapore. http://hdl.handle.net/10356/74108 10.32657/10356/74108 en 112 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics::Applied mathematics::Information theory Liu, Shu List decoding of rank-metric and cover-metric codes |
| title | List decoding of rank-metric and cover-metric codes |
| title_full | List decoding of rank-metric and cover-metric codes |
| title_fullStr | List decoding of rank-metric and cover-metric codes |
| title_full_unstemmed | List decoding of rank-metric and cover-metric codes |
| title_short | List decoding of rank-metric and cover-metric codes |
| title_sort | list decoding of rank metric and cover metric codes |
| topic | DRNTU::Science::Mathematics::Applied mathematics::Information theory |
| url | http://hdl.handle.net/10356/74108 |
| work_keys_str_mv | AT liushu listdecodingofrankmetricandcovermetriccodes |