Skip to main content
eScholarship
Open Access Publications from the University of California

UC San Diego

UC San Diego Electronic Theses and Dissertations bannerUC San Diego

List decoding of subspace codes and rank-metric codes

Abstract

Subspace codes and rank-metric codes can be used to correct errors and erasures in networks with linear network coding. Both types of codes have been extensively studied in the past five years. We develop in this document list-decoding algorithms for subspace codes and rank-metric codes, thereby providing a better tradeoff between rate and error-correction capability than existing constructions. Randomized linear network coding, considered as the most practical approach to network coding, is a powerful tool for disseminating information in networks. Yet it is highly susceptible to transmission errors caused by noise or intentional jamming. Subspace codes were introduced by Koetter and Kschischang to correct errors and erasures in networks with a randomized protocol where the topology is unknown (the non-coherent case). The codewords of a subspace code are vector subspaces of a fixed ambient space; thus the codes are collections of such subspaces. We first develop a family of subspace codes, based upon the Koetter-Kschichang construction, which are efficiently list decodable. We show that, for a certain range of code rates, our list- decoding algorithm provides a better tradeoff between rate and decoding radius than the Koetter-Kschischang codes. We further improve these results by introducing multiple roots in the interpolation step of our list-decoding algorithm. To this end, we establish the notion of derivative and multiplicity in the ring of linearized polynomials. In order to achieve a better decoding radius, we take advantage of enforcing multiple roots for the interpolation polynomial. We are also able to list decode for a wider range of rates. Furthermore, we propose an alternative approach which leads to a linear-algebraic list-decoding algorithm. Rank-metric codes are suitable for error correction in the case where the network topology and the underlying network code are known (the coherent case). Gabidulin codes are a well-known class of algebraic rank-metric codes that meet the Singleton bound on the minimum rank-distance of a code. In this dissertation, we introduce a folded version of Gabidulin codes along with a list-decoding algorithm for such codes. Our list-decoding algorithm makes it possible to achieve the information theoretic bound on the decoding radius of a rank-metric code

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View