In this paper, we analyze the formation of small stopping sets in joint factor graphs describing a frame-asynchronous two-user transmission. Furthermore, we propose an algorithm to completely avoid small stopping sets in the joint factor graph over the entire range of symbol delays. The error floor caused by these stopping sets is completely mitigated. Our key observation is that, while the order of bits in the codeword is irrelevant in a single-user environment, it turns out to be crucial in an asynchronous, unsourced two-user system. Subsequently, our algorithm finds a reordering of variable nodes which avoids the smallest stopping set in the joint graph. We show that further improvements can be achieved when girth optimization of the single-user graphs by progressive edge growth (PEG) is used in combination with our proposed algorithm. Starting with a randomized code construction with optimized degree distribution, our simulation results show that PEG followed by the proposed algorithm can improve the average per user probability of error in a noiseless channel by almost two orders of magnitude for a broad range of frame delays.

In this work we demonstrate how a lack of synchronization can in fact be advantageous in the problem of random access. Specifically, we consider a multiple-access problem over a frame-asynchronous 2-user binary-input adder channel in the unsourced setup (2-UBAC). Previous work has shown that under perfect synchronization the per-user rates achievable with linear codes over the 2-UBAC are limited by 0.5 bit per channel use (compared to the capacity of 0.75). In this paper, we first demonstrate that arbitrary small (even single-bit) shift between the user’s frames enables (random) linear codes to attain full capacity of 0.75 bit/user. Furthermore, we derive density evolution equations for irregular LDPC codes, and prove (via concentration arguments) that they correctly track the asymptotic bit-error rate of a BP decoder. Optimizing the degree distributions we construct LDPC codes achieving per-user rates of 0.73 bit per channel use.

We consider the unsourced random access problem on a Rayleigh block-fading AWGN channel with multiple receive antennas. Specifically, we treat the slow fading scenario where the coherence blocklength is large compared to the number of active users and a message can be transmitted in a single fading coherence block. Unsourced random access refers to a form of grant-free random access where users are constrained to use the same codebook and therefore are a priori indistinguishable. The receiver must recover the list of transmitted messages up to permutations. In this paper, we propose an approach based on splitting the user messages into two parts. First, a small block of bits selects a relatively short codeword from a common “pilot” codebook. Then the remaining message bits are encoded by a standard block code for the Gaussian channel. The receiver makes use of a multiple measurement vector approximate message passing (MMV-AMP) algorithm to estimate the active user channels from the “pilot” part, and then uses the estimated channels to perform coherent maximum ratio combining (MRC) to decode the second part. We provide an accurate closed-form approximated analysis of the proposed scheme. Furthermore, we analyze the MRC decoding when successive interference cancellation is performed over groups of users, striking an attractive tradeoff between complexity and performance. Finally, we investigate the impact of power control policies, taking into account the unique nature of massive random access. As a byproduct, we also present an extension of the MMV-AMP algorithm which allows pathloss coefficients to be treated as deterministic unknowns by performing maximum likelihood estimation in each step of the MMV-AMP algorithm.

In this paper, we study the problem of user activity detection and large-scale fading coefficient estimation in a random access wireless uplink with a massive MIMO base station with a large number M of antennas and a large number of wireless single-antenna devices (users). We consider a block fading channel model where the M-dimensional channel vector of each user remains constant over a coherence block containing L signal dimensions in time-frequency. In the considered setting, the number of potential users Ktotis much larger than L but at each time slot only Katotof them are active. Previous results, based on compressed sensing, require that Ka≤ L, which is a bottleneck in massive deployment scenarios. In this work, we show that such limitation can be overcome when the number of base station antennas M is sufficiently large. More specifically, we prove that with a coherence block of dimension L and a number of antennas M such that Ka/M = o(1), one can identify Ka= O(L2/log2(Ktot/ Ka)) active users, which is much larger than the previously known bounds. We also provide two algorithms. One is based on Non-Negative Least-Squares, for which the above scaling result can be rigorously proved. The other consists of a low-complexity iterative componentwise minimization of the likelihood function of the underlying problem. While for this algorithm a rigorous proof cannot be given, we analyze a constrained version of the Maximum Likelihood (ML) problem (a combinatorial optimization with exponential complexity) and find the same fundamental scaling law for the number of identifiable users. Therefore, we conjecture that the low-complexity (approximated) ML algorithm also achieves the same scaling law and we demonstrate its performance by simulation. We also compare the discussed methods with the (Bayesian) MMV-AMP algorithm, recently proposed for the same setting, and show superior performance and better numerical stability. Finally, we use the discussed approximated ML algorithm as the inner decoder in a concatenated coding scheme for unsourced random access, a grant-free uncoordinated multiple access scheme where all users make use of the same codebook, and the receiver must produce the list of transmitted messages, irrespectively of the identity of the transmitters. We show that reliable communication is possible at any Eb/N0provided that a sufficiently large number of base station antennas is used, and that a sum spectral efficiency in the order ofO(Llog(L)) is achievable.

Unsourced random-access (U-RA) is a type of grant-free random access with a virtually unlimited number of users, of which only a certain number Kaare active on the same time slot. Users employ exactly the same codebook, and the task of the receiver is to decode the list of transmitted messages. We present a concatenated coding construction for U-RA on the AWGN channel, in which a sparse regression code (SPARC) is used as an inner code to create an effective outer OR-channel. Then an outer code is used to resolve the multiple-access interference in the OR-MAC. We propose a modified version of the approximate message passing (AMP) algorithm as an inner decoder and give a precise asymptotic analysis of the error probabilities of the AMP decoder and of a hypothetical optimal inner MAP decoder. This analysis shows that the concatenated construction under optimal decoding can achieve a vanishing per-user error probability in the limit of large blocklength and a large number of active users at sum-rates up to the symmetric Shannon capacity, i.e. as long as KaR2(1+KaSNR). This extends previous point-to-point optimality results about SPARCs to the unsourced multiuser scenario. Furthermore, we give an optimization algorithm to find the power allocation for the inner SPARC code that minimizes the SNR required to achieve a given target per-user error probability with the AMP decoder.

Unsourced random-access (U-RA) is a type of grant-free random access with a virtually unlimited number of users, of which only a certain number Kaare active on the same time slot. Users employ exactly the same codebook, and the task of the receiver is to decode the list of transmitted messages. Recently a concatenated coding construction for U-RA on the AWGN channel was presented, in which a sparse regression code (SPARC) is used as an inner code to create an effective outer OR-channel. Then an outer code is used to resolve the multiple-access interference in the OR-MAC. In this work we show that this concatenated construction can achieve a vanishing per-user error probability in the limit of large blocklength and a large number of active users at sum-rates up to the symmetric Shannon capacity, i.e. as long as KaR2(1 + KaSNR). This extends previous point-to-point optimality results about SPARCs to the unsourced multiuser scenario. Additionally, we calculate the algorithmic threshold, that is a bound on the sum-rate up to which the inner decoding can be done reliably with the low-complexity AMP algorithm.

This paper studies the optimal achievable performance of compressed sensing based unsourced random-access communication over the real AWGN channel. "Unsourced" means that every user employs the same codebook. This paradigm, recently introduced by Polyanskiy, is a natural consequence of a very large number of potential users of which only a finite number is active in each time slot. The resemblance of compressed sensing based communication and sparse regression codes (SPARCs), a novel type of point-to-point channel codes, allows us to design and analyse an efficient unsourced random-access code. Finite blocklength simulations show that the combination of AMP decoding, with suitable approximations, together with an outer code recently proposed by Amalladinne et. al. outperforms state of the art methods in terms of required energyper-bit at lower decoding complexity.