Asymptotic Error Free Partitioning Over Noisy Boolean Multiaccess Channels

DOI10.1109/TIT.2015.2477399MaRDI QIDQ2977126zbMATH OpenFDO

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

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.06452

Channel models (including quantum) in information and communication theory (94A40)

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 g e q (C_{1} + x i_{1}) l o g N

, where

C_{1}

and

x i_{1}

are positive constants (independent of

N

), and

x i_{1}

can be arbitrary small, the partition problem can be solved with error probability

P_{e}^{(N)} o 0

, for large

N

. Under the same scheme, we also bound

T

from the other direction, establishing that, for any

T l e q (C_{2} - x i_{2}) l o g N

, the error probability

P_{e}^{(N)} o 1

for large

N

; again

C_{2}

and

x i_{2}

are constants and

x i_{2}

can be arbitrarily small. These bounds on the number of steps are lower than the tight achievable lower-bound in terms of

T g e q (C_{g} + x i) l o g 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.

Cited in

(1)

Partition Information and its Transmission Over Boolean Multi-Access Channels

This page was built for publication: Asymptotic Error Free Partitioning Over Noisy Boolean Multiaccess Channels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977126)