Network Function Computation for Vector Linear Functions

In this paper, we consider the vector linear function computing problem in a network where communication links may suffer from errors. A sink node is required to compute with zero error a vector linear function over a finite field, and the inputs of the target function are generated by multiple source nodes. The nodes in this network can combat errors by network coding. Given a nonnegative integer <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tau$</tex>, the robust computing capacity for the above model is defined as the maximum average number of times that the target function can be computed with zero error at the sink node for one use of the network, in which at most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tau$</tex> links may suffer from errors. When <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tau=0$</tex>, the robust computing capacity degenerates into the computing capacity without errors. For <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tau\geq 0$</tex>, we propose two cut-set bounds on the robust computing capacity. By comparing their performance under the same conditions, we find that the latter bound is superior to the former. Furthermore, we present an improved Singleton bound for linear network codes in the above model, and show that the improved Singleton bound performs better and is tight in a specific scenario. Moreover, we present the Hamming bound and an improved Hamming bound for linear network codes.