Locally Decodable Index Codes
Locally Decodable Index Codes
复制标题
本地可解码索引代码
DOI：
--
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
D. Dau
中科院分区：
文献类型：
--
作者：
L. Natarajan;Prasad Krishnan;V. Lalitha;Hoang Dau;D. Dau
如果每个接收机可以通过仅观察所发送的码字符号的子集而不是整个码字来解码其需求，则具有接收机侧信息的广播信道的索引码是本地可解码的。在无线衰落信道中，索引编码的局部可解码性可以降低接收机的复杂度，提高用户隐私性，降低解码错误概率。传统的索引编码解决方案假设接收机观察整个码字，并且因此，对于这些码，每个解码消息符号由用户查询的码字符号的数量（我们称之为局部性）可能很大。在本文中，我们提出了索引编码问题，即对于给定的局部性值（反之亦然）最小化广播速率，并设计实现局部性和速率之间最佳权衡的代码。我们确定了与所有单个单播问题的最小可能局部值相对应的最佳广播速率。我们提出了新的结构属性的索引代码，使我们能够表征的最佳权衡实现：向量线性代码时，边信息图是一个有向循环;和标量线性代码时，边信息图的minrank是一个小于问题的顺序。我们还确定了最佳的权衡之间的所有代码，包括非线性代码，当边信息图是一个有向3-循环。最后，我们提出的技术来设计本地可解码的索引码的任意单单播问题和任意值的地方。
An index code for broadcast channel with receiver side information is locally decodable if each receiver can decode its demand by observing only a subset of the transmitted codeword symbols instead of the entire codeword. Local decodability in index coding is known to reduce receiver complexity, improve user privacy and decrease decoding error probability in wireless fading channels. Conventional index coding solutions assume that the receivers observe the entire codeword, and as a result, for these codes the number of codeword symbols queried by a user per decoded message symbol, which we refer to as locality, could be large. In this paper, we pose the index coding problem as that of minimizing the broadcast rate for a given value of locality (or vice versa) and designing codes that achieve the optimal trade-off between locality and rate. We identify the optimal broadcast rate corresponding to the minimum possible value of locality for all single unicast problems. We present new structural properties of index codes which allow us to characterize the optimal trade-off achieved by: vector linear codes when the side information graph is a directed cycle; and scalar linear codes when the minrank of the side information graph is one less than the order of the problem. We also identify the optimal trade-off among all codes, including non-linear codes, when the side information graph is a directed 3-cycle. Finally, we present techniques to design locally decodable index codes for arbitrary single unicast problems and arbitrary values of locality.
索引编码中的隐私：$k$ - 有限访问方案
影响因子：
2.5
作者：
Karmoose, Mohammed;Song, Linqi;Cardone, Martina;Fragouli, Christina
通讯作者：
Fragouli, Christina