论文标题
在成对共享的侧面信息下计算计算的最佳零错误编码
Optimal Zero-Error Coding for Computing under Pairwise Shared Side Information
论文作者
论文摘要
我们研究了零错误的源编码问题，其中用侧面信息（si）$ g（y）$ transmits源符号$ x $向解码器进行编码。解码器具有si $ y $，并希望收回$ f（x，y）$，其中$ f，g $是确定性的。我们表现出关于源分布的条件和$ g $，我们称为“成对共享的侧面信息”，因此最佳速率具有单个字母的表达式。如果每对$ g $的输出至少一个SI符号“共享”至少一个SI符号，则可以满足此条件。它具有实用的解释，因为$ y $型号是由编码器在图像$ x $上提出的请求，而$ g（y）$对应于请求的类型。它还具有图理论的解释：在“成对共享侧面信息”下，特征图可以写成或产品的不相交联合。如果源分布是全供支持的，则为最佳速率提供分析表达式。我们在“成对共享侧面信息”下开发了一个示例，我们表明，最佳编码方案的表现优于文献中的几种策略。
We study the zero-error source coding problem in which an encoder with Side Information (SI) $g(Y)$ transmits source symbols $X$ to a decoder. The decoder has SI $Y$ and wants to recover $f(X,Y)$ where $f,g$ are deterministic. We exhibit a condition on the source distribution and $g$ that we call "pairwise shared side information", such that the optimal rate has a single-letter expression. This condition is satisfied if every pair of source symbols "share" at least one SI symbol for all output of $g$. It has a practical interpretation, as $Y$ models a request made by the encoder on an image $X$, and $g(Y)$ corresponds to the type of request. It also has a graph-theoretical interpretation: under "pairwise shared side information" the characteristic graph can be written as a disjoint union of OR products. In the case where the source distribution is full-support, we provide an analytic expression for the optimal rate. We develop an example under "pairwise shared side information", and we show that the optimal coding scheme outperforms several strategies from the literature.
