We consider network coding for a noiseless broadcast channel where each receiver demands a subset of messages available at the transmitter and is equipped with noisy side information in the form an erroneous version of the message symbols it demands. We view the message symbols as elements from a finite field and assume that the number of symbol errors in the noisy side information is upper bounded by a known constant. This communication problem, which we refer to as 'broadcasting with noisy side information' (BNSI), has applications in the re-transmission phase of downlink networks. We derive a necessary and sufficient condition for a linear coding scheme to satisfy the demands of all the receivers in a given BNSI network, and show that syndrome decoding can be used at the receivers to decode the demanded messages from the received codeword and the available noisy side information. We represent BNSI problems as bipartite graphs, and using this representation, classify the family of problems where linear coding provides bandwidth savings compared to uncoded transmission. We provide a simple algorithm to determine if a given BNSI network belongs to this family of problems, i.e., to identify if linear coding provides an advantage over uncoded transmission for the given BNSI problem. We provide lower bounds and upper bounds on the optimal codelength and constructions of linear coding schemes based on linear error correcting codes. For any given BNSI problem, we construct an equivalent index coding problem. A linear code is a valid scheme for a BNSI problem if and only if it is valid for the constructed index coding problem.
@cite_10 is a related code design problem that is concerned with the transmission of a set of information symbols to finitely many receivers in a noiseless broadcast channel where each receiver demands a subset of information symbols from the transmitter and already knows a subset of symbols as side information. The demand subset and the side information subset at each receiver in index coding are disjoint and the side information is assumed to be noiseless. Several results on index coding are available based on algebraic and graph theoretic formulations @cite_13 @cite_3 @cite_0 @cite_8 @cite_16 @cite_19 @cite_18 @cite_2 @cite_15 @cite_9 . The problem of index coding under noisy broadcast channel conditions has also been studied. @cite_14 analyzed linear index codes for error-prone broadcast channels. Several works, for example @cite_6 @cite_12 , provide constructions of error correcting index codes. Kim and No @cite_11 consider errors both during broadcast channel transmission as well as in receiver side information.
@cite_18 @cite_14 @cite_8 @cite_10 @cite_9 @cite_3 @cite_6 @cite_0 @cite_19 @cite_2 @cite_15 @cite_16 @cite_13 @cite_12 @cite_11
2951862780 2013945717 2130507035 2586563294 2010213837 2613309614 2413001059 1992260716 2012559125 2950353084 1653737407 2613231979 2950739801
We present a novel upper bound for the optimal index coding rate. Our bound uses a graph theoretic quantity called the local chromatic number. We show how a good local coloring can be used to create a good index code. The local coloring is used as an alignment guide to assign index coding vectors from a general position MDS code. We further show that a natural LP relaxation yields an even stronger index code. Our bounds provably outperform the state of the art on index coding but at most by a constant factor. A problem of index coding with side information was first considered by Birk and Kol in 1998. In this study, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols δ , what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the α-bound and the κ -bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with a maximum distance separable classical code is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another inexplicit bound on the length of an optimal linear ECIC. Further, the problem of error-correcting decoding by a linear ECIC is studied. It is shown that in order to decode correctly the desired symbol, the decoder is required to find one of the vectors, belonging to an affine space containing the actual error vector. The syndrome decoding is shown to produce the correct output if the weight of the error pattern is less or equal to the error-correcting capability of the corresponding ECIC. Finally, the notion of static ECIC, which is suitable for use with a family of instances of an index coding problem, is introduced. Several bounds on the length of static ECICs are derived, and constructions for static ECICs are discussed. Connections of these codes to weakly resilient Boolean functions are established. Motivated by a problem of transmitting supplemental data over broadcast channels (Birk and Kol, INFOCOM 1998), we study the following coding problem: a sender communicates with n receivers R1,..., Rn. He holds an input x ∈ 0,01l n and wishes to broadcast a single message so that each receiver Ri can recover the bit xi. Each Ri has prior side information about x, induced by a directed graph Grain nodes; Ri knows the bits of a; in the positions j | (i,j) is an edge of G .G is known to the sender and to the receivers. We call encoding schemes that achieve this goal INDEXcodes for 0,1 n with side information graph G. In this paper we identify a measure on graphs, the minrank, which exactly characterizes the minimum length of linear and certain types of nonlinear INDEX codes. We show that for natural classes of side information graphs, including directed acyclic graphs, perfect graphs, odd holes, and odd anti-holes, minrank is the optimal length of arbitrary INDEX codes. For arbitrary INDEX codes and arbitrary graphs, we obtain a lower bound in terms of the size of the maximum acyclic induced subgraph. This bound holds even for randomized codes, but has been shown not to be tight. We present a generalized novel upper-bound (and encoding scheme) - in the form of the minimum value of a linear program - for optimal index coding. Our scheme combines the notions of local chromatic number and partial clique covering into a new definition of the local partial clique cover, which outperforms the previous bounds such as the one by Arbabjolfaei and Kim, 2014. Further, we look at the upper bound derived recently by , 2015, and extend their @math - @math (Generalized Interlinked Cycle) construction to @math - @math graphs, which are a generalization of @math -partial cliques. Author(s): Maleki, H; Cadambe, VR; Jafar, SA | Abstract: The index coding problem is studied from an interference alignment perspective providing new results as well as new insights into, and generalizations of, previously known results. An equivalence is established between the capacity of multiple unicast index coding (where each message is desired by exactly one receiver), and groupcast index coding (where a message can be desired by multiple receivers), which settles the heretofore open question of insufficiency of linear codes for the multiple unicast index coding problem by equivalence with groupcast settings, where this question has previously been answered. Necessary and sufficient conditions for the achievability of rate half per message in the index coding problem are shown to be a natural consequence of interference alignment constraints, and generalizations to feasibility of rate 1 (L+1)per message when each destination desires at least L messages, are similarly obtained. Finally, capacity optimal solutions are presented to a series of symmetric index coding problems inspired by the local connectivity and local interference characteristics of wireless networks. The solutions are based on vector linear coding. © 1963-2012 IEEE. The symmetric capacity for index coding problems with @math messages and @math receivers, each demanding a unique message (Single Unicast Index Coding Problem) and having symmetric (with respect to receiver index), neighboring and consecutive side information (SUICP-SNC) have been reported by Maleki, Cadambe and Jafar. For these index coding problems, assuming that the transmissions are error prone, we present optimal length error-correcting index codes for all one-sided SUICP-SNC problems and for some cases of two-sided SUICP-SNC problems. We also discuss construction for these optimal Error Correcting Index Codes. The capacity of symmetric instance of the multiple unicast index coding problem with neighboring antidotes (side-information) with number of messages equal to the number of receivers was given by Maleki In this paper, we construct matrices of size @math over @math such that any @math adjacent rows of the matrix are linearly independent. By using such matrices, we give an optimal scalar linear index codes over @math for the symmetric one-sided antidote problems considered by Maleki for any given number of messages and one-sided antidotes. The constructed codes are independent of field size and hence works over every field. We analyze a generalized index coding problem that allows multiple users to request the same packet. For this problem we introduce a novel coding scheme called partition multicast. Our scheme can be seen as a natural generalization of clique cover for directed index coding problems. Further, partition multicast corresponds to an achievable scheme for the generalized bipartite index coding problem that we introduce in this paper. Our scheme partitions the nodes into groups and solves a multicasting problem within each group. We show that Partition Multicast is optimal for a few families of graphs and generalizes previous achievable schemes, namely directed cycle covers. We also show that finding the best partition is computationally intractable to compute in general. We consider a wireless broadcast station that transmits packets to multiple users. The packet requests for each user may overlap, and some users may already have certain packets. This presents a problem of broadcasting in the presence of side information, and is a generalization of the well-known (and unsolved) index coding problem of information theory. We represent the problem by a bipartite demand graph. Uncoded transmission is optimal if and only if this graph is acyclic. Next, we define a code-constrained capacity region that restricts attention to any prespecified set of coding actions. A dynamic max-weight algorithm that acts over variable length frames is developed. The algorithm allows for random packet arrivals and supports any traffic inside the code-constrained capacity region. A simple set of codes that exploit cycles in the demand graph are shown to be optimal for a class of broadcast relay problems. The index coding problem is a problem of efficient broadcasting with side-information. We look at the uniprior index coding problem, in which the receivers have disjoint side-information symbols and arbitrary demand sets. Previous work has addressed single uniprior index coding, in which each receiver has a single unique side-information symbol. Modeling the uniprior index coding problem as a , we focus on a class of uniprior problems defined on supergraphs. For such problems, we prove upper and lower bounds on the optimal broadcast rate. Using a connection with Eulerian directed graphs, we also show that the upper and lower bounds are equal for a subclass of uniprior problems. We show the NP-hardness of finding the lower bound for uniprior problems on generalized cycles. Finally, we look at a simple extension of the generalized cycle uniprior class for which we give bounds on the optimal rate and show an explicit scheme which achieves the upper bound. Index Coding has received considerable attention recently motivated in part by real-world applications and in part by its connection to Network Coding. The basic setting of Index Coding encodes the problem input as an undirected graph and the fundamental parameter is the broadcast rate @math , the average communication cost per bit for sufficiently long messages (i.e. the non-linear vector capacity). Recent nontrivial bounds on @math were derived from the study of other Index Coding capacities (e.g. the scalar capacity @math ) by Bar- (2006), Lubetzky and Stav (2007) and (2008). However, these indirect bounds shed little light on the behavior of @math : there was no known polynomial-time algorithm for approximating @math in a general network to within a nontrivial (i.e. @math ) factor, and the exact value of @math remained unknown for any graph where Index Coding is nontrivial. Our main contribution is a direct information-theoretic analysis of the broadcast rate @math using linear programs, in contrast to previous approaches that compared @math with graph-theoretic parameters. This allows us to resolve the aforementioned two open questions. We provide a polynomial-time algorithm with a nontrivial approximation ratio for computing @math in a general network along with a polynomial-time decision procedure for recognizing instances with @math . In addition, we pinpoint @math precisely for various classes of graphs (e.g. for various Cayley graphs of cyclic groups) thereby simultaneously improving the previously known upper and lower bounds for these graphs. Via this approach we construct graphs where the difference between @math and its trivial lower bound is linear in the number of vertices and ones where @math is uniformly bounded while its upper bound derived from the naive encoding scheme is polynomially worse. In an index coding with side-information (ICSI) problem there is a sender with a set of independent messages @math and there are receivers @math , each identified with ( @math ), where @math is the set of messages wanted by receiver @math and @math is the set of messages known a priori to receiver @math . We call a ICSI problem to be single-prior if @math In addition, if @math it is called a single-uniprior problem and has been studied in detail by Ong, Ho and Lim OHL . Error Correcting index codes (ECIC) have been studied by Dau, Skachek and Chee DSC and lower and upper bounds on the optimal length of ECICs have been reported. In this paper we show that for single-prior ICSI problems the lower and upper bounds on the optimal ECICs coincide. This leads to construction of optimal length linear ECICs. In this paper, new index coding problems are studied, where each receiver has erroneous side information. Although side information is a crucial part of index coding, the existence of erroneous side information has not been considered yet. We study an index code with receivers that have erroneous side information symbols in the error-free broadcast channel, which is called an index code with side information errors (ICSIE). The encoding and decoding procedures of the ICSIE are proposed, based on the syndrome decoding. Then, we derive the bounds on the optimal codelength of the proposed index code with erroneous side information. Furthermore, we introduce a special graph for the proposed index coding problem, called a @math -cycle whose properties are similar to those of the cycle in the conventional index coding problem. Properties of the ICSIE are also discussed in the @math -cycle and clique. Finally, the proposed ICSIE is generalized to an index code for the scenario having both additive channel errors and side information errors, called a generalized error correcting index code.