Some Results on Distributed Source Coding for Interactive Function Computation
Some Results on Distributed Source Coding for Interactive Function Computation
复制标题
DOI：
10.1109/tit.2011.2161916
复制
发表时间：
2011-09-01
影响因子：
2.5
通讯作者：
Ishwar, Prakash
中科院分区：
文献类型：
--
作者：
Ma, Nan;Ishwar, Prakash
研究了一个在两个位置进行函数计算且消息交替的两端交互式分布式信源编码问题。对于任意数量的消息，根据单字母信息量给出了速率区域的一种可计算表征。虽然就一个或两个位置无损信源再现的最小和速率而言，交互是无用的，但对于函数计算，即使信源是独立的，增益也可以任意大。对于一类信源和函数，当仅需在一个位置计算函数时，即使有无限条消息，交互也被证明是无用的，但如果需在两个位置计算函数，则被证明是有用的。对于在两个位置计算两个独立伯努利信源的布尔“与”函数，根据一个二维定积分和一条速率分配曲线，推导出了一种可实现的具有无穷小速率消息的无限消息和速率。通过实例在多端函数计算问题中强调了交互的益处。对于具有星型拓扑的网络，随着网络的增长，多轮交互式编码被证明可将总网络速率的缩放定律降低一个数量级。
A two-terminal interactive distributed source coding problem with alternating messages for function computation at both locations is studied. For any number of messages, a computable characterization of the rate region is provided in terms of single-letter information measures. While interaction is useless in terms of the minimum sum-rate for lossless source reproduction at one or both locations, the gains can be arbitrarily large for function computation even when the sources are independent. For a class of sources and functions, interaction is shown to be useless, even with infinite messages, when a function has to be computed at only one location, but is shown to be useful, if functions have to be computed at both locations. For computing the Boolean AND function of two independent Bernoulli sources at both locations, an achievable infinite-message sum-rate with infinitesimal-rate messages is derived in terms of a 2-D definite integral and a rate-allocation curve. The benefit of interaction is highlighted in multiterminal function computation problem through examples. For networks with a star topology, multiple rounds of interactive coding is shown to decrease the scaling law of the total network rate by an order of magnitude as the network grows.