Partition Information and its Transmission Over Boolean Multi-Access Channels

Shuhang Wu, Shuangqing Wei, Yue Wang, Ramachandran Vaidyanathan, Jian Yuan

Abstract

In this paper, we propose a novel reservation system to study partition information and its transmission over a noise-free Boolean multiaccess channel. The objective of transmission is not to restore the message, but to partition active users into distinct groups so that they can, subsequently, transmit their messages without collision. We first calculate (by mutual information) the amount of information needed for the partitioning without channel effects, and then propose two different coding schemes to obtain achievable transmission rates over the channel. The first one is the brute force method, where the codebook design is based on centralized source coding; the second method uses random coding, where the codebook is generated randomly and optimal Bayesian decoding is employed to reconstruct the partition. Both methods shed light on the internal structure of the partition problem. A novel formulation is proposed for the random coding scheme, in which a sequence of channel operations and interactions induces a hypergraph. The formulation intuitively describes the transmitted information in terms of a strong coloring of this hypergraph. An extended Fibonacci structure is constructed for the simple, but nontrivial, case with two active users. A comparison between these methods and group testing is conducted to demonstrate the potential of our approaches.

Introduction

In distributed wireless networks, the "collision problem" remains a fundamental bottleneck. When multiple users attempt to access a shared Boolean multi-access channel (MAC) simultaneously, their signals interfere, often requiring a reservation phase to coordinate access. Traditionally, this coordination relies on group testing, a method designed to identify the exact identities of all active users.

However, this research posits that full identification is often an unnecessary overhead. If the goal is simply to ensure that active users can eventually transmit without colliding, the system only needs to partition them into distinct groups or time slots. By shifting the objective from identification to partitioning, we can significantly reduce the communication overhead required during the reservation phase.

The Concept of Partition Information

To establish a theoretical foundation, we first define "partition information." Using a constrained mutual information framework, we calculate the minimum number of bits required to successfully partition active users. This theoretical baseline confirms that partitioning requires strictly less information than the full identification required by group testing. This insight suggests that the capacity of a reservation system can be expanded if we relax the requirement of knowing who is transmitting, focusing instead on how to separate them.

Proposed Coding Schemes

We explore two primary methodologies for achieving this partitioning over a noise-free Boolean MAC:

1. The Brute Force Method

This approach is inspired by centralized source coding. It involves generating a codebook of all possible valid partitions. The channel is then used to exhaustively verify these partitions. While this method is highly efficient for a small, fixed number of active users ($K$), achieving an arbitrarily low error probability in $O(\log N)$ time slots, it scales poorly as $K$ increases due to the exponential growth of the partition space.

2. Random Coding and MAP Decoding

In this decentralized approach, users transmit based on a Bernoulli distribution (effectively a coin flip). The decoder then employs Maximum A Posteriori (MAP) decoding to infer the most likely partition based on the channel feedback. This method is more practical for distributed systems where centralized coordination is difficult.

Hypergraph Formulation and the Fibonacci Connection

A key contribution of this work is the translation of the random coding scheme into a hypergraph problem. In this model:

  • Nodes represent users.
  • Hyperedges represent possible sets of active users.
  • Channel Feedback (such as a '0' indicating no transmission) acts as an operator that prunes nodes or cliques from the graph.

Successfully partitioning the users is mathematically equivalent to finding a $K$-strong coloring of the resulting hypergraph. For the specific case of two active users ($K=2$), we identified an "extended Fibonacci structure." The probability of successfully isolating two users is tied to the probability of avoiding consecutive zeros in a random binary sequence, a property governed by Fibonacci numbers.

Key Results and Comparison

Our analysis demonstrates that partitioning is fundamentally more efficient than identification:

  • Achievable Rates: For the $K=2$ case, the achievable transmission rate for partitioning ($S_c \approx 0.5896$) is strictly higher than the theoretical capacity of group testing ($S_{cg} = 0.5$).
  • Error Decay: While the random coding method exhibits a strict threshold effect, the brute force method avoids these thresholds for fixed $K$, providing a robust alternative for specific network configurations.

Conclusion and Future Work

By reframing the collision resolution problem as a partition problem rather than an identification problem, we uncover new efficiencies in multi-access channels. The hypergraph coloring formulation provides a powerful tool for visualizing how channel feedback reduces uncertainty.

Future research will focus on extending the random coding analysis to cases where $K > 2$, deriving formal converse bounds to establish the absolute maximum capacity of partition information, and adapting the framework to handle noisy channels where feedback may be unreliable.

Summary updated

Abstract

In this paper, we propose a novel reservation system to study partition information and its transmission over a noise-free Boolean multiaccess channel. The objective of transmission is not to restore the message, but to partition active users into distinct groups so that they can, subsequently, transmit their messages without collision. We first calculate (by mutual information) the amount of information needed for the partitioning without channel effects, and then propose two different coding schemes to obtain achievable transmission rates over the channel. The first one is the brute force method, where the codebook design is based on centralized source coding; the second method uses random coding, where the codebook is generated randomly and optimal Bayesian decoding is employed to reconstruct the partition. Both methods shed light on the internal structure of the partition problem. A novel formulation is proposed for the random coding scheme, in which a sequence of channel operations and interactions induces a hypergraph. The formulation intuitively describes the transmitted information in terms of a strong coloring of this hypergraph. An extended Fibonacci structure is constructed for the simple, but nontrivial, case with two active users. A comparison between these methods and group testing is conducted to demonstrate the potential of our approaches.
BibTeX
@article{wu2014partition,
  author = {Shuhang Wu and Shuangqing Wei and Yue Wang and Ramachandran Vaidyanathan and Jian Yuan},
  title = {{Partition Information and its Transmission Over Boolean Multi-Access Channels}},
  journal = {IEEE Transactions on Information Theory},
  year = {2014},
  doi = {10.1109/tit.2014.2375211},
}
Figure