List decoding of rank-metric and cover-metric codes

Abstract

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.