Extreme Rate Optimal Index Code

Abstract

Index coding is an elegant and powerful idea for minimal usage of broadcast channels that investigates the fundamental limits and optimal coding schemes in information flow networks such as wireless networks, data storage networks, and content delivery networks. Minimal usage of broadcast channels is the main requirement of efficient information broadcasting in information flow networks which is the ultimate goal for successful communication. Finding the optimal index code with extreme rate for the class of index coding problems is the fundamental question in index coding. In this work, we present a new class of index coding problems with the size of maximum acyclic induced subgraph = 3. We refer to this class of index coding problems as $class \mathbb {III}$ index coding problems. Our goal is to characterize the extreme rate (i.e., the optimal index code length for extreme rate) for $class \mathbb {III}$ index coding problems. We show that the optimal linear index code of the $class \mathbb {III}$ index coding problem over $\mathbb {F}_{2}$ achieves the extreme rate on the broadcast rate. To present this new result, we use the results of index coding network coding duality. In contrast with this new result, we also present that there exists maximum acyclic induced subgraph size 3 index coding problems with the optimal broadcast rate strictly greater than the extreme rate. To present this contrast, we use the alignment graph and the conflict hyper graph based approach.

Keywords

• Duality
• extreme rate
• index coding
• network coding
• multiple unicast