Coded Categorization in Massive Random Access
Ryan Song, Kareem M. Attiah, Wei Yu · 2022 IEEE International Symposium on Information Theory (ISIT) · 2022
This paper considers a massive random access scenario in which a small set of k users out of a large number of n potential users are active at any given time, and a central base-station wishes to send a common message to the active users in order to label them into a finite number of categories. Specifically, given c possible categories, the base-station wishes to send label ℓ to a set of kℓusers, where ℓ ∈ {1, …, c} and $\sum olimits_{\ell = 1}^c {{k_\ell } = k} $. Assuming that n, k1, …, kcare fixed, we ask: what is the minimum rate of the common message that the base-station needs to send so that the correct label is received at each of the k active users? This paper shows that instead of a conventional scheme of listing the indices of the users followed by their labels, which requires a common message rate of $k\left( {\log (n) + H\left( {\frac{{{k_1}}}{k}, \ldots ,\frac{{{k_c}}}{k}} \right)} \right)$ bits, it is possible to construct a fixed-length common message code with a rate of just $kH\left( {\frac{{{k_1}}}{k}, \ldots ,\frac{{{k_c}}}{k}} \right)$ bits plus a term that scales in n as O(log log(n)) for fixed k1, …, kc, where H(•) is the entropy of a probability distribution. If a variable-length code is permitted, the minimum common message rate is characterized as $kH\left( {\frac{{{k_1}}}{k}, \ldots ,\frac{{{k_c}}}{k}} \right) + O(1)$ bits, with no dependence on n. Finally, if k1, …, kcdeviate from the values for which the common message is designed, an additional cost per user equal to a Kullback-Leibler divergence term would be incurred.