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) ) 有更好的广播性能。