Lattice Index Coding

Preprint English OPEN
Natarajan, Lakshmi ; Hong, Yi ; Viterbo, Emanuele (2014)

The index coding problem involves a sender with K messages to be transmitted across a broadcast channel, and a set of receivers each of which demands a subset of the K messages while having prior knowledge of a different subset as side information. We consider the specific case of noisy index coding where the broadcast channel is Gaussian and every receiver demands all the messages from the source. Instances of this communication problem arise in wireless relay networks, sensor networks, and retransmissions in broadcast channels. We construct 'lattice index codes' for this channel by encoding the K messages individually using K modulo lattice constellations and transmitting their sum modulo a coarse lattice. We introduce a design metric called 'side information gain' that measures the advantage of a code in utilizing the side information at the receivers, and hence its goodness as an index code. Based on the Chinese remainder theorem, we then construct lattice index codes with large side information gains using lattices over the following principal ideal domains: rational integers, Gaussian integers, Eisenstein integers, and the Hurwitz quaternions. Among all lattice index codes constructed using any densest lattice of a given dimension, our codes achieve the maximum side information gain. Finally, using an example, we illustrate how the proposed lattice index codes can benefit Gaussian broadcast channels with more general message demands.
  • References (27)
    27 references, page 1 of 3

    [1] Y. Birk and T. Kol, “Informed-source coding-on-demand (ISCOD) over broadcast channels,” in Proc. 17th Annu. Joint Conf. IEEE Computer and Communications Societies (INFOCOM), vol. 3, Mar. 1998, pp. 1257-1264.

    [2] Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, “Index coding with side information,” IEEE Trans. Inf. Theory, vol. 57, no. 3, pp. 1479-1494, Mar. 2011.

    [3] N. Alon, E. Lubetzky, U. Stav, A. Weinstein, and A. Hassidim, “Broadcasting with side information,” in Proc. 49th IEEE Symp. Foundations of Computer Science (FOCS), Oct. 2008, pp. 823-832.

    [4] S. El Rouayheb, A. Sprintson, and C. Georghiades, “On the index coding problem and its relation to network coding and matroid theory,” IEEE Trans. Inf. Theory, vol. 56, no. 7, pp. 3187-3195, Jul. 2010.

    [5] A. Blasiak, R. D. Kleinberg, and E. Lubetzky, “Index coding via linear programming,” arXiv preprint, 2010. [Online]. Available:

    [6] S. Unal and A. Wagner, “General index coding with side information: Three decoder case,” in Proc. IEEE Int. Symp. Information Theory (ISIT), Jul. 2013, pp. 1137-1141.

    [7] Y. Wu, “Broadcasting when receivers know some messages a priori,” in Proc. IEEE Int. Symp. Information Theory (ISIT), Jun. 2007, pp. 1141-1145.

    [8] G. Kramer and S. Shamai, “Capacity for classes of broadcast channels with receiver side information,” in Proc. IEEE Information Theory Workshop (ITW), Sep. 2007, pp. 313-318.

    [9] L.-L. Xie, “Network coding and random binning for multi-user channels,” in Proc. 10th Canadian Workshop on Information Theory (CWIT), Jun. 2007, pp. 85-88.

    [10] J. W. Yoo, T. Liu, and F. Xue, “Gaussian broadcast channels with receiver message side information,” in Proc. IEEE Int. Symp. Information Theory (ISIT), Jun. 2009, pp. 2472-2476.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository
Share - Bookmark