A Caltech Library Service

Network Coding for Error Correction


Vyetrenko, Svitlana S. (2011) Network Coding for Error Correction. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/D2ZM-V541.


In this thesis, network error correction is considered from both theoretical and practical viewpoints. Theoretical parameters such as network structure and type of connection (multicast vs. nonmulticast) have a profound effect on network error correction capability. This work is also dictated by the practical network issues that arise in wireless ad-hoc networks, networks with limited computational power (e.g., sensor networks) and real-time data streaming systems (e.g., video/audio conferencing or media streaming).

Firstly, multicast network scenarios with probabilistic error and erasure occurrence are considered. In particular, it is shown that in networks with both random packet erasures and errors, increasing the relative occurrence of erasures compared to errors favors network coding over forwarding at network nodes, and vice versa. Also, fountain-like error-correcting codes, for which redundancy is incrementally added until decoding succeeds, are constructed. These codes are appropriate for use in scenarios where the upper bound on the number of errors is unknown a priori.

Secondly, network error correction in multisource multicast and nonmulticast network scenarios is discussed. Capacity regions for multisource multicast network error correction with both known and unknown topologies (coherent and noncoherent network coding) are derived. Several approaches to lower- and upper-bounding error-correction capacity regions of general nonmulticast networks are given. For 3-layer two-sink and nested-demand nonmulticast network topologies some of the given lower and upper bounds match. For these network topologies, code constructions that employ only intrasession coding are designed. These designs can be applied to streaming erasure correction code constructions.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:network coding, network error correction
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Ho, Tracey C.
Thesis Committee:
  • Ho, Tracey C. (chair)
  • Effros, Michelle
  • Tropp, Joel A.
  • Owhadi, Houman
Defense Date:26 May 2011
Record Number:CaltechTHESIS:06032011-153909265
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6497
Deposited By: Svitlana Vyetrenko
Deposited On:06 Jun 2011 16:03
Last Modified:07 Jun 2023 17:17

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page