In this paper, we propose a new scalar linear coding scheme for the index coding problem called update-based maxi-mum column distance (UMCD) coding scheme. The central idea in each transmission is to code messages such that one of the receivers with the minimum size of side information is instantaneously eliminated from unsatisfied receivers. One main contribution of the paper is to prove that the other satisfied receivers can be identified after each transmission, using a polynomial-time algorithm solving the well-known maximum cardinality matching problem in graph theory. This leads to determining the total number of transmissions without knowing the coding coefficients. Once this number and what messages to transmit in each round is found, we then propose a method to determine all coding coefficients from a sufficiently large finite field. We provide concrete instances where the proposed UMCD scheme has a better broadcast performance compared to the most efficient existing linear coding schemes, including the recursive scheme (Arbabjolfaei and Kim, 2014) and the interlinked-cycle cover scheme (Thapaet al., 2017).


翻译:在本文中, 我们为索引编码问题提出了一个名为“ 基于更新的 最大- mm 列距离( UMCD) ” ( UMCD) 的新的 标度线性编码方案。 每次传输的中心思想是代码信息, 使侧边信息最小尺寸的接收器之一能够从不满意的接收器中瞬间消除。 本文的一个主要贡献是证明其他满意接收器可以在每次传输后被识别出来, 使用多元时间算法解决图形理论中众所周知的最大基本匹配问题。 这导致在不知道编码系数的情况下确定传输的总数。 一旦发现该数和每轮传输的信息, 我们然后提议一个方法来确定从足够大的限制字段中的所有编码系数。 我们提供了具体实例, 说明拟议的 UMCD 计划比现有最有效的线性编码方案( ARbabjolfaei 和 Kim, 2014) 以及互联循环覆盖计划( Thapaet al., 201717) ) 有更好的广播性能。

0
下载
关闭预览

相关内容

最新《时序分类:深度序列模型》教程,172页ppt
专知会员服务
42+阅读 · 2020年11月11日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【斯坦福大学Chelsea Finn-NeurIPS 2019】贝叶斯元学习
专知会员服务
37+阅读 · 2019年12月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
LeetCode的C++ 11/Python3 题解及解释
专知
16+阅读 · 2019年4月13日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Arxiv
0+阅读 · 2021年3月17日
VIP会员
相关VIP内容
最新《时序分类:深度序列模型》教程,172页ppt
专知会员服务
42+阅读 · 2020年11月11日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【斯坦福大学Chelsea Finn-NeurIPS 2019】贝叶斯元学习
专知会员服务
37+阅读 · 2019年12月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
LeetCode的C++ 11/Python3 题解及解释
专知
16+阅读 · 2019年4月13日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Top
微信扫码咨询专知VIP会员