  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).
