On the capacity region for index coding

Authors:
  • FAFatemeh Arbabjolfaei
    Fatemeh Arbabjolfaei
  • BBBernd Bandemer
    Bernd Bandemer
  • YKYoung-Han Kim
    Young-Han Kim
  • ESEren Sasoglu
    Eren Sasoglu
  • LWLele Wang
    Lele Wang

Abstract
A new inner bound on the capacity region of a general index coding problem is established. Unlike most existing bounds that are based on graph theoretic or algebraic tools, the bound is built on a random coding scheme and optimal decoding, and has a simple polymatroidal single-letter expression. The utility of the inner bound is demonstrated by examples that include the capacity region for all index coding problems with up to five messages (there are 9846 nonisomorphic ones).Comment: 5 pages, 6 figures, accepted to the 2013 IEEE International Symposium on Information Theory (ISIT), Istanbul, Turkey, July 201