Function Computation Through a Bidirectional Relay

DOI10.1109/TIT.2018.2884490zbMATH Open1427.94057arXiv1609.07923OpenAlexW2963824470WikidataQ128825693 ScholiaQ128825693MaRDI QIDQ4615349FDOQ4615349

Authors: Jithin Ravi, Bikash Kumar Dey 

Publication date: 28 January 2019

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We consider a function computation problem in a three node wireless network. Nodes A and B observe two correlated sources $X$ and $Y$ respectively, and want to compute a function $f(X,Y)$. To achieve this, nodes A and B send messages to a relay node C at rates $R_A$ and $R_B$ respectively. The relay C then broadcasts a message to A and B at rate $R_C$. We allow block coding, and study the achievable region of rate triples under both zero-error and $epsilon$-error. As a preparation, we first consider a broadcast network from the relay to A and B. A and B have side information $X$ and $Y$ respectively. The relay node C observes both $X$ and $Y$ and broadcasts an encoded message to A and B. We want to obtain the optimal broadcast rate such that A and B can recover the function $f(X,Y)$ from the received message and their individual side information $X$ and $Y$ respectively. For this problem, we show equivalence between $epsilon$-error and zero-error computations-- this gives a rate characterization for zero-error computation. As a corollary, this also gives a rate characterization for the relay network under zero-error for a class of functions called {em component-wise one-to-one functions} when the support set of $p_{XY}$ is full. For the relay network, the zero-error rate region for arbitrary functions is characterized in terms of graph coloring of some suitably defined probabilistic graphs. We then give a single-letter inner bound to this rate region. Further, we extend the graph theoretic ideas to address the $epsilon$-error problem and obtain a single-letter inner bound.

Full work available at URL: https://arxiv.org/abs/1609.07923

Mathematics Subject Classification ID

Information theory (general) (94A15) Source coding (94A29)

This page was built for publication: Function Computation Through a Bidirectional Relay

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4615349)