Computing Linear Functions by Linear Coding Over Networks

作者：Appuswamy Rathinakumar^*; Franceschetti Massimo

来源：IEEE Transactions on Information Theory, 2014, 60(1): 422-431.

DOI：10.1109/TIT.2013.2283075

• Function computation
• linear coding
• network coding
• network computing

We consider the scenario in which a set of sources generates messages in a network and a receiver node demands an arbitrary linear function of these messages. We formulate an algebraic test to determine whether an arbitrary network can compute linear functions using linear codes. We identify a class of linear functions that can be computed using linear codes in every network that satisfies a natural cut-based condition. Conversely, for another class of linear functions, we show that the cut-based condition does not guarantee the existence of a linear coding solution. For linear functions over the binary field, the two classes are complements of each other.

• 出版日期2014-1
• 单位IBM