Date

2015

Document Type

Dissertation

Degree

Doctor of Philosophy

Department

Electrical Engineering

First Adviser

Yan, Zhiyuan

Other advisers/committee members

Yan, Zhiyuan; Li, Tiffany J.; Dodson, Bruce A.; Suter, Bruce W.

Abstract

Random linear network coding (RLNC) has shown advantages in improved throughput, robustness, and reduced delay over traditional routing in a communication network. However, the underlying finite field has to be large enough for RLNC to work effectively, leading to high computational complexity. This dissertation proposes efficient decoding algorithms for RLNC with and without error control schemes, as well as new error control code constructions for a particular realization of RLNC, the coding for distributed storage systems (DSSs). In RLNC, neither the source nor the sink node has knowledge of the channel transfer characteristic. To deal with errors and erasures in this scenario, subspace codes have been proposed in the literature, including Kotter and Kschischang (KK) codes, lifting of Gabidulin code, and Mahdavifar and Vardy (MV) codes. All these codes can be constructed from evaluations of linearized polynomials. Hence we propose a general interpolation algorithm over linearized polynomials ring, and decode all the three families of codes efficiently. For Gabidulin code, our general interpolation algorithm is deterministic compared to another current decoding algorithm, i.e., it is always be able to produce the correct decoding result when errors are within the error correction capability. For KK codes and MV codes, our algorithm has lower complexity than solving linear equations, especially for MV codes with large list sizes.For RLNC without error control technique, rank deficient decoding (RDD) has been proposed to decode the package at the receiver, which transforms the decoding problem into that of a linear block code. To implement RDD efficiently, we first adopt an existing linear programming (LP) approach to accommodate equations with both even and odd parities over the binary field GF(2). Then, we propose a simplified LP algorithm for codes over extension fields of GF(2), and provide some simulation results to show that less packages are required at the receiver to get a same rate of correctly decoded packets. The data repair and reconstruction problems in distributed storage systems (DSS) were shown to be a multicast problem, thus can be solved by RLNC. Effort has been devoted to explicit code constructions for different optimization goals. We view the DSS coding from a vector space's perspective, and transform data reconstruction and repair requirements into intersection properties of certain subspaces. Three code constructions are proposed for DSSs under the same vector space structure, aiming at low repair complexity, minimized repair bandwidth, and maximized minimum distance given a repair locality, respectively.

Share

COinS