Coded Acknowledgement with Random Subspaces

This paper studies efficient acknowledgement strategies for massive random access, where a random subset of ℓ users from a large pool of n potential users seek connectivity from the base-station (BS); the BS detects k ≤ ℓ of these users and wishes to communicate a positive acknowledgement message ACK to the k detected users and a negative acknowledgement NACK to the ℓ−k remaining users whose identities are not known to the BS. Assuming that the BS communicates to the ℓ users by broadcasting a common message, what is the minimum length of the common message that can communicate the ACK and NACK messages up to some allowable per-user error probabilities λ1 and λ2 for the k detected and ℓ−k undetected users, respectively? Assuming that the BS and users have shared common randomness, we use bounds on Gaussian coefficients to show that a common message length of ⌈(1 −λ1)k⌉⌈log(1/λ2)⌉ + 2 bits is sufficient, independent of n. For large n, the achievability is tight to within O(k). We propose a low-complexity coding strategy based on communicating the subspace spanned by the random binary codewords assigned to the users as the acknowledgement message, and show that such a scheme is order optimal in term of the common message length, and has a complexity equivalent to row reducing a k× (k + ⌈log(1/λ2)⌉) binary matrix.