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...

Full description

Saved in:
Bibliographic Details
Main Author: Liu, Shu
Other Authors: Wang Huaxiong
Format: Theses and Dissertations
Language:English
Published: 2018
Subjects:
Online Access:http://hdl.handle.net/10356/74108
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-74108
record_format dspace
spelling sg-ntu-dr.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
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Science::Mathematics::Applied mathematics::Information theory
spellingShingle DRNTU::Science::Mathematics::Applied mathematics::Information theory
Liu, Shu
List decoding of rank-metric and cover-metric codes
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.
author2 Wang Huaxiong
author_facet Wang Huaxiong
Liu, Shu
format Theses and Dissertations
author Liu, Shu
author_sort Liu, Shu
title List decoding of rank-metric and cover-metric codes
title_short 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_sort list decoding of rank-metric and cover-metric codes
publishDate 2018
url http://hdl.handle.net/10356/74108
_version_ 1759855709264019456