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.
翻译:我们研究的是零危险源编码问题, 使用侧边信息编码器( SI) $g( Y) 的编码器将源符号 $X 美元传送给解码器。 解码器有 SI 美元 美元, 想要在 $f ( X, Y) 美元为确定性的情况下收回 $f( X, Y) 美元 。 我们展示了一个源分布条件和 $g 美元, 我们称之为“ 双向共享侧信息 ”, 这样, 最佳比率就有一个单字母表达方式。 如果每对源符号“ share” 至少有一个 SI 符号, 则这个条件得到满足 。 它有一个实用的解释, 作为 $Y 模型, 由编码器以 $X$( $) 和 $g( Y) 美元 来代表请求的类型 。 我们还有一个图形理论解释 : 在“ 双向共享侧信息 ” 下, 特征图表可以写成一个不连接的 ORE 产品。 在源分布是 完全支持的案例中, 我们为最佳比率表示 。 我们从 格式展示了一种战略 。