Unified Error Analysis for Synchronous and Asynchronous Two-User Random Access
Nazanin Mirhosseini and Jie Luo · 2025
Read Unified Error Analysis for Synchronous and Asynchronous Two-User Random Access by Nazanin Mirhosseini and Jie Luo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-17718.txt.
Introduction
Nazanin Mirhosseini and Jie Luo study error in a shared channel where two users send messages without telling each other, or the receiver, which code they picked for each message. The receiver mainly wants the first user's message but may decode both when that helps.
They treat timed and untimed sending in a unified way, using groups of sub decoders that sort each case as normal, borderline, or a collision. For both settings they derive upper bounds on a combined error measure that mixes wrong decoding, collisions, and missed detection. The bounds give a shared yardstick for random access design.
Catalog record
| CREATOR | Nazanin Mirhosseini and Jie Luo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-17718
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unified Error Analysis for Synchronous and Asynchronous Two-User Random Access Nazanin Mirhosseini and Jie Luo Abstract We consider a two-user random access system in which each user independently selects a coding scheme from a finite set for every message, without sharing these choices with the other user or with the receiver. The receiver aims to decode only user 1’s message but may also decode user 2’s message when beneficial. In the synchronous setting, the receiver employs two parallel sub-decoders: one dedicated to decoding user 1’s message and another that jointly decodes both users’ messages. Their outputs are synthesized to produce the final decoding or collision decision. For the asynchronous setting, we examine a time interval containing L L consecutive codewords from each user. The receiver deploys 2 2 L 2^{2L} parallel sub-decoders, each responsible for decoding a subset of the message-code index pairs. In both synchronous and asynchronous cases, every sub-decoder partitions the coding space into three disjoint regions: operation, margin, and collision, and outputs either decoded messages or a collision report according to the region in which the estimated code index vector lies. Error events are defined for each sub-decoder and for the overall receiver whenever the expected output is not produced. We derive achievable upper bounds on the generalized error performance, defined as a weighted sum of incorrect-decoding, collision, and miss-detection probabilities, for both synchronous and asynchronous scenarios 1 1 1 This work was supported by the National Science Foundation under Grant ECCS-2128569. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation. . I Introduction Random access communication manages uncoordinated and bursty transmissions by relying on pre-defined protocols rather than real-time online coordination [ 1 ] , [ 3 ] . A central challenge in such systems is that a receiver must be prepared to decode a message from any transmitter within a large population of legitimate users. If each user were assigned a unique codebook, identifying an active user would require prohibitively high computational complexity [ 4 ] , [ 12 ] , [ 15 ] . Practical systems therefore employ a limited set of pre-designed signaling schemes, enabling the receiver to decode a message without knowing the sender’s identity in advance, an idea formalized by the unsourced random access (URA) model [ 12 ] . Although recent URA work has been motivated by supporting multi-packet reception (MPR), the standard URA model contains assumptions that are incompatible with this goal. First, URA assumes that user identification (ID) is unnecessary. However, under MPR, when multiple users transmit packet streams concurrently, the receiver cannot properly reassemble messages unless each packet embeds its user ID; this in turn forces distinct effective codebooks and contradicts the single-codebook premise of URA [ 5 ] , [ 6 ] . Second, URA relies on a single, fixed codebook for all users, which inherently limits the number of decodable parallel messages. A codebook optimized for a large number of users must operate at a low rate, leading to poor throughput when only a few users are active [ 9 ] , [ 11 ] . Consequently, any fixed coding scheme, if pre-specified in the physical-layer protocol, is poorly suited for the time-varying traffic conditions of random access. To address these limitations, this paper investigates a semi-unsourced random access model . In this framework, each active user independently selects a coding option from a finite, pre-shared ensemble for every message, without coordinating its choice with the receiver or other users. Code ensembles are unique across active users, enabling the receiver to distinguish active transmitters while allowing each user to dynamically adapt parameters such as rate or power based on sensed channel contention. The receiver, knowing the code ensembles but not the selected indices, must jointly identify the coding options and decode the messages of interest. This is achieved using a bank of parallel sub-decoders. In the synchronous scenario, these sub-decoders implement different decoding strategies for recovering the message of a target user (denoted as user 1), such as treating interference as noise or jointly decoding multiple users’ messages. The final decision combines their outputs to obtain user 1’s decoded message or to declare a collision. We further extend the analysis to an asynchronous scenario to incorporate key practical factors in random access. Protocols such as Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) require users to sense the channel and postpone transmissions when it is busy [ 2 ] , [ 10 ] , leading to deliberate, staggered packet arrivals. Supporting such protocols requires a communication model that accommodates frame-asynchronous codeword transmissions. We therefore analyze a setting in which user transmissions are not aligned in time, ensuring that the proposed framework remains applicable to realistic system designs. II Frame Synchronous Transmission Consider symbol and frame synchronous random multiple access communication over a memoryless channel with two users and one receiver. The channel is modeled by the conditional distribution P_{Y|X_{1},X_{2}} , where Y\in{\cal Y} is the channel output symbol, X_{1}\in{\cal X}_{1} and X_{2}\in{\cal X}_{2} are respectively the channel input symbols from the two users, with {\cal Y} , {\cal X}_{1} , and {\cal X}_{2} being the corresponding alphabets. For notational convenience, define the input vector \mbox{\boldmath$X$}=[X_{1},X_{2}]^{\top} and denote the channel by P_{Y|\mbox{\scriptsize\boldmath$X$}} . Each user is equipped with an ensemble of random blockcodes. A code is denoted by g=[P_{g}(X),r_{g}] , where P_{g}(X) specifies the input distribution and r_{g} is the rate parameter. While codebooks are generated randomly, we assume that their pseudo-random generation algorithms are shared offline with the receiver. If the random seeds (e.g., time and temporary user ID) are available online, the receiver can reproduce the ensemble of codebooks used by the users. Time is slotted, with each slot spanning N channel symbol durations. At the beginning of each time slot, each user selects a code to encode its message and transmits the corresponding codeword. The receiver, unaware of the users’ code selections, searches over possible code combinations and attempts to decode. If the resulting error probability is within a prescribed threshold, the receiver outputs the decoded messages; otherwise, it declares a collision . To be technically specific, consider communication in one time slot. Let (w_{1},g_{1}) and (w_{2},g_{2}) denote the message-code pairs of the two users, where g_{1}\in{\cal G}_{1} and g_{2}\in{\cal G}_{2} . The corresponding codewords are X^{(N)}_{1}(w_{1},g_{1}) and X^{(N)}_{2}(w_{2},g_{2}) . The receiver knows all randomly generated codebooks in {\cal G}_{1} and {\cal G}_{2} , but is unaware of the transmitted messages or code selections. We assume that the receiver is only interested in decoding the message of user 1. Given the received channel output Y^{(N)} , the receiver either outputs an estimated message-code pair (\hat{w}_{1},\hat{g}_{1}) or declares a collision for user 1. For convenience, define \mbox{\boldmath$w$}=[w_{1},w_{2}]^{\top} , \hat{\mbox{\boldmath$w$}}=[\hat{w}_{1},\hat{w}_{2}]^{\top} and \mbox{\boldmath$g$}=[g_{1},g_{2}]^{\top} , \hat{\mbox{\boldmath$g$}}=[\hat{g}_{1},\hat{g}_{2}]^{\top} . The receiver partitions the space of coding vectors g into three disjoint regions: an operation region {\cal R} , an operation margin \widehat{{\cal R}} , and a collision region {\cal R}_{c} . While the receiver does not know g , if \mbox{\boldmath$g$}\in{\cal R} , the receiver attempts decoding; if \mbox{\boldmath$g$}\in{\cal R}_{c} , it attempts a collision report; and if \mbox{\boldmath$g$}\in\widehat{{\cal