四川师范大学学报（自然科学版）2026，Vol.49Issue(2)：170-183,14.DOI:10.3969/j.issn.1001-8395.2026.02.003
网络函数计算编码的容量增益
Capacity Gain for Computing Coding of the Network Function
摘要
Abstract
The problem for the computation of the network function is considered in this paper,where in a directed acyclic network,a single sink node requires to repeatedly compute a target function of source messages generated by multiple source nodes with zero error.The information-theoretic computing capacity is defined as the maximum average number of times that the function can be computed with zero error per use of the network.For the traditional way of separating communication and computation,the sink node computes the target function after receiving all the needed source messages.This reduces to a problem of network coding,where the transmission rate is con-strained by the capacity of network coding.The joint coding of communication and computation allows the nodes to encode based on the properties of the function such that the sink node can compute the target function directly.The performance is characterized by the com-puting capacity.In order to quantify the performance gap,we introduce the concept of computing gain,which is defined as the ratio of the computing capacity to the capacity of network coding.In this paper,we consider the model of computing as a class of linear functions over reversed combination networks.For this model,by evaluating the computing capacity and the capacity of network coding,we explic-itly quantify the computing gain in a closed form,which is determined by three parameters.Further,based on the asymptotic behavior of these parameters,we fully analyze the asymptotic properties of the computing gain.The obtained results show that the gain of computing capacity over the capacity of network coding can be unbounded.Thus,this implies that the efficiency of integrating communication and computation over the separate way of communication and computation is significant in general.关键词
网络函数计算/网络编码/计算容量/计算增益/反向组合网络Key words
network function computation/network coding/computing capacity/computing gain/reversed combination network分类
数理科学引用本文复制引用
光炫,李丹,李珊珊,孙秀芳..网络函数计算编码的容量增益[J].四川师范大学学报（自然科学版）,2026,49(2):170-183,14.基金项目
国家自然科学基金(62171238和62461160306)、天津市高等学校研究生教育改革研究计划项目、南开大学本科教育教学改革项目(NKJG2025161) （62171238和62461160306）
