Network Function Computation for Vector Linear Functions
Qin Zhou, Fang‐Wei Fu · 2024
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$\tau$, 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$\tau$links may suffer from errors. When$\tau=0$, the robust computing capacity degenerates into the computing capacity without errors. For$\tau\geq 0$, 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.