63
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Linear Network Coding, Linear Index Coding and Representable Discrete Polymatroids

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding and representable discrete polymatroids. We consider vector linear solutions of networks over a field \(\mathbb{F}_q,\) with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. We define a \textit{discrete polymatroidal} network and show that a linear fractional solution over a field \(\mathbb{F}_q,\) exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over \(\mathbb{F}_q.\) An algorithm to construct networks starting from certain class of discrete polymatroids is provided. Every representation over \(\mathbb{F}_q\) for the discrete polymatroid, results in a linear fractional solution over \(\mathbb{F}_q\) for the constructed network. Next, we consider the index coding problem and show that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions which are determined by the index coding problem considered. El Rouayheb et. al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a \textit{perfect linear index coding solution} for an index coding problem obtained from that matroid. We generalize the result of El Rouayheb et. al. by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid.

          Related collections

          Most cited references5

          • Record: found
          • Abstract: not found
          • Article: not found

          Insufficiency of Linear Coding in Network Information Flow

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Matroid representations by partitions

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Ideal Hierarchical Secret Sharing Schemes

                Bookmark

                Author and article information

                Journal
                2013-06-05
                2016-03-20
                Article
                1306.1157
                f45ff914-ed42-45f0-9edc-2675d2562109

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                24 pages, 6 figures, 4 tables, some sections reorganized, Section VI newly added, accepted for publication in IEEE Transactions on Information Theory
                cs.IT math.IT

                Numerical methods,Information systems & theory
                Numerical methods, Information systems & theory

                Comments

                Comment on this article