Asymptotic Error Free Partitioning over Noisy Boolean Multiaccess Channels

Abstract

In this paper, we consider the problem of partitioning active users in a manner that facilitates multi-access without collision. The setting is of a noisy, synchronous, Boolean, multi-access channel where $K$ active users (out of a total of $N$ users) seek to access. A solution to the partition problem places each of the $N$ users in one of $K$ groups (or blocks) such that no two active nodes are in the same block. We consider a simple, but non-trivial and illustrative case of $K=2$ active users and study the number of steps $T$ used to solve the partition problem. By random coding and a suboptimal decoding scheme, we show that for any $T\ge (C_1+{\xi }_1)\log N$, where $C_1$ and ${\xi }_1$ are positive constants (independent of $N$), and ${\xi }_1$ can be arbitrary small, the partition problem can be solved with error probability $P_e^{(N)}\to 0$, for large $N$. Under the same scheme, we also bound $T$ from the other direction, establishing that, for any $T\le (C_2-{\xi }_2)\log N$, the error probability $P_e^{(N)}\to 1$ for large $N$; again $C_2$ and ${\xi }_2$ are constants and ${\xi }_2$ can be arbitrarily small. These bounds on the number of steps are lower than the tight achievable lower-bound in terms of $T\ge (C_g+\xi )\log N$ for group testing (in which all active users are identified, rather than just partitioned). Thus, partitioning may prove to be a more efficient approach for multi-access than group testing.

This paper was submitted in June 2014 to IEEE Transactions on Information Theory, and is under review now

References in corpus (1)

• Partition Information and its Transmission over Boolean Multi-Access Channels