Open AccessArticle

Patterned Reed–Muller Sequences with Outer A-Channel Codes and Projective Decoding for Slot-Controlled Unsourced Random Access

Wenjiao Xie

and

Huisheng Zhang

School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710129, China

Author to whom correspondence should be addressed.

Sensors 2023, 23(11), 5239; https://doi.org/10.3390/s23115239

Submission received: 19 April 2023 / Revised: 20 May 2023 / Accepted: 30 May 2023 / Published: 31 May 2023

(This article belongs to the Special Issue Sustainable Solutions for 6G-Enabled Internet of Things Networks)

Download

Browse Figures

Versions Notes

Abstract

We propose a novel slot-pattern-control based coded compressed sensing for unsourced random access with an outer A-channel code capable of correcting t errors. Specifically, an RM extension code called patterned Reed–Muller (PRM) code is proposed. We demonstrate the high spectral efficiency due to its enormous sequence space and prove the geometry property in the complex domain that enhances the reliability and efficiency of detection. Accordingly, a projective decoder based on its geometry theorem is also proposed. Next, the “patterned” property of the PRM code, which partitions the binary vector space into several subspaces, is further extended as the primary principle for designing a slot control criterion that reduces the number of simultaneous transmissions in each slot. The factors affecting the chance of sequence collisions are identified. Finally, the proposed scheme is implemented in two practical outer A-channel codes: (i) the t-tree code and (ii) the Reed–Solomon code with Guruswami–Sudan list decoding, and the optimal setups are determined to minimize SNR by optimizing the inner and outer codes jointly. In comparison with the existing counterpart, our simulation results confirm that the proposed scheme compares favorably with benchmark schemes regarding the energy-per-bit requirement to meet a target error probability as well as the number of accommodated active users in the system.

Keywords:

block fading channels; machine-to-machine communications; unsourced random access; geometry theory; projective decoder; error correcting codes; complex Reed–Muller codes

1. Introduction

The continuous evolution of massive machine type communication (mMTC+) [1] will still be one of main use cases of sixth-generation (6G) wireless networks [2,3]. In this context, the battery-limited terminals sporadically connected to the network grow exponentially and they are expected to send short information packets for low transmission latency [4,5].

The most promising way is to address grant-free transmission, i.e., the device transmits the packet without requiring coordination among users [6,7,8]. The “Sourced random access (SRA)” case refers to assigning separate dictionaries to individual users, i.e., employing different encoders for users [9,10]. Due to a large number of users, the SRA mechanism will result in exorbitant complexity as the AP does not know which decoder to utilize and is forced to try all possibilities. Therefore, employing the same coding protocol for all users is the most promising approach. Such schemes are known as “Unsourced random access (URA)” [11]. By using this mechanism, AP is not required to recognize active users’ identities and all users are allowed to share the same codebook, avoiding complex identity assignment and authentication processes among a large number of users. Additionally, the access and transmission performance of the overall system are analyzed based on the per-user probability of error (PUPE) for all active users.

Since then, several papers have been published demonstrating fundamental limits for various massive access channel models and configurations (see, e.g., [12,13,14]). Many transmission schemes have been proposed to achieve performance as close to these fundamental limits as possible [15,16,17].

The Background for Unsourced Random Access with Outer A-Channel Codes: The URA benefited greatly from the outer A-channel codes [18,19], e.g., the coded compressed sensing is a divide-and-conquer scheme that uses random inner codes of capacity

2^{G}

concatenated with an outer G-ary A-channel code, in which a tree code is a type of A-channel code designed for this purpose. This flexible structure made it easy to adapt to new channel models. Several subsequent studies on URA (e.g., [16,20,21,22,23,24]) made use of an outer A-channel code.

The field of study [19] for a tree code as the outer A-channel code is extended in paper [25], which leverages the approximate message passing (AMP) strategy in conjunction with sparse regression codes. The coded compressed sensing (CCS) strategy is further improved in [16], where the inner AMP decoder and the outer tree decoder are authorized to exchange soft information via a shared message-passing protocol. By using the same sensing matrix as in [19], the authors reduce complexity in [26]. The paper [27] proposes a coded demixing strategy to facilitate the joint detection of high dimensional sparse signals concerning different bases.

The Background for Reed–Muller Sequence: The second-order Reed–Muller-related codebook construction schemes have been widely utilized in compressed sensing [28,29,30,31]. For instance, in [28], the complexity of the chirp reconstruction is dependent on the number of measurements rather than the signal dimension since RM sequences are utilized to build deterministic measurement matrices. In [29], the idea of using a measurement matrix whose columns are codewords of a linear code is proposed. In addition, a quadratic reconstruction algorithm that takes advantage of the multivariable quadratic functions is further employed. According to [31], full-duplex compressed neighbor discovery is supported by on–off RM signatures. Additionally, RM sequences are regarded as excellent options for massive access in mMTC due to their large codebook capacity and ability to be used in low-complexity random access [32]. The non-orthogonal RM sequences are used as signatures for active device detection [33] which is the grant-based access scheme that suffers from low access efficiency and high signaling overhead in mMTC. As described in [34], an incremental massive random access scheme is proposed. Furthermore, RM sequences leveraged as the inner codes for the URA scheme are proposed in [35,36] and the tree coding is used for stitching messages in packetized and slotted transmissions.

In this paper, based on the “patterned” property of the proposed patterned Reed–Muller (PRM) sequences, we design a slot-pattern-control (SPC) criterion that corresponds one-to-one to an information segment to construct the slot occupation guideline for each active user. We then partition the users’ messages into several sub-blocks and add the same SPC segment in each block as a prefix to make up the input signal of the inner encoder. On this basis, each sequence related a single codeword from a proposed common codebook called patterned Reed–Muller codes. For recovering the PRM sequences received at the receiver, an algorithm exploiting the geometry of PRM sequences is proposed. Moreover, the outer tree code is replaced with an error-correcting code and the codewords with a distance at most t from the channel output are recovered by outer codes.

1.1. Main Contributions of the Paper

To summarize, our contributions are listed as follows:

This paper designs a common codebook that optimizes URA energy efficiency performance by embedding zero bits in the second-order Reed–Muller sequences in accordance with a specific principle, which is the simplified version proposed by Pllaha et al. (2022) [37,38,39], and we denote it as a patterned Reed–Muller (PRM) code.
Instead of the available common codebook that uses Reed–Muller (RM) properties in the binary domain, we explore its exclusive natures in the complex domain. In detail, we prove the algebraic and geometric properties of the second-order Reed–Muller sequence in the complex field, and related theories for PRM codes are also proven.
A projective decoder is proposed for the PRM sequence and the fundamental theory for proposing such precise detection algorithm stems from its geometry property.
The dependencies enlightened by the patterned property of PRM sequences prescribe how the information messages are mapped to the elements in a pool of slot-pattern controls (SPCs). The information message guides a single user to select the corresponding SPC from the pool and users randomly select SPCs as their transmission criteria to reduce collision chance.
The factors affecting the reliability of the PRM detection are discussed. As a result of our simulations, we conclude that the proposed slot-pattern-control PRM-based scheme offers significant advantages in terms of error probability.
Instead of the outer tree code proposed by Amalladinne et al. (2020) [19], we couple the proposed slot-pattern-control PRM-based scheme with two practical list recoverable codes. The first is a modification of the tree code called t-tree code and the second is based on the Reed–Solomon codes and Guruswami–Sudan list decoding algorithm. The optimal setups are determined to minimize SNR by optimizing the inner and outer codes jointly. In regimes of practical interest, the proposed scheme compares favorably with benchmark schemes regarding the energy-per-bit requirement to meet a target error probability as well as the number of accommodated active users in the system.

In Section 2, we introduce the system model. Several theorems of RM for the complex field are proved in Section 3. In Section 4, we construct the proposed PRM sequence and design a single-user decoding algorithm based on a proven theorem. Section 5 provides a high-level description of the transmitter architecture, decoding procedures and a proposed slot-pattern-control pool design, followed by Section 6 on the factors influencing the PRM detection ability. The performance of the proposed transmission schemes is assessed via numerical simulations in Section 7. Section 8 concludes the paper.

1.2. Notation

This paper uses lowercase letters to represent scalars. Column vectors and matrices are denoted by boldface letters in lower case and upper case, respectively. We represent

F_{2}^{m}

as the binary field. Sym

(m; 2)

denotes the group of binary

m \times m

symmetric matrices. We will denote matrices (resp., vectors) with upper case (resp., lower case) bold letters.

A^{T}

will denote the transpose and

A^{- T}

will denote the inverse transposed

span (A)

column space and the row space of

A

. Since all our vectors are columns, we will typically deal with column spaces.

I_{m}

will denote the

m \times m

matrix (complex or binary).

U (N)

denotes the set of unitary

N \times N

complex matrices and H will denote the conjugate transpose of a matrix. The length N column vectors of all zeros and all ones are denoted as

0_{N}

and

1_{N}

, respectively. We use

A = {[a_{i}]}_{i = 1}^{I}

to represent the I-element vector made up of the elements

a_{i}

, where

i = 1, \dots, I

. The result of appending the column vector

B_{1} \in C^{T_{1} \times 1}

B_{2} \in C^{T_{2} \times 1}

has the form of

B = [B_{1}; B_{2}] \in C^{(T_{1} + T_{2}) \times 1}

0^{N}

is an all-zero column vector of length N.

0_{Υ \times Υ}

denotes a full-zero matrix of size

Υ \times Υ

. We denote by

CN (0, I_{N})

a complex standard normal random vector. The symbol

|\cdot|

is the cardinality of a set.

O (\cdot)

represents the complexity order.

E [\cdot]

denotes the expectation operator and

D [\cdot]

denotes the variance operator.

\Pr [e]

means a probability of the event e. The vector

v_{n - 1}

is the decimal number

(n - 1)

, while conversely we have that

decimal (v_{n - 1}) = n

, i.e.,

decimal (\cdot)

converts the binary vector to the corresponding decimal number and then increases the result by one.

2. System Model

In this paper, let us reuse the system proposed in [19,36]. Users are always silent in the absence of information to transmit. There are K potential users in the system and

K_{a}

components are active, which typically means

K_{a}

is far less than K in the mMTC scenario due to the infrequent activity of users.

K_{a}

users transmit codewords drawn at random from a common codebook containing entries derived from a G-ary alphabet

[G] = \{1, \dots, G\}

over T channel uses. The relationship between inputs and outputs of a channel over H slots is expressed as

Y = ⋃_{k = 1}^{K_{a}} [C_{k, 1}, \dots, C_{k, H}],

(1)

where

C_{k, h} \in [G]

represents the inner codeword sent by user k in the m-th message segment,

1 \leq h \leq H

, and the length of the codeword is

N = 2^{m}

The expectation is that each active user will send B bits of information to the receiver utilizing T channel uses. Specifically, the set

{W_{1}, W_{2}, \dots, W_{K_{a}}}

for B-bit messages, which contain all messages sent by

K_{a}

users, are encoded into H-length G-ary A-channel codes, where

W_{k} \in [N]

[N] = \{1, \dots, N\}

and

N = 2^{B}

. We then define the URA code for the A-channel as:

encoder E_{n} : [N] \mapsto {[G]}^{H};

decoder \hat{D} : \overset{N_{T} times}{\overset{︷}{[\{⋃_{k = 1}^{K} (\binom{[G]}{k})\}, \dots, \{⋃_{k = 1}^{K} (\binom{[G]}{k})\}]}} \mapsto (\binom{[N]}{K}),

where K is the number of simultaneous appearances in each block,

K < K_{a}

. We require

{∥E_{n} (W)∥}_{2}^{2} \leq H N P

, which means the power limitation. In this article, a proposed slot-pattern-control technique is used to carry out the packetized and slotted transmission; hence, the H-length outer codes are distributed throughout

N_{T}

slots and

T = N \cdot N_{T}

At the receiver, after detecting codewords in each slot, the A-channel decoder is used to couple the divided information chunks. Here, a quasi-static Rayleigh fading channel is considered, in which the channel remains constant inside a single slot but fluctuates independently between slots. We assess performance from the perspective of messages and use the miss detection rate (MDR) and the false-alarm rate (FAR) as the primary indicators, which are given as

P_{e} ≜ \frac{1}{K_{a}} \sum_{k \in K_{a}} \Pr [W_{k} \notin \hat{D} (Y)],

(2)

and

P_{f} ≜ \Pr [\hat{D} (Y) \ {W_{k} | k \in K_{a}} \neq \emptyset],

(3)

respectively, where

K_{a} = {1, \dots, K_{a}}

. Energy efficiency is of critical importance for the mMTC scenario; our goal is to minimize the energy per bit (

E_{b} / N_{0} = H N P / B

) spent by each user.

3. Reed–Muller Sequences

The existing unsourced random access systems using Reed–Muller sequences primarily investigate the RM features in the binary domain [35]. In reality, the complex RM sequences are unit norm vectors on

C^{N}

, which exhibit subtle algebraic and geometric properties. In this section, we present a novel direction for comprehending the RM sequence by revealing its particular theories in the complex domain, which offer the theoretical bases for constructing RM expansion codes.

3.1. Binary RM Codes

For an

m \times m

binary symmetric matrix

P \in Sym (m; 2)

and a binary vector

B \in F_{2}^{m}

, the n-th entry of the complexed RM sequence is denoted as

C_{P, B} (n) = \frac{1}{\sqrt{N}} i^{2 v_{n - 1}^{T} B + v_{n - 1}^{T} P v_{n - 1}}, n = 1, \dots, N,

(4)

where n is the decimal expression of binary vector

v_{n - 1}

, i.e.,

decimal (v_{n - 1}) = n

. In other words, the RM sequence in (4) is an algebraic equation associated with the time index

v

, where n in

C_{P, B} (n)

represents the decimal time index and

v_{n - 1}

is the corresponding binary expression. To facilitate presentation, the index-related RM is illustrated via a simple example and we write out a basis of RM

(3, 2)

as follows [40,41]:

\begin{matrix} (v_{1}, v_{2}, v_{3}) & (1, 1, 1) & (1, 1, 0) & (1, 0, 1) & (1, 0, 0) & (0, 1, 1) & (0, 1, 0) & (0, 0, 1) & (0, 0, 0) \\ A = {2, 1} & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ A = {3, 1} & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ A = {3, 2} & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ A = {1} & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ A = {2} & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ A = {3} & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ A = \emptyset & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}

The first row lists all indices

v \in F_{2}^{m}

for each bit position within a codeword, which can also be denoted as

(decimal (1, 1, 1), decimal (1, 1, 0), \dots, decimal (0, 0, 0))

or directly

(8, 7, \dots, 1)

. Binary Reed–Muller codes consist of the evaluation vectors of multivariate polynomials over the binary field

F_{2}

. The codeword RM

(m, r)

with parameters m and r consist of all the evaluation vectors of polynomials with m variables and degree no larger than r. The second to the last rows are polynomials of degree two, degree one and zero, respectively. It is noteworthy that the first-order part coincides with the first line (bit position indices) and the above basis is the generation matrix for RM

(3, 2)

3.2. Geometry of Complex RM Sequence

Complex RM sequences are made of two parts: a mask sequence [28]

m_{S} = {[i^{v^{T} P v}]}_{v \in F_{2}^{m}}

and a Hadamard sequence

h_{B} = {[i^{2 v^{T} B}]}_{v \in F_{2}^{m}}

. Overall, the exponents in (4) are evaluations (modulo 4) of degree 2 polynomials in m variables and therefore the collection is just an exponentiated second-order Reed–Muller code. However, from a geometric perspective, it is not sufficient to consider only the first- and second-order polynomials. This subsection offers a novel interpretation of RM in the complex domain.

As a matter of fact, for Pauli matrices

E (x, y)

with

x, y \in F_{2}^{m}

, the absolute value of

C_{P, B}^{H} E (x, y) C_{P, B}

cannot exceed 1 (see more details in [42,43,44]). To proceed, we define a notion associated with shift

e_{r}

for the Reed–Muller sequence as

C_{P, B}

F_{A} (y) = C_{P, B}^{H} E (e_{r}, y) C_{P, B},

(5)

where

0 \leq r \leq m

e_{r}

is the standard basis vector in m-dimensional space. To conclude, we summarize the

C_{P, B}

related geometry theorem in Theorem 1.

Theorem 1.

C_{P, B}^{H} E (e_{r}, y) C_{P, B}

is equivalent to implementing a Walsh–Hadamard transform (WHT) on RM sequence

C_{P, B}

Proof of Theorem 1.

The formula

C_{P, B}^{H} E (e_{r}, y) C_{P, B}

can be extended as follows:

\begin{matrix} \begin{matrix} F_{A} (y) & = C_{P, B}^{H} E (e_{r}, y) C_{P, B} \\ = C_{P, B}^{H} \cdot [i^{e_{r}^{T} y} \sum_{a \in F_{2}^{m}} {(- 1)}^{a^{T} y} e_{a + e_{r}} \cdot e_{a}^{T}] \cdot C_{P, B} \\ = \frac{i^{e_{r}^{T}} y}{N} \cdot \sum_{a \in F_{2}^{m}} C_{P, B}^{H} \cdot [{(- 1)}^{a^{T} y} \cdot D (e_{r}, 0) e_{a} \cdot e_{a}^{T}] \cdot C_{P, B} \\ = \frac{i^{e_{r}^{T} y}}{N} \sum_{a \in F_{2}^{m}} [C_{P, B}^{H} \cdot D (e_{r}, 0)] \cdot [D (0, y) \cdot C_{P, B}] \\ = \frac{i^{e_{r}^{T} y}}{N} \sum_{a \in F_{2}^{m}} \bar{C_{P, B} (a + e_{r})} \cdot {(- 1)}^{y^{T} a} \cdot C_{P, B} (a) \\ = \frac{i^{e_{r}^{T} y}}{N} \sum_{a \in F_{2}^{m}} {(- 1)}^{{(P e_{r} + y)}^{T} a}, \end{matrix} \end{matrix}

(6)

where

N = 2^{m}

. The result of (6) completes the proof. □

In fact, the Hadamard transformations of “shift”, “multiplication” and “shift and multiplication” in Equation (6) show that the process is actually a translation of the “shift-and-multiply” technique into the operation of the Pauli matrices. In essence, this transformation constitutes the difference between the traditional binary RM sequence and the complex one.

The complex RM sequence

C_{P, B}

still has the following theorem.

Theorem 2.

There is a relationship between between

P_{r}

and

B_{r}

as follows:

E (e_{r}, P_{r}) C_{P, B} = {(- 1)}^{B_{r}} \cdot C_{P, B},

(7)

where

P_{r} = P \cdot e_{r}

and

B_{r}

is the

r

-th element of vector

B

Proof of Theorem 2.

\begin{matrix} \begin{matrix} E (e_{r}, P_{r}) C_{P, B} & = [i^{e_{r}^{T} P_{r}} \sum_{v \in F_{2}^{m}} {(- 1)}^{P_{r}^{T} v} \cdot e_{v + e_{r}} \cdot e_{v}^{T}] [\sum_{a \in F_{2}^{m}} i^{a^{T} Pa + 2 a^{T} B} \cdot e_{a}] \\ = \frac{i^{P_{r, r}}}{\sqrt{N}} \sum_{v \in F_{2}^{m}} {(- 1)}^{P_{r}^{T} v} \cdot i^{v^{T} P v + 2 v^{T} B} \cdot e_{v + e_{r}} \\ = \frac{i^{P_{r, r}}}{\sqrt{N}} \sum_{v \in F_{2}^{m}} {(- 1)}^{{(e_{r} + v)}^{T} P_{i}} \cdot i^{{(e_{r} + v)}^{T} P (e_{r} + v) + 2 B^{T} (e_{r} + v)} \cdot e_{v} \\ = \frac{1}{\sqrt{N}} \sum_{v \in F_{2}^{m}} i^{2 e_{r}^{T} P_{r} + 2 P_{r}^{T} v + e_{r}^{T} P e_{r} + e_{r}^{T} P v + v^{T} P e_{r} + v^{T} P v + 2 B_{i} + 2 B^{T} v} \cdot e_{v} \\ = \frac{1}{\sqrt{N}} \sum_{v \in F_{2}^{m}} i^{2 B_{r}} i^{3 P_{r, r}} i^{4 v^{T} P e_{r} + 2 B^{T} v + v^{T} P v} \cdot e_{v} \\ = \frac{{(- 1)}^{B_{r}}}{\sqrt{N}} \sum_{v \in F_{2}^{m}} i^{v^{T} P v + 2 B^{T} v} \cdot e_{v} \\ = {(- 1)}^{B_{r}} \cdot C_{P, B} \end{matrix} \end{matrix}

(8)

where

P_{r, r} = e_{r}^{T} P_{r} = e_{r}^{T} P e_{r}

and

B_{r} = e_{r}^{T} B

. This completes the proof. □

Pauli matrices are in one-to-one correspondence to a set of half-space projection operators. Thus, from an estimated

E (e_{r}, P_{r})

, a projection operator

λ_{R M, ϖ}^{(r)} = \frac{[I_{N} + ϖ \cdot E (e_{r}, P_{r})]}{2},

(9)

can be constructed, for which we have

λ_{R M, ϖ}^{(r)} C_{P, B} = \{\begin{matrix} C_{P, B}, & if ϖ = {(- 1)}^{B_{r}}, \\ 0, & if ϖ \neq {(- 1)}^{B_{r}} . \end{matrix}

(10)

4. Expansion of Complex Reed–Muller Sequences

In this section, an alternative code of binary subspace chirp (BSSC) in [39] is proposed, which simplifies the number of subspaces in

F_{2}^{m}

, preserves the “patterned” behavior and ultimately exhibits less interference than BSSCs. A geometric feature of the proposed code is also demonstrated, which provides the theoretical basis for the proposed decoding algorithm. We finally propose a projective decoder based on its geometry theorem.

4.1. Patterned Reed–Muller Codes

The novel patterned Reed–Muller (PRM) codeword introduces a new parameter

Υ

that signifies all possible subsets of m. Specifically, all potential subsets for m of rank

Υ \in {1, 2, \dots, m}

are denoted as

χ \subseteq [m]

. Thus, the possible count

|χ| = (\binom{m}{Υ})

varies with variable

Υ

. The first-order item of the RM generation matrix (mentioned in Section 3.1) is employed here as the position indices

v \in F_{2}^{m}

. In order to retrieve the PRM sequence, it is necessary to manipulate the position indices in a precise manner: first, place “0” bits in all positions but

I_{χ} v + \tilde{I_{χ}} {B |}_{Υ + 1}^{m}

, where

{B |}_{Υ + 1}^{m}

denotes the sub-sequence of post-

(m - Υ)

bits of vector

B

and

I_{χ}

is a matrix of size

m \times Υ

with column vectors

e_{χ (1)}, e_{χ (2)}, \dots, e_{χ (Υ)}

, and

e_{χ (r)}

is the unit vector with non-zero at the r-th position(

1 \leq r \leq Υ

). Accordingly, matrix

\tilde{I_{χ}}

is of size

m \times (m - Υ)

with column vectors

e_{\tilde{χ} (1)}, e_{\tilde{χ} (2)} \dots e_{\tilde{χ} (m - Υ)}

, where

\tilde{χ}

is the complement set of

χ

in m. Second, a sequence RM

(Υ, 2)

is then added to the above non-zero positions and written as follows:

C_{\hat{P}, B, I_{χ}} (v) = \{\begin{matrix} \frac{1}{\sqrt{2^{Υ}}} i^{2 w^{T} {B |}_{1}^{Υ} + w^{T} \hat{P} w}, & if v = I_{χ} w + \tilde{I_{χ}} {B |}_{Υ + 1}^{m}, \\ 0, & otherwise, \end{matrix}

(11)

where

w \in F_{2}^{Υ}

and

\hat{P}

is the symmetric matrix for RM

(Υ, 2)

As a matter of fact, the PRM sequence simply reduces the subspace matrix

H_{τ}

I_{χ}

; we refer the reader to [39] for more details. Let us further define the matrix

Q = [I_{χ} \tilde{I_{χ}}]

and write (11) in the following format:

C_{\hat{P}, B, I_{χ}} (v) = \frac{{(- 1)}^{wt (B |_{Υ + 1}^{m})}}{\sqrt{2^{Υ}}} i^{2 B^{T} (Q^{- 1} v) + {(Q^{- 1} v)}^{T} P (Q^{- 1} v)} \cdot [ϕ (B, Q^{- 1} v, Υ)],

(12)

in the case of

{B |}_{Υ + 1}^{m} = Q^{- 1} {v |}_{Υ + 1}^{m}

ϕ (B, Q^{- 1} v, Υ)

equal to 1.

We now depict the PRM sequence with a toy example before concluding its general rule. Let

m = 4

, the vector

B = [0101]

and matrix

S = [\begin{matrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{matrix}]

are fixed; on this basis, three different dimensional spaces of

Υ = 1, Υ = 2

and

Υ = 3

F_{2}^{m}

with the corresponding subsets

χ \in {1}

χ \in {12}

and

χ \in {124}

are substituted into (11). The resulting sequences are depicted in Figure 1.

We conclude the PRM sequences with the following properties:

The evidence demonstrates that, given a sequence of length $N = 2^{m}$ , PRM codes may increase the origin capacity of ${\sqrt{N}}^{{log}_{2} N + 3}$ while maintaining the code distance and the cardinality of the PRM set $Γ$ is equal to

$\begin{matrix} | Γ | = \sum_{Υ = 1}^{m} (\binom{m}{Υ}) \cdot 2^{m} \cdot 2^{\frac{Υ (Υ + 1)}{2}}; \end{matrix}$

(13)
In PRM sequence construction, the RM $(Υ, 2)$ is not just inserted into a $2^{m}$ -length sequence, but has a sign ${(- 1)}^{wt (B |_{Υ + 1}^{m})}$ attached (Equation (12) illustrates this). The sign comes from the $i^{2 B^{T} (Q^{- 1} v)}$ part, i.e., the constraint of $ϕ (B, Q^{- 1} v, Υ)$ means the post- $(m - Υ)$ bits should be equal, which leads to the two identical vector multiplication (modulo 4) equal to the weight of ${B |}_{Υ + 1}^{m}$ or $(Q^{- 1} v) |_{Υ + 1}^{m}$ ;
The vector ${B |}_{1}^{Υ}$ and matrix $P$ serve as the determinants of the non-zero RM $(Υ, 2)$ part, where only the upper matrix $P_{Υ}$ is valid. Moreover, the subspace $I_{χ}$ and ${B |}_{Υ + 1}^{m}$ determine the “patterned” form.

4.2. Geometry Property of PRM sequence

This section discusses the geometry property of PRM along the lines of Section 3.2 and summarizes the conclusion in Theorem 3.

Theorem 3.

The PRM sequence fulfills the following equation for any

z \in F_{2}^{m - Υ}

E (I_{χ} e_{r}, \tilde{I_{χ}} z + I_{χ} \hat{P} e_{r}) \cdot C_{\hat{P}, B, I_{χ}} = {(- 1)}^{B^{T} (e_{r}; 0^{m - Υ}) + {(B |_{Υ + 1}^{m})}^{T} z} \cdot C_{\hat{P}, B, I_{χ}},

(14)

where Υ is dimension of the set χ and

e_{r}

denotes the unit vector on domain

F_{2}^{Υ}

0 \leq r \leq Υ

, while

\hat{P}

is a

(Υ \times Υ)

-element symmetric binary matrix of rank Υ.

Proof of Theorem 3.

The left term of Equation (14) can be expanded as

\begin{matrix} \begin{matrix} E (I_{χ} e_{r}, {\tilde{I}}_{χ} z + I_{χ} \hat{P} e_{r}) C_{\hat{P}, B, I_{χ}} \\ \overset{(a)}{=} & 1 / H \cdot i^{{(I_{χ} e_{r})}^{T} ({\hat{I}}_{χ} z + I_{χ} \hat{P} e_{r})} \cdot \sum_{w \in F_{2}^{m}} {(- 1)}^{{({\tilde{I}}_{χ} z + I_{χ} \hat{P} e_{r})}^{T} w} e_{w + I_{χ} e_{r}}^{T} e_{w} \\ \cdot \sum_{a \in F_{2}^{m}} i^{{(Q^{- 1} a)}^{T} P Q^{- 1} a + 2 B^{T} Q^{- 1} a} ϕ [B, Q^{- 1} a, Υ] e_{a} \\ = & 1 / H \cdot i^{P_{r, r}} \sum_{a \in F_{2}^{m}} {(- 1)}^{{({\tilde{I}}_{χ} z + I_{χ} \hat{P} e_{r})}^{T} a} \cdot i^{a^{T} Q^{- T} P Q^{- 1} a + 2 B^{T} Q^{- 1} a} \cdot ϕ [B, Q^{- 1} a, Υ] e_{a + I_{χ} e_{r}} \\ \overset{(b)}{=} & 1 / H \cdot i^{P_{r, r}} \sum_{a \in F_{2}^{m}} i^{{\underset{︸}{2 {({\tilde{I}}_{χ} z + I_{χ} \hat{P} e_{r})}^{T} (a + I_{χ} e_{r})}}_{A}} \cdot i^{{\underset{︸}{{(a + I_{χ} e_{r})}^{T} Q^{- T} P Q^{- 1} (a + I_{χ} e_{r})}}_{B}} \\ \cdot \underset{C}{\underset{︸}{ϕ [B, Q^{- 1} (a + I_{χ} e_{r}), Υ]}} \cdot e_{a}, \end{matrix} \end{matrix}

(15)

where

H = 2^{Υ}

. The equals sign (a) is based on the formula for Pauli matrices (see Equation (14) in [38] for details) and (b) is the process of replacing all variable

a

with

(a + I_{χ} e_{r})

. Next, we will develop each item

A, B

and C in the last equation of (15).

Using process

{(I_{χ})}^{T} \cdot I_{χ} = I_{Υ}

, we expand item A into the following equation

A = 2 {({\tilde{I}}_{χ} z + I_{χ} \hat{P} e_{r})}^{T} a + 2 P_{r, r},

(16)

where

P_{r, r}

is the

r

-th diagonal element (from top down) of the matrix

\hat{P}

. We further employ the equation

Q^{- 1} \cdot I_{χ} = {(I_{χ})}^{T} \cdot I_{χ}

and

{({\tilde{I}}_{χ})}^{T} \cdot I_{χ} = 0_{Υ \times Υ}

and item B can be expressed as

B = {(Q^{- 1} a)}^{T} P (Q^{- 1} a) + 2 B Q^{- 1} a + 2 {({\hat{P}}_{r}; 0_{m \times r})}^{T} Q^{- 1} a + P_{r, r} + 2 B^{T} (e_{r}; 0^{m - r}),

(17)

where

{\hat{P}}_{r} = \hat{P} e_{r}

. Similarly, we have

C = ϕ [B, Q^{- 1} a + (e_{r}; 0^{m - r}), Υ] .

(18)

The following equation can be obtained by substituting (16)–(18) into (15):

\begin{matrix} \begin{matrix} 1 / H \cdot i^{4 P_{r, r}} {(- 1)}^{B^{T} (e_{r}; 0^{m - r})} \\ \cdot \sum_{a \in F_{2}^{m}} i^{2 {({\tilde{I}}_{χ} z + I_{χ} \hat{P} e_{r})}^{T} a} \cdot i^{2 {({\hat{P}}_{r}; 0_{m \times r})}^{T} Q^{- 1} a} \cdot i^{{(Q^{- 1} a)}^{T} P (Q^{- 1} a) + 2 B Q^{- 1} a} \cdot ϕ [B, Q^{- 1} a + (e_{r}; 0^{m - r}), Υ] \cdot e_{a} \\ \overset{(c)}{=} & 1 / H \cdot {(- 1)}^{B^{T} (e_{r}; 0^{m - r})} \sum_{a \in F_{2}^{m}} i^{2 {({\tilde{I}}_{χ} z)}^{T} a} \cdot i^{{(Q^{- 1} a)}^{T} P (Q^{- 1} a) + 2 B Q^{- 1} a} \cdot ϕ [B, Q^{- 1} a + (e_{r}; 0^{m - r}), Υ] \cdot e_{a} \\ \overset{(d)}{=} & 1 / H \cdot {(- 1)}^{B^{T} (e_{r}; 0^{m - r}) + {(B |_{Υ + 1}^{m})}^{T} z} \sum_{I_{χ} w + {\tilde{I}}_{χ} {B |}_{Υ + 1}^{m} \in F_{2}^{m}} i^{{(w; B |_{Υ + 1}^{m})}^{T} \hat{P} (w; B |_{Υ + 1}^{m}) + 2 B^{T} (w; B |_{Υ + 1}^{m})} \cdot e_{I_{χ} w + {\tilde{I}}_{χ} {B |}_{Υ + 1}^{m}} \\ \overset{(e)}{=} & {(- 1)}^{B^{T} (e_{r}; 0^{m - r}) + {(B |_{Υ + 1}^{m})}^{T} z} \cdot C_{\hat{P}, B, I_{χ}}, \end{matrix} \end{matrix}

(19)

where the equals sign (c) uses the equation

i^{2 {({\tilde{I}}_{χ} z + I_{χ} \hat{P} e_{r})}^{T} a} \cdot i^{2 {({\hat{P}}_{r}; 0_{m \times r})}^{T} Q^{- 1} a} = i^{2 {({\tilde{I}}_{χ} z)}^{T} a}

, while (d) replacing

a

with

I_{χ} w + {\tilde{I}}_{χ} {B |}_{Υ + 1}^{m}

as well as using the following formula

\begin{matrix} \begin{matrix} ϕ [B, Q^{- 1} a + (e_{r}; 0^{m - r}), Υ] \\ = & ϕ [B, Q^{- 1} (I_{χ} w + {\tilde{I}}_{χ} B |_{Υ + 1}^{m}) + (e_{r}; 0^{m - r}), Υ] \\ = & ϕ [B, (w; B_{1}^{Υ}) + (e_{r}; 0^{m - r}), Υ] \\ = & ϕ [B, (w + e_{r}; B_{1}^{Υ}), Υ] = 1 \end{matrix} \end{matrix}

(20)

to eliminate

ϕ (\cdot)

as 1. We use the equation

\begin{matrix} \begin{matrix} C_{\hat{P}, B, I_{χ}} = & \sum_{I_{χ} w + {\tilde{I}}_{χ} {B |}_{Υ + 1}^{m} \in F_{2}^{m}} i^{{(w; B |_{Υ + 1}^{m})}^{T} \hat{P} (w; B |_{Υ + 1}^{m}) + 2 B^{T} (w; B |_{Υ + 1}^{m})} \cdot e_{I_{χ} w + {\tilde{I}}_{χ} {B |}_{Υ + 1}^{m}} \\ \overset{(f)}{=} & \sum_{w \in F_{2}^{Υ}} i^{w^{T} \hat{P} w + 2 B_{1}^{Υ} + wt (B_{1}^{Υ})} \cdot e_{I_{χ} w + {\tilde{I}}_{χ} {B |}_{Υ + 1}^{m}} \end{matrix} \end{matrix}

(21)

in (e). Thus, (19) agrees with the conclusion in Theorem 3. □

Lemma 1.

For any

z \in F_{2}^{m - Υ}

, the following projection operator exists

λ_{P R M, ϖ}^{(r)} (z |_{z \in F_{2}^{m - Υ}}) = \frac{[I_{N} + ϖ \cdot E (I_{χ} e_{r}, {[\tilde{I_{χ}} z + I_{χ} \hat{P} e_{r}]}_{z \in F_{2}^{m - Υ}})]}{2},

(22)

where

ϖ = {(- 1)}^{B_{r} + {(B |_{Υ + 1}^{m})}^{T} {z |}_{z \in F_{2}^{m - Υ}}}

. For any vector

\tilde{z} \in F_{2}^{m - Υ}

we get

λ_{P R M, ϖ}^{(r)} (\tilde{z}) \cdot C_{\hat{P}, B, I_{χ}} = \{\begin{matrix} C_{\hat{P}, B, I_{χ}}, & if ϖ = {(- 1)}^{B_{r} + {(B |_{Υ + 1}^{m})}^{T} \tilde{z};}, \\ 0, & if ϖ \neq {(- 1)}^{B_{r} + {(B |_{Υ + 1}^{m})}^{T} \tilde{z} .} \end{matrix}

(23)

\tilde{z} = 0^{m - Υ}

is fixed, we have

λ_{P R M, ϖ}^{(r)} (0^{m - Υ}) = \frac{I_{N} + ϖ \cdot E (I_{χ} e_{r}, I_{χ} \hat{P} e_{r})}{2},

(24)

and we get

λ_{P R M, ϖ}^{(r)} (0^{m - Υ}) \cdot C_{\hat{P}, B, I_{χ}} = \{\begin{matrix} C_{\hat{P}, B, I_{χ}}, & if ϖ = {(- 1)}^{B_{r};}, \\ 0, & if ϖ \neq {(- 1)}^{B_{r} .} \end{matrix}

(25)

Lemma 1 is the core idea of the detection algorithm.

4.3. The Proposed Geometry-Based PRM Detection

We model a single-user scenario in which the receiver observes

\begin{matrix} \begin{matrix} y = C_{\hat{P}, B, I_{χ}} + n, \end{matrix} \end{matrix}

(26)

where

C_{\hat{P}, B, I_{χ}}

is a PRM sequence while

n

represents an additive noise. Unlike the RM sequence decoding algorithm, PRM code needs to decode three items, i.e.,

\{I_{χ}, \hat{P}, B\}

. In view of the fact that decoding the second-order RM

(Υ, 2)

at non-zero positions can be accomplished only if the subspace

I_{χ}

is known, the knowledge of subspace matrix

I_{χ}

should be recovered in priority. Algorithm 1 summarizes the detail of the proposed decoding algorithm.

Algorithm 1: Estimation of single PRM sequence

Due to the indeterminate rank of the received PRM sequence, we traverse all possible ranks

1 \leq Υ \leq m

and reserve L candidate subspaces beneath each rank (line 1). Lines 2–5 describe the process for collecting candidates: for each vector

f_{χ_{(Υ)}} \in F_{2}^{m}

, we compute the related

y^{H} E (0, f_{χ_{(Υ)}}) y

and its summation form

\begin{matrix} \begin{matrix} F_{sum} (f_{χ_{(Υ)}}) = \sum_{j = 1}^{2^{(m - Υ)}} |y^{H} E (0, f_{χ_{(Υ)}}^{(j)}) y| . \end{matrix} \end{matrix}

(27)

By searching the largest

2^{(m - Υ)}

estimatios of

F_{sum}

, the corresponding set

{[f_{χ_{(Υ)}}^{(j)}]}_{j = 1}^{2^{(m - Υ)}}

and the subspace matrix

{\tilde{I}}_{χ_{(Υ)}}

are identified and placed as a candidate, in which the relation between

{[f_{χ_{(Υ)}}^{(j)}]}_{j = 1}^{2^{(m - Υ)}}

and

{\tilde{I}}_{χ_{(Υ)}}

{[f_{χ_{(Υ)}}^{(j)}]}_{j = 1}^{2^{(m - Υ)}} = span ({\tilde{I}}_{χ_{(Υ)}}) .

(28)

We repeat the above steps and keep L candidates in set

I_{χ_{(Υ)}} = \{{[{\tilde{I}}_{χ_{(Υ)}}^{(l)}]}_{l = 1}^{L}, Υ\}

The subsequent RM

(Υ, 2)

recovery is based on the subspaces in candidates

I_{χ_{(Υ)}}

. As shown in lines 9–18, the symmetric matrix

{\hat{P}}_{l}

and the vector

B_{l}

for decoding RM

(Υ, 2)

are recovered layer by layer within the l-th interaction, where the subscript l denotes the current l-th candidate in

I_{χ_{(Υ)}}

. Since the matrix is of Kerdock set with symmetric properties, we denote the set of indexes for the rows determined by decoded layers as

R

(

R = 1, \dots, r - 1

). Utilizing the estimated row vectors to complete the symmetric matrix, the current matrix for the

r

-th layer decoding can be represented as

{\underset{̲}{\hat{P}}}_{R}

. Hence, the search space under the l-th submatrix is limited to

F_{l, r} = \{f \in F_{2}^{m} ∣ f_{i} = {\underset{̲}{\hat{P}}}_{R} (i, r) for all i \in R\},

(29)

where the value of

{\underset{̲}{\hat{P}}}_{R} (i, r)

refers to the i-th row and

r

-th column of matrix

{\underset{̲}{\hat{P}}}_{R}

. On this basis, for all vectors

f \in F_{l, r}

, an equation written as

\begin{matrix} \begin{matrix} F_{sum} (f) = \sum_{j = 1}^{2^{(m - Υ)}} |y^{H} E (I_{χ_{(Υ)}}^{(l)} \cdot e_{r}, f) y| \end{matrix} \end{matrix}

(30)

is calculated to search the largest

2^{(m - Υ)}

values of

F_{sum} (f)

and herein find the corresponding set

{[f_{j}]}_{j = 1}^{2^{(m - Υ)}}

based on

\begin{matrix} \begin{matrix} {[f_{j}]}_{j = 1}^{2^{(m - Υ)}} = span ({\tilde{I}}_{χ_{(Υ)}}^{(l)}) + I_{χ_{(Υ)}}^{(l)} {\hat{P}}_{r, l} e_{r} . \end{matrix} \end{matrix}

(31)

We finally get

{\hat{P}}_{r, l} e_{r}

, where

{\hat{P}}_{r, l}

is the

r

-th row/column vector for

{\hat{P}}_{l}

In the case of

B_{l}

decoding, as can be seen from Lemma 1, we first compute

F_{r} (f)

by substituting (31) into (30) and letting

z^{(m - Υ)} = 0^{m - Υ}

\begin{matrix} \begin{matrix} F_{r} (f) = y^{H} E (I_{χ_{(Υ)}}^{(l)} \cdot e_{r}, I_{χ_{(Υ)}}^{(l)} {\hat{P}}_{r, l} e_{r}) y, \end{matrix} \end{matrix}

(32)

we then obtain

sign (F_{r} (f)) = {(- 1)}^{B_{r, l}}

. Therefore,

B_{r}

can be obtained immediately as

B_{r, l} = \{\begin{matrix} 1, & if sign (F_{r} (f)) = - 1; \\ 0, & if sign (F_{r} (f)) = 1 . \end{matrix}

(33)

(33) can be summarized as the relationship of

B_{r, l} = \frac{(1 - ϖ)}{2},

(34)

where

ϖ = sign (F_{r} (f))

The power of

y

(subscripts for

r = 1

is omitted) projected with this operator is

\begin{matrix} \begin{matrix} {∥λ_{P R M, ϖ} (0^{m - Υ}) \cdot y∥}^{2} \\ = & y^{H} \cdot λ_{P R M, ϖ} (0^{m - Υ}) \cdot y \\ = & \frac{1}{2} [C_{\hat{P}, B, I_{χ}}^{H} C_{\hat{P}, B, I_{χ}} + ϖ C_{\hat{P}, B, I_{χ}}^{H} E (I_{χ_{(Υ)}}^{(l)} e_{r}, f) C_{\hat{P}, B, I_{χ}} + ϖ C_{\hat{P}, B, I_{χ}}^{H} E (I_{χ_{(Υ)}}^{(l)} e_{r}, f) n + C_{\hat{P}, B, I_{χ}}^{H} n \\ + ϖ n^{H} E (I_{χ_{(Υ)}}^{(l)} e_{r}, f) C_{\hat{P}, B, I_{χ}} + ϖ n^{H} E (I_{χ_{(Υ)}}^{(l)} e_{r}, f) n + C_{\hat{P}, B, I_{χ}}^{H} n + n^{H} n] \\ \geq & \frac{1}{2} [C_{\hat{P}, B, I_{χ}}^{H} C_{\hat{P}, B, I_{χ}} + ϖ \cdot F_{r} (f)], \end{matrix} \end{matrix}

(35)

where

f = I_{χ_{(Υ)}}^{(l)} {\hat{P}}_{r, l} e_{r}

. We see that the halfspace to which the projection of

y

is largest.

We perform a projection operation on the

r

-th layer signal

y

before performing the next layer decoding by employing the projection operator

λ_{D R M, ϖ}^{(r)} (0^{m - Υ})

(see line 14 in Algorithm 1). While

2 \leq r \leq Υ

, the input signal becomes

\begin{matrix} \begin{matrix} y_{r} = λ_{P R M, ϖ}^{(r)} \cdot y_{r - 1} \\ = & C_{\hat{P}, B, I_{χ}} + \prod_{i = 1}^{r - 1} λ_{P R M, ϖ}^{(i)} \cdot n \\ = & C_{\hat{P}, B, I_{χ}} + \frac{1}{2^{r - 1}} \prod_{i = 1}^{r - 1} (I_{N} + ϖ_{i} \cdot E [I_{χ} e_{i}, I_{χ} \hat{P} e_{i}]) \cdot n, \end{matrix} \end{matrix}

(36)

which indicates that the power of noise is halved within each iteration.

Line 21 evaluates the L results under each rank and retains the optimal solution. Finally, line 23 selects the optimal solution for the results of all ranks.

5. Unsourced Random Access Scheme Using Patterned Reed–Muller Sequence

The k-th active user preferentially converts its message sequence

U^{(k)}

into the corresponding M-length J-ary Reed–Solomon code, which completes the outer A-channel coding. Before conducting the inner encoding, a random prefix message is repeatedly added into M sub-blocks. The combination of the prefix and J-ary bits can produce a G-ary message in each slot. By using this prefix, an slot occupation criterion is selected from a common pool

Ω

. The binary sequence transformed by a G-ary bit is subsequently mapped to an element in a common codebook

Γ

and the resulting codeword is then transmitted to the AP side. In the receiver, the AP detects the users’ messages using the proposed projection method. In the sequel, we will describe every module of the proposed URA system in detail.

5.1. Transmitter

The specific structure of the transmitter is shown in Figure 2. This subsection provides a detailed description of how the transmission sequence is generated in the transmitter, followed by the construction of the slot-pattern-control pool.

5.1.1. Transmitter Design

The A-channel code used for the outer encoding is derived from paper [22]: the kth user’s message

U^{(k)}

of length B is mapped to a J-ary Reed–Solomon code of length H, designated

{[{\underset{̲}{M}}_{RS, h}^{(k)}]}_{h = 1}^{H} = (M_{RS, 1}^{(k)}, M_{RS, 2}^{(k)}, \dots, M_{RS, H}^{(k)}) \in {[J]}^{H}

0 \leq h \leq H

, where

M_{RS, h}^{(k)} \in [J]

is the h-th output bit of outer coding. To satisfy the coding rate requirement, we repeatedly append the binary prefix sequence

X_{p}^{(k)}

to each J-ary bit

M_{RS, h}^{(k)}

to create the G-ary sequence. Thus, the length of the binary sequence

X_{p}^{(k)}

is set to

{log}_{2} (G / J)

and we denote

x_{p} = {log}_{2} (G / J)

. For further interpretation, a G-ary bit is divided into

2^{x_{p}}

cosets, each containing

2^{J}

components, and this process can be summarized as follows:

{\overset{˘}{m}}_{PRM, h}^{(k)} = ϝ ([X_{p}^{(k)}; M_{RS, h}^{(k)}]),

(37)

where

𝘍 (\cdot)

is the bijective mapping:

𝘍 (\cdot) : [2^{x_{p}}] \times [J]

and

{\overset{˘}{m}}_{PRM, h}^{(k)} \in G

. By repeating (37) H times, an H-length sequence

{[{\underset{̲}{m}}_{PRM, h}^{(k)}]}_{h = 1}^{H} = ({\overset{˘}{m}}_{PRM, 1}^{(k)}, {\overset{˘}{m}}_{PRM, 2}^{(k)}, \dots, {\overset{˘}{m}}_{PRM, H}^{(k)})

is obtained, which serves as the input sequence for the inner encoder. We require a one-to-one matching between

{\overset{˘}{m}}_{PRM}^{(k)}

and codeword

C_{PRM}^{(k)}

from the common codebook (we omit the subscript m here for simplicity), and, herein,

{\overset{˘}{m}}_{PRM}^{(k)}

is the input signal of the inner encoder while the output codeword is

C_{PRM}^{(k)}

Let the message

{\overset{˘}{m}}_{PRM}^{(k)}

have a length of

N_{PRM, h}^{(k)}

; it is evident that

N_{PRM}^{(k)} = {log}_{2} G

. Furthermore, according to the codebook capacity

| Γ |

of Equation (13), the size of information bits that a PRM sequence can carry in each slot for user k is

N_{PRM}^{(k)} = ⌊{log}_{2} (| Γ |)⌋

. Finally, the output of inner coding over H slots is recorded as

{[{\underset{̲}{C}}_{PRM, h}^{(k)}]}_{h = 1}^{H} = (C_{PRM, 1}^{(k)}, C_{PRM, 2}^{(k)}, \dots, C_{PRM, H}^{(k)})

. This process of the transmitter is depicted in Figure 2.

5.1.2. The Construction of Slot-Pattern-Control Pool

In the practical encoding procedure, each user inserts its H-length RS code into

N_{T}

slots by looking up a criterion from the common dictionary

Ω

. Specifically, we construct a collection pool

Ω

for holding the common slot-pattern-control criteria and the k-th user retrieves the matching SPC from the pool based on the specific

X_{p}^{(k)}

The slot-pattern-control scheme is designed using a manner that refers to the construction of PRM code as a heuristic algorithm: the initial step is to unify all users’ slot indices, which can be managed by utilizing the binary notation

t \in F_{2}^{\ddot{m}}

to identify each slot. It is evident that, for a time slot of length

N_{T}

, the equation

N_{T} = 2^{\ddot{m}}

is necessary. Next, we extend the subspace generation rule in

F_{2}^{m}

for the PRM construction to classify

N_{T}

time slots into several sub-slots; in detail, let

N_{group}

denote the possible number of r dimensional spaces in

F_{2}^{m}

with

N_{group} = (\binom{\ddot{m}}{r})

and the corresponding subset is represented as

ξ

. Obviously, the length of

ξ

is r and

ξ \in F_{2}^{\ddot{m}}

. On the condition that r is constant, the slots used to place the

2^{r}

-length (

H = 2^{r}

) outer codeword are labeled as

{[t_{ξ}^{(h)}]}_{h = 1}^{H} = I_{ξ} x^{r} + \tilde{I_{ξ}} {b |}_{r + 1}^{\ddot{m}} x^{r} \in F_{2}^{r},

(38)

where the set

{I_{ξ} x^{r}}

(span all

x^{r} \in F_{2}^{r}

) indicates a subspace and the vector

\tilde{I_{ξ}} {b |}_{r + 1}^{\ddot{m}}

controls the cosets of the subspace. Since vector

{b |}_{r + 1}^{\ddot{m}}

has

2^{(\ddot{m} - r)}

possibilities,

n_{subgroup} = 2^{(\ddot{m} - r)}

cosets exist for each subspace. On this basis, the pool

Ω

generates a total of

|Ω| = (\binom{\ddot{m}}{r}) \cdot 2^{(\ddot{m} - r)}

candidates and the length of the information

X_{p}^{(k)}

is fixed as

x_{p} = ⌊ {log}_{2} |Ω| ⌋

. In this way, once the user has acquired the knowledge of

X_{p}^{(k)}

(there exists a one-to-one correspondence between

\{{b |}_{r}^{\ddot{m}}, ξ\}

-pair and sequence

X_{p}^{(k)}

), an H length codeword is successively inserted into the slots in accordance with (38).

In general, given a SPC

{[t_{ξ}^{(h)}]}_{h = 1}^{H}

and a random slot index

t_{h} \in F_{2}^{m}

, the signals to be sent in slot

t_{h}

are formulated as

x_{k, n} = \{\begin{matrix} C_{PRM, h}^{(k)}, & if t_{h} \in {[t_{ξ}^{(h)}]}_{h = 1}^{H}; \\ 0^{N}, & if t_{h} \notin {[t_{ξ}^{(h)}]}_{h = 1}^{H} . \end{matrix}

(39)

We let the vector

t_{h} [ξ] \in F_{2}^{r}

retain the certain bits from vector

t_{ξ}^{(h)}

at locations of

ξ

and regard

h = decimal (t_{h} [ξ]) + 1

as the decimal index of non-zero position in all slots. Moreover,

n = decimal (t_{h}) + 1

1 \leq n \leq N_{T}

5.2. Slot-Based PRM Detection and Reed–Solomon List Recovery Decoding

The complete signal sent by the active user k is expressed as

x_{k} = [x_{k, 1}; \dots; x_{k, N_{T}}],

(40)

after receiving the signals, the AP prioritizes performing decoding operations in each slot. To be more specific, the received signal in time slot n

(1 \leq n \leq N_{T})

can be expressed as

y_{n} = \sum_{k = 1}^{K_{a}} h_{k, n} \cdot x_{k, n} + n_{n},

(41)

where

h_{k, n} \sim C N (0, 1)

denotes the channel coefficient between the active user k and AP in slot n. The coefficients

h_{k, n}

are estimated in the process of identifying the most probable transmitted signals, while

n_{n} \sim C N (0, I_{N})

is the complex additive white Gaussian noise (AWGN).

In Algorithm 2, we summarize the process of PRM reconstruction in a multi-user scenario within a single slot. We consider the input signal

Y = (y_{1}, \dots, y_{N_{T}})

as a linear superposition of

K_{a}

users and require the AP to output all the message set

{W_{1}, W_{2}, \dots, W_{K_{a}}}

. Lines 1–7 of Algorithm 2 summarize the OMP-based inner-code detection algorithm in the multi-user scenario. Since OMP is an iterative algorithm, the number of output codewords is equivalent to the count of decoding iterations

K_{0}

. For the outer-decode process, we denote

Y = (Y_{1}, \dots, Y_{H})

(Y_{h} \subseteq [H])

as the input signal of the outer-decoder, which results from removing the coset sequence from the messages received from inner decoding and connecting the repeated

N_{T}

results. This process is described in lines 8–10. Lines 12 to 15 perform the outer Reed–Solomon decoding process and the detailed procedure is suggested in the literature [22]. All possibilities of decoding results for each user are saved in the list

V_{L}

Algorithm 2: PRM reconstruction in a multi-user scenario

6. Performance Analysis

Our proposed URA system depends on the reliability of PRM detection in each chunk and the efficiency of the outer decoder in coupling the information between slots. The purpose of this section is to discuss how the PRM sequence is distributed in each sub-block, which is one of the most crucial factors influencing slot-based inner-code detection performance.

The PRM Distribution for a Single Slot

The number of sequences for a received signal involved in linear superposition is the key factor governing the distribution of codewords within a particular slot.

Next, we define a random variable

T

to further explore the above event

\tilde{t_{s}} \in {[t_{ξ}^{(i)}]}_{i = 1}^{\frac{2^{\ddot{m}}}{n_{subgroup}}}

and we use

T = 1

to denote the event that “a set corresponding to the selected rule contains a specific slot index”.

To examine the probability that the time slot

\tilde{t_{s}}

will be chosen, evaluate the likelihood that the event “a slot

\tilde{t_{s}}

is contained in the chosen set

{[t_{ξ}^{(i)}]}_{i = 1}^{\frac{2^{\ddot{m}}}{n_{subgroup}}}

” takes place is sufficient, which can be described as

\tilde{t_{s}} \in {[t_{ξ}^{(i)}]}_{i = 1}^{\frac{2^{\ddot{m}}}{n_{subgroup}}}

and the probability equals

\Pr [\tilde{t_{s}} \in {[t_{ξ}^{(i)}]}_{i = 1}^{\frac{2^{\ddot{m}}}{n_{subgroup}}}] = \frac{N_{group}}{2^{\ddot{m} - r} \cdot N_{group}} = 2^{r - \ddot{m}} = n_{subgroup}^{- 1},

(42)

where

N_{group} = (\binom{\ddot{m}}{r})

and

n_{subgroup} = 2^{(\ddot{m} - r)}

. This result is numerically equivalent to the probability that a coset will be selected when a subspace

I_{ξ}

is provided. As a matter of fact, a specific slot will appear only once in each manner of partitioning the space

F_{2}^{m}

. Thus, with a total of

(\binom{\ddot{m}}{r})

partition manners, a specific bit will appear

(\binom{\ddot{m}}{r})

times in all conceivable subsets

2^{(\ddot{m} - r)} \cdot (\binom{\ddot{m}}{r})

. Furthermore, the number of subgroups is

n_{subgroup}

and the exact location is repeated

N_{group}

times for a given subspace

I_{ξ}

; herein, users who choose the same subspace but different subgroups will not collide; in other words, for two random selections within a given subspace, the probability that no conflicts will arise equals the chance of selecting two different subsets.

Next, we use

T = 1

to denote the event “a set corresponding to the selected rule contains a specific slot index”. According to (42), the variable

T

obeys the Bernoulli distribution; we then derive the expectation

E [T] = n_{subgroup}^{- 1}

. As the value of

| Ω |

2^{x_{m}}

, the number of probable appearances for slot

\tilde{t_{s}}

is formulated as

N_{t} = 2^{x_{p}} \cdot n_{subgroup}^{- 1},

(43)

which holds for arbitrary locations.

Let the random variable

K

denote the total number of simultaneous appearances for

K_{a}

users in slot

\tilde{t_{s}}

. Consider the case in which users select separate elements from pool

Ω

, which means that all users are not putting elements back while selecting rules. Thus, the probability mass function (PMF) of

K

is calculated as follows

\Pr_{unrepeatable} [K = κ] = \frac{(\begin{matrix} N_{t} \\ κ \end{matrix}) (\begin{matrix} N_{group} \cdot n_{subgroup} - N_{t} \\ K_{a} - κ \end{matrix})}{(\begin{matrix} N_{group} \cdot n_{subgroup} \\ K_{a} \end{matrix})},

(44)

where

κ = 1, \dots, N_{t}

K_{a} = 0, \dots, N_{group} \cdot n_{subgroup}

. Accordingly, the variable

K

is expected to be

E_{unrepeatable} [K] = \frac{K_{a} \cdot N_{t}}{N_{group} \cdot n_{subgroup}},

(45)

and variance have the form of

D_{unrepeatable} [K] = \frac{K_{a} \cdot N_{t}}{N_{group} \cdot n_{subgroup}} \frac{N_{group} \cdot n_{subgroup} - K_{a}}{N_{group} \cdot n_{subgroup} - 1} (1 - \frac{N_{t}}{N_{group} \cdot n_{subgroup}}) .

(46)

It is assumed that users are not prohibited from selecting the same rules more than once (SPC collisions) and

K

obeys the PMF being

\Pr_{repeatable} [K = κ] = (\begin{matrix} K_{a} \\ κ \end{matrix}) {(\frac{N_{t}}{N_{group} \cdot n_{subgroup}})}^{κ} {(1 - \frac{N_{t}}{N_{group} \cdot n_{subgroup}})}^{K_{a} - κ} .

(47)

K

obey the binomial distribution with its expectation and variance expressed as

E_{repeatable} [K] = \frac{K_{a} \cdot N_{t}}{N_{group} \cdot n_{subgroup}},

(48)

and

D_{repeatable} [K] = \frac{K_{a} \cdot N_{t}}{N_{group} \cdot n_{subgroup}} (1 - \frac{N_{t}}{N_{group} \cdot n_{subgroup}}) .

(49)

We find that

E_{unrepeatable} [K] = E_{repeatable} [K]

, while

D_{unrepeatable} [K] = D_{repeatable} [K]

. Different strategies for picking rules from pool

Ω

do not affect the average number of codewords in one slot. Furthermore, when the active users choose from the separate SPCs, the inner codes are distributed more uniformly throughout the slots. In the presence of selecting the same rules more than once, the probability that many PRM sequences could collide in one slot increases, thus resulting in a higher multi-user interference (MUI).

7. Simulation Results

7.1. The Distribution of Slot-Based PRM Sequences

The simulations in this subsection illustrate the probability distribution of the number of PRM codes that can be accommodated simultaneously in one slot, i.e.,

\Pr (K)

. We denote “PRM-RS, no collision” and “PRM-RS, collision”, respectively, as the practical simulation results with and without SPC collision. Moreover, we denote “PRM-RS, Equation (44)” and “PRM-RS, Equation (47)”, respectively, as the theoretical results calculated from (44) and (47). The parameters for our PRM-RS scheme are

\ddot{m} = 8

and

r = 5

, and the sequence distributions for

K_{a} = 100, 150

and 200 users are, respectively, depicted in Figure 3, Figure 4 and Figure 5. Moreover, Figure 6 illustrates the results with parameters

\ddot{m} = 8

and

r = 6

under

K_{a} = 100

. Observations can be drawn from this as follows:

PRM sequences are distributed more evenly when active users employ different SPCs. If collisions occur, more codewords will overlap at one slot, resulting in a rise in multi-user interference (MUI) and an increased probability of failure detection.
According to Figure 3, Figure 4 and Figure 5, the distributions of “PRM-RS” and “RM-Shift” almost overlap until $k_{a} = 200$ . Compared to the benchmark, the overall simulation of the simultaneously accommodated codeword count for “PRM-RS” becomes larger when the number of users exceeds 200.
Figure 6 illustrates that the “no collision” case is no longer valid when $r = 6$ .

Even though the distribution is only improved under certain conditions (user count less than 200), the proposed inner-code construction and detection algorithm, in conjunction with the outer error correction technique, can improve the overall performance. This will be discussed in more detail in the next subsection.

7.2. The Overall Performance of the SPC-Based CCS for URA System

7.2.1. t-Tree Code as the Outer Code

To begin with, let us employ a decoder capable of correcting up to t errors as the outer code in different URA schemes, i.e., “t-tree code” and “PRM-tree”. The benchmarks called “t-tree code” from [22] are plotted by the green lines in Figure 7. We then evaluated the proposed “PRM-tree” scheme, i.e., the proposed PRM sequence is employed as the inner codeword, in which the former

x_{p}

-bit message is filled with the selected SPC, and the remaining J-bit is used to transport the user’s messages; moreover, the decoder capable of correcting t errors continues to make up the outer code. Following [22], we employ the greedy information bits allocation method, assigning the maximum number of information bits at each subsequent slot keeping the

E [| V_{l} |] \leq 2^{25}

constraint to find the minimum

E_{b} / N_{0}

(see Section VII in [22] for more details). Based on this, parameters of H, N,

N_{T}

, m,

\ddot{m}

, G, J and

x_{p}

in the proposed URA scheme are also considered.

The PRM capacity formula under one rank

Υ

is shown below:

\begin{matrix} {| Γ |}_{Υ} = (\binom{m}{Υ}) \cdot 2^{m} \cdot 2^{\frac{Υ (Υ + 1)}{2}}, \end{matrix}

(50)

it is worth noting that

{| Γ |}_{Υ}

and

{| Ω |}_{r}

share the similar Formula (48).

Increasing t requires a longer outer-code length H, where

H = 2^{r}

. By substituting

\ddot{m}

and r into (48), it is easy to see that the H value directly controls the SPC capacity

{| Ω |}_{r}

. On this basis, the optimal setups of H for

t = 1

and

t = 2, 3

are set to be 32 and 64, respectively. However,

t = 4, 5

cases are not valid in our URA setups since

H = 64

is no longer sufficient for

t = 4, 5

and thus

H = 128

is the next choice (H must be a power of two). It can be seen from Equation (42) that the value of

{| Ω |}_{r}

related to

H = 128

requires a larger

\ddot{m}

to preserve the average number of probable appearances in each slot, whereas

N = 2^{m}

would become smaller under the constraint of

T = N_{T} \cdot N

(T is fixed and

N_{T} = 2^{\ddot{m}}

), which results in the collapse of the inner-code performance. Table 1 presents the optimal G-ary,

x_{p}

and J-ary for different t, as well as the outer-code length (and rate). Optimal parameters for the overall system are carefully selected as in Table 2. Simulations are shown in Figure 7, where purple lines illustrate the resulting energy efficiency for

t = 1, 2

and 3 of “PRM-tree”. Based on the simulations, we can infer the following observations:

PRM sequence for a given rank suffices for a user’s message delivery, indicating that the PRM codebook is highly spectral efficient due to its large sequence space.
The outer-code length $H = 32 (r = 5)$ is used for $t = 1$ and $64 (r = 6)$ for $t = 2, 3$ . Substituting $r = 5, 6$ and $\ddot{m} = 8$ into (38), we observe that the latter case ( $r = 6$ ) performs relatively poorly since it has a greater number of simultaneous appearances, which leads to inner-code failure at $K_{a} = 200$ for $t = 1$ and, for $t = 2, 3$ , $K_{a} = 150$ . This result is consistent with Figure 6.
For the curves of $t = 2, 3$ , the “PRM-tree” scheme corrects the case of the “t-tree code” scheme in which the overall performance degrades as t increases, i.e., an outer code with a larger t performs better on the condition that the inner code has the same length and the required path number is sufficient (“PRM-tree” schemes use $2^{25}$ paths and $2^{10}$ paths for “t-tree code”).

7.2.2. PRM-Based Reed–Solomon Scheme

A “PRM-RS” scheme based on the inner PRM code in conjunction with an outer Reed–Solomon code (as illustrated in Algorithm 2) is simulated in this section, and the per-user error probability

P_{e}

as a function of

E_{b} / N_{0}

for

K_{a} = 130, 180

and 200 for this “PRM-RS” scheme is obtained (in Figure 8). The optimal system parameters are depicted in Table 3. It can be seen from Figure 8 that:

The minimum $P_{e}$ exceeds $0.1$ when the user count reaches 220.
The simulation curves in Figure 8 are consistent with the bar chart performances in Figure 6, i.e., when the number of users exceeds 200, the number of simultaneous transmissions exceeds the identifiable maximum.

The energy efficiency is the minimum energy required to serve

K_{a}

users with PUPE less than

0.1

, which is depicted in the blue line in Figure 7 under our optimal setups (see Table 3). We also need to adjust the number of CRC bits

b_{c}

to suppress falsely detected messages following the same method as operated in [22]. The benchmark is the RS scheme in [22] which is plotted using an orange line.

The increase of r necessitates a lengthier

\ddot{m}

to maintain the SPC pool capacity and the length of the inner code cannot be increased due to the channel uses T constraint. Furthermore, the decrease in inner-code length also weakens its performance. Therefore, we fix the SPC capacity as

{| Ω |}_{r}

with

\ddot{m} = 8

and

r = 7

. On this basis, when the prefix length

x_{p}

is fixed, a rise in value G leads to a larger J, which directly increases the outer code rate. Additionally, an increase in the outer code rate would weaken its performance. In light of this, carefully selecting the G value is critical. Simulation demonstrates that it is more efficient than the original RS when

K_{a}

is less than 185, even with a constant inner-code length for different user counts.

8. Conclusions

In this paper, We addressed a general framework for CCS under the packetized and slotted transmission protocol based on inner PRM codes and outer error correction codes. First, we propose PRM sequences to transmit information chunks in slots since their geometry property facilitates computationally efficient PRM detection. Furthermore, we extend the space segmenting strategy of PRM sequences to construct a predefined dictionary of SPCs for slot occupation and the SPC selection mechanism is prescribed by an information segment for each user. The factors influencing slot-based PRM detection performance are discussed. We validate the error probability advantage of our proposed PRM-based URA scheme through simulation. We further proposed to use list recoverable codes correcting t errors in the coded compressed sensing scheme. Specifically, we propose two practical constructions of outer codes. The first one is a modification of the tree code. It utilizes the PRM as inner codes and adds a SPC, and the major difference is a decoder capable of correcting up to t errors. The second one is based on the Reed–Solomon codes and Guruswami–Sudan list decoding algorithm. The optimal setups are determined to minimize SNR by optimizing the inner and outer codes jointly. Both schemes provide better energy efficiency compared with the benchmark. In the following study, we will perform a matrix decomposition of the Clifford matrix

G_{F}

related to the patterned Reed–Muller sequence and view this decomposition process as a reconstruction of the transmitter design. Moreover, the model is extended to accommodate multiple antennas for the URA system. We will also consider an iterative decoding algorithm to solve the signal recovery at the receiver.

Author Contributions

The work was realized with the collaboration of all the authors. W.X. contributed to the main results and simulation. H.Z. organized the work, supervised the research and reviewed the draft of the paper. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

References

Saad, W.; Bennis, M.; Chen, M. A vision of 6G wireless systems: Applications, trends, technologies, and open research problems. IEEE Netw. 2019, 34, 134–142. [Google Scholar] [CrossRef]
Guo, F.; Yu, F.R.; Zhang, H.; Li, X.; Ji, H.; Leung, V.C. Enabling massive IoT toward 6G: A comprehensive survey. IEEE Internet Things J. 2021, 8, 11891–11915. [Google Scholar] [CrossRef]
Wu, Y.; Gao, X.; Zhou, S.; Yang, W.; Polyanskiy, Y.; Caire, G. Massive access for future wireless communication systems. IEEE Wirel. Commun. 2020, 27, 148–156. [Google Scholar] [CrossRef]
Chen, X.; Ng, D.W.K.; Yu, W.; Larsson, E.G.; Al-Dhahir, N.; Schober, R. Massive access for 5G and beyond. IEEE J. Sel. Areas Commun. 2020, 39, 615–637. [Google Scholar] [CrossRef]
Chettri, L.; Bera, R. A comprehensive survey on Internet of Things (IoT) toward 5G wireless systems. IEEE Internet Things J. 2020, 7, 16–32. [Google Scholar] [CrossRef]
Zhang, J.; Lu, L.; Sun, Y.; Chen, Y.; Liang, J.; Liu, J.; Hernando, F.J.L. PoC of SCMA-based uplink grant-free transmission in UCNC for 5G. IEEE Internet Things J. 2017, 35, 1353–1362. [Google Scholar]
Masoudi, M.; Azari, A.; Yavuz, E.A.; Cavdar, C. Grant-free radio access IoT networks: Scalability analysis in coexistence scenarios. In Proceedings of the IEEE International Conference on Communications (ICC), Kansas City, MO, USA, 20–24 May 2018; pp. 1–7. [Google Scholar]
Shahab, M.B.; Abbas, R.; Shirvanimoghaddam, M.; Johnson, S.J. Grant-free non-orthogonal multiple access for IoT: A survey. IEEE Commun. Surv. Tutorials 2020, 22, 1805–1838. [Google Scholar] [CrossRef]
Chen, X.; Guo, D. Many-access channels: The Gaussian case with random user activities. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Honolulu, HI, USA, 30 June–5 July 2014; pp. 3127–3131. [Google Scholar]
Chen, X.; Chen, T.Y.; Guo, D. Capacity of Gaussian many-access channels. IEEE Trans. Inf. Theory 2017, 63, 3516–3539. [Google Scholar] [CrossRef]
Polyanskiy, Y. A perspective on massive random-access. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 25–30 June 2017; pp. 2523–2527. [Google Scholar]
Zadik, I.; Polyanskiy, Y.; Thrampoulidis, C. Improved bounds on Gaussian MAC and sparse regression via Gaussian inequalities. In Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France, 7–12 July 2019; pp. 430–434. [Google Scholar]
Kowshik, S.S.; Polyanskiy, Y. Fundamental limits of many-user MAC with finite payloads and fading. IEEE Trans. Inf. Theory 2021, 67, 5853–5884. [Google Scholar] [CrossRef]
Ngo, K.H.; Lancho, A.; Durisi, G. Unsourced multiple access with random user activity. arXiv 2022, arXiv:2202.06365. [Google Scholar] [CrossRef]
Pradhan, A.K.; Amalladinne, V.K.; Narayanan, K.R.; Chamberland, J.F. LDPC Codes with Soft Interference Cancellation for Uncoordinated Unsourced Multiple Access. In Proceedings of the IEEE International Conference on Communications (ICC), Montreal, QC, Canada, 14–23 June 2021; pp. 1–6. [Google Scholar]
Amalladinne, V.K.; Pradhan, A.K.; Rush, C.; Chamberland, J.F.; Narayanan, K.R. Unsourced random access with coded compressed sensing: Integrating AMP and belief propagation. IEEE Trans. Inf. Theory 2022, 68, 2384–2409. [Google Scholar] [CrossRef]
Truhachev, D.; Bashir, M.; Karami, A.; Nassaji, E. Low-Complexity Coding and Spreading for Unsourced Random Access. IEEE Commun. Lett 2021, 25, 774–778. [Google Scholar] [CrossRef]
Amalladinne, V.K.; Vem, A.; Soma, D.K.; Narayanan, K.R.; Chamberland, J.F. A coupled compressive sensing scheme for unsourced multiple access. In Proceedings of the 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Calgary, AB, Canada, 15–20 April 2018; pp. 6628–6632. [Google Scholar]
Amalladinne, V.K.; Chamberland, J.F.; Narayanan, K.R. A Coded Compressed Sensing Scheme for Unsourced Multiple Access. IEEE Trans. Inf. Theory 2020, 66, 6509–6533. [Google Scholar] [CrossRef]
Fengler, A.; Haghighatshoar, S.; Jung, P.; Caire, G. Non-Bayesian Activity Detection, Large-Scale Fading Coefficient Estimation, and Unsourced Random Access With a Massive MIMO Receiver. IEEE Trans. Inf. Theory 2021, 67, 2925–2951. [Google Scholar] [CrossRef]
Andreev, K.; Rybin, P.; Frolov, A. Reed-Solomon coded compressed sensing for the unsourced random access. In Proceedings of the 2021 17th International Symposium on Wireless Communication Systems (ISWCS), Berlin, Germany, 6–9 September 2021; pp. 1–5. [Google Scholar]
Andreev, K.; Rybin, P.; Frolov, A. Coded Compressed Sensing with List Recoverable Codes for the Unsourced Random Access. IEEE Trans. Commun. 2022, 70, 7886–7898. [Google Scholar] [CrossRef]
Liang, Z.; Zheng, J.; Ni, J. Index modulation–aided mixed massive random access. Front. Commun. Networks 2021, 2, 694557. [Google Scholar] [CrossRef]
Che, J.; Zhang, Z.; Yang, Z.; Chen, X.; Zhong, C.; Ng, D.W.K. Unsourced random massive access with beam-space tree decoding. IEEE J. Sel. Areas Commun. 2021, 40, 1146–1161. [Google Scholar] [CrossRef]
Fengler, A.; Jung, P.; Caire, G. SPARCs for unsourced random access. IEEE Trans. Inf. Theory 2021, 67, 6894–6915. [Google Scholar] [CrossRef]
Ebert, J.R.; Amalladinne, V.K.; Chamberland, J.F.; Narayanan, K.R. A Hybrid Approach to Coded Compressed Sensing Where Coupling Takes Place Via the Outer Code. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Toronto, ON, Canada, 6–11 June 2021; pp. 4770–4774. [Google Scholar]
Ebert, J.R.; Amalladinne, V.K.; Rini, S.; Chamberland, J.F.; Narayanan, K.R. Coded demixing for unsourced random access. IEEE Trans. Signal Process. 2022, 70, 2972–2984. [Google Scholar] [CrossRef]
Howard, S.D.; Calderbank, A.R.; Searle, S.J. A fast reconstruction algorithm for deterministic compressive sensing using second order Reed-Muller codes. In Proceedings of the 2008 42nd Annual Conference on Information Sciences and Systems, Princeton, NJ, USA, 19–21 March 2008; pp. 11–15. [Google Scholar]
Calderbank, R.; Jafarpour, S. Reed Muller sensing matrices and the LASSO. In Proceedings of the Sequences and Their Applications–SETA 2010: 6th International Conference (SETA), Paris, France, 13–17 September 2010; pp. 442–463. [Google Scholar]
Calderbank, R.; Howard, S.; Jafarpour, S. Sparse reconstruction via the Reed-Muller sieve. In Proceedings of the 2010 IEEE International Symposium on Information Theory (ISIT), Austin, TX, USA, 13–18 June 2010; pp. 1973–1977. [Google Scholar]
Zhang, L.; Luo, J.; Guo, D. Neighbor discovery for wireless networks via compressed sensing. Perform. Eval. 2013, 70, 457–471. [Google Scholar] [CrossRef]
Zhang, H.; Li, R.; Wang, J.; Chen, Y.; Zhang, Z. Reed-Muller sequences for 5G grant-free massive access. In Proceedings of the GLOBECOM 2017 IEEE Global Communications Conference, Singapore, 4–8 December 2017; pp. 1–7. [Google Scholar]
Wang, J.; Zhang, Z.; Hanzo, L. Joint active user detection and channel estimation in massive access systems exploiting Reed–Muller sequences. IEEE J. Sel. Top. Signal Process 2019, 13, 739–752. [Google Scholar] [CrossRef]
Wang, J.; Zhang, Z.; Hanzo, L. Incremental massive random access exploiting the nested Reed-Muller sequences. IEEE Trans. Wirel. Commun. 2020, 20, 2917–2932. [Google Scholar] [CrossRef]
Wang, J.; Zhang, Z.; Chen, X.; Zhong, C.; Hanzo, L. Unsourced massive random access scheme exploiting reed-muller sequences. IEEE Trans. Commun. 2020, 70, 1290–1303. [Google Scholar] [CrossRef]
Calderbank, R.; Thompson, A. CHIRRUP: A practical algorithm for unsourced multiple access. Inform. Inference J. IMA 2020, 9, 875–897. [Google Scholar] [CrossRef]
Tirkkonen, O.; Calderbank, R. Codebooks of complex lines based on binary subspace chirps. In Proceedings of the 2019 IEEE Information Theory Workshop (ITW), Visby, Sweden, 25–28 August 2019; pp. 1–5. [Google Scholar]
Pllaha, T.; Tirkkonen, O.; Calderbank, R. Reconstruction of multi-user binary subspace chirps. In Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, 21–26 June 2020; pp. 531–536. [Google Scholar]
Pllaha, T.; Tirkkonen, O.; Calderbank, R. Binary subspace chirps. IEEE Trans. Inf. Theory 2022, 68, 7735–7752. [Google Scholar] [CrossRef]
Abbe, E.; Ye, M. Reed-Muller codes polarize. IEEE Trans. Inf. Theory 2020, 66, 7311–7332. [Google Scholar] [CrossRef]
Abbe, E.; Shpilka, A.; Ye, M. Reed–Muller codes: Theory and algorithms. IEEE Trans. Inf. Theory 2020, 67, 3251–3277. [Google Scholar] [CrossRef]
Calderbank, R.; Howard, S.; Jafarpour, S. Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property. IEEE J. Sel. Top. Signal Process. 2022, 4, 358–374. [Google Scholar] [CrossRef]
Rengaswamy, N.; Calderbank, R.; Kadhe, S.; Pfister, H.D. Logical Clifford synthesis for stabilizer codes. IEEE Trans. Quantum Eng. 2020, 1, 1–17. [Google Scholar] [CrossRef]
Maslov, D.; Roetteler, M. Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations. IEEE Trans. Inf. Theory 2018, 64, 4729–4738. [Google Scholar] [CrossRef]

Figure 1. The top line is the indexes of bit position. White = 0, Blue = 1, Purple =

- 1

, Orange= i, Green =

- i

Figure 1. The top line is the indexes of bit position. White = 0, Blue = 1, Purple =

- 1

, Orange= i, Green =

- i

Figure 2. The diagram of the transmitter technique in our proposed URA system.

Figure 3. The distribution of PRM sequences across slots for

\ddot{m} = 8

r = 5

and

m = 8

for the benchmark scheme, both under

K_{a} = 100

Figure 3. The distribution of PRM sequences across slots for

\ddot{m} = 8

r = 5

and

m = 8

for the benchmark scheme, both under

K_{a} = 100

Figure 4. The distribution of PRM sequences across slots for

\ddot{m} = 8

r = 5

and

m = 8

for the benchmark scheme, both under

K_{a} = 150

Figure 4. The distribution of PRM sequences across slots for

\ddot{m} = 8

r = 5

and

m = 8

for the benchmark scheme, both under

K_{a} = 150

Figure 5. The distribution of PRM sequences across slots for

\ddot{m} = 8

r = 5

and

m = 8

for the benchmark scheme, both under

K_{a} = 200

Figure 5. The distribution of PRM sequences across slots for

\ddot{m} = 8

r = 5

and

m = 8

for the benchmark scheme, both under

K_{a} = 200

Figure 6. The distribution of PRM sequences across slots for

\ddot{m} = 8

r = 6

and

K_{a} = 100

Figure 6. The distribution of PRM sequences across slots for

\ddot{m} = 8

r = 6

and

K_{a} = 100

Figure 7. The performance for quasi-static Rayleigh fading channel is expressed as the required

E_{b} / N_{0}

per active user vs. the number of active users

K_{a}

, given the channel uses

T = 32, 768

, the users’ messages

B = 10

bits and the target error probability

P_{e} = 10^{- 1}

P_{f} = 10^{- 3}

. The optimal parameters in our PRM-based scheme are carefully chosen to minimize the required

E_{b} / N_{0}

. The curves are presented as follows: t-tree code for

t = 1, \dots, 5

from [22], PRM-tree scheme (optimal parameters are taken from the Table 1 and Table 2), Reed–Solomon scheme from [22] and PRM-RS scheme (optimal parameters are taken from Table 3).

Figure 7. The performance for quasi-static Rayleigh fading channel is expressed as the required

E_{b} / N_{0}

per active user vs. the number of active users

K_{a}

, given the channel uses

T = 32, 768

, the users’ messages

B = 10

bits and the target error probability

P_{e} = 10^{- 1}

P_{f} = 10^{- 3}

. The optimal parameters in our PRM-based scheme are carefully chosen to minimize the required

E_{b} / N_{0}

. The curves are presented as follows: t-tree code for

t = 1, \dots, 5

from [22], PRM-tree scheme (optimal parameters are taken from the Table 1 and Table 2), Reed–Solomon scheme from [22] and PRM-RS scheme (optimal parameters are taken from Table 3).

Figure 8. Probability of error

P_{e}

vs.

E_{b} / N_{0}

for three system loads (number of active users),

K_{a} = 130, 180

and 220.

Figure 8. Probability of error

P_{e}

vs.

E_{b} / N_{0}

for three system loads (number of active users),

K_{a} = 130, 180

and 220.

Table 1. Optimal G-ary,

x_{p}

and J-ary, as well as the outer-code length H (and rate

R = \frac{B}{H {log}_{2} J}

) for different t.

Table 1. Optimal G-ary,

x_{p}

and J-ary, as well as the outer-code length H (and rate

R = \frac{B}{H {log}_{2} J}

) for different t.

t	G	$x_{p}$	J	$K_{a} = 50$	$K_{a} = 100$	$K_{a} = 150$	$K_{a} = 200$
$t = 1$	19	9	10	$32 (0.3125)$	$32 (0.3125)$	$32 (0.2232)$	$32 (0.3125)$
$t = 2$	15	7	8	$64 (0.1953)$	$64 (0.1953)$	−	−
$t = 3$	15	7	8	$64 (0.1953)$	$64 (0.1953)$	−	−

Table 2. URA system parameters for “PRM-tree” scheme.

Parameter Description	Specific Value
Transmit a message of size, B	100 bits
PRM sequence length, $N = 2^{m}$	$2^{7} (m = 7)$
The length of RS codes, $H = 2^{r}$	$2^{5} (r = 5) / 2^{6} (r = 6)$
The number of slots, $N_{T}$	$2^{8} (\ddot{m} = 8)$
The number of complex channel uses, T	$2^{15}$
The capacity of slot-occupation pool, ${\| Ω \|}_{r}$	$448 (r = 5) / 112 (r = 6)$
The length of slot-occupation control, $x_{p}$	$9 / 7$
G-ary	$19 / 15$
J-ary	$10 / 8$
The capacity of PRM codebook, $\| Γ_{Υ} \|$	$286,720 (Υ = 3) / 21,504 (Υ = 2)$
The code rate	$0.3125 / 0.1953$

Table 3. URA system parameters for “PRM-RS” scheme.

Parameter Description	Specific Value
Transmit a message of size, B	100 bits
PRM sequence length, $N = 2^{m}$	$2^{7} (m = 7)$
The length of RS codes, $H = 2^{r}$	$2^{5} (r = 5)$
The number of slots, $N_{T}$	$2^{8} (\ddot{m} = 8)$
The number of complex channel uses, T	$2^{15}$
The capacity of slot-occupation pool, ${\| Ω \|}_{r}$	$448 (r = 5)$
The length of slot-occupation control, $x_{p}$	9
G-ary	15
J-ary	6
The capacity of PRM codebook, $\| Γ_{Υ} \|$	$21,504 (Υ = 2)$
The code rate of RS	$0.5208$

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Xie, W.; Zhang, H. Patterned Reed–Muller Sequences with Outer A-Channel Codes and Projective Decoding for Slot-Controlled Unsourced Random Access. Sensors 2023, 23, 5239. https://doi.org/10.3390/s23115239

AMA Style

Xie W, Zhang H. Patterned Reed–Muller Sequences with Outer A-Channel Codes and Projective Decoding for Slot-Controlled Unsourced Random Access. Sensors. 2023; 23(11):5239. https://doi.org/10.3390/s23115239

Chicago/Turabian Style

Xie, Wenjiao, and Huisheng Zhang. 2023. "Patterned Reed–Muller Sequences with Outer A-Channel Codes and Projective Decoding for Slot-Controlled Unsourced Random Access" Sensors 23, no. 11: 5239. https://doi.org/10.3390/s23115239

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Patterned Reed–Muller Sequences with Outer A-Channel Codes and Projective Decoding for Slot-Controlled Unsourced Random Access

Abstract

1. Introduction

1.1. Main Contributions of the Paper

1.2. Notation

2. System Model

3. Reed–Muller Sequences

3.1. Binary RM Codes

3.2. Geometry of Complex RM Sequence

4. Expansion of Complex Reed–Muller Sequences

4.1. Patterned Reed–Muller Codes

4.2. Geometry Property of PRM sequence

4.3. The Proposed Geometry-Based PRM Detection

5. Unsourced Random Access Scheme Using Patterned Reed–Muller Sequence

5.1. Transmitter

5.1.1. Transmitter Design

5.1.2. The Construction of Slot-Pattern-Control Pool

5.2. Slot-Based PRM Detection and Reed–Solomon List Recovery Decoding

6. Performance Analysis

The PRM Distribution for a Single Slot

7. Simulation Results

7.1. The Distribution of Slot-Based PRM Sequences

7.2. The Overall Performance of the SPC-Based CCS for URA System

7.2.1. t-Tree Code as the Outer Code

7.2.2. PRM-Based Reed–Solomon Scheme

8. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI