Design and Analysis of Efficient Index Coding Methods for Future Wireless Communications

This thesis considers the problem of efficient broadcast in a system where a single server transmits a set of messages to a number of users via a noiseless broadcast channel. Each user requests one specific message and may know some of the other messages a priori as its side information. This problem is known as the index coding problem and was first introduced by Birk and Kol [Birk and Kol, 1998], in the context of satellite communications. Exploiting the side information of the receivers along with the coding techniques at the server can reduce the number of transmissions to satisfy all the receivers. The simple model in index coding can establish a useful framework for studying other research areas, including network coding, distributed storage systems, and coded caching. In this thesis, index coding is approached from a new perspective to propose a new scalar linear coding scheme called the update-based maximum column distance (UMCD) coding scheme. In the beginning, the receivers are sorted based on the size of their side information. Then, in each transmission, a linear combination of the messages is designed to instantaneously satisfy one of the receivers with the minimum size of side information. Then, the problem is updated by eliminating all receivers who are able to decode their requested message from the coded messages received so far along with the messages in their side information. This process is repeated until all receivers can successfully decode their requested message. Concrete instances are provided to show that the proposed UMCD coding scheme has a better broadcast performance compared to the most efficient existing coding schemes, including the recursive coding scheme (Arbabjolfaei and Kim, 2014) and the interlinked-cycle cover coding scheme (Thapa et al., 2017). Also in this thesis, the insufficiency of linear coding and the necessity of nonlinear codes for index coding problem are investigated, with two main contributions. First, while the insufficiency of linear coding has been proved ...