151. Asymptotic Error Free Partitioning Over Noisy Boolean Multiaccess Channels
- Author
-
Ramachandran Vaidyanathan, Shuhang Wu, Yue Wang, Jian Yuan, and Shuangqing Wei
- Subjects
FOS: Computer and information sciences ,Computer Science - Information Theory ,Information Theory (cs.IT) ,Partition problem ,Block (permutation group theory) ,Library and Information Sciences ,Binary logarithm ,Upper and lower bounds ,Computer Science Applications ,Combinatorics ,Simple (abstract algebra) ,Scheme (mathematics) ,Decoding methods ,Information Systems ,Communication channel ,Mathematics - 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\geq (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 \leq (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 \geq (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., Comment: This paper was submitted in June 2014 to IEEE Transactions on Information Theory, and is under review now
- Published
- 2015