Journals: On the Computation of the Capacity Region of the Discrete MAC
E. Calvo Page, D. Pérez Palomar, J. Rodríguez Fonollosa and J. Vidal Manzano


The computation of the channel capacity of discrete memoryless channels is a convex problem that can be
efficiently solved using the Arimoto-Blahut (AB) iterative algorithm. However, the extension of this algorithm to
the computation of capacity regions of multiterminal networks is not straightforward since it gives rise to nonconvex
problems. In this context, the AB algorithm has been only successfully extended to the calculation of the
sum-capacity of the discrete memoryless multiple-access channel (DMAC). Thus, the computation of the whole
capacity region still requires the use of computationally demanding search methods.
In this paper, we first give an alternative reformulation of the capacity region of the DMAC which condenses
all the non-convexities of the problem into a single rank-one constraint. Then, we propose efficient methods to
compute outer and inner bounds on the capacity region by solving a relaxed version of the problem and projecting
its solution onto the original feasible set. Targeting numerical results, we first take a randomization approach.
Focusing on analytical results, we study projection via minimum divergence, which amounts to the marginalization
of the relaxed solution. In this case we derive sufficient conditions and necessary and sufficient conditions for the
bounds to be tight. Furthermore, we are able to show that the class of channels for which the marginalization
bounds match exactly the capacity region includes all the two-user binary-input deterministic DMACs as well as
other non-deterministic channels. In general, however, both methods are able to compute very tight bounds as
shown for various examples.

Full document

©UPC Universitat Politècnica de Catalunya
Signal Processing and Communications group
Powered by Joomla!.