Update-based Maximum Column Distance Coding Scheme for Index Coding Problem

In this paper, we propose a new scalar linear coding scheme for the index coding problem called update-based maximum column distance (UM CD) 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 UM CD 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 (Thapa et al., 2017).