We consider the 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 , and demands to know another set of functions of messages, called the . Cognizant of the receivers' , the source aims to satisfy the demands of each receiver by making coded transmissions, called a . 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 and obtain a code using the 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 this paper, we consider the problem of multifunctional compression with side information. The problem is how we can compress a source X so that the receiver is able to compute some deterministic functions f1(X, Y1), ..., fm(X, Ym), where Yi, 1 ≤ i ≤ m, are available at the receiver as side information. In [1], Wyner and Ziv considered this problem for the special case of m = 1 and f1(X, Y1) = X and derived a rate-distortion function. Yamamoto extended this result in [2] to the case of having one general function f1(X, Y1). Both of these results were in terms of an auxiliary random variable. For the case of zero distortion, in [3], Orlitsky and Roche gave an interpretation of this variable in terms of properties of the characteristic graph which led to a particular coding scheme. This result was extended in [4] by providing an achievable scheme based on colorings of the characteristic graph. In a recent work, reference [5] has considered this problem for a general tree network where intermediate nodes are allowed to perform some computations. These previous works only considered the case where the receiver only wants to compute one function (m=1). Here, we want to consider the case in which the receiver wants to compute several functions with different side information random variables and zero distortion. Our results do not depend on the fact that all functions are desired in one receiver and one can apply them to the case of having several receivers with different desired functions (i.e., functions are separable). We define a new concept named the multi-functional graph entropy which is an extension of the graph entropy defined by Korner in [6]. We show that the minimum achievable rate for this problem is equal to the conditional multi-functional graph entropy of random variable X given side informations. We also propose a coding scheme based on graph colorings to achieve this rate. 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. We consider the remote computation of a function of two sources where one is receiver side information. Specifically, given side information Y , we wish to compute f(X, Y) based on information transmitted by X over a noise-less channel. The goal is to characterize the minimal rate at which X must transmit information to enable the computation of the function f. Recently, Orlitsky and Roche (2001) established that the conditional graph entropy of the characteristic graph of the function is a solution to this problem. Their achievability scheme does not separate "functional coding" from the well understood distributed source coding problem. In this paper, we seek a separation between the functional coding and the coding for correlation. In other words, we want to preprocess X (with respect to f), and then transmit the preprocessed data using a standard Slepian-Wolf coding scheme at the Orlitsky-Roche rate. We establish that a minimum (conditional) entropy coloring of the product of characteristic graphs is asymptotically equal to the conditional graph entropy. This can be seen as a generalization of a result of Korner (1973) which shows that the minimum entropy coloring of product graphs is asymptotically equal to the graph entropy. Thus, graph coloring provides a modular technique to achieve coding gains when the receiver is interested in decoding some function of the source. A sender communicates with a receiver who wishes to reliably evaluate a function of their combined data. We show that if only the sender can transmit, the number of bits required is a conditional entropy of a naturally defined graph. We also determine the number of bits needed when the communicators exchange two messages. Reference is made to the results of rate distortion in evaluating the function of two random variables.