Performance Bounds on Pliable Index Coding Using Absent Receivers

doi:10.1109/TIT.2025.3632399

2026-01-01

PRE

DOI：10.1109/TIT.2025.3632399

原文链接

原文求助

摘要

En 中文

我们研究了针对几类可塑性索引编码实例的最优广播速率的界限。与目前已解决实例的大多数（属于一个特殊类别，其中所有具有特定边信息的接收器要么全部存在，要么全部缺失）不同，我们考虑了更一般的无此约束的实例。我们设计了一种新型算法，通过迭代添加可被已有边信息在链中的接收器解码的消息来构建解码链。若因缺少携带所需消息的接收器导致解码链无法继续，则跳过该消息并将其强制加入链中。我们证明了最优广播速率的下界是跳过消息数量的函数，该函数遍及所有可能的接收器解码选择以及针对每种解码选择的算法实现。尽管该结果单独计算不可行，但它为推导特定可塑性索引编码实例类别的显式广播速率下界奠定了基础。这些下界取决于缺失接收器的数量或其边信息集的模式。具体而言，我们明确刻画了最多包含四个缺失接收器（任意边信息模式）以及边信息集以特定方式嵌套的实例的最优广播速率。

Keyword:

Receivers

Lower bound

Codes

Indexes

Encoding

Decoding

Upper bound

Iterative decoding

Web sites

Social networking (online)

Source coding