Algebraic Codes for Random Linear Network Coding (Paperback)

This dissertation is devoted to the study of algebraic codes proposed for error control in random linear network coding, namely rank metric codes, subspace codes, and constant-dimension codes (CDCs). Rank metric codes have further applications in data storage, cryptography, and space-time coding. Chapter 2 investigates the properties of rank metric codes through a geometric approach. We study the fundamental problems of sphere packing and sphere covering in the rank metric, and our results provide guidelines on the design of rank metric codes. In Chapter 3, we derive the MacWilliams identity and related identities for rank metric codes which parallel the binomial and power moment identities derived for codes with the Hamming metric. These identities are fundamental relationships between linear rank metric codes and their dual. In Chapter 4, we introduce a new approach to studying CDCs. We show that optimal CDCs correspond to optimal constant-rank codes over sufficiently large extension fields, hence the problem of determining the cardinality of an optimal CDC can be solved by studying constant-rank codes instead. Constant-rank codes are also a useful tool to investigate the decoder error probability (DEP) of rank metric codes. We thus show that the maximum DEP of rank metric codes used over an equal row or an equal column space channel decreases exponentially with t2, where t is the error correction capability of the code. In Chapter 5, we investigate the packing and covering properties of CDCs and subspace codes. We first construct a new class of CDCs and investigate the covering properties of CDCs. We then prove that optimal packing CDCs are nearly optimal packing subspace codes for both metrics. However, optimal covering CDCs can be used to construct asymptotically optimal covering subspace codes only for the injection metric. We finally determine the DEP of any lifting of a rank metric code over a symmetric operator channel.