A Two Step Optimal Decoding for PSK and Trellis Coded Modulation in Noisy Index Coding Problem

Abstract

Index coding is a communication problem in which a server has a set of messages and wants to broadcast them to a set of receivers. Each receiver is interested in a single message, but some of the receivers may have some of the messages as side information. The goal is to broadcast all the messages to their designated receivers using the minimum possible number of transmissions. For example, consider a server with three messages, x1, x2, and x3, and three receivers, R1, R2, and R3. Receiver R1 is interested in x1, receiver R2 is interested in x2, and receiver R3 is interested in x3. Receiver R1 has x2 as side information, receiver R2 has x1 and x3 as side information, and receiver R3 has x1 as side information. The naive way to broadcast all the messages would be to send each message one at a time, which would require three transmissions. However, it is possible to do better than this. For example, the server could send the coded messages x1 + x2 and x3. Receiver R1 can decode x1 from the first coded message, receiver R2 can decode x2 from the second coded message, and receiver R3 can decode x3 from the sum of the two coded messages. In our work, we have considered noisy index coding problems over single-input single-output broadcast channels. The codewords from a chosen index code of length N are transmitted after 2 N -PSK modulation over an AWGN channel. The receivers follow the two-step decoding process of first estimating the PSK symbol using an ML decoder and then performing index decoding. After estimating the PSK symbol, there might be more than one decoding strategy at a receiver, i.e., a linear combination of index-coded bits along with a subset of side information bits, that can be used to estimate the requested message. Thomas et al. in [“Single Uniprior Index Coding With Min–Max Probability of Error Over Fading Channels,”] showed that for binary-modulated index code transmissions, minimizing the number of transmissions used to decode a requested message is equivalent to reducing the probability of error. This paper shows that this is no longer true while employing multi-level modulations. Further, we consider that the side information available to each receiver is also noisy and derive an expression for the probability that a requested message bit is estimated erroneously at a receiver. We also show that the criterion for choosing a decoding strategy that gives the best probability of error performance at a receiver changes with the signal to-noise ratio at which the side information is broadcast. Hence, for a given index coding problem and a chosen index code, we give an algorithm to select the best decoding strategy for the receivers. The above results are shown to be valid over fading channels also. Lastly, we have used the bandwidth-efficient scheme, Trellis Coded Modulation. As we know, this scheme gives better error performance than the Uncoded system. We have employed this scheme in Index Coding Problem to get further gain in the error performance of the system. Here also, the two-step decoding process is used. We have also found the criteria for selecting the optimal decoding strategy for this.