PaperlayerView exact revision on arXiv

Source-linked AI summary

SPARCs for Unsourced Random Access

Alexander Fengler, Peter Jung, Giuseppe Caire

arXiv:1901.06234v3cs.IT

TL;DR

The paper addresses unsourced random access for many sporadically active users sharing a common codebook. It proposes a concatenated SPARC-based AWGN construction with AMP and MAP inner-decoding analysis, and shows capacity-level asymptotic rates while developing power allocation to improve AMP performance.

  • Problem

    Unsourced random access requires decoding messages from many active users sharing one codebook, where conventional dedicated-resource allocation is inefficient for short, sporadic transmissions.

  • Method

    The paper concatenates a SPARC-based inner code and an outer tree code, analyzes modified AMP and hypothetical MAP decoding asymptotically, and optimizes non-uniform inner-code power allocation.

  • Results

    Vanishing per-user error is achieved with inner MAP decoding whenever K_aR < 0.5 log2(1 + K_aSNR), the symmetric Shannon-capacity condition.

  • Takeaways & Limitations

    The concatenated construction can reach Shannon-limit sum-rates in unsourced multiuser access, while tailored power allocation improves AMP when it trails MAP decoding.

Abstract

from arXiv · show

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 $K_a$ are 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 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 $K_aR < 0.5\log_2(1+K_a\SNR)$. 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 required $\SNR$.

I. INTRODUCTION

The paper develops a concatenated SPARC-based construction for unsourced random access, motivated by many sporadically active devices sharing a common codebook. It analyzes AMP and MAP inner decoding, characterizes asymptotic error behavior, and studies power allocation for improving AMP performance.

  • Motivation: Unsourced random access targets short, sporadic messages from many devices without dedicating transmission resources to each user.Users share one codebook, and the decoder recovers the list of transmitted messages.
  • Concatenated coding: The construction extends SPARCs to unsourced random access by combining an inner sparse-regression code with an outer tree code and outer-channel analysis.The inner and outer rates are Rin = LJ/n and Rout = B/LJ, respectively.
  • Inner decoding: A modified AMP decoder is analyzed through state evolution, while replica-symmetric analysis is used to determine the error probability of a hypothetical MAP decoder.The AMP analysis gives asymptotic error probabilities, and MAP decoding provides an optimal but generally infeasible benchmark.
  • Asymptotic analysis: The inner decoder's error probability has a closed-form asymptotic limit when K_a and J grow with J = α log2 K_a for α > 1.This regime relates J to the number of bits needed to encode user identities under the stated scaling.
  • Asymptotic analysis: The concatenated scheme with inner MAP decoding achieves vanishing per-user error when K_aR < 0.5 log2(1 + K_aSNR).Thus, in the analyzed limit, unsourced random access can attain the symmetric Shannon capacity despite users sharing a codebook and lacking coordination.
  • Power allocation: An optimized non-uniform power allocation can significantly improve AMP performance when AMP and MAP decoding have different achievable error probabilities.The allocation is tailored to the expected parameters and is useful only when a gap exists between the algorithmic and optimal performance.

A. Asymptotic Error Analysis

The asymptotic analysis reduces AMP and posterior-based estimation to effective Gaussian channels characterized by stationary points of RS potentials. In sparse regimes, scalar and vector analyses become closely aligned, enabling tractable approximations of AMP and SBS-MAP errors.

  • Asymptotic analysis: As L,n →∞ with fixed J and Rin, AMP error probabilities converge to deterministic values characterized by J, Rin, SNR, and Ka.The analysis uses self-averaging and state-evolution equations.
  • RS-potential characterization: The AMP MSE is determined by the smallest stationary point of the relevant RS potential, whereas optimal MMSE uses its global minimizer.This distinction can disappear when the smallest stationary point and global minimum coincide.
  • Decoupling: The decoupling property maps marginal posterior estimators, including SBS-MAP, to estimation in a degraded Gaussian channel whose strength is set by the global minimizer.This provides an asymptotic route for computing SBS-MAP error statistics.
  • Sparse-regime approximation: For Ka ≪ 2^J, the minima of the vector and scalar potentials differ negligibly, so scalar RS analysis approximates both AMP and SBS-MAP performance.The scalar potential is based on mutual information in a scalar Gaussian channel.
  • Sparse-regime approximation: The vector MMSE function approaches the scalar MMSE function exponentially fast in L1 as J →∞.This supports replacing vector-channel calculations with scalar ones in the large-section regime.
  • OR approximation: Binary OR-channel MMSE is no smaller than the corresponding section MMSE, enabling scalar fixed-point calculations for both global and local potential minimizers.The resulting corollary relates the OR-channel potential to the vector global minimizer and scalar AMP minimizer.

B. The J →∞limit

The section derives a large-section asymptotic limit of the RS potential under simultaneous growth of active users and section size. This limit yields analytically tractable stationary-point conditions despite numerical difficulties at large J.

  • Numerical regime: Numerical evaluation of the stationary points becomes difficult around J = 60 because 2^-J is too small for standard double precision.Higher-precision implementations may extend this range.
  • Asymptotic regime: In the sparse limit, the RS potential characterizes AMP and SBS-MAP performance while allowing analysis with growing aspect ratios and vanishing sparsity.The limiting regime studies nontrivial behavior as sparsity decreases and system dimensions grow.
  • Asymptotic regime: For Ka,J →∞ with fixed Ein, Sin and J = α log2 Ka, α > 1, the RS potential has a pointwise analytic limit up to η-independent terms.The omitted additive or multiplicative terms do not affect stationary points.
  • Stationary points: The stationary points of the limiting RS potential can be calculated analytically, producing simple conditions for the asymptotic behavior.These conditions are obtained from the derivative of the limiting potential.
  • Stationary points: The global-minimum condition is equivalent to condition (44), with the analysis also implying η̄ < 1.The conclusion uses the fact that condition (44) entails η̄ ≤ 1.

V. HARD DECISION

Hard decisions focus on detecting support by distinguishing s = 0 from s ≥ 1 using a threshold on the effective Gaussian observation. Threshold selection trades false alarms against missed detections and can be adapted to the outer decoder.

  • Estimator choice: The scalar MAP analysis is justified for the symbol-wise detector through the decoupling claim, while the suboptimal scalar estimator is sufficiently accurate when Ka ≪ 2^J.The vector MAP estimate is difficult to analyze directly.
  • Support detection: The detector uses only support information because the outer code depends on support and the analysis targets the sparse regime.The decision problem is binary: s = 0 versus s ≥ 1.
  • Thresholding: Under the OR approximation, varying threshold θ traces the trade-off between missed-detection and false-alarm probabilities.The trade-off follows a curve determined by the Gaussian Q-function.
  • Thresholding: For Ka = 300 and J = 12, OR-approximation error curves are barely distinguishable from precise Neyman–Pearson evaluations across the plotted effective channel strengths.Choosing θ = p0/(1 − p0) yields the SBS-MAP estimator that minimizes total error probability.
  • Thresholding: Thresholds can be varied in practice to balance false alarms and missed detections according to the needs of the outer decoder.This extends beyond the threshold minimizing total error probability.

VI. OUTER CHANNEL

The section models the inner decoder’s estimated supports as repeated vector OR-MAC outputs with asymmetric noise, then develops entropy bounds and outer-code limits. A cover decoder achieves vanishing error under an asymptotic scaling, while false positives must remain controlled.

  • OR-MAC model: The estimated support vector is interpreted as L uses of a vector OR-MAC with symbol-wise asymmetric noise.The outer decoder must recover the transmitted message list up to permutation from the section-wise active-index lists.
  • OR-MAC model: The outer code is a subset of [1 : 2^J]^L with 2^(JLR_out) codewords, equivalently binary vectors with one 1 in each section.This sectionized representation encodes each message as one index per section.
  • Rate bounds: The coding-theorem rate constraint is only an upper bound here because it assumes each user has a distinct codebook, unlike the shared-codebook setting.The resulting mutual-information bound therefore does not directly establish achievability for unsourced access.
  • Cover decoding: The cover decoder finds all transmitted codewords, and its per-user error probability is governed by the number of false positives n_fa.For a random outer code, the error probability vanishes as L, K_a, and J grow with J = α log2 K_a, α > 1, under the theorem’s rate condition.
  • Cover decoding: False positives may scale as n_fa = cK_a without changing the cover-decoding result, provided the corresponding asymptotic condition holds.Since p_fa = n_fa/2^J, the condition is equivalent to the stated false-positive constraint.

A. Tree code

The tree code divides each message into section blocks and appends shared parity bits so valid sequences form paths in a depth-L tree. Parity placement trades decoding complexity against achievable outer rate, with simulations comparing finite-length rates to the theoretical bound.

  • Tree-code construction: The B-bit message is split into blocks, and later blocks are padded with shared pseudo-random parity bits derived from earlier information bits.This creates a one-to-one correspondence between coded-block sequences and paths through a depth-L tree.
  • Tree-code construction: The outer decoder identifies valid message sequences by extending only index combinations whose parity checks are satisfied.It processes the active-index lists section by section and prunes paths that fail the checks.
  • Complexity and rates: Parity placement determines both the required parity overhead and decoding complexity.The two analyzed profiles place all parity bits in the final sections or distribute them across later sections.
  • Complexity and rates: O(K_a^RoutL log K_a) complexity results when parity bits are placed only in the last sections, whereas O(LK_a log K_a) complexity results from distributed parity.The first profile has no pruning during the initial R_outL subslots; the second scales linearly with L.
  • Complexity and rates: As L →∞, the two parity profiles achieve outer rates 1 − 1/α and 1 − c/α, respectively.The first matches the asymptotic upper bound for p_md = 0, while the second matches it up to a constant.
  • Finite-length evaluation: Finite-length simulations use B = 100 bits and L = 8, increasing parity bits until the per-user error probability falls below 0.05.Figures 3 and 4 compare these empirical results with the upper bound and vary α in the latter comparison.

VII. ANALYSIS OF THE CONCATENATED SCHEME

The analysis characterizes when the concatenated scheme supports vanishing error, including the outer-rate constraint and the inner-decoder threshold. It also relates the framework to classical multiple-access settings and finite-parameter behavior.

  • Asymptotic analysis: The concatenated scheme is reformulated through its sum-rate and an outer-rate factor Rout = 1 − α^-1.This factor is also the best achievable outer rate in the asymptotic analysis.
  • Asymptotic analysis: Theorem 8 requires the inner-channel strength to satisfy a threshold ensuring the false-positive-to-true-positive ratio remains bounded.This condition is needed for the outer-channel rate to attain its asymptotic form.
  • Asymptotic analysis: Reliable decoding with AMP is characterized asymptotically by a corollary covering n, L, J, and K_a tending to infinity under J = α log2 K_a.The corollary states conditions for P_e → 0 in the low-rate, low-SNR limit with fixed E_b/N_0.
  • Asymptotic analysis: With the SBS-MAP inner decoder, reliable decoding is possible if and only if the condition given in equation (90) holds.This provides the optimal-decoding benchmark for the concatenated construction.
  • Connections and scope: For K_a = 1, the framework reduces to point-to-point SPARCs and recovers reliability up to Shannon capacity under optimal decoding.The analysis also connects classical AWGN multiple-access models and many-access channels to different parameter scalings, while finite-L behavior is not directly covered.
  • Finite-parameter behavior: Finite-J curves approach the asymptotic trade-off from below, while empirical AMP results qualitatively agree with state-evolution predictions.Finite-length curves show constant regions that shrink as J increases and disappear asymptotically.

VIII. OPTIMIZING THE POWER ALLOCATION

The section develops a linear-programming method for optimizing non-uniform SPARC power allocation, motivated by gaps between AMP and MAP performance. Simulations show that carefully chosen two-level allocations can reduce required power, but benefits depend on the operating parameters.

  • Simulation results: The required energy can increase sharply beyond a critical user count, with the threshold becoming smaller as J grows because of decoder suboptimality.Figures 5–7 compare optimal and AMP decoding across finite and asymptotic regimes, including an AMP suboptimality threshold near J*≈22.
  • Optimization method: A linear program optimizes the power distribution for AMP by selecting section powers from a discretized interval based on Popt.The interval is uniformly discretized from Popt to 5Popt, with section fractions constrained by the average-power condition.
  • Optimization method: The optimized allocation places about one fifth of sections at higher power, allowing the remaining sections to use Popt without a local convergence point.The reported average power is about 0.5dB below Palg, the power at which the relevant potential has no local minimizers.
  • Simulation results: Finite-length simulations use L = 8, J = 20 and an outer tree code with 89 data bits to evaluate the power-allocation efficiency.The construction uses 0 parity bits in the first section, 20 in the last, and alternates between 8 and 9 in the remaining sections.
  • Optimization method: For Ka = 300, J = 20, and Rin = 0.0061, the solution uses Popt and P*∼1.9Popt with ratios 0.81 and 0.19.The resulting total power is Ein = 1.6dB versus an algorithmic threshold of Ein,alg = 2.1dB, a gain of 0.5dB.
  • Practical boundary: Non-uniform allocation can worsen performance for Ka ≤250 and improves performance only when a gap exists between Palg and Popt.Thus, the allocation must be tailored to the expected parameters rather than applied uniformly across operating regimes.

IX. CONSIDERATIONS FOR PRACTICAL IMPLEMENTATION

This section simplifies the AMP denoiser in the regime Ka ≪ 2^J by approximating the section occupancy distribution with its dominant low-occupancy terms. The resulting OR-estimator closely matches the full denoiser in the reported simulations.

  • Practical implementation: When Ka ≪ 2^J, the AMP denoiser neglects probabilities pk for k ≥2 and becomes a modified OR-estimator.The approximation is based on the small probabilities of multiple users selecting the same column.
  • Practical implementation: In the reported simulation range, the truncated OR-estimator shows almost no difference from the full AMP denoiser.For moderate 2^J relative to Ka, including the p2 term can improve the approximation slightly.
  • Practical implementation: Further occupancy terms can be added to the denoiser when needed.The same extension procedure applies beyond the p2 correction.

X. FINITE-LENGTH SIMULATIONS

The finite-length simulations evaluate the concatenated SPARC scheme using AMP inner decoding and an outer tree code. At K_a = 300, the scheme reaches 4.3 dB, while its asymptotic analysis closely predicts the required energy.

  • Simulation setup: The simulations use AMP to generate active-section lists, followed by an outer tree code that resolves the resulting multiple-access interference.The decoder declares the K_a + Δ largest entries active, with Δ = 50, and passes the list to the outer code.
  • Simulation results: 4.3 dB is achieved for K_a = 300, improving by 0.7 dB over the best previously reported 5 dB result.For smaller K_a, other schemes perform better, but their required energy rises rapidly as K_a grows.
  • Simulation results: The calculated asymptotic results describe the finite-length required energy-per-bit very precisely for a fixed per-user error probability.Figure 10 targets P_e < 0.05 using J = 15 or J = 20 parameter settings.
  • Asymptotic implication: As J grows, concatenated-code achievable sum-rates converge to the Shannon limit even when K_a grows simultaneously.The paper highlights this result for short messages and no coordination between users.
  • Limitations and optimization: The AMP decoder can require substantially more energy than the optimal decoder once J exceeds a rate-dependent threshold.A non-uniform power allocation and a linear-programming algorithm are proposed to improve AMP performance; at sum-spectral efficiency 1 bit/c.u. and K_a = 300, the improvement over existing schemes is almost 1 dB.

APPENDIX A OPTIMAL PRODUCT DISTRIBUTION

This appendix establishes that, among product distributions, the divergence from a fixed distribution is minimized by matching each factor to the corresponding marginal. It then applies multinomial and binomial identities to characterize the relevant distributions and asymptotics.

  • Optimal product distribution: The optimal product distribution has factors equal to the marginals of the target distribution.The proof rewrites the divergence into a q-independent term and a nonnegative term minimized by q_i = p_{s_i}.
  • Distributional properties: A multinomially distributed vector has binomial marginals, with covariance cov(Z_i, Z_j) = -n p_i p_j.The multinomial theorem establishes normalization, while the appendix states the marginal and covariance properties.
  • Uniform specialization: For n = K_a and uniform probabilities p_i = 2^-J, all multinomial marginals are identical binomial distributions.The appendix uses this specialization to compare the multinomial distribution with its product of binomial marginals.
  • Asymptotic calculation: Large-J expansions use log_2(1 − 2^-J) and Stirling’s approximation for log_2 K_a!.These approximations simplify the entropy and factorial expressions appearing in the appendix’s asymptotic calculations.

CONVERGENCE IN MEASURE

The convergence-in-measure argument shows that pointwise convergence fails only on a set whose measure can be made arbitrarily small. The theorem provides an explicit exceptional-set scale for sufficiently large J.

  • Theorem statement: For every δ > 0, a threshold J_δ exists such that the stated bound holds for all J ≥ J_δ.The theorem assumes a sequence of integrable functions satisfying the stated condition for sufficiently large J.
  • Exceptional set: The exceptional set has size O(δ J^-1/2), apart from the stated conditions on t.The bound holds for all t except for a set of this size.
  • Convergence consequence: The measure of the points where pointwise convergence fails can therefore be made arbitrarily small.The proof derives this from the integral argument and the preceding convergence bound.

APPENDIX D PROOF OF THEOREM 3

The proof of Theorem 3 compares posterior means under the true and OR distributions through Gaussian observations and bounds their differences. The resulting error terms decay at order O(K_a^2/2^(2J)).

  • Integral bounds: The relevant integral terms are bounded using nonnegative summands and the factor 1/p_1.The argument restricts integration to regions defined by the comparison between Z(r) and Z_OR(r).
  • Posterior means: The true and mismatched posterior means estimate s from a Gaussian observation under the original and OR distributions, respectively.The mismatched estimator assumes the OR distribution, whose mean-square error is no smaller than the optimal MMSE.
  • Bounding strategy: The proof splits the expectations according to whether Z(r) is smaller or larger than Z_OR(r).This decomposition allows the individual terms in the comparison to be bounded separately.
  • Asymptotic bound: O(K_a^2/2^(2J)) bounds the difference between the true and OR quantities for all r.The proof applies these bounds to f(r) − f_OR(r), f_OR(r)^2 − f(r)^2, and the remaining integral term.
  • Conclusion: The proof concludes Theorem 3 after transferring the individual bounds to the target expression.The final step combines the estimates obtained for the posterior-mean comparison and associated integrals.

APPENDIX E PROOF OF THEOREM 4

The appendix derives asymptotic expressions for the mutual information and MMSE-related functions underlying the RS potential. It analyzes distinct regimes separated by the threshold η̄ and establishes uniform convergence away from that threshold.

  • Mutual-information calculation: The mutual information is decomposed through H(Y)−H(Y|X), with the conditional entropy independent of η in the additive Gaussian channel.The input is binary with P(X=0)=p0, and Y=(ηP̂)^1/2X+Z for independent Gaussian noise Z.
  • Mutual-information calculation: The logarithm of the output-density sum is approximated by its dominant exponential because the correction decays exponentially with the exponent difference.The approximation is handled under an integral using uniform integrable bounds and dominated convergence.
  • Asymptotic regimes: The asymptotic behavior changes at η̄: γ′ tends to ∞ for η<η̄, 0 for η=η̄, and −∞ for η>η̄.The resulting asymptotic expression is piecewise, with separate forms below and above η̄.
  • Asymptotic regimes: The limiting MMSE function is constant on the intervals (0,η̄) and (η̄,η), while its component terms are obtained using dominated convergence.The proof shows different limiting behavior for the relevant terms below and above η̄.
  • Convergence: Pointwise convergence of the mutual-information and MMSE functions yields uniform convergence on intervals where their limiting functions are continuous.This also gives uniform convergence of the RS potential and its derivatives on (0,η̄) and (η̄,η).
Loading 1901.06234v3…