Infinite-message distributed source coding for two-terminal interactive computing
Infinite-message distributed source coding for two-terminal interactive computing
复制标题
面向两端交互计算的无限消息分布式源码编码
DOI：
10.1109/allerton.2009.5394497
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
P. Ishwar
中科院分区：
文献类型：
--
作者：
Nan Ma;P. Ishwar
在分布式分块信源编码理论框架内研究了具有交替消息的两端交互式函数计算问题。对于任意固定数量的消息，先前的工作使用传统信息论技术给出了最小和速率函数的单字母表征。然而，这并不能直接对无限消息极限给出令人满意的表征，而无限消息极限是分布式分块信源编码中渐近分析的一个新的、尚未探索的维度，其中涉及可能具有无穷小速率的消息。本文引入一种新的凸几何方法，将无限消息最小和速率函数作为联合信源概率质量函数（pmf）的一个泛函给出无分块长度的单字母表征。这种表征不是通过取消息数量趋于无穷时的极限得到的。相反，它是根据与要计算的函数相关的一族偏序边际扰动 - 凹泛函的最小元素来表示的。对于在一个终端和两个终端计算两个独立伯努利信源的布尔“与”函数，分别以封闭解析形式给出了相应的无限消息最小和速率。这些和速率可以使用无限多个无穷小速率消息来实现。凸几何泛函观点还提出了一种用于评估任何有限消息最小和速率函数的迭代算法。
A two-terminal interactive function computation problem with alternating messages is studied within the framework of distributed block source coding theory. For any arbitrary fixed number of messages, a single-letter characterization of the minimum sum-rate function was provided in previous work using traditional information-theoretic techniques. This, however, does not directly lead to a satisfactory characterization of the infinite-message limit, which is a new, unexplored dimension for asymptotic-analysis in distributed block source coding involving potentially infinitesimal-rate messages. This paper introduces a new convex-geometric approach to provide a blocklength-free single-letter characterization of the infinite-message minimum sum-rate function as a functional of the joint source pmf. This characterization is not obtained by taking a limit as the number of messages goes to infinity. Instead, it is in terms of the least element of a family of partially-ordered marginal-perturbations-concave functionals associated with the functions to be computed. For computing the Boolean AND function of two independent Bernoulli sources at one and both terminals, the respective infinite-message minimum sum-rates are characterized in closed analytic form. These sum-rates are achievable using infinitely many infinitesimal-rate messages. The convex-geometric functional viewpoint also suggests an iterative algorithm for evaluating any finite-message minimum sum-rate function.