Broadcast Function Computation with Complementary Side Information
Jithin Ravi, Bikash Kumar Dey · 2016
We consider the function computation problem in a three node network with one encoder and two decoders. The encoder has access to two correlated sources X and Y. The encoder encodes Xnand Yninto a message which is given to two decoders. Decoder 1 and decoder 2 have access to X and Y respectively, and they want to compute two functions f (X, Y) and g(X, Y) respectively using the encoded message and their respective side information. We want to find the optimum (minimum) encoding rate under the zero error and ϵ-error(i.e. vanishing error) criteria. For the special case of this problem with f (X, Y) = Y and g(X, Y) = X, we show that the ϵ-error optimum rate is also achievable with zero error. This result extends to a more general `complementary delivery index coding' problem with arbitrary number of messages and decoders. For other functions, we show that the cut-set bound is achievable under ϵ-error if X and Y are binary, or if the functions are from a special class of `compatible' functions which includes the case f = g.