Computing linear functions with linear network codes
Rathinakumar Appuswamy, Massimo Franceschetti · 2010
We study the problem of computing linear functions over a finite field in arbitrary networks with a single receiver node. We follow an algebraic approach similar to the one developed by Koetter and Médard for conventional network coding problems. First, we find a necessary and sufficient condition for the existence of a linear solution; then we identify a class of linear functions over the binary field that are solvable whenever the network min-cut is at least one. For linear functions outside this class, we shown that there always exists a network of min-cut one which has no linear solution.