Permutation Capacity Region of Adder Multiple-Access Channels

William Lu, Anuran Makur

Abstract

This paper provides the first information-theoretic characterization of the "permutation capacity region" for a multi-user network. We investigate the Permutation Adder Multiple-Access Channel (PAMAC), where multiple signals are summed and then randomly shuffled. We demonstrate that even under complete loss of ordering, a total communication rate of $d(p-1)/2$ (where $d$ is the number of users and $p$ is the alphabet size) is achievable. This is accomplished through clever encoding schemes that "tag" packets to recover their original timing information and robust statistical estimation of message parameters.

Introduction

In traditional communication theory, the sequence and timing of packets are fundamental to information transfer. However, many modern systems—such as DNA-based data storage, multipath routed networks, and mobile ad-hoc networks—behave as permutation channels, where packets arrive in a random order.

This work tackles the Permutation Adder Multiple-Access Channel (PAMAC). In this model, $d$ senders transmit signals simultaneously. These signals are combined via an adder (representing physical layer interference) and then passed through a random shuffle block. The receiver's task is twofold: disentangle the combined signals and reconstruct the information despite the loss of temporal order.

The system model for the Permutation Adder Multiple-Access Channel (PAMAC), showing encoders, an adder, a Discrete Memoryless Channel (DMC), and a random permutation block.

Achievability Strategies

The authors employ two distinct strategies to prove the capacity region:

1. Root Stability of Probability Generating Functions (PGFs)

For binary channels, the probability distribution of the output can be treated as the coefficients of a PGF. Since the output is the sum of independent Bernoulli trials, the roots of this polynomial correspond to the senders' message parameters. By applying the Bauer-Fike theorem from matrix perturbation theory, the authors prove that these roots are stable enough to be recovered from the empirical distribution of the shuffled output, even in the presence of sampling noise.

Visualization of message parameters (theta) for different senders distributed across a unit interval, facilitating recovery through root stability analysis.

2. Segmentation and Time-Sharing

To achieve the full capacity region for $p$-ary alphabets, the authors develop a "segmentation" technique. The transmission block is divided into $d$ segments. While one sender is "active" (sending information), the other "passive" senders transmit hard-coded constants. These constants act as a domain shift, effectively tagging the packets. Even after the packets are shuffled, the receiver can infer which segment a packet originally belonged to based on its value, effectively "undoing" the permutation.

Key Results

  • Capacity Region: The permutation capacity region $C_{perm}$ is the simplex consisting of all rate $d$-tuples $(R_1, \dots, R_d)$ such that their sum is less than or equal to $d(p-1)/2$.
  • Binary PAMAC: For the binary case ($p=2$), the sum-rate is $d/2$. This is a tight bound, establishing the exact fundamental limit of this channel.
  • Computational Efficiency: The proposed randomized encoders and decoders have polynomial time complexity $O(n)$, making the theoretical limits practically attainable.

Conclusion and Future Work

This research establishes that permutation is not fatal to communication. By using the alphabet itself to encode position or by leveraging the stability of PGF roots, users can coordinate to achieve significant throughput. Future work will explore "high-density" networks where the number of users $d$ scales with the blocklength $n$, as well as more general combining functions beyond the simple adder model.

Summary updated

BibTeX
@article{lu2024permutation,
  author = {William Lu and Anuran Makur},
  title = {{Permutation Capacity Region of Adder Multiple-Access Channels}},
  journal = {IEEE Trans. Information Theory},
  year = {2024},
  doi = {10.1109/tit.2024.3350436},
}
Figure