pith. sign in

arxiv: 1907.09448 · v1 · pith:OGGV7CH7new · submitted 2019-07-22 · 💻 cs.IT · math.IT

Energy efficient coded random access for the wireless uplink

Suhas S Kowshik , Kirill Andreev , Alexey Frolov , Yury Polyanskiy This is my paper

Pith reviewed 2026-05-24 17:51 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords random accessRayleigh fadingmultiple-access channelinterference cancellationphase transitionbelief propagation decoderenergy efficiencygrant-free access
0
0 comments X

The pith

In Rayleigh fading random access, joint decoding of many users enables perfect multi-user interference cancellation below a critical spectral efficiency threshold of 5-15 bps/Hz.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper studies the design of energy-efficient random access schemes for dense wireless uplinks under Rayleigh fading with unknown channel gains. It develops a random coding achievability bound and an explicit sparse graph coding scheme decoded via alternating belief propagation. The central result is that joint decoding leads to a phase transition effect, allowing perfect cancellation of interference from many users at spectral efficiencies below 5-15 bits per second per Hertz. This holds promise for grant-free uncoordinated access in future wireless networks. The presence of fading raises the required energy per bit but helps iterative methods reach optimal performance through added randomization.

Core claim

The authors show that for the Rayleigh fading multiple access channel with channel gains unknown at the decoder, there exists a phase transition in spectral efficiency below which perfect multi-user interference cancellation is possible when jointly decoding a large number of users. They support this with a non-asymptotic random coding bound and demonstrate that a practical sparse-graph code with belief-propagation decoding performs close to this bound, while noting that fading increases the minimal Eb/N0 but facilitates attaining the optimum via iteration.

What carries the argument

The phase transition effect in the spectral efficiency of the random access code, below which perfect multi-user interference cancellation occurs.

If this is right

  • Perfect interference cancellation is achievable in dense networks below the threshold.
  • Required energy per bit increases to 8-11 dB due to fading.
  • Iterative decoding schemes can more easily reach optimal performance because of channel randomization.
  • The framework allows unified benchmarking of random access solutions for 5G/6G.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach may generalize to other channel models with similar randomization effects.
  • Practical implementations could benefit from operating just below the identified thresholds to maximize reliability.
  • This phase transition might connect to similar phenomena in other multi-user communication scenarios.

Load-bearing premise

The analysis relies on a Rayleigh fading model with unknown channel gains and uses a random coding achievability bound to predict practical performance.

What would settle it

Observing that the error probability does not drop sharply to zero for a large number of users at spectral efficiencies below the predicted threshold would falsify the phase transition claim.

Figures

Figures reproduced from arXiv: 1907.09448 by Alexey Frolov, Kirill Andreev, Suhas S Kowshik, Yury Polyanskiy.

Figure 1
Figure 1. Figure 1: Iterative joint decoding algorithm (alternating BP [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Ka vs Eb/N0 for ǫ ≤ 0.1, n = 30000, k = 100 bits. Dashed lines correspond to asymptotic approximation obtained by taking n → ∞ and are shown only for reference. The converse from (8) and (9) is also plotted. This is in essence a single user based converse bound. We can also derive a Fano type converse, but for the range of parameters we work with, it is worse than the presented one. The converse presented … view at source ↗
Figure 3
Figure 3. Figure 3: Eb/N0 vs P UP E for n = 30000, k = 100 bits VII. ASYMPTOTICS OF RANDOM-ACCESS In [1] the authors evaluated a random coding bound for AWGN RAC with n = 30000 and Ka = 1, ..., 300. The most interesting observation was that the bound on energy-per-bit was essentially constant up until about Ka = 150 and only then started to increase with Ka. To explain this ”phase transition” behavior a particular asymptotics… view at source ↗
Figure 4
Figure 4. Figure 4: µ vs E for ǫ ≤ 10−3 , M1 = 2100 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 0 2 · 10−2 4 · 10−2 6 · 10−2 8 · 10−2 0.1 E, dB µ Optimal decoder (Replica method) Achievability Theorem B.1 ML bound from [19] Converse (i.i.d. codebook) Converse [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: µ vs E for ǫ ≤ 0.1, M1 = 2100 VIII. CONCLUSION AND FUTURE WORK In this work we considered random access for a quasi-static Rayleigh fading model. We developed low-complexity iterative decoding scheme using LDPC codes to decode up to T –users in a slot, and using T –fold ALOHA on top of it gave us a practical achievable scheme whose required Eb/N0 vs Ka trade-off is very close to that of a potential random … view at source ↗
Figure 6
Figure 6. Figure 6: Simulation results for K = 2 users APPENDIX E SINGLE-COMPONENT GM PERFORMANCE TABLE I: GM parameters for single and multiple component GM model Parameter Multi-component GM Single-component GM Gaussian mixture merge distance (dmin) 1 − Gaussian mixture maximum component count (ν) 500 1 GM sample count to evaluate (16) 20 20 Maximum cumulative weight to drop at prune (The components with the least weights a… view at source ↗
Figure 7
Figure 7. Figure 7: Simulation results for K = 3 users 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 10−2 10−1 Eb/N0, dB Pe K = 4 K = 4, known H K = 4, FBL achievability K = 4, Converse [PITH_FULL_IMAGE:figures/full_fig_p025_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Simulation results for K = 4 users The second setup should be explained in more details. Recall to the four message types described in section V. Each GM at every message passing step consists of a single component with the highest probability and the sampling (required to evaluate (16)) is performed from a single Gaussian distribution. As soon as the only GM component retains after every message type pass… view at source ↗
Figure 9
Figure 9. Figure 9: Simulation results for K = 4 users. Single component GM and multiple-component GM model (including component merge and prune model) frame error rate performance by different mean and covariance vectors. • Blue curve corresponds to the case when ν = 1. We still perform prune operation but do not perform merge operation. At each step, the most probable component is chosen. So, in this case, the message is a … view at source ↗
read the original abstract

We discuss the problem of designing channel access architectures for enabling fast, low-latency, grant-free and uncoordinated uplink for densely packed wireless nodes. Specifically, we study random-access codes, previously introduced for the AWGN multiple-access channel (MAC) by Polyanskiy'2017, in the practically more relevant case of users subject to Rayleigh fading, when channel gains are unknown to the decoder. We propose a random coding achievability bound, which we analyze both non-asymptotically (at finite blocklength) and asymptotically. As a candidate practical solution, we propose an explicit sparse-graph based coding scheme together with an alternating belief-propagation decoder. The latter's performance is found to be surprisingly close to the finite-blocklength bounds. Our main findings are twofold. First, just like in the AWGN MAC we see that jointly decoding large number of users leads to a surprising phase transition effect, where at spectral efficiencies below a critical threshold (5-15 bps/Hz depending on reliability) a perfect multi-user interference cancellation is possible. Second, while the presence of Rayleigh fading significantly increases the minimal required energy-per-bit $E_b/N_0$ (from about 0-2 dB to about 8-11 dB), the inherent randomization introduced by the channel makes it much easier to attain the optimal performance via iterative schemes. In all, it is hoped that a principled definition of the random-access model together with our information-theoretic analysis will open the road towards unified benchmarking and comparison performance of various random-access solutions, such as the currently discussed candidates (MUSA, SCMA, RSMA) for the 5G/6G.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript extends the unsourced random-access model of Polyanskiy (2017) to the Rayleigh-fading uplink with unknown channel gains. It derives a random-coding achievability bound, both non-asymptotically (finite blocklength) and in the asymptotic regime, and constructs an explicit sparse-graph code whose alternating belief-propagation decoder tracks the bound closely enough to exhibit a phase transition: below a critical spectral-efficiency threshold (5–15 bps/Hz, reliability-dependent) perfect multi-user interference cancellation becomes possible. The presence of fading raises the required Eb/N0 (to 8–11 dB) yet simplifies attainment of the bound via iterative methods. The work positions these results as a principled benchmark for grant-free schemes such as MUSA, SCMA and RSMA.

Significance. If the bounds and the constructive scheme hold, the paper supplies both an information-theoretic reference point and a practical decoder that nearly achieves it, thereby enabling unified performance comparisons of random-access architectures for 5G/6G. The explicit construction, the documented proximity of the BP decoder to the finite-blocklength bound, and the identification of the phase-transition phenomenon constitute concrete strengths.

minor comments (3)
  1. [Section 3] §3 (or wherever the finite-blocklength bound is stated): the precise dependence of the critical spectral-efficiency threshold on the target error probability should be made explicit, e.g., by tabulating the threshold for the reliability levels used in the numerical examples.
  2. The description of the alternating BP decoder would benefit from a short pseudocode listing or a clear statement of the message-update schedule; the current prose leaves the alternation rule slightly ambiguous.
  3. Figure captions should indicate the precise blocklength, number of users, and target error probability used for each curve so that the plots can be reproduced without consulting the main text.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work, as well as the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper introduces and analyzes a new random coding achievability bound for the Rayleigh fading unsourced random-access channel (both finite-blocklength and asymptotic regimes), then benchmarks an explicit sparse-graph code against it. The phase-transition claim follows directly from this analysis rather than from any self-referential reduction, fitted parameter renamed as prediction, or load-bearing self-citation. The Polyanskiy 2017 reference only defines the prior AWGN model; the Rayleigh extension and its bounds are derived independently in the present work. No equations reduce to their own inputs by construction, and the derivation remains self-contained against external information-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard information-theoretic assumptions and the Rayleigh fading model; no new entities introduced based on abstract.

axioms (2)
  • domain assumption Rayleigh fading channel model with unknown gains to decoder
    Central to the analysis as stated in the abstract.
  • standard math Standard random coding achievability arguments for MAC
    Used to derive the bounds.

pith-pipeline@v0.9.0 · 5843 in / 1142 out tokens · 25575 ms · 2026-05-24T17:51:47.966836+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · 6 internal anchors

  1. [1]

    A perspective on massive random-access ,

    Y . Polyanskiy, “A perspective on massive random-access ,” in 2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017, pp. 2523–2527. 12

    work page 2017

  2. [2]

    A user-independent serial interference cancellation bas ed coding scheme for the unsourced random access Gaussian chan nel,

    A. V em, K. R. Narayanan, J. Cheng, and J.-F. Chamberland, “A user-independent serial interference cancellation bas ed coding scheme for the unsourced random access Gaussian chan nel,” in Information Theory W orkshop (ITW), 2017 IEEE . IEEE, 2017, pp. 121–125

    work page 2017

  3. [3]

    A Coded Compressed Sensing Scheme for Uncoordinated Multiple Access

    V . K. Amalladinne, A. V em, D. K. Soma, K. R. Narayanan, and J.-F. Chamberland, “A coupled compressive sensing scheme for uncoordinated multiple access,” arXiv preprint arXiv:1809.04745 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  4. [4]

    Massive MIMO Unsourced Random Access

    A. Fengler, G. Caire, P . Jung, and S. Haghighatshoar, “Ma ssive MIMO Unsourced Random Access,” arXiv preprint arXiv:1901.00828, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  5. [5]

    Low complexity scheme s for the random access gaussian channel,

    O. Ordentlich and Y . Polyanskiy, “Low complexity scheme s for the random access gaussian channel,” in 2017 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2017, pp. 2528–2532

    work page 2017

  6. [6]

    Stability propert ies of slotted Aloha with multipacket reception capability ,

    S. Ghez, S. V erdu, and S. C. Schwartz, “Stability propert ies of slotted Aloha with multipacket reception capability ,” IEEE Trans. Autom. Control , vol. 33, no. 7, pp. 640–649, 1988

    work page 1988

  7. [7]

    Graph-based analysis and optimization of cont ention resolution diversity slotted ALOHA,

    G. Liva, “Graph-based analysis and optimization of cont ention resolution diversity slotted ALOHA,” IEEE Transactions on Communications , vol. 59, no. 2, pp. 477–487, 2011

    work page 2011

  8. [8]

    Achievability Bounds for T-Fold Irregular Repetitio n Slotted ALOHA Scheme in the Gaussian MAC,

    A. Glebov, N. Matveev, K. Andreev, A. Frolov, and A. Turli kov, “Achievability Bounds for T-Fold Irregular Repetitio n Slotted ALOHA Scheme in the Gaussian MAC,” in 2019 IEEE Wireless Communications and Networking Conferen ce (WCNC). IEEE, 2019

    work page 2019

  9. [9]

    On LDPC Cod e Based Massive Random-Access Scheme for the Gaussian Multiple Access Channel,

    A. Glebov, L. Medova, P . Rybin, and A. Frolov, “On LDPC Cod e Based Massive Random-Access Scheme for the Gaussian Multiple Access Channel,” in Internet of Things, Smart Spaces, and Next Generation Netwo rks and Systems . Springer, 2018, pp. 162–171

    work page 2018

  10. [10]

    A joint graph based coding scheme for the unsourced random access gaussian channel,

    A. Pradhan, V . Amalladinne, A. V em, K. R. Narayanan, and J.-F. Chamberland, “A joint graph based coding scheme for the unsourced random access gaussian channel,” arXiv preprint arXiv:1906.05410 , 2019

    work page arXiv 1906

  11. [11]

    The optimal received power dist ribution for ic-based iterative multiuser joint decoders,

    G. Caire and R. Muller, “The optimal received power dist ribution for ic-based iterative multiuser joint decoders, ” in Proc. Allerton Conf. Comm. Control Comp. , vol. 39, no. 2, 2001, pp. 1132–1141

    work page 2001

  12. [12]

    Improv ed bounds on Gaussian MAC and sparse regression via Gaussian inequalities,

    I. Zadik, Y . Polyanskiy, and C. Thrampoulidis, “Improv ed bounds on Gaussian MAC and sparse regression via Gaussian inequalities,” in 2019 IEEE International Symposium on Information Theory (I SIT). IEEE, 2019

    work page 2019

  13. [13]

    Massive Random Access with Common Alarm Messages

    K. Stern, A. E. Kalør, B. Soret, and P . Popovski, “Massiv e random access with common alarm messages,” arXiv preprint arXiv:1901.06339, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  14. [14]

    Sparse activity detecti on for massive connectivity,

    Z. Chen, F. Sohrabi, and W . Y u, “Sparse activity detecti on for massive connectivity,” IEEE Transactions on Signal Processing, vol. 66, no. 7, pp. 1890–1904, 2018

    work page 1904

  15. [15]

    Sparse Signal Processing for Grant-Free Massive Connectivity: A Future Paradigm for Random Access Protocols in the Internet of Things

    L. Liu, E. G. Larsson, W . Y u, P . Popovski, C. Stefanovic, and E. De Carvalho, “Sparse Signal Processing for Grant-Fre e Massive IoT Connectivity,” arXiv preprint arXiv:1804.03475 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  16. [16]

    Massive connectivity with massive MIM O—Part I: Device activity detection and channel estimation ,

    L. Liu and W . Y u, “Massive connectivity with massive MIM O—Part I: Device activity detection and channel estimation ,” IEEE Transactions on Signal Processing , vol. 66, no. 11, pp. 2933–2946, 2018

    work page 2018

  17. [17]

    A New Scaling Law for Activity Detection in Massive MIMO Systems

    S. Haghighatshoar, P . Jung, and G. Caire, “Improved sca ling law for activity detection in massive MIMO systems,” arXiv preprint arXiv:1803.02288 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  18. [18]

    Information-theoretic limits on sp arsity recovery in the high-dimensional and noisy setting,

    M. J. Wainwright, “Information-theoretic limits on sp arsity recovery in the high-dimensional and noisy setting, ” IEEE Transactions on Information Theory , vol. 55, no. 12, pp. 5728–5741, 2009

    work page 2009

  19. [19]

    The sampling rate-distortio n tradeoff for sparsity pattern recovery in compressed sens ing,

    G. Reeves and M. Gastpar, “The sampling rate-distortio n tradeoff for sparsity pattern recovery in compressed sens ing,” IEEE Transactions on Information Theory , vol. 58, no. 5, pp. 3065–3092, 2012

    work page 2012

  20. [20]

    A note on optimal support recovery in compressed se nsing,

    ——, “A note on optimal support recovery in compressed se nsing,” in Signals, Systems and Computers, 2009 Conference Record of the F orty-Third Asilomar Conference on . IEEE, 2009, pp. 1576–1580

    work page 2009

  21. [21]

    Sparse Signal Sampling using Noisy Linear P rojections,

    G. Reeves, “Sparse Signal Sampling using Noisy Linear P rojections,” Univ. Calif., Berkeley, Dept. of Electrical Engineering and Computer Science, Tech. Rep., 2008

    work page 2008

  22. [22]

    Capacity of gaussian many-access channels

    X. Chen, T.-Y . Chen, D. Guo et al. , “Capacity of gaussian many-access channels.” IEEE Trans. Information Theory , vol. 63, no. 6, pp. 3516–3539, 2017

    work page 2017

  23. [23]

    Fundamental limits of many-user MAC with finite payloads and fading,

    S. S. Kowshik and Y . Polyanskiy, “Fundamental limits of many-user MAC with finite payloads and fading,” arXiv preprint arXiv:1901.06732, 2019

    work page arXiv 1901

  24. [24]

    Quasi-static fading MAC with many users and finite p ayload,

    ——, “Quasi-static fading MAC with many users and finite p ayload,” in 2019 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2019

    work page 2019

  25. [25]

    R. G. Gallager, Low-Density Parity-Check Codes . M.I.T. Press, 1963

    work page 1963

  26. [26]

    A recursive approach to low complexity code s,

    R. Tanner, “A recursive approach to low complexity code s,” IEEE Transactions on information theory , vol. 27, no. 5, pp. 533–547, 1981

    work page 1981

  27. [27]

    Richardson and R

    T. Richardson and R. Urbanke, Modern coding theory . Cambridge university press, 2008

    work page 2008

  28. [28]

    Quasi-static SIMO fading channels at finite blocklength,

    W . Y ang, G. Durisi, T. Koch, and Y . Polyanskiy, “Quasi-static SIMO fading channels at finite blocklength,” in Information Theory Proceedings (ISIT), 2013 IEEE International Sympos ium on . IEEE, 2013, pp. 1531–1535

    work page 2013

  29. [29]

    Polyanskiy, Channel coding: non-asymptotic fundamental limits

    Y . Polyanskiy, Channel coding: non-asymptotic fundamental limits . Princeton University, 2010

    work page 2010

  30. [30]

    Fixed Error Asymptotics For Erasure and List Decoding

    V . Y . Tan and P . Moulin, “Fixed error asymptotics for era sure and list decoding,” arXiv preprint arXiv:1402.4881 , 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  31. [31]

    Channel coding rate in the finite blocklength regime,

    Y . Polyanskiy, H. V . Poor, and S. V erdú, “Channel coding rate in the finite blocklength regime,” IEEE Transactions on Information Theory , vol. 56, no. 5, pp. 2307–2359, 2010

    work page 2010

  32. [32]

    Fact or graphs and the sum-product algorithm,

    F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Fact or graphs and the sum-product algorithm,” IEEE Transactions on information theory , vol. 47, no. 2, pp. 498–519, 2001

    work page 2001

  33. [33]

    The GM-PHD Filter Mul tiple Target Tracker,

    D. E. Clark, K. Panta, and B. n. V o, “The GM-PHD Filter Mul tiple Target Tracker,” in 2006 9th International Conference 13 on Information Fusion , July 2006, pp. 1–8

    work page 2006

  34. [34]

    Successive int erference cancellation with SISO decoding and EM channel estimation,

    M. Kobayashi, J. Boutros, and G. Caire, “Successive int erference cancellation with SISO decoding and EM channel estimation,” IEEE Journal on Selected Areas in Communications , vol. 19, no. 8, pp. 1450–1460, Aug 2001

    work page 2001

  35. [35]

    Outages, expected rates and d elays in multiple-users fading channels,

    I. Bettesh and S. Shamai, “Outages, expected rates and d elays in multiple-users fading channels,” in Proceedings of the 2000 Conference on Information Science and Systems , vol. 1, 2000

    work page 2000

  36. [36]

    Approximate sparsity patt ern recovery: Information-theoretic lower bounds,

    G. Reeves and M. C. Gastpar, “Approximate sparsity patt ern recovery: Information-theoretic lower bounds,” IEEE Transactions on Information Theory , vol. 59, no. 6, pp. 3451–3465, 2013

    work page 2013

  37. [37]

    Minimum energy to send k bits through the Gaussian channel with and without feedback,

    Y . Polyanskiy, H. V . Poor, and S. V erdú, “Minimum energy to send k bits through the Gaussian channel with and without feedback,” IEEE Transactions on Information Theory , vol. 57, no. 8, pp. 4880–4902, 2011

    work page 2011

  38. [38]

    A strong law for linear functions of order s tatistics,

    W . V an Zwet, “A strong law for linear functions of order s tatistics,” The Annals of Probability , pp. 986–990, 1980

    work page 1980

  39. [39]

    An alternative point of view on Lepski’s meth od,

    L. Birgé, “An alternative point of view on Lepski’s meth od,” Lecture Notes-Monograph Series , pp. 113–133, 2001. 14 APPENDIX A FBL ACHIEVABILITY BOUNDS In this section we state the random coding FBL achievability bounds for the model in (2). But first, we discuss the encoding and decoding which we use to derive achievability. For encod ing, we use random ...

    work page 2001