Scalar Linear Network Coding for Networks with Two Sources

Abstract

Determining the capacity of networks has been a long-standing issue of interest in the literature. Although for multi-source multi-sink networks it is known that using network coding is advantageous over traditional routing, finding the best coding strategy is not trivial in general. Among different classes of codes that could be potentially used in a network, linear codes due to their simplicity are of particular interest. Although linear codes are proven to be sub-optimal in general, in some cases such as the multicast scenario they achieve the cut-set bound. Since determining the capacity of a network is closely related to the characterization of the entropy region of all its random variables, if one is interested in finding the best linear solution for a network, one should find the region of all linear representable entropy vectors of that network. With this approach, we study the scalar linear solutions over arbitrary network problems with two sources. We explicitly calculate this region for small number of variables and suggest a method for larger networks through finding the best scalar linear solution to a storage problem as an example of practical interest.

Files

Additional details