PaperlayerView exact revision on arXiv

Source-linked AI summary

Capacity of Gaussian Many-Access Channels

Xu Chen, Tsung-Yi Chen, Dongning Guo

arXiv:1607.01048v2cs.ITmath.IT

TL;DR

Classical multiuser information theory generally studies a fixed number of users, while many practical systems have populations that grow with blocklength and may transmit sporadically. This paper characterizes message-length capacity for the Gaussian many-access channel, using active-user identification followed by message decoding; that separation achieves capacity.

  • Problem

    Classical multiuser theory assumes a fixed user population, whereas many-access systems can have a growing population and an unknown active subset that must be identified.

    Source: §I · p. 1

  • Method

    Each user sends a signature and a message-bearing codeword; the receiver identifies active users from the signatures before decoding their messages.

    Source: §I · p. 2, B. Achievability for Case 1 and Case 2… · p. 9

  • Results

    The paper characterizes Gaussian many-access message-length capacity as the sum of a term for known active users and a cost of user identification, and separate identification and decoding achieves capacity.

    Source: B. Achievability for Case 1 and Case 2… · p. 9, §VIII · p. 15

  • Takeaways & Limitations

    The resulting asymptotic theory is presented as having better explanatory power for random massive access than classical theory.

    Source: §I · p. 2

    The exact capacity for a given large finite user population and blocklength remains an open problem.

    Source: §I · p. 2

Abstract

from arXiv · show

Classical multiuser information theory studies the fundamental limits of models with a fixed (often small) number of users as the coding blocklength goes to infinity. This work proposes a new paradigm, referred to as {\em many-user information theory}, where the number of users is allowed to grow with the blocklength. This paradigm is motivated by emerging systems with a massive number of users in an area, such as machine-to-machine communication systems and sensor networks. The focus of the current paper is the {\em many-access} channel model, which consists of a single receiver and many transmitters, whose number increases unboundedly with the blocklength. Moreover, an unknown subset of transmitters may transmit in a given block and need to be identified. A new notion of capacity is introduced and characterized for the Gaussian many-access channel with random user activities. The capacity can be achieved by first detecting the set of active users and then decoding their messages.

I. INTRODUCTION

Classical multiuser theory typically holds the user population fixed as blocklength grows, leaving systems with user counts comparable to or larger than blocklength outside its usual setting. This paper develops a many-access model and characterizes message-length capacity for random user activity.

II. SYSTEM MODEL AND MAIN RESULTS

  • The many-access channel has one receiver and a growing number of transmitters; users access it independently with a common probability, and transmissions are synchronous.The model reduces to the conventional multiaccess channel when the user count is fixed and every user is active.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • Many-user information theory addresses systems where the transmitter population grows with blocklength, a regime motivated by massive device populations and not captured by fixed-user asymptotics.The paper notes that the order and scaling of user-count and blocklength limits can matter, and that bits per channel use may not describe communication well in this regime.Source: §I · p. 1
  • The proposed scheme gives each user a signature followed by a message-bearing codeword, then identifies active users before decoding their messages.The paper characterizes the signature length as matching the capacity penalty due to uncertainty about user activity.Source: §I · p. 2

A. The Message-Length Capacity

  • When the overhead factor θ exceeds 1, a user cannot reliably send even one bit; with unbounded total users but bounded average activity, message length is sublinear in blocklength.In the latter case, no positive linear message length is achievable.Source: A. The Message-Length Capacity · p. 3
  • The symmetric message-length capacity includes a cost for activity uncertainty; when every user is active, that penalty is zero.The paper relates the cost per active user to H2(α_n)/α_n and notes that capacity depends on how the user population and active-user count scale.Source: A. The Message-Length Capacity · p. 3

B. The User Identification Cost

The section characterizes the signature length needed to identify randomly active users and develops converse arguments for the Gaussian many-access channel’s message-length capacity. The identification threshold depends on the scaling of the user population and average active-user count.

B. The User Identification Cost

  • The identification setup models each user as independently active with probability αℓ and uses n0 channel symbols for identification.The average number of active users is kℓ=αℓℓ.Source: B. The User Identification Cost · p. 4
  • When kℓ→∞ and n(ℓ)/kℓ→0, n0=εkℓ gives vanishing identification error, whereas n0≤(1−ε)n(ℓ) cannot make the error vanish.These statements hold for any ε>0 in the achievability claim and any 0<ε<1 in the converse claim.Source: B. The User Identification Cost · p. 4
  • For kℓ=⌈ℓ^(1/d)⌉ with d>1, the minimum identification cost is n(ℓ)=2(d−1)kℓ+o(kℓ), linear in the average active-user count.The paper illustrates n(ℓ) with Fig. 2.Source: B. The User Identification Cost · p. 4, Figure 2 · p. 4

A. Converse for Case 1: unbounded ℓn and unbounded kn

  • A straightforward Fano-inequality converse is insufficient because the joint input alphabet may grow rapidly with blocklength.The proof introduces an additional construction to handle this difficulty.Source: A. Converse for Case 1: unbounded ℓn… · p. 5

III. CONVERSE OF THEOREM 1 (MNAC CAPACITY)

B. Converse for Case 2: unbounded ℓn and bounded kn

The section establishes converse bounds for bounded-user regimes and develops converse and achievability results for reliable user identification.

B. Converse for Case 2: unbounded ℓn and bounded kn

  • Linear message-length growth is not achievable when the total user population is unbounded but the average number of active users is bounded.The converse uses the nonvanishing probability of more than a fixed number of active users.Source: B. Converse for Case 2: unbounded ℓn… · pp. 5–6

C. Converse for Case 3: bounded ℓn

  • For αn→0, the converse is bounded by point-to-point capacity 2 log(1 + P); for αn→α > 0, it follows from the symmetric rate of the conventional multiaccess channel with ℓ users.When αn→0, a transmitting user sees no interference with probability tending to one; when αn→α > 0, all ℓ users are active with probability αℓ > 0.Source: C. Converse for Case 3: bounded ℓn · p. 6

A. Converse of Theorem 2

  • The converse of Theorem 2 rules out vanishing random-user identification error when the signature length is n0=(1−ε)n(ℓ), for any 0<ε<1.It follows by applying the converse of Theorem 1 with M=1 and n=n0.Source: A. Converse of Theorem 2 · p. 6

B. Achievability of Theorem 2

  • For user identification, the scheme achieves an error probability bounded by e^(−ckℓ) for some positive c, and establishes reliable identification with signature length n0 from (41).The result holds with SNR P′=P−ε, where ε can be arbitrarily small.Source: B. Achievability of Theorem 2 · pp. 6, 8

V. ACHIEVABILITY OF THEOREM 1 (MNAC CAPACITY)

This section proves the achievability part of Theorem 1 to establish the symmetric capacity of the many-access channel.

V. ACHIEVABILITY OF THEOREM 1 (MNAC CAPACITY)

  • The section proves the achievability part of Theorem 1, establishing the symmetric capacity of the MnAC.MnAC denotes the many-access channel.Source: §V · p. 8

A. Achievability for Case 3 with bounded ℓn

The achievability analysis covers bounded and growing user populations, using active-user identification followed by message decoding in the growing-population cases.

A. Achievability for Case 3 with bounded ℓn

  • For bounded ℓn, if αn→α>0 achievability follows from the conventional ℓ-user multiaccess channel; if αn→0 it follows from the point-to-point channel.In the latter case, a transmitting user experiences a single-user channel with probability tending to one.Source: A. Achievability for Case 3 with… · p. 8

B. Achievability for Case 1 and Case 2 with unbounded ℓn

  • For unbounded ℓn and unbounded kn with lim θn<1, message length (1−ε)B(n) is asymptotically achievable using the two-stage scheme.The decoder first identifies active users from signatures, then decodes their messages.Source: B. Achievability for Case 1 and Case 2… · p. 9

C. Optimal User Identification

  • Reliable user identification is achieved by choosing signature length n0=(1+ε)θnn when θnn/kn has a positive limit, or n0=εkn when that ratio tends to zero.Here ε∈(0,1) is arbitrary.Source: C. Optimal User Identification · p. 9

D. Achieving the MnAC Capacity with Known User Activities

  • With kn always-active users growing as O(n), the symmetric capacity is 1/(2kn) log(1+knP).For any ε∈(0,1), message lengths B1(n)(1−ε) are achievable with arbitrarily small average error for sufficiently large n.Source: D. Achieving the MnAC Capacity with… · p. 10

E. Achieving the Capacity of MnAC with Random Access

For unbounded total and active user counts, the section establishes achievability across two limits of θn. It also gives an achievable sublinear message length when the total population is unbounded but the average active-user count is bounded.

E. Achieving the Capacity of MnAC with Random Access

VI. SUCCESSIVE DECODING FOR MNAC

The paper finds that Gaussian-code successive decoding can leave the first user’s error probability bounded away from zero when the user count scales linearly with blocklength. It also characterizes capacity for heterogeneous groups, with feasibility conditions and a weighted-average message-length constraint.

VI. SUCCESSIVE DECODING FOR MNAC

  • When k_n=an, some λ makes the first user’s error-probability lower bound strictly positive under Gaussian-code successive decoding.The section gives a negative answer to whether this decoding scheme achieves the many-access sum capacity in that setting.Source: §VI · p. 12
  • With k_n=an, the first decoded user faces interference from the other users, and the error exponent may be too small to drive error probability to zero.The section explains that nC converges to a finite constant in this regime.Source: §VI · p. 12

VII. MNAC WITH HETEROGENEOUS USER GROUPS

  • For heterogeneous groups, the capacity characterization covers finitely many groups with different channel gains and activity patterns.Users within each group share a power constraint and activity probability.Source: §VII · p. 12
  • When the sum of the group θ(j) values exceeds 1, some user cannot reliably transmit even a single bit.The theorem also gives a capacity-region characterization when that sum is below 1.Source: §VII · p. 13
  • In the heterogeneous-group asymptotics, transmit power is inconsequential and the message constraint is a weighted average, unlike classical multiaccess subset bounds.The section contrasts this with separate upper bounds on the sum rate of each user subset in the classical channel.Source: §VII · p. 13

A. Converse

The converse shows that, for an unbounded number of active users, the total-group constraint dominates the heterogeneous-group bounds. The achievability construction identifies active users before decoding messages, and the conclusion notes that the asymptotic results leave the finite-but-large regime open.

A. Converse

  • For unbounded active-user counts, the constraint for all groups together dominates the constraints for every group subset.When the sum of θ(j) exceeds 1, the converse implies that all group message lengths are zero for sufficiently large n.Source: A. Converse · p. 14

B. Achievability

  • The achievable scheme allocates time to group signatures and then group message codewords, with active-user identification preceding message decoding.Groups transmit their signatures and message-bearing codewords in turn.Source: B. Achievability · p. 14

VIII. CONCLUSION

  • Separate identification and decoding achieves the capacity characterization, and the detection scheme extends to the capacity region for finitely many groups with different channel gains.The conclusion describes this extension for groups with heterogeneous channel gains.Source: §VIII · p. 15
  • The paper leaves many-user information theory for finite but large user populations and blocklengths as an open challenge.The stated results characterize capacity growth in the asymptotic regime.Source: §VIII · p. 15

APPENDIX A PROOF OF LEMMA 1

The appendices develop proof ingredients for the main bounds: mutual-information control, error-event estimates, a Gaussian decomposition, and a uniform lower bound across miss and false-alarm cases.

APPENDIX A PROOF OF LEMMA 1

  • The Lemma 1 proof bounds white-Gaussian-channel mutual information using the signal power constraint and the distribution of the binary activity vector.It then invokes a parallel-Gaussian-channel bound.Source: Appendix A · p. 15

APPENDIX B PROOF OF LEMMA 2

  • The Lemma 2 proof bounds the number of candidate activity vectors using a binomial tail estimate and entropy bounds.The activity count has a binomial distribution with mean k_n.Source: Appendix B · pp. 15–16

APPENDIX C DERIVATION OF (77)

  • When |A1|=w1 and |A2|=w2, Z1, Z2, and Z3 are Gaussian with variances v1=w1P′, v2=w2P′, and v3=(|A∗|−w1)P′, respectively.mλ,ρ(w1,w2) is given by (77).Source: Appendix C · pp. 16–17

APPENDIX D PROOF OF LEMMA 3

  • Lemma 3 establishes a uniform lower bound on the error exponent across miss-detection and false-alarm regimes as the system grows.The proof treats small and larger false-alarm counts separately.Source: Appendix D · p. 17, A. The case of φ > 0 · p. 18

1) The case of 0

The proof lower-bounds the relevant error expression by separating false-alarm and miss-detection cases and controlling the possible miss counts.

1) The case of 0

  • The proof splits the lower bound into separate contributions associated with false alarms and misses.It distinguishes small false-alarm counts from larger ones.Source: 1) The case of 0 · p. 18
  • For misses, the proof separates cases according to the active-set size and the number of missed users, then bounds the resulting expression.It treats three ranges of active-set and miss counts.Source: 1) The case of 0 · p. 18
  • Across the considered miss and false-alarm cases, the resulting bound is uniform over the admissible error-event pairs.The proof concludes a uniform lower bound over the specified range of (w1,w2).Source: 1) The case of 0 · p. 19

2) The case of ¯w < w2 ≤(1 + δℓ)kℓ:

The proof bounds the relevant expressions uniformly over the stated ranges, establishing Lemma 3 for both φ > 0 and φ = 0. In the case splits, the derived lower bounds grow without bound as ℓ or kℓ increases.

2) The case of ¯w < w2 ≤(1 + δℓ)kℓ

APPENDIX E PROOF OF LEMMA 4

The proof establishes achievability for kn = O(n), focusing on unbounded kn because the bounded case was covered in earlier work. It derives a lower bound that grows without bound and completes the lemma.

APPENDIX E PROOF OF LEMMA 4

  • The achievability result covers kn = O(n), while the proof focuses on unbounded kn because bounded kn was included in.The lemma had previously been proved for kn = o(n) in.Source: Appendix E · p. 21
  • For sufficiently large n, f(γ, 1) is concave on 1/kn ≤ γ ≤ γ′.The proof uses this concavity to obtain its bound for the indicated γ range.Source: Appendix E · p. 21
  • The lower bound given by (297) grows without bound as n increases.The passage attributes this growth to the convergence of the stated logarithmic difference and kn/n to constants.Source: Appendix E · p. 21
  • The proof concludes by lower-bounding the error exponent for every |A*| and establishing the lemma.The exponent bound applies for n ≥ max{N0, N1}.Source: Appendix E · p. 21

APPENDIX F PROOF OF THEOREM 5

For Theorem 5, the proof shows that detection error vanishes under the stated conditions on sn, including when no user is active. For Lemma 5, it establishes a positive lower bound on the first user's error probability under the specified code setting.

APPENDIX F PROOF OF THEOREM 5

  • The probability that the number of active users exceeds sn vanishes as sn grows without bound.The proof bounds this tail probability using the Chernoff bound for a binomial distribution.Source: Appendix F · p. 21
  • The overall detection error probability vanishes as n increases under the stated conditions on the increasing sequence sn.The proof treats the zero-active-user case separately and handles 1 ≤ |A*| ≤ sn using the unbounded-user analysis.Source: Appendix F · p. 22
  • When no user is active, the conditional detection error probability vanishes as n increases.With no active users, the received signal in the first n0 channel uses is purely noise.Source: Appendix F · p. 22

APPENDIX G PROOF OF LEMMA 5

  • Treating other users as interference, the first decoded user sees Gaussian noise of variance 1 + (kn − 1)P; the proof lower-bounds its error probability by a positive constant.The bound concerns codes of blocklength n with message length v(n) as specified in (122).Source: Appendix G · p. 22
Loading 1607.01048v2…