List decoding of rank-metric and cover-metric codes

• Main Author: Liu, Shu
• Other Authors: Wang Huaxiong
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Science::Mathematics::Applied mathematics::Information theory
• Online Access: http://hdl.handle.net/10356/74108
• Institution: Nanyang Technological University

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.