# On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
## 1 Introduction  
The emergence of the Internet of Things (IoT) has motivated much research interest in designing communication protocols for massive machine-to-machine type communication. This type of communication setup is characterized by a large number of users that transmit simultaneously to the same receiver, while each of these users has a very short message to send. In addition, since IoT sensors are often required to be extremely cheap, the transmission scheme must be as simple as possible, and the design objective is to minimize the energy-per-bit, \(E_{b}/N_{0}\), under a reliability constraint. In [1], [PERSON] defined a communication model capturing the challenges in massive machine-to-machine type communication. In this model, there is an unbounded number of potential users, among which only \(k\) are active at each frame. Each active user has a message of \(B\) bits to transmit, and transmission takes place over a multiple access channel (MAC). Since the number of users is unbounded, the receiver cannot recover the identities of the active users (as this information has unbounded entropy, assuming all potential users are equally likely to transmit, and the channel has bounded capacity). Thus, the receiver's goal is to recover a list of \(k\) messages that contains \"most\" of the transmitted messages, without identifying the sender of each message. This setup is therefore called _the unsourced random access channel_[2]. The performance of a communication scheme over the unsourced random access channel is assessed by the tradeoff it achieves between energy-per-bit and the per-user probability of error (PUPE), which is the probability that the message transmitted by an active user did not enter the list of messages the receiver outputs. Over the last few years, there has been great interest in developing efficient low-complexity schemes for the unsourced random access channel [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]. A natural approach for this setup is for all users to transmit codewords from the same codebook. It can be easily seen that if \(A\in\mathbb{R}^{n\times 2^{B}}\) is a matrix whose columns are the codewords of this codebook, and \(\mathbf{x}\in\{0,1\}^{2^{B}}\) is a vector whose \(i\)th entry equals \(1\) if one of the active users chose message \(i\) and \(0\) otherwise, the channel output is \(\mathbf{y}=A\mathbf{x}+\sigma\mathbf{z}\), where \(\mathbf{z}\) is whiteGaussian noise (we assume here for simplicity that no message was chosen by more than one user). Since the number of active users \(k\) is typically of the order of tens to hundreds, and is much smaller than \(2^{B}\), whereas the blocklength \(n\) is typically on the order of \(10^{4}\) to \(10^{5}\), the problem of designing efficient codebooks and decoding algorithm for the unsourced random access channel corresponds to designing the sensing matrix \(A\) and a recovery algorithm for a compressed sensing problem [1]. However, this compressed sensing problem has two non-standard features: (i) the dimensions of the problem are huge (recall that \(B=100\) is a typical number); and (ii) the sparse vector is binary, in contrast to the standard compressed sensing setup where the nonzero entries can take values in an interval within the real line. To address the dimensions of the compressed sensing problem, [PERSON] et al. [7] introduced the coded compressed sensing framework, where the \(B\) message bits are divided to smaller chunks and are encoded on different sub-blocks. This idea breaks the original compressed sensing problem into a sequence of compressed sensing problems with manageable dimensions, which can be handled via existing tools from the compressed sensing literature (we remark that this is somewhat related to ideas that have previously appeared in the compressed sensing and group testing literature, wherein one constructs the measurements matrix by combining an \"outer\" and \"inner\" code--see, e.g., [16; 17; 18]).