{'fraction_non_alphanumeric': 0.03964740602671637, 'fraction_numerical': 0.00730040385212799, 'mean_word_length': 4.16807144290588, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Unsourced Random Massive Access with Beam-Space Tree Decoding

The core requirement of massive Machine-Type Communication (mMTC) is to support reliable and fast access for an enormous number of machine-type devices (MTDs). In many practical applications, the base station (BS) only concerns the list of received messages instead of the source information, introducing the emerging concept of unsourced random access (URA). Although some massive multiple-input multiple-output (MIMO) URA schemes have been proposed recently, the unique propagation properties of millimeter-wave (mmWave) massive MIMO systems are not fully exploited in conventional URA schemes. In grant-free random access, the BS cannot perform receive beamforming independently as the identities of active users are unknown to the BS. Therefore, only the intrinsic beam division property can be exploited to improve the decoding performance. In this paper, a URA scheme based on beam-space tree decoding is proposed for mmWave massive MIMO system. Specifically, two beam-space tree decoders are designed based on hard decision and soft decision, respectively, to utilize the beam division property. They both leverage the beam division property to assist in discriminating the sub-blocks transmitted from different users. Besides, the first decoder can reduce the searching space, enjoying a low complexity. The second decoder exploits the advantage of list decoding to recover the miss-detected packets. Simulation results verify the superiority of the proposed URA schemes compared to the conventional URA schemes in terms of error probability.

reliable access for an increasingly large number of machinetype devices (MTDs) [1], [2]. Different from human-centric communication, the resultant Massive Machine-Type Communication (mMTC) has two distinct features. In particular, only a small number of devices are active in each communication round due to the sporadic activity in mMTC [3]. Besides, MTDs usually transmit small data payloads adopting short-packet signaling [4]. These make traditional grant-based random access schemes generally not very suitable for the mMTC scenario because of their low spectral efficiency and exceedingly long latency [5]. Therefore, the design of reliable and efficient grant-free random access schemes has attracted significant attention recently, where active users transmit pilots and data to the base station (BS) directly without permission granted [6], [7]. In most grant-free random access schemes, a set of pilot sequences that are designated to the users are used for the BS to ensure its accurate user activity detection and channel estimation [8]- [10]. However, this is neither affordable nor feasible in the next generation multiple access (NGMA) scenarios due to the high density, the large number of connections therein, and the frequent collisions that may occur. To tackle the issues, a special type of grant-free random access, the so-called unsourced random access (URA), is introduced in [11], in which users do not transmit preambles, all the potential users share a common codebook, and the BS only needs to decode a list of messages instead of the identities of active users. This scheme can avoid the huge cost of preambles and the extra protocol of collision resolution, thus well meeting the requirements of next generation massive access.
On the other hand, massive or super MIMO technology, in combination with the millimeter-wave (mmWave) technology, have been promoted as two core technological features for the next generation wireless communication system with a witnessed potential to boost the capacity and efficiency. These two underlying key technologies jointly bring additional spatial-domain signal dimension with their excellent intrinsic directivity and proper beamforming, and also result in salient beam-space sparsity due to the lack of scattering in a mmWave MIMO channel [12]- [14]. To further increase the efficiency of the future massive access systems, such spatial-domain resources and properties should be fully explored and exploited. Various multi-user transmission schemes have been proposed to unleash the potential and properties of the beam-space resources, such as the typical works on beam division multiple access (BDMA), which simultaneously serves multiple users via different beams [15]- [17].
However, for grant-free random access, even if the information of the location of all potential users is stored at the BS, the identities of active users are unknown to the BS. Therefore, the beam dimension cannot be directly exploited in the design of the encoding process of an unsourced grant-free random access, which is different from previous works [15]- [17]. Moreover, in a general URA system, the messages of active users are divided into several sub-blocks and transmitted in consecutive sub-slots. As the signals transmitted from active users often experience deep fading, some sub-blocks may be missed by the decoder at the receiver. The loss of any subblock in any sub-slot finally leads to the failure of recovering the corresponding original message. The problem of packet loss is also needed to be solved as it can cause severe decoding performance degradation. Note that the user location information can generally serve as a hint of the indices of the messages originated from it. Therefore, the intrinsic beam division property and salient spatial sparsity in a mmWave MIMO system can provide extra extrinsic information for both multiuser signal separation and multi-sub-block message stitching. This motivates us to exploit the beam space properties to design new URA schemes for next generation multiple access to help the entire system accommodate more active users and improve the decoding performance.

B. Related Works
Y. Polyanskiy first introduced a framework named URA [11]. Specifically, in URA, all the users share a common codebook, and the decoder only needs to decode a list of messages transmitted from the active users. The error probability is defined as the average fraction of mis-decoded messages over the number of active users, including both missed detection and false alarm. It is obvious that the message recovery at the BS can be formulated as a compressed sensing (CS) problem due to the sporadic activity in mMTC, which is similar to the conventional grant-free random access schemes [18], [19]. However, the size of the common codebook grows exponentially with the number of information bits. In practice, even if a short packet is transmitted, the size of information messages is typically at the order of 100 bits, which makes the CS algorithms computationally intractable. In this context, V. K. Amalladinne et al. proposed a coded compressed sensing (CCS) scheme for URA communication [20]. In particular, the messages from active users are first divided into several sub-blocks. Then, a systematic linear code adds redundancy to those sub-blocks. Once this is achieved, each sub-block is mapped into a codeword in a common codebook and transmitted in a certain sub-slot. Then a standard CS algorithm implements the detection of the sub-blocks. Finally, the subblocks transmitted in different sub-slots are stitched together to obtain the original messages. Build upon the findings in [20] and the structure of sparse regression codes (SPARCs), A. Fengler et al. provided an improved inner decoder, and a complete asymptotic error analysis [21].
Apart from the above works, the study of massive multipleinput multiple-output (MIMO) URA has also attracted much attention. A. Fengler et al. extended the URA model of [20] to a block-fading MIMO channel by using a lowcomplexity covariance-based CS (CB-CS) recovery algorithm [22]. Considering the low code rate and spectral efficiency of the CCS scheme, V. Shyianov et al. proposed a new algorithmic solution to solve the massive URA problem by leveraging the rich spatial dimensionality offered by largescale antenna arrays [23]. Besides, without requiring a separate activity detection or channel estimation step, A. Decurninge et al. introduced a structure that allows the receiver to separate the users using a classical tensor decomposition [24]. As URA is a special scheme of grant-free random access, A. Fengler et al. presented a conceptually simple algorithm based on pilot transmission, activity detection, channel estimation, Maximum Ratio Combining (MRC), and single-user decoding [25], which is similar to the existing grant-free random access schemes [3], [18]. The difference is that they use a pool of non-orthogonal pilots where every active user picks one of them pseudo-randomly. Furthermore, X. Shao et al. proposed a unified cooperative activity detection framework for sourced and unsourced random access based on the covariance of the received signals for the sixth generation (6G) cell-free wireless networks [26].

C. Main Contributions
In this paper, we propose a URA scheme with beamspace tree decoding. Specifically, we adopt the CCS scheme [20] suitably to our case and design two beam-space tree decoders, which are based on hard decision and soft decision, respectively. By leveraging the beam division property to assist in distinguishing the sub-blocks transmitted from different users, both decoders can help the system serve more active users. As the discriminating power is improved, the searching space of the solution in the decoding process is reduced, such that the first decoder has low complexity. In addition, notice that any sub-block missed by the CS decoder would finally lead to missed detection, which degrades the decoding performance. To tackle this issue, the second decoder establishes factor graphs at each stage during the decoding process and implements message passing algorithm (MPA) to give each candidate sub-block drawn from the checking relationship a log-likelihood ratio (LLR) value. Then the reliability of every candidate path is calculated by a path metric (PM). At every stage, some reliable paths are kept, and finally, the surviving path is output as the valid message. Even if a sub-block is missed by the CS decoder, it is possible that the path of the original message is reliable and kept. The main contributions of this paper are summarized as follows: • A URA scheme with beam-space tree decoding is proposed for mmWave communication systems in mMTC to accommodate more active users and to improve the system performance. • Two beam-space tree decoders are designed. Both of them can exploit the intrinsic beam division property to improve the decoding performance of the tree decoder by enhancing the discriminating power and helping the system serve more active users. Besides, the first decoder is based on hard decision with low complexity. The second one is based on soft decision and exploits the advantage of list decoding to recover the packet loss, which is the key of the proposed URA scheme. • Simulation results verify that our URA schemes have significantly better performances than existing works.

D. Paper Organization and Notations
The rest of this paper is organized as follows: Section II provides a brief introduction of the considered massive URA system. Section III provides the encoding and decoding process of the considered system. Section IV proposes a beamspace tree decoder with hard decision. Then, Section V designs a beam-space tree decoder with soft decision. Next, Section VI analyzes the performance of the proposed URA scheme. Afterward, Section VII provides extensive simulation results to validate the effectiveness of the proposed algorithm. Finally, Section VIII concludes the paper.
Throughout this paper, we use bold letters to denote matrices or vectors and non-bold letters to denote scalars. We denote the i-th row and the j-th column of a matrix X with the rowvector X i,: and the column-vector X :,j respectively. We denote C A×B by the space of complex matrices of size A×B. We use |·| to denote the absolute value of a complex number, (·) H and (·) T to denote conjugate transpose and transpose, respectively. The l i -norm of an input vector is denoted by · i . |K| c denotes the number of elements of set K. The notation x ∼ CN (µ, δ 2 ) denotes that the random variable (r.v.) x follows the circular symmetric complex Gaussian distribution. O(·) stands for the big-O notation.

II. SYSTEM MODEL
Consider an uplink single-cell cellular network consisting of K total single-antenna users. The BS is equipped with N r antennas and N RF radio frequency (RF) chains such that N RF < N r , as shown in Fig. 1. Due to the sporadic user activity of mMTC, only a small number of K a users are active in a transmisson process, i.e., K a ≪ K total . Each active user has B bits of information to be transmitted in a block-fading channel. According to [12], [14], the channel vector h k from user k to the BS can be written as where P c denotes the total number of clusters and within the p-th cluster there are Q p sub-paths. β p,q and θ p,q denote the gain and the the angle of arrival (AOA) of the q-th sub-path within the p-th cluster. For the uniform linear array (ULA), the N r × 1 array steering vector e(θ) can be expressed as where J(N r ) = {i − Nr−1 2 , i = 0, 1, 2, . . . , N r − 1}, θ ∈ [− π 2 , π 2 ], λ is the signal wavelength, and d is the antenna spacing which is usually half of the signal wavelength.
To overcome the strong path loss in mmWave channels, a beamforming technique should be adopted. However, the BS cannot focus in any specific direction in grant-free random access. The reason is that even if the location of all potential users is stored at the BS, which users are active is not prior information known to the BS. Besides, due to the constraint of hardware implementations and large energy consumption of RF chains, we have N RF < N r . Therefore, many beamforming methods in existing works [27], [28] cannot be applied in our system directly as N RF narrow beams cannot cover the whole beam space. In this paper, we give a beamforming method based on the widely used Discrete Fourier Transform (DFT) based beamforming codebook [27], [28], to overcome the strong path loss of mmWave channels in grant-free random access. Specifically, the DFT based beamforming codework, which is denoted by W, can be writtern as where Consider the process of hardware implementations, the number of antennas is usually a multiple of the number of RF chains. Therefore, the Nr NRF consecutive beamforming vectors can be grouped and summed together to form a new beamforming vector w i , i = 1, 2, . . . , N RF . w i is expressed as where the parameter γ is set to constrain the power of receive beamforming, i.e., w i 2 2 = 1. Then the beamforming matrix W is obtained, where W is written as W = [w 1 , w 2 , . . . , w NRF ] ∈ C Nr×NRF . By applying this beamforming method, the width of every beam is π NRF , thus the N RF beams can cover the whole beam space, which means that the signals coming from all directions can be received by the BS.
In a typical URA scenario, all the users share a common codebook A, which is denoted by A = [a 1 , a 2 , . . . , a N ] ∈ C Lp×N . The power of each codeword a n ∈ C Lp×1 is constrained to 1, i.e., a n 2 2 = 1. Let δ n,k ∈ {0, 1} denote whether user k transmits the codeword a n . δ n,k can be written as δ n,k = 1, active user k transmits codeword a n , 0, otherwise.
After receive beamforming at the receiver, the beam domain channel vector of the active user k is denoted by where z is modeled by a complex circular Gaussian random vector with i.i.d. components, i.e., z ∼ CN (0, σ 2 z I). Then the received signal on the b-th beam can be written as By summarizing all the N RF samples in a transmission block, the received signal can be recast as where The matrix ∆ contains only K a non-zero columns each of which having a non-zero entry.
For the matrix X = ∆H, where H = [h 1 , h 2 , . . . , h K total ] T , the i-th row of such matrix is given as The probability that X i,: is identically zero is given by (1 − 2 −J ) Ka . Since 2 J is significantly larger than K a , the matrix X is row-sparse, which is shown in Fig. 2(a). The reason is that only a small number of users are active due to the sporadic traffic of users, i.e., K a ≪ K total . For the same reason, the matrix X is also row-sparse. Moreover, due to the lack of scattering in mmWave bands, the signal propagates from the transmitter to the receiver through a small number of path clusters. This leads to the sparsity of mmWave massive MIMO channels in the beam domain as well, i.e., the channel vector h k is sparse. Therefore, for the matrix X, the number of non-zero entries of its columns is less than that of X, which is shown in Fig. 2(b). Note that the total number of users K total plays no role in the matrix X. This means that if the matrix X is recovered, only the codeword index is known to the BS, instead of the user's ID, which leads to the so-called unsourced property.
Let L and K a denote the set of the recovered messages at the BS and the set of the active users, respectively. Each active user k ∈ K a expects to transmit B bits of information, i.e., u k = {0, 1} B . The performance in URA is evaluated by the probability of missed detection and false alarm, denoted by p md and p fa respectively, which can be given by: and the error probability of the system is defined as III. PROPOSED URA SCHEME In this section, we first review the studies of the CCS scheme in [20] and then propose a URA scheme. In the CCS scheme, each active user partitions the message into several sub-blocks and adds parity bits. The CS techniques detect the sub-blocks transmitted by active users in all sub-slots. A treebased algorithm then stitched these sub-blocks to recover the original messages.

A. Encoding Process
The transmission strategy includes two encoders: tree encoder and CS encoder. The tree encoder uses a systematic linear block code based on random parity checks to add parity bits to every sub-block. The CS encoder maps each sub-block into a codeword in the common codebook.

1) Tree Encoder
. . , S. Each sub-block s is resized to length J by appending l s = J − b s parity bits, which is obtained by linear combinations of the information bits of the previous sub-blocks. Mathematically, define m as a coded message, then we have where G i,s−1 ∈ {0, 1} bi×ls is a binary matrix. Parity bits are computed using modulo-2 arithmetic and, as such, they remain binary. Every sub-block has the same size b s + l s = J, and the code rate R tree is fixed as , which denote the indices of the codewords in the common codebook A ∈ C Lp×N , where N = 2 J . Then the active user k transmits the consecutive codewords of length L p , i.e., a i k (1) , a i k (2) , . . . , a i k (S) .

B. Decoding Process
The input to the decoder is the sum of the signals transmitted by active users plus noise after receive beamforming. The decoding process also consists of a CS decoder and tree decoder. The conventional CS decoder exploits CS techniques to recover the sub-blocks transmitted from all active users. The tree decoder forms code trees to piece these sub-blocks together to obtain the original messages.
1) CS Decoder: For each sub-slot s, the received signal can be expressed as X s is a row sparse matrix and can be recovered by CS techniques such as Approximate Message Passing (AMP) [29]. For rich-scattering environments, an accurate and widely used statistical model for the actual channel coefficients is the Gaussian model. However, in mmWave communications, the entries H s cannot be approximated by a Gaussian distribution due to the lack of scatterers. Thus, we design a special activity detector for our considered scenario. Specifically, we approximate the unknown prior distribution with Gaussian mixture (GM) [13] and EM-GM-AMP [30] models for activity detection and channel estimation. The coefficients in the i-th column of X s = [x s,1 , x s,2 , . . . , x s,NRF ] are approximated to be i.i.d with marginal pdf where δ(·) is the Dirac delta, ρ is the sparsity rate, and for the k-th GM component, w k , µ k , ν k are the weight, mean, and variance, respectively. The sparsity of the vector is captured by the sparsity rate ρ. The weights, means, and variances can be iteratively learned by the Expectation-Maximization (EM) algorithm.
For each sub-slot s, the CS algorithm outputs the estimation of X s , i.e.,X s . Via maximum-ratio-combining (MRC), the activity detectorã k (s) is defined as where ǫ is a threshold, and η i is expressed as Through the activity detector, the indices of the transmitted codewords in the common codebook A are obtained and collected in the set K s , which is written as K s = {k |ã k (s) = 1, k = 1, 2, . . . , N }. As the relationship between a sub-block and the corresponding codeword is a one-to-one mapping, if a codeword is detected, then the corresponding sub-block can be recovered automatically. The CS Decoder finally outputs the set of the sub-blocks L s = {m k (s) | k ∈ K s } and the cor- Notice that the index k cannot represent the identity of the active user. The information that is known at the BS is that a sub-block m k (s) is transmitted, it comes from a certain user and the estimated channel gain of that user isĥ (s) k . Besides, let |L s | c = K s , K s means the number of the sub-blocks collected in sub-slot s. K s is usually less than K a , i.e., K s ≤ K a , due to the following two reasons: i) Since all users use a common codebook, the messages from different users may share some sub-blocks, which is defined as collision. ii) Due to the poor channel condition and the mistake of the CS decoder, some sub-blocks may be lost. 2) Tree Decoder: The traditional tree decoder in [20] aims to recover the original messages transmitted from all active users by piecing together valid sequences of the sub-blocks drawn from L 1 , L 2 , . . . , L S . As an initial step, the decoder fixes a sub-block in L 1 as the root of a tree and gets the parity bits of the next sub-block by (13). All sub-blocks in L 2 matching the parity bits are attached to the root. This process then moves forward. For every candidate path at stage s, parity bits are computed, and the matching sub-blocks in L s are attached to this path, forming new branches. This continues until the last sub-slot is reached. At this point, every surviving path is output as a valid tree message.
However, the traditional tree decoder has the following two problems: i) The loss of a sub-block from a particular user by the CS decoder finally leads to missed detection of the original message from that user. ii) The parity bits to be attended in every sub-block are fixed, which restricts the maximum active users that the system Notation Parameter Description m i (s) The i-th sub-block detected in the s-th sub-slot The index of the sub-block at stage i in the l-th path f The beam pattern of the sub-block m k (s) A set that contains the indexes of the detected sub-blocks that meet the parity constraints at stage s for the l-th path A set that contains the detected sub-blocks that meet the parity constraints at stage s for the l-th path A set that contains the detected sub-blocks that meet the parity and beam pattern matching constraints at stage s for the l-th path can serve. To tackle the above problems, we propose two beam-space tree decoders, which are based on hard decision and soft decision, respectively. The beam-space tree decoder with hard decision has low complexity, which is suitable to the scenario of massive connectivity. The beam-space tree decoder with soft decision considers the problem of packet loss, which can be applied to the scenario with poor channel condition.

IV. BEAM-SPACE TREE DECODER WITH HARD DECISION
The traditional tree decoder exploits the discriminating power of parity bits to stitch the sub-blocks together to form a valid message instead of the erroneous one. At any stage of a path during the decoding process, the sub-blocks meeting the parity constraints are attached to the path. Besides the valid sub-block, other attached sub-blocks are the ones that cannot be distinguished by the parity bits. These invalid subblocks may finally lead to an erroneous message output by the tree decoder. Notice that in all sub-slots, the sub-blocks sent by different users are received by different beams at the BS according to the location of the users and scatterers. Therefore, the discriminating power of beams can be exploited to distinguish the invalid sub-blocks that meet the parity constraints. By leveraging the beam dimension, the decoding process can be formulated as a problem of path search in the three-dimensional space, which is shown in Fig. 3.
To better describe the decoding process of the beam-space tree decoder with hard decision, Table I is given to summarize the important parameters encountered in this Section. Specifically, define the beam pattern of a sub-block as a set that contains the indices of the beams that receive the sub-block. Then different sub-blocks can be distinguished by their beam patterns. The beam pattern f obey another known Gaussian distribution, i.e., N (µ 2 , δ 2 2 ), where µ 1 > µ 2 and δ 1 > δ 2 . For the gains of the inactive beams, as no signal is received or the signal experiences deep fading, µ 2 is close to zero. For the gains of the active beams, δ 1 is large as the signals experience random fading. Using these two prior distributions, the gains of the beams can be grouped into two classes. And for each class, the mean and variance of the samples are calculated and the prior distributions can be updated, i.e., µ 1 →μ 1 , µ 2 →μ 2 , δ 1 →δ 1 and δ 2 →δ 2 . Then according to these updated distributions, we can give the decision rules of the beam patterns. Specifically, f where . For this proposed beam-space tree decoder, take the decoding process of a certain user for example. At the first stage, a code tree is created and a detected sub-block in the first subslot becomes the root of the tree and forms the first path. The root sub-block is written as m c1 [1] (1) and its beam pattern is f (1) c1 [1] . At later stages, the sub-blocks that meet the parity and the beam pattern matching constraints are kept. By meeting the parity constraints, T s [l] is written as After beam pattern matching, only the sub-blocks in M hd s [l] For each path l:

4:
Get M hd i [l] according to (21). 5: if M hd i [l] is empty then 6: Delete the path l.
where M hd i f (s) j T = 0 means that the sub-blocks m i (1) and m j (s) are received by at least one same beam at the BS, then m i (1) and m j (s) have the probability to be transmitted by the same user. By beam pattern matching, the proposed beam-space tree decoder can reduce the number of surviving sub-blocks in each sub-slot, which improves the discriminating power of the decoder. A practical pruning process of this algorithm is shown in Fig. 4. The sub-block is received by several beams at the BS, which is shown in the beam pattern. For every candidate path at stage s, there are 2 bs candidate sub-blocks in the common codebook A that meet the parity constraints according to the parity bits. A part of them are inactive, while another part of them are discriminated by the beam pattern matching. As shown in Fig  .4, the lines of the 2-nd and the 2 b3 -th candidate sub-blocks change from solid lines to dashed lines, which means that they are deleted, as there is no overlap between their beam patterns and the beam pattern of the root sub-block at stage 1.
Finally, the proposed beam-space tree decoder with hard decision is summarized and given in Algorithm 1. F s is a set that contains the beam patterns of the sub-blocks detected in sub-slot s, where F s is expressed as V. BEAM-SPACE TREE DECODER WITH SOFT DECISION As described above, the CS decoder cannot always detect all the transmitted sub-blocks because the received signals may experience deep fading. The loss of a sub-block by the CS decoder in any sub-slot finally leads to missed detection of the original message. This is because the traditional tree decoder and the beam-space tree decoder with hard decision just stitch the sub-blocks drawn from the output of the CS decoder. At any stage, according to the parity bits, the set of candidate sub-blocks can be obtained. At stage s, the tree decoder keeps the intersection between the candidate set and L s . In this proposed algorithm, we keep all the candidate subblocks and calculate the LLR values of them by implementing the MPA algorithm, which denotes the probability of whether the sub-blocks are transmitted. Then, we define a path metric to calculate the reliability of the consecutive sub-blocks and keep some reliable paths at every stage. Even if a sub-block in a sub-slot is missed, it is possible for the path to be reliable because the path metric measures the reliability of the entire path. Therefore, the purpose of packet loss recovery is achieved.
Specifically, take a user's decoding process for example. At stage s for the l-th path, the number of the candidate subblocks is 2 bs , and these sub-blocks are collected in the set where where k ∈ {1, 2, . . . , N }\T ′ s [l] means that k is in the set . Then a factor graph is formed, taking the corresponding codewords as variable nodes and beam resources as resource nodes. Let K and T denote the number of variable nodes and resource nodes. To exploit the beam division property, the active beams in the beam pattern of the root sub-block form the resource nodes. Then the remaining received signal is defined as Y r For the sake of simplicity, define y t as the received signal at the t-th resource,ĥ k,t as the estimated channel gain between the user transmitting the k-th codeword and the BS at the t-th resource, a k as the kth possible codeword and x k ∈ {0, 1} as a random variable that indicates whether the codeword a k is transmitted. Then Y r s [l] is written as Y r s [l] = [y 1 , y 2 , . . . , y T ], where y t can be expressed as where and ξ k,t = [ξ k,t,1 , ξ k,t,2 , . . . , ξ k,t,Lp ]. To reduce the computational complexity, we resort to Gaussian Approximation (GA) as in [31], and approximate ξ k,t,j as a complex Gaussiandistributed random variable with mean µ ξ k,t,j and variance δ 2 ξ k,t,j , i..e., ξ k,t,j ∼ CN (µ ξ k,t,j , δ 2 ξ k,t,j ). µ ξ k,t,j and δ 2 ξ k,t,j can be expressed as respectively, where L k→t is the log likelihood ratio (LLR) delivered from the k-th variable node to the t-th resource node. Also, L t→k denotes the LLR delivered from the t-th resource node to the k-th variable node, which is written as where p(y t |x k = 1) Besides, L k→t is given as Finally, L k can be expressed as Denote l (n) as the new paths that are split from the l-th path. By implementing MPA, from path l at stage s, we can obtain the LLRs of the candidate sub-blocks in M ′ s [l], which are written as L s [l (n) ], n = 1, 2, . . . , 2 bs . Learning from the way of list decoding [32], we define a path metric to calculate the reliability of the new branches from path l at stage s. Specifically, the PM of the new branch l (n) is written as where L i [l] denotes the LLR of the sub-block at stage i in the path l. The decoder calculates the PM of all the branches from every candidate path and keep some reliable paths at every stage. And at the last stage, the decoder outputs the most reliable path as the recovered message.
However, this scheme is not suitable in the case that collision occurs. As mentioned above, active users select codewords from a common codebook A. Even if the dimension of A is large, collisions may still occur. If the traditional tree decoder fixes a sub-block transmitted by two active users at the first stage, then the decoder finally outputs two valid tree messages. According to [25], we give E{C k,s } as the average number of collisions of k users on consistent s sub-blocks started from the first one, which is written as The collision of more than two users is ignored because the number is usually much smaller than 1. As s grows, the collision can be ignored when k = 2. In other words, it is impossible for the valid messages of the collision users to be the new branches of the same candidate path. However, when the depth of a code tree grows, the LLR of a sub-block has less impact on the PM of the entire path. Therefore, the remaining paths at stage s may all come from the new branches of the most reliable path at stage s − 1, leading to missed detection. Actually, there is no need to keep all new branches from a candidate path because the valid messages of collision users come from different candidate paths. Denote L split as the number of splitting paths, which means that only L split new branches from a candidate path are kept according to the PM. Then for the current stage, keep L save most reliable paths, where L save > L split . This pruning process is shown in Fig. 5.
The number of candidate sub-blocks at stage s is 2 bs , which is equivalent to the process in Fig. 4. At stage s, for the new branches of a path, a factor graph is created to implement the MPA algorithm and give the candidate sub-blocks LLRs. Then the most reliable L split paths are kept, and others are deleted, which is shown in Fig. 5 that the lines of those deleted sub-blocks change from solid to dashed. Finally at stage s, For each path l:

5:
Get M ′ i [l] according to (22 Keep the Lsave most reliable paths and delete others. For each path l: 12: Get M hd i [l] according to (21). 13: if M hd i [l] is empty then 14: Delete the path l. For every pair um, un in the surviving paths: 21: Get Ps(um, un) according to (36). 22: if Ps(um, un) > τ then 23: Keep the more reliable one according to (34) and delete the other. 24: end if 25: Add the remaining paths to L. 26: end for for the 2 bs−1 L split paths, the most reliable L save paths are kept and others are deleted. L split is chosen according to the trade-off between the computational complexity and decoding performance of the decoder.
At the last stage, the number of messages output by the decoder cannot be determined because whether a collision occurs is unknown to the decoder. Notice that the traditional tree decoder outputs all the paths meeting the parity constraints as valid messages. When a collision occurs, the traditional tree decoder outputs several paths as the recovered messages. Besides, more parity bits are pushed towards later stages to reduce the probability of error according to [20]. Thus, we exploit the discriminating power of the parity bits at later stages to output the results of the beam-space tree decoder with soft decision. To summarize, list decoding is implemented at the former S ′ stages to keep the missed sub-blocks, and the sub-blocks that are full of parity bits are exploited to prune the erroneous paths at the latter S − S ′ stages.
However, due to the loss packet recovery, the missed detection rate decreases while the false alarm rate increases. The reason is that some undetected sub-blocks may be kept in the decoding process. Some of them are not transmitted actually, which may lead to false alarm. As the valid messages from collision users are not similar with each other, the invalid messages can be discriminated. Specifically, define a similarity metric P s (u i , u j ), which is denoted by where I(·) is the indicator function, u i and u j are two messages output by a code tree. Calculate every pair of the outputs from a code tree, if P s (u i , u j ) > τ , then keep the more reliable one according to the PM, otherwise keep both, where τ is a threshold. By leveraging the similarity metric, the invalid messages meeting the parity constraints are deleted. The beam-space tree decoder with soft decision is summarized and given in Algorithm 2.

VI. PERFORMANCE ANALYSIS
The performance of our proposed URA system is connected with the reliability of CS techniques in each sub-slot and the efficiency of message stitching across different sub-slots. In the remainder of this section, we ignore the collision that different active users share a sub-block in the first sub-slot.
Take the decoding process of user k for example. Let p cs be the probability that at least one sub-block of user k is not output by the CS decoder, p tree be the probability of error, p md tree be the probability of missed detection, and p fa tree be the probability of false alarm. p tree is written as p tree = p md tree + p fa tree = p cs p md tree|cs + p cs p md tree|cs + p fa tree , where p cs = 1 − p cs , which denotes the probability that the CS decoder is error-free. p md tree|cs denotes the probability that the message of user k is not output by the tree decoder in the case that the CS decoder is error-free.

A. Tree Code Analysis
In this subsection, we analyze the error probability of all the tree decoders. Denote p tree ,p tree ,p tree as the error probability of the traditional tree decoder, the beam-space tree decoder with hard decision and the beam-space tree decoder with soft decision.
For the traditional tree decoder and the beam-space tree decoder with hard decision, it is obvious that p md tree|cs = 1,p md tree|cs = 1 because these two decoders cannot deal with the problem of packet loss. In contrast, p tree|cs = 0,p tree|cs = 0 because there is no missed detection when the CS decoder is error-free. Thus, we use p fa tree ,p fa tree to analyze the performance of the two decoders, respectively.
Let L (j) ,L (j) be the number of erroneous paths of the traditional tree decoder and the beam-space tree decoder with hard decision at stage j, respectively. Define p match as the probability of the event that the intersection between the beam patterns of two sub-blocks are not empty. Assume the signal transmitted from an active user is received by N b beams at the BS. According to (21), the beam pattern matching is implemented by f Then p match is given as p match ≪ 1 because of the lack of scatterers in the mmWave communication system, i.e., N b ≪ N RF . For the beam-space tree decoder with hard decision, we give the expected values ofL (j) in Theorem 1.

Theorem 1:
The expected values ofL (j) , which is denoted by E[L (j) ], can be expressed as where K = K a , j = 2, . . . , S.
Proof: According to [20], for j ≥ 3, E[L (j) ] is written as For j = 2, E[L (2) ] is given as By implementing beam pattern matching, the expected erroneous paths E[L (j) ] at every stage are reduced. For j = 2, E[L (2) ] can be expressed as For j ≥ 3, E[L (j) ] is written as Using (42) as initial condition, E[L (j) ] is rewritten as (39). Based on Theorem 1, we give the upper bound of the false alarm rate of the beam-space tree decoder with hard decision in Corollary 1.
Proof:p fa tree is the probability of false alarm, which means that the number of erroneous paths at the last stage is at least one. Therefore,p fa tree is written as The inequality (45) is obtained by the application of Markov inequality.
For the beam-space tree decoder with soft decision, p md tree|cs < 1 because the decoder considers the problem of packet loss.p md tree|cs > 0 because the decoder keeps limit reliable paths at every stage. As L save grows,p md tree|cs decreases. Besides, notice that the decoder outputs the most reliable path at the last stage. If the recovered message is invalid, then missed detection and false alarm occur simultaneously, i.e., p md tree =p fa tree .

B. CS Analysis
A fundamental limitation of compressed sensing is that the required signal dimension L p to reliably identify a subset of K a transmitted codewords among a set consisting of N codewords in the common codebook scales as L p = O(K a log N Ka ). L p is almost linearly with K a . K a is bounded by K a = O(L p /log N Lp ). In our scenario, although K a active users transmit codewords simultaneously, only a small number of codewords is received by a certain beam at the BS. The average number of codewords received by a beam is given as Denote p b = N b NRF , then K a is bounded by Similarly, L p is bounded by Considering the limitation of both the CS decoder and the tree decoder, we give the upper bound of the number of active users K a in Lemma 1.
Lemma 1: In our scenario, the number of active users, i.e., K a , is bounded by where c 1 is a constant.
Proof: Denote the average number of sub-blocks detected in a certain beam as K v , where K v = p b K a . According to the limitation of the tree decoder given in [33], K v is bounded by

C. Asymptotic Analysis
In this subsection, we study the proposed algorithms in the context of large settings. The asymptotic analysis in [20] shows that the probability of false alarm goes to zero in the logarithmic regime with constant code rate R tree . In this subsection, we analyze the impact of the beam division property on system performance in the asymptotic regime while fixing the number of parity bits. Lemma 2: Fix N RF = αK a , for some α < 1 and consider the number of active users K a → ∞. For the CS decoder, the required signal dimension L p is given as where c 2 is a constant.
Proof: According to (48), L p is rewritten as This completes the proof. Lemma 2 shows that as the number of RF chains and active users increases together while keeping a fixed ratio, the number of active users K a plays no role in the required signal dimension L p . This means that the decoding performance of the CS decoder is guaranteed by exploiting the beam division property while keeping the dimension of the common codebook A. Theorem 2: Fix N RF = αK a , J = log Ka ε for some 0 < α < 1, ε ≪ 1, consider the number of active users K a → ∞ and the number of paths L save → ∞. The decoding performance of the beam-space tree decoder with hard decision and the beamspace tree decoder with soft decision, i.e.,p fa tree andp fa tree , is close to zero.
Proof: For the beam-space tree decoder with hard deci- α . For the sake of similarity, assume 2 −ls = c 3 ≪ 1 for s = 2,3,. . . ,S. Then E[L S ] is approximated as where c 4 is a constant. According to Corollary 1,p fa tree is rewritten as For the beam-space tree decoder with soft decision, let the number of paths L save → ∞. At every stage, although 2 bs → ∞ sub-blocks are drawn by the checking relationship, most of the new paths are not reliable. Only p match K a + 1 → As L save → ∞, the valid path is reliable and kept. At the last stage, the valid path has a high probability of being the most reliable path according to the PM and being output by the decoder as a result.
It can be seen from Theorem 2 that in the regime, the decoding performance of the beam-space tree decoder with hard decision and the beam-space tree decoder with soft decision is guaranteed by exploiting the beam division property.

D. Computational Complexity Analysis
We denote C tree ,C tree ,Ĉ tree as the computational complexity of the traditional tree decoder, the beam-space tree decoder with hard decision and the beam-space tree decoder with soft decision. For the sake of simplicity, let K be the candidate subblocks in every sub-slot and ignore the collision. According to [20], the expected computational computational complexity of the traditional tree decoder, i.e., E[C tree ], is given as The computational complexity of the beam-space tree decoder with hard decision, i.e., E[C tree ], is written as Therefore, the beam-space tree decoder with hard decision has low computational complexity. For the beam-space tree decoder with soft decision, the computational complexityĈ tree is given aŝ where 2 bj and N b are the number of variable nodes and resource nodes of the factor graph, I max is the max number of iterations of MPA.
VII. NUMERICAL RESULTS In this section, we investigate the performance of our proposed scheme in terms of error probability. We consider a simulation scenario where the BS employs a ULA antenna array with N r = 256, and the RF chains are set to N RF = 16. The multipath channel consists of P c = 3 clusters each of which containing Q p = 10 sub-paths. It is assumed that the location of users obeys a two-dimensional Poisson distribution. The transmit power is fixed as P = 20 dBm for all users. For the tree code scheme, B = 94 bits of information are split into S = 32 sub-blocks with length J = 10 bits. Data profile and parity profile are given as [10, 3, . . . , 3, 0, 0, 0] and [0, 7, . . . , 7, 10, 10, 10], respectively. For the beam-space tree decoder with soft decision, L save = 24, L split = 8. As a reference, we compare the proposed beam-space tree decoders with the traditional tree decoder [20] and the CB-CS algorithm [22]. For the sake of simplicity, in the following figures, TD means tree decoder, HD means hard decision, and SD means soft decision.  The difference between the tree decoder (beam domain) and the tree decoder (spatial domain) is whether the tree decoding process is performed after receive beamforming. Comparing these two algorithms, we can see that the decoding performance is significantly improved after receive beamforming because the detection performance of CS techniques is improved by exploiting the sparsity of beam domain channel and the beamforming gain. Besides, at the BS the signals are received after beamforming, which means that the dimension of the received signals is determined by the number of RF chains instead of the number of antennas. Therefore, the high dimension of antennas can not be exploited by the CB-CS algorithm in mmWave scenarios. In addition, there is a gap between the beam-space tree decoder with hard decision and the traditional tree decoder (beam domain). The reason is that getting accurate beam patterns of the sub-blocks, which means that whether the signal is received by every beam at the BS should be accurately determined, is harder than the activity detection of these sub-blocks. Therefore, the beam patterns of the sub-blocks obtained by (18) may not always be accurate, resulting in a decrease in the decoding performance. Besides, it is observed that for the considered E b /N 0 , the beam-space tree decoder with soft decision achieves the best performance. Such advantages come from the fact that this algorithm considers the problem of packet loss.  Initially, in the regime with a few number of active users, the error probability of all algorithms increases slowly. However, when the number of active users continues to increase, the error probability of the tree decoder increases sharply to 1, which means that the tree decoder cannot discriminate and stitch the valid sub-blocks when the number of active users is large. Actually, allocating more parity bits can help the traditional tree decoder accommodate more active users while the computational complexity of the CS techniques and the tree decoders grows. It is observed that the error probability of the two beam-space tree decoders increases slowly when the number of active users is large. Such an advantage of the beam-space tree decoders mainly comes from enhancing the discriminating power of the decoder by exploiting beam resources.
Then we study the impact of the number of parity bits on the system performance. For J = 11, data profile and parity profile are given as [11, 3, . . . , 3, 0, 0, 0] and [0, 8, . . . , 8,11,11,11], respectively. In Fig. 8, we compare the performance of the tree decoder (beam domain), the beam-space tree decoder with hard decision, and the beam-space tree decoder with soft decision. It is observed that allocating more parity bits can improve the decoding performance, which is seen in Fig. 8(a). Notice that as the number of active users grows, the error probability of the tree decoder and the beam-space tree decoder with hard decision increase sharply to 1. This is because the number of parity bits added to sub-blocks is fixed, the max number of active users the system can serve is limited. Once beyond the limit, the decoders cannot recover   any original message of the active users, thus p md = 1, p fa = 0. As the beam-space tree decoder with hard decision exploits the beam division property, more active users can be served by the system. For the beam-space tree decoder with soft decision, the number of candidate sub-blocks to be kept is determined by the list numbers, not the parity bits. Therefore, the decoder is implemented successfully as the number of active users is sufficiently large. Besides, Fig. 8(b) shows that the missed detection rate of the tree decoder (beam domain) and the beam-space tree decoder with hard decision decreases slowly as the number of parity bits increases. This is because these two algorithms do not deal with the problem of packet loss. Besides, as the number of parity bits is increased, the discriminating power of the tree decoder is improved. Therefore, the false alarm rate of the tree decoder (beam domain) decreases, which is shown in Fig. 8(c). Since the beam-space tree decoders exploit beam resources to improve the discriminating power, there is no false alarm when J = 11.  The total spectral efficiency is calculated by KaB LpS . As the number of observations controls the spectral efficiency, the code length L p is set as the axis. It can be seen that as the spectral efficiency increases, L p decreases, and the error probability increases. The reason is that as fewer observations are obtained, the performance of activity detection and channel estimation decreases.
Next, we evaluate the decoding performance with different active users when the BS is equipped with different antennas and RF chains in Fig. 10. It can be observed that as the number of antennas and RF chains grows, the error probability decreases, and more active users can be served. The reason is that the BS can generate more narrow beams for the receive beamforming simultaneously, which means that the spatial resolution of the beams is improved, and the beam division property can be exploited completely. Besides, Fig. 11 plots the increasing number of users and antennas together while keep a fixed ratio, i.e., Ka Nr = 1 2 . It can be observed that as the number of users and antennas increases, the error probability increases slowly. The reason is that although the number of users increases, more antenna array gain is obtained, and the beam division property is exploited. For the conventional tree decoder, as the beam division property is not exploited, the error probability increases more rapidly.

VIII. CONCLUSION
An URA scheme with beam-space tree decoding under the framework of bit partition and slotted transmission was proposed in this paper. Specifically, we designed two beamspace tree decoders, which are based on hard decision and soft decision, respectively. Both of them exploit the intrinsic beam division property to improve the system performance and help the system serve more active users. Besides, the first decoder can reduce the solution searching space and has low complexity, while the second decoder exploits the advantage of list decoding to recover the miss-detected packets. Simulation results validated that our proposed URA scheme was superior with respect to error probability.
The beam division property is an intrinsic property in mmWave communication systems due to channel propagation. Therefore, this property exploited by our proposed decoders can also be exploited by other schemes under the scenarios of NGMA to help the system serve more users and improve the system performance.