Academic literature on the topic 'Index coding problem'

The connections between index coding and matroid theory have been well studied in the recent past. Index coding solutions were first connected to multi linear representation of matroids. For vector linear index codes, discrete polymatroids, which can be viewed as a generalization of the matroids, were used. The index coding problem has been generalized recently to accommodate receivers that demand functions of messages and possess functions of messages. In this work we explore the connections between generalized index coding and discrete polymatroids. The conditions that need to be satisfied by a representable discrete polymatroid for a generalized index coding problem to have a vector linear solution is established. From a discrete polymatroid, an index coding problem with coded side information is constructed and it is shown that if the index coding problem has a certain optimal length solution then the discrete polymatroid is representable. If the generalized index coding problem is constructed from a matroid, it is shown that the index coding problem has a binary scalar linear solution of optimal length if and only if the matroid is binary representable.

The index coding problem consists of a system with a server and multiple receivers with different side information and demand sets, connected by a noiseless broadcast channel. The server knows the side information available to the receivers. The objective is to design an encoding scheme that enables all receivers to decode their demanded messages with a minimum number of transmissions, referred to as an index code length. The problem of finding the minimum length index code that enables all receivers to correct a specific number of errors has also been studied. This work establishes a connection between index coding and error-correcting codes with multiple interpretations from the tree construction of nested cyclic codes. The notion of multiple interpretations using nested codes is as follows: different data packets are independently encoded, and then combined by addition and transmitted as a single codeword, minimizing the number of channel uses and offering error protection. The resulting packet can be decoded and interpreted in different ways, increasing the error correction capability, depending on the amount of side information available at each receiver. Motivating applications are network downlink transmissions, information retrieval from datacenters, cache management, and sensor networks.

This paper studies index coding with two senders. In this setup, source messages are distributed among the senders possibly with common messages. In addition, there are multiple receivers, with each receiver having some messages a priori, known as side-information, and requesting one unique message such that each message is requested by only one receiver. Index coding in this setup is called two-sender unicast index coding (TSUIC). The main goal is to find the shortest aggregate normalized codelength, which is expressed as the optimal broadcast rate. In this work, firstly, for a given TSUIC problem, we form three independent sub-problems each consisting of the only subset of the messages, based on whether the messages are available only in one of the senders or in both senders. Then, we express the optimal broadcast rate of the TSUIC problem as a function of the optimal broadcast rates of those independent sub-problems. In this way, we discover the structural characteristics of TSUIC. For the proofs of our results, we utilize confusion graphs and coding techniques used in single-sender index coding. To adapt the confusion graph technique in TSUIC, we introduce a new graph-coloring approach that is different from the normal graph coloring, which we call two-sender graph coloring, and propose a way of grouping the vertices to analyze the number of colors used. We further determine a class of TSUIC instances where a certain type of side-information can be removed without affecting their optimal broadcast rates. Finally, we generalize the results of a class of TSUIC problems to multiple senders.

In theindex codingproblem, introduced by Birk and Kol (INFOCOM, 1998), the goal is to broadcast ann-bit word tonreceivers (one bit per receiver), where the receivers haveside informationrepresented by a graphG. The objective is to minimize the length of a codeword sent to all receivers which allows each receiver to learn its bit. Forlinearindex coding, the minimum possible length is known to be equal to a graph parameter calledminrank(Bar-Yossef, Birk, Jayram and Kol,IEEE Trans. Inform. Theory, 2011).We show a polynomial-time algorithm that, given ann-vertex graphGwith minrankk, finds a linear index code forGof lengthÕ(nf(k)), wheref(k) depends only onk. For example, fork= 3 we obtainf(3) ≈ 0.2574. Our algorithm employs a semidefinite program (SDP) introduced by Karger, Motwani and Sudan for graph colouring (J. Assoc. Comput. Mach., 1998) and its refined analysis due to Arora, Chlamtac and Charikar (STOC, 2006). Since the SDP we use is not a relaxation of the minimization problem we consider, a crucial component of our analysis is anupper boundon the objective value of the SDP in terms of the minrank.At the heart of our analysis lies a combinatorial result which may be of independent interest. Namely, we show an exact expression for the maximum possible value of the Lovász ϑ-function of a graph with minrankk. This yields a tight gap between two classical upper bounds on the Shannon capacity of a graph.

The Comparative Manifesto Project (CMP) provides the only time series of estimated party policy positions in political science and has been extensively used in a wide variety of applications. Recent work (e.g., Benoit, Laver, and Mikhaylov 2009; Klingemann et al. 2006) focuses on nonsystematic sources of error in these estimates that arise from the text generation process. Our concern here, by contrast, is with error that arises during the text coding process since nearly all manifestos are coded only once by a single coder. First, we discuss reliability and misclassification in the context of hand-coded content analysis methods. Second, we report results of a coding experiment that used trained human coders to code sample manifestos provided by the CMP, allowing us to estimate the reliability of both coders and coding categories. Third, we compare our test codings to the published CMP “gold standard” codings of the test documents to assess accuracy and produce empirical estimates of a misclassification matrix for each coding category. Finally, we demonstrate the effect of coding misclassification on the CMP's most widely used index, its left-right scale. Our findings indicate that misclassification is a serious and systemic problem with the current CMP data set and coding process, suggesting the CMP scheme should be significantly simplified to address reliability issues.

Multiple-VQ methods generate multiple independent codebooks to compress an image by using a neural network algorithm. In the image restoration, the methods restore low quality images from the multiple codebooks, and then combine the low quality ones into a high quality one. However, the naive implementation of these methods increases the compressed data size too much. This paper proposes two improving techniques to this problem: “index inference” and “ranking based index coding.” It is shown that index inference and ranking based index coding are effective for smaller and larger codebook sizes, respectively.

The receiver of OFDM with Index Modulation (OFDM-IM) usually adopts a Log Likelihood Ratio (LLR) detection algorithm based on the activation state of subcarriers. However, the LLR detection algorithm will cause detection errors in subcarrier activation pattern (SAP) or get illegal SAP. Consequently, further errors occur in demodulation, increasing the bit error rate (BER). To solve this problem, we propose the protection scheme of subcarrier index aided by LDPC coding, which reduces the SAP detection errors by encoding the index information bits. On the receiver, the LDPC Coding Aided (LA) detection algorithm is designed, and the formula of LLR of index information bits is derived in detail. Monte Carlo simulation is carried out over multi-path fading channel by MATLAB software. The results show that under the condition that the spectrum efficiency is not lower than the classical OFDM-IM scheme, the proposed protection scheme can obtain a gain of about 5~9 dB when the BER is 10-4, effectively improving the BER performance of OFDM-IM scheme.

SummaryObjectives: The International Classification of Diseases and Related Health Problems, 10th Revision, Thai Modification (ICD-10-TM) ontology is a knowledge base created from the Thai modification of the World Health Organization International Classification of Diseases and Related Health Problems, 10th Revision. The objectives of this research were to develop the ICD-10-TM ontology as a knowledge base for use in a semi-automated ICD coding system and to test the usability of this system.Methods: ICD concepts and relations were identified from a tabular list and alphabetical indexes. An ICD-10-TM ontology was defined in the resource description framework (RDF), notation-3 (N3) format. All ICD-10-TM contents available as Microsoft Word documents were transformed into N3 format using Python scripts. Final RDF files were validated by ICD experts. The ontology was implemented as a knowledge base by using a novel semi-automated ICD coding system. Evaluation of usability was performed by a survey of forty volunteer users.Results: The ICD-10-TM ontology consists of two main knowledge bases (a tabular list knowledge base and an index knowledge base) containing a total of 309,985 concepts and 162,092 relations. The tabular list knowledge base can be divided into an upper level ontology, which defines hierarchical relationships between 22 ICD chapters, and a lower level ontology which defines relations between chapters, blocks, categories, rubrics and basic elements (include, exclude, synonym etc.)of the ICD tabular list. The index knowledge base describes relations between keywords, modifiers in general format and a table format of the ICD index. In this research, the creation of an ICD index ontology revealed interesting findings on problems with the current ICD index structure. One problem with the current structure is that it defines conditions that complicate pregnancy and perinatal conditions on the same hierarchical level as organ system diseases. This could mislead a coding algorithm into a wrong selection of ICD code. To prevent these coding errors by an algorithm, the ICD-10-TM index structure was modified by raising conditions complicating pregnancy and perinatal conditions into a higher hierarchical level of the index knowledge base. The modified ICD-10-TM ontology was implemented as a knowledge base in semi-automated ICD-10-TM coding software. A survey of users of the software revealed a high percentage of correct results obtained from ontology searches (> 95%) and user satisfaction on the usability of the ontology.Conclusion: The ICD-10-TM ontology is the first ICD-10 ontology with a comprehensive description of all concepts and relations in an ICD-10-TM tabular list and alphabetical index. A researcher developing an automated ICD coding system should be aware of The ICD index structure and the complexity of coding processes. These coding systems are not a word matching process. ICD-10 ontology should be used as a knowledge base in The ICD coding software. It can be used to facilitate successful implementation of ICD in developing countries, especially in those countries which do not have an adequate number of competent ICD coders.

An instance of the multi-sender index coding problem consists of a set of senders collectively having all the messages demanded by a set of receivers. Each receiver knows a subset of messages a priori, called its side information, and receives all the transmissions from all the senders. Each sender avails the knowledge of the side information and the demands of all the receivers, and the knowledge of messages available with other senders, to broadcast coded messages called an index code. Transmissions of each sender are orthogonal in time with those of others. The objective is to minimize the total number of coded transmissions, such that each receiver can decode its demands. The multi-sender index coding problem is related to many problems of practical interest such as multi-source satellite communication, multi-source coded caching, coded cooperative data exchange and distributed computing among many others. The multi-sender index coding problem is NP-hard and the optimal codelength is known only for a few special classes of the problem. In a prior work (V. K. Gummadi, A. Choudhary, and P. Krishnan, \Index Coding : Rank-Invariant Extensions," arXiv preprint arXiv:1704.00687 [cs.IT], 3 Apr, 2017), some classes of single-sender index coding problems called rank invariant extensions were identified. Optimal scalar linear codes of any problem belonging to this class were obtained using those of a particular subproblem. In another line of research ( C. Thapa, L. Ong, S. J. Johnson, and M. Li, \Structural Characteristics of Two-Sender Index Coding," Entropy 21, no. 6, 615, 2019), optimal codes for some classes of the two-sender index coding problem were constructed using those of its subproblems. In this work, we identify some classes of single-sender index coding problems, and construct optimal scalar linear codes for the same using scalar linear codes of some subproblems. All the scalar linear codes need not be optimal for the constructed codes to be scalar linear optimal. This result generalizes the notion of rank invariant extensions and solves many classes of single-sender problems for optimal scalar linear codes. This result is also applied to construct optimal scalar linear codes for some classes of the two-sender index coding problem. Moreover, all unsolved problems belonging to a fundamental class of the two-sender problem are solved for optimal broadcast rates. Optimal linear codelength of error correcting index codes are established for some classes of single-sender problems and multisender problems using related parameters of some subproblems. Weakly secure index codes are constructed for some classes of the two-sender problem using those of its single-sender problems. Many results presented in this thesis can be extended to solve many multi-sender index coding problems. We first introduce the notion of joint extensions of any finite number of single sender groupcast index coding problems which generalizes the notion of rank invariant extensions. A class of joint extensions is identi fied, where optimal scalar linear codes are constructed using those of the subproblems. This result is used to construct optimal scalar linear codes for some classes of the two-sender groupcast index coding problem. Another class of joint extensions referred to as base induced joint extensions is identi fied, where a problem called the base problem dictates the relations among the subproblems in the jointly extended problem. We present an algorithm to construct scalar linear codes using those of the subproblems, for any base induced joint extension. We observe that the algorithm constructs optimal scalar linear codes for a particular class of base induced joint extensions. An index coding problem is said to be unicast if each message is demanded by only one receiver. We establish the optimal broadcast rate (total number of transmitted bits per message bit as message length tends to in finity) for all the unsolved problems belonging to a fundamental class of the two-sender unicast index coding problem introduced by Thapa et al. Related code constructions with finite length messages make use of optimal codes of the single-sender subproblems. The established optimal broadcast rates take into account both linear and nonlinear encoding schemes at the senders. The proof techniques employed are used to construct optimal linear codes for some classes of multi-sender unicast problems We then consider the problem of multi-sender groupcast index coding with error correction, where any receiver receives atmost a speci fied number of coded symbols erroneously. A parameter called the generalized independence number is established for base induced joint extensions and rank invariant extensions in terms of those of its subproblems. Using this result, optimal length of linear error correcting index codes are provided for some classes of the single-sender index coding problem. These results are used to construct optimal linear error correcting index codes for some classes of the multi-sender groupcast index coding problem. We then consider the problem of index coding with weak security which consists of an adversary having some messages as side information. An index code is said to be weakly secure if the adversary can not obtain any information about any single message which it does not have using the index code and its side information. We show that the codes constructed for some classes of the two-sender groupcast index coding problem, using weakly secure codes of single-sender subproblems are also weakly secure. A subclass of the two-sender groupcast problem is identi fied where the constructed codes are optimal. Finally, we consider the problem of broadcasting with noisy side information introduced in S. Ghosh, and L. Natarajan, \Linear codes for broadcasting with noisy side information," arXiv preprint arXiv:1801.02868v1 [cs.IT], 9 Jan, 2018. Any wireless channel experiences outage due to fading. Some receivers erroneously decode their demanded messages during the fi rst round of transmissions from a sender. The sender can now avail the knowledge of the maximum number of erroneously decoded messages at any receiver (known as its error threshold), to reduce the number of retransmissions. The receivers make use of the erroneously decoded messages as side information (which is thus noisy) to decode their demands in the retransmission phase. We consider the problem with different error thresholds at different receivers and generalize a field-size independent encoding scheme given for the case with the same error threshold at every receiver. We show that this scheme saves at least two transmissions for a particular class of the problem with different error thresholds. We then extend the equivalence established between the problem of broadcasting with noisy side information and the index coding problem to the case with different error thresholds. We use this result to obtain optimal linear codes for a special class of the problem.

In an index coding problem, there is a sender which has a set of messages and there are multiple receivers demanding possibly different subsets of these messages and possessing some other subsets of these messages as side-information. The goal for the sender is to meet the demands of the receivers in minimum number of transmissions using which along with the side-information every receiver can get what it demands. There have been many extensions and generalizations to the index coding prob- lem in the literature. One such generalization is to the case when the transmissions are subject to errors. Lower and upper bounds on the optimal number of transmis- sions required to correct a speci ed number of errors have been established. In this work, optimal linear error correcting index codes are obtained for three classes of index coding problems namely single-prior index coding problems, single unicast index coding problems with symmetric neighboring consecutive side-information and index coding problems with min-rank at most two. In another generalization of index coding problem, namely Generalized Index Coding (GIC) problem, linear combination of the messages can be demanded and the side-information at the receivers may also be some linear combinations of messages. For a particular class of GIC problems we discuss a construction of the optimal scalar linear index codes. For this class of GIC problems, the optimal linear error correcting index codes are also constructed. In a coded caching problem, a single server is connected to a set of users through a shared bottleneck link, which is assumed to be error-free. A coded caching problem involves two phases. The placement or prefetching phase is done during non-peak hours during which all the users ll their local cache with the portions of the les available. During the delivery phase, each user requests a le and the server delivers coded transmissions to meet the demands. During the placement, if the parts of the les are stored in the cache without coding, the prefetching is termed as uncoded prefetching. If coding is done among the parts of the les during the placement, then the prefetching is referred to as coded prefetching. When multiple users share a common cache, the scheme is referred to as the shared cache scheme. The centralized schemes involve a central coordi- nation during the placement phase. The schemes for which a central coordination is not required during the placement phase are called the decentralized schemes. In our work, the links between the server and the users are assumed to be error prone. A new delivery scheme is required to meet the demands of each user even after receiving a nite number of transmissions in error in the presence of erro- neous portions of les in the cache. The minimum average rate and the minimum peak rate for this problem are characterized. The optimal linear error correcting delivery schemes are proposed for various classes of coded caching problems in the absence of prefetching errors. The classes of problems which we considered include centralized schemes like the symmetric batch prefetching and the shared cache scheme, which involve uncoded prefetching, the Chen, Fan, Letaif scheme and the Jesus Vilardebo scheme, which involve coded prefetching. We have also considered decentralized schemes like the Ali-Niesen decentralized Scheme and the Least Recently Sent (LRS) online coded caching scheme. We also prove the optimality of the LRS online coded caching scheme using results from index cod- ing. Furthermore, alternate proofs for the optimality are given for coded caching problems with the symmetric batch prefetching and the Ali-Niesen decentralized prefetching. In addition to this, lower bounds are established for the optimal rate required when there are prefetching errors in the symmetric batch prefetching.

An index coding problem, comprises a transmitter that has a set of independent messages and a set of receivers. Each receiver knows a subset of messages, called its side-information, and demands another subset of messages, called its want-set. The transmitter can take cognizance of the side-information of the receivers and broadcast coded messages, called the index code, over a noiseless channel. The objective is to minimize the number of coded transmissions, called the length of the index code, such that each receiver can decode its wanted messages using its sideinformation and the coded messages. An index coding problem is single unicast if the want-sets of the receivers are disjoint and the cardinality of want-set of every receiver is one. In a single unicast index coding problem, we have equal number of messages and receivers. A single unicast index coding problem is called symmetric if the side-information of the receivers is symmetric with respect to their wanted message. Motivated with topological interference management problems, Maleki, Cadambe and Jafar studied the symmetric index coding problems. This thesis deals with the symmetric index coding problems and present some interesting results. In this work, we construct binary matrices of size m × n such that any n adjacent rows of the matrix are linearly independent over every finite field for any arbitrary positive integers m and n (m ≥ n). We call these matrices as Adjacency Independent Row (AIR) matrices. We derive combinatorial properties of AIR matrices. We use AIR matrices to construct optimal or near-optimal index codes for various symmetric settings. By using the combinatorial properties of AIR matrices, we give a simple low-complexity decoding procedure for the constructed optimal or near-optimal index codes. By using this decoding procedure, we give a reduced set of side-information required by each receiver to decode its wanted message. We also derive bounds on the broadcast rate of two well known classes of symmetric settings and derive the capacity for some special cases of the same. The interlinked cycle (IC) structure, that generalizes cycles and cliques was defined by Thapa, Ong and Johnson. Interlinked-cycle-cover (ICC) scheme that leverages IC structures as side-information graphs to construct scalar linear index codes was proposed. A class of infinitely many digraphs, where the proposed scalar linear codes based on ICC scheme are optimal were characterized. Thapa et. al. conjectured that for any IC structure, the ICC scheme is optimal. It was also conjectured that for any digraph, the ICC scheme performs at least as well as the partial-clique-cover scheme. In this work, we disprove both the conjectures. We provide an addition to the class of IC structures by providing optimal length index codes for IC structures with one cycle among non-inner vertex set.

Network coding was introduced as a means to increase throughput in communication networks when compared to routing. Network coding can be used not only to communicate messages from some nodes in the network to other nodes but are also useful when some nodes in a network are interested in computing some functions of information generated at some other nodes. Such a situation arises in sensor networks. In this work, we study three problems in network coding. First, we consider the functional source coding with side information problem wherein there is one source that generates a set of messages and one receiver which knows some functions of source messages and demands some other functions of source messages. Cognizant of the receiver's side information, the source aims to satisfy the demands of the receiver by making minimum number of coded transmissions over a noiseless channel. We use row-Latin rectangles to obtain optimal codes for a given functional source coding with side information problem. Next, we consider the multiple receiver extension of this problem, called the functional index coding problem, in which there are multiple receivers, each knowing and demanding disjoint sets of functions of source messages. The source broadcasts coded messages, called a functional index code, over a noiseless channel. For a given functional index coding problem, the restrictions the demands of the receivers pose on the code are represented using the generalized exclusive laws and it is shown that a code can be obtained using the confusion graph constructed using these laws. We present bounds on the size of an optimal code based on the parameters of the confusion graph. For the case of noisy broadcast channel, we provide a necessary and sufficient condition that a code must satisfy for correct decoding of desired functions at each receiver and obtain a lower bound on the length of an error-correcting functional index code. In the second problem, we explore relation between network function computation problems and functional index coding and Metroid representation problems. In a network computation problem, the demands of the sink nodes in a directed acyclic multichip network include functions of the source messages. We show that any network computation problem can be converted into a functional index coding problem and vice versa. We prove that a network code that satisfies all the sink demands in a network computation problem exists if and only if its corresponding functional index coding problem admits a functional index code of a specific length. Next, we establish a relation between network computation problems and representable mastoids. We show that a network computation problem in which the sinks demand linear functions of source messages admits a scalar linear solution if and only if it is matricidal with respect to a representable Metroid whose representation fulfils certain constraints dictated by the network computation problem. Finally, we study the usage of the sum-product (SP) algorithm for decoding network codes. Though lot of methods to obtain network codes exist, the decoding procedure and complexity have not received much attention. We propose a SP algorithm based decoder for network codes which can be used to decode both linear and nonlinear network codes. We pose the decoding problem at a sink node as a marginalize a product function (MPF) problem over the Boolean smearing and use the SP algorithm on a suitably constructed factor graph to perform decoding. We propose and demonstrate the usage of trace back to reduce the number of operations required to perform SP decoding. The computational complexity of performing SP decoding with and without trace back is obtained. For nonlinear network codes, we define fast decidability of a network code at sinks that demand all the source messages and identify a sufficient condition for the same. Next, for network function computation problems, we present an MPF formulation for function computation at a sink node and use the SP algorithm to obtain the value of the demanded function.

Network coding was introduced as a means to increase throughput in communication networks when compared to routing. Network coding can be used not only to communicate messages from some nodes in the network to other nodes but are also useful when some nodes in a network are interested in computing some functions of information generated at some other nodes. Such a situation arises in sensor networks. In this work, we study three problems in network coding. First, we consider the functional source coding with side information problem wherein there is one source that generates a set of messages and one receiver which knows some functions of source messages and demands some other functions of source messages. Cognizant of the receiver's side information, the source aims to satisfy the demands of the receiver by making minimum number of coded transmissions over a noiseless channel. We use row-Latin rectangles to obtain optimal codes for a given functional source coding with side information problem. Next, we consider the multiple receiver extension of this problem, called the functional index coding problem, in which there are multiple receivers, each knowing and demanding disjoint sets of functions of source messages. The source broadcasts coded messages, called a functional index code, over a noiseless channel. For a given functional index coding problem, the restrictions the demands of the receivers pose on the code are represented using the generalized exclusive laws and it is shown that a code can be obtained using the confusion graph constructed using these laws. We present bounds on the size of an optimal code based on the parameters of the confusion graph. For the case of noisy broadcast channel, we provide a necessary and sufficient condition that a code must satisfy for correct decoding of desired functions at each receiver and obtain a lower bound on the length of an error-correcting functional index code. In the second problem, we explore relation between network function computation problems and functional index coding and Metroid representation problems. In a network computation problem, the demands of the sink nodes in a directed acyclic multichip network include functions of the source messages. We show that any network computation problem can be converted into a functional index coding problem and vice versa. We prove that a network code that satisfies all the sink demands in a network computation problem exists if and only if its corresponding functional index coding problem admits a functional index code of a specific length. Next, we establish a relation between network computation problems and representable mastoids. We show that a network computation problem in which the sinks demand linear functions of source messages admits a scalar linear solution if and only if it is matricidal with respect to a representable Metroid whose representation fulfils certain constraints dictated by the network computation problem. Finally, we study the usage of the sum-product (SP) algorithm for decoding network codes. Though lot of methods to obtain network codes exist, the decoding procedure and complexity have not received much attention. We propose a SP algorithm based decoder for network codes which can be used to decode both linear and nonlinear network codes. We pose the decoding problem at a sink node as a marginalize a product function (MPF) problem over the Boolean smearing and use the SP algorithm on a suitably constructed factor graph to perform decoding. We propose and demonstrate the usage of trace back to reduce the number of operations required to perform SP decoding. The computational complexity of performing SP decoding with and without trace back is obtained. For nonlinear network codes, we define fast decidability of a network code at sinks that demand all the source messages and identify a sufficient condition for the same. Next, for network function computation problems, we present an MPF formulation for function computation at a sink node and use the SP algorithm to obtain the value of the demanded function.