While feasibility and obtaining a solution of a given network coding problem are well studied, the decoding procedure and complexity have not garnered much attention. We consider the decoding problem in a network wherein the sources generate multiple messages and the sink nodes demand some or all of the source messages. We consider both linear and non-linear network codes over a finite field and propose to use the sum-product (SP) algorithm over the Boolean semiring for decoding at the sink nodes in order to reduce the computational complexity. We use traceback to further lower the computational cost incurred by SP decoding. For sinks demanding all the messages, we define fast decodability of a network code and identify a sufficient condition for the same.

We consider the functional index coding problem over an error-free broadcast network in which a source generates a set of messages and there are multiple receivers, each holding a set of functions of source messages in its cache, called the Has-set, and demands to know another set of functions of messages, called the Want-set. Cognizant of the receivers' Hassets, the source aims to satisfy the demands of each receiver by making coded transmissions, called a functional index code. The objective is to minimize the number of such transmissions required. The restriction a receiver's demands pose on the code is represented via a constraint called the generalized exclusive law and obtain a code using the confusion graph constructed using these constraints. Bounds on the size of an optimal code based on the parameters of the confusion graph are presented. Next, we consider the case of erroneous transmissions and provide a necessary and sufficient condition that an FIC must satisfy for correct decoding of desired functions at each receiver and obtain a lower bound on the length of an error-correcting FIC.

In contrast to the network coding problem wherein the sinks in a network demand subsets of the source messages, in a network computation problem the sinks demand functions of the source messages. Similarly, in the functional index coding problem, the side information and demands of the clients include disjoint sets of functions of the information messages held by the transmitter instead of disjoint subsets of the messages, as is the case in the conventional index coding problem. It is known that any network coding problem can be transformed into an index coding problem and vice versa. In this work, we establish a similar relationship between network computation problems and a class of functional index coding problems, viz., those in which only the demands of the clients include functions of messages. We show that any network computation problem can be converted into a functional index coding problem wherein some clients demand functions of messages and vice versa. We prove that a solution for a network computation problem exists if and only if a functional index code (of a specific length determined by the network computation problem) for a suitably constructed functional index coding problem exists. Next we show that a functional index coding problem admits a solution of a specified length if and only if a suitably constructed network computation problem admits a solution.

While the capacity, feasibility, and methods to obtain codes for network coding problems are well studied, the decoding procedure and complexity have not garnered much attention. In this paper, we pose the decoding problem at a sink node in a network as a marginalize product function (MPF) problem over the Boolean semiring and use the sum product (SP) algorithm on a suitably constructed factor graph to perform iterative decoding. The number of operations required to perform SP decoding is reduced using traceback. The number of operations required to perform SP decoding with and without traceback is obtained. For nonlinear network codes, we define fast decodability of a network code at sinks demanding all the messages and identify a sufficient condition for the same. Next, we consider the network function computation problem wherein the sink nodes demand a function of the messages. We present an MPF formulation for function computation at the sink nodes and use the SP algorithm to obtain the value of the demanded function. Though the proposed method can be used for decoding both linear and nonlinear network codes, it is advantageous only for the case of nonlinear network codes.

The functional source coding problem in which the receiver side information (Has-set) and demands (Want-set) include functions of source messages is studied using row-Latin rectangle. The source transmits encoded messages, called the functional source code, in order to satisfy the receiver's demands. We obtain a minimum length using the row-Latin rectangle. Next, we consider the case of transmission errors and provide a necessary and sufficient condition that a functional source code must satisfy so that the receiver can correctly decode the values of the functions in its Want-set.