Deterministic broadcast channels fully described by bipartite graphs
The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach
Information Theory
Summary
Broadcast channels let one signal reach many receivers with different outputs. Previous studies used probability to understand how much information can be sent through these channels. This paper shows how to fully describe these channels without relying on probability, using a special kind of network called a bipartite graph. The authors provide exact formulas and methods to find the best way to send messages, which were unknown for most cases before.
What this means in practice
- •For communication system designers: Design communication schemes for multi-receiver deterministic channels using explicit capacity formulas derived from bipartite graph properties.
- •For coding algorithm developers: Create optimal finite-blocklength codes for deterministic broadcast channels with binary linear programming based on the bipartite graph formulation.
Authors
Yiyu Qiu, Wei Chen, H. Vincent Poor
Abstract
The general broadcast channel (BC) has attracted considerable attention because it is a central problem in network or multi-user information theory. The deterministic BC (det-BC), in which both output symbols are functions of the input symbol, plays a vital role in understanding general BCs. In the 1970s, Marton and Pinsker investigated the det-BC independently using a random coding approach and hence quantified its capacity region as functions of the entropy of output symbols. In this paper, we present a purely deterministic and combinatorial treatment of the deterministic BC, which is in contrast to Marton and Pinsker's probabilistic treatment. In particular, we show that each det-BC can be uniquely and completely characterized by a bipartite graph. Based on the bipartite graph model, we present the explicit capacity region of the general det-BC and a deterministic capacity-achieving coding scheme. Specifically, each point on the capacity region boundary is expressed as an explicit function of the degree sequences of the two parts, with boundary coordinates parametrized by the tangent slope. As a result, a closed-form capacity region, which was previously unknown except for special cases such as the Blackwell channel, can be analytically determined, without optimizing the probability distribution of input symbols numerically. For a bipartite graph consisting of multiple isolated subgraphs, there can exist a commonly decodable message while preserving the maximum achievable sum rate, and its achievable rate is explicitly characterized. Finally, the bipartite-graph formulation allows us to construct optimal finite-blocklength coding for the det-BC through binary linear programming.