# Faster-than-Nyquist Asynchronous NOMA Outperforms Synchronous NOMA

Shuangyang Li, Zhiqiang Wei, Weijie Yuan, Jinhong Yuan, Baoming Bai, , Derrick
Wing Kwan Ng, , and Lajos Hanzo  Part of the paper was presented in the IEEE
Wireless Communications and Networking Conference 2021 [1].

###### Abstract

Faster-than-Nyquist (FTN) signaling aided non-orthogonal multiple access
(NOMA) is conceived and its achievable rate is quantified in the presence of
_random_ link delays of the different users. We reveal that exploiting the
link delays may potentially lead to a signal-to-interference-plus-noise ratio
(SINR) gain, while transmitting the data symbols at FTN rates has the
potential of increasing the degree-of-freedom (DoF). We then unveil the
fundamental trade-off between the SINR and DoF. In particular, at a
sufficiently high symbol rate, the SINR gain vanishes while the DoF gain
achieves its maximum, where the achievable rate is almost $(1+\beta)$ times
higher than that of the conventional synchronous NOMA transmission in the high
signal-to-noise ratio (SNR) regime, with $\beta$ being the roll-off factor of
the signaling pulse. Our simulation results verify our analysis and
demonstrate considerable rate improvements over the conventional power-domain
NOMA scheme.

###### Index Terms:

NOMA, asynchronous transmission, achievable rate, faster-than-Nyquist
signaling

##  I Introduction

The escalating number of wireless devices and sensors has inspired exploring
efficient multiple access solutions for future Internet-of-things (IoT)
networks. In particular, non-orthogonal multiple access (NOMA) has been
extensively studied as a promising radio access scheme due to its superiority
in handling massive connectivity [2], which is a crucial requirement for IoT
networks. In contrast to conventional orthogonal multiple access (OMA)
schemes, NOMA allows more than one user to transmit their information via the
same time-frequency resource block, hence enjoying an improved spectral
efficiency via exploiting their channel disparities [3]. However, future
beyond fifth-generation (B5G) wireless networks are expected to attain even
higher spectral efficiency than the 5G networks [4]. Therefore, the existing
NOMA schemes have to be improved in order to meet the ultra-high data rate
requirement of B5G wireless networks.

Hence, diverse advanced transmission schemes have been proposed in the
literature [5, 6, 7, 8, 9, 10, 11, 12]. For example, a NOMA-based system
design by considering minimum error probability was conceived in [5], where
the effect of realistic imperfect successive interference cancellation (SIC)
was also taken into account for the system design. The simulation results
showed that a superior error performance can be obtained based on the proposed
design compared to the conventional power-domain NOMA. Furthermore, the rate-
splitting multiple access (RSMA) was considered in [6], where each user
partially decoded the interference and treated the rest of the interference as
noise. In this way, RSMA has been shown, by Clerckx _et. al._ , to achieve
both an improved spectral efficiency and an enhanced robustness against
imperfect channel state information at the transmitter [7]. Besides, an
intelligent reflecting surface (IRS) assisted NOMA scheme was designed in [8]
by Ding _et. al._ , where the IRSs are used for beneficially aligning the
cell-edge users’ effective channel vectors with the predetermined spatial
directions in order to improve the overall performance of NOMA transmissions.
Moreover, the sparse code multiple access (SCMA) transmission allows more
users to transmit their information among a less number of resource blocks
using an appropriately designed codebook [9]. By relying on a carefully
constructed codebook, it has been shown that SCMA can achieves a better error
performance than conventional power-domain NOMA [9]. On the other hand,
asynchronous NOMA (aNOMA) transmissions have also been shown to offer an
extended achievable rate region compared to conventional synchronous NOMA
transmissions [10, 11, 1]. Specifically, Haci _et. al._ [10] conceived the
aNOMA concept based on orthogonal frequency-division multiplexing (OFDM) and
showed that the aNOMA scheme outperforms both the conventional synchronous
NOMA scheme and the classic orthogonal frequency-division multiple access
(OFDMA) arrangement in terms of both its bit error rate (BER) and capacity.
Furthermore, time domain (TD) aNOMA transmission was evaluated by Zou _et.
al._ [11], where the authors considered a fixed link delay introduced by each
user and the data was conveyed by finite-duration signaling pulses. Similar to
the frequency domain (FD) aNOMA transmission, the TD aNOMA technique has also
shown advantages in terms of its achievable rate [11]. Moreover, NOMA
transmission based on faster-than-Nyquist (FTN) signaling was also considered
in the literature [12]. Indeed, FTN signaling is a classic non-orthogonal
signaling scheme exhibiting an enhanced spectral efficiency [13, 14, 15, 16],
where data is transmitted at a symbol rate higher than the Nyquist intersymbol
interference (ISI)-free rate111It should be noted that the idea of
transmitting symbols faster is not limited to the TD. For example, it has been
shown that transmitting symbols faster in the FD also enjoys advantages [17,
18]. [19]. Although FTN-based NOMA (FTN-NOMA) transmission is expected to have
an increased achievable rate, its theoretical rate analysis has not been
disseminated in the open literature.

As an extension of the state-of-the-art, we improve the conventional power-
domain NOMA scheme for bandlimited uplink transmissions from two different
perspectives, namely, its signal-to-interference-plus-noise ratio (SINR) and
its degree-of-freedom (DoF). In particular, we show that an SINR gain can be
achieved by exploiting the _link delay difference_ between different users,
while a DoF gain is attained by FTN signaling. However, interestingly enough,
there is a fundamental trade-off between the SINR gain and DoF gain. In fact,
the potential of both the SINR and DoF improvements arise from the spectral
aliasing of signal transmissions under a practical bandwidth constraint. Apart
from the practical benefits of an enhanced throughput, the proposed NOMA
scheme also provides theoretical insights. It is widely recognized that
spectral aliasing occurs when the signal bandwidth is higher than half the
sampling frequency. We reveal two ways of mitigating the effect of spectral
aliasing. The first one is by imposing phase rotations on the signal spectrum
(corresponding to imposing delay for the TD signal), so that the power
spectral density (PSD) at the aliased FD components generally has a reduced
value due to the superposition of adjacent spectra (caused by spectral
aliasing). The second one is to transmit signals at an FTN symbol rate222It
should be noted that the potential DoF gain is not due to the oversampling but
owing to the increased symbol rate at the transmitter side. More details on
this argument can be found in [20].. These two solutions lead to potential
SINR and DoF gains, and we will show that there is a trade-off between these
gains.

To further clarify the above arguments, we conceive more complex but practical
uplink transmission scenarios in this paper, where each user experiences a
_random_ link delay. This is in contrast to the majority of the literature,
e.g., [2, 21] and the references therein, which assumed perfectly time-
synchronous transmission among NOMA users. However, the perfect
synchronization assumption is often unrealistic in practical uplink
transmissions, due to the use of different clock generators adopted at
geographically distributed uplink users and owing to the distance-dependent
propagation delays. As a consequence, the signals from multiple users cannot
be synchronously superimposed at the BS as commonly assumed in the
literature333Although the conception of the 2G system’s adaptive time-frame
alignment has been used, in the face of mobility, non-negligible time-of-
arrival differences are experienced at the uplink receiver. [3, 2, 21]. Given
practical considerations, we study the achievable rates of both the
asynchronous FTN-NOMA (aFTN-NOMA) scheme and the aNOMA scheme (aFTN-NOMA
scheme using Nyquist symbol rate). We also compare them to the achievable
rates of the conventional synchronous power-domain NOMA schemes under the same
channel conditions. In summary, our work is motivated by the following facts:
1) Although FTN-NOMA transmission has been proposed in the literature, its
transmission with arbitrary link delay has not been considered, even though it
is of great practical interest; 2) The theoretical rate analysis of FTN-NOMA
is absent in the literature and the potential rate improvement attained by
asynchronous transmissions due to arbitrary link delays is still not well-
understood; 3) The fundamental relationships between the symbol rate,
asynchronous transmission, and spectrum aliasing has not been unveiled
previously. Furthermore, their effects on the achievable rate has not been
documented. For a better understanding of our motivations and the novelty of
this work, we have summarized the major contributions of the related
literature in Table I in comparison to this work.

TABLE I: Summary of Related Works Related works |  [1] |  [10] |  [11] |  [12] |  This work
---|---|---|---|---|---
Asynchronous transmission |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  ✗ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓
Arbitrary link delay |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  ✗ |  ✗ |  ✗ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓
FTN signaling |  ✗ |  ✗ |  ✗ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓
Achievable rate analysis |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  ✗ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓

Corresponding to the motivations of this work, the main contributions of this
paper are summarized as follows:

  * •

We derive the closed-form expression of the mutual information for aFTN-NOMA
schemes at various symbol rates using SIC detection and specific link delays
for each user.

  * •

In order to characterize the effect of link delays, we propose to apply
bounding techniques to the mutual information derived for each user.
Specifically, we show that the link delay may potentially affect the
achievable rate via changing the discrete-time Fourier transform (DTFT) of the
transmitted signal. Therefore, we derive both the upper- and lower-bounds of
the signal DTFTs that are independent from the link delays.

  * •

Based on the DTFT bounds derived, we invoke Szegö’s Theorem [22] for
characterizing the mutual information of the aFTN-NOMA schemes at various
symbol rates and derive the corresponding upper- and lower-bounds of the
achievable rates. Based on the bounds derived, the influence of the link delay
and symbol rate on the signal spectrum (DTFT) is unveiled. In particular, we
also reveal the relationships between the effect of spectral aliasing and the
link delay as well as the symbol rate.

  * •

We show that exploiting the link delay actually results in an SINR gain, while
increasing the symbol rate may lead to a DoF gain, but there is a trade-off
between them. Explicitly, at a sufficiently high symbol rate, the SINR gain
vanishes, while the DoF gain attains its maximum. In this case, the achievable
rate is essentially the capacity associated with the specific signaling pulse.
Explicitly, this is about $1+\beta$ times higher than the conventional
synchronous NOMA scheme in the high signal-to-noise ratio (SNR) regime, with
$0\leq\beta\leq 1$ being the FD roll-off factor of the signaling pulse.

  * •

Simulation results confirm the accuracy of our analysis, and demonstrate a
significant improvement in terms of the rate attained by the aFTN-NOMA scheme
compared to the perfectly synchronous NOMA scheme.

_Notations:_ $\max\left\\{{\cdot}\right\\}$ and $\min\left\\{{\cdot}\right\\}$
denote the maximization and minimization operations, respectively; $\otimes$
denotes the convolution operation; $I\left(\cdot;\cdot\right)$ and
$h\left(\cdot\right)$ denote the mutual information and the differential
entropy, respectively; $\delta(\cdot)$ denotes the Dirac delta function;
${{\bf I}_{N\times N}}$ denotes the identity matrix of size $N\times N$; the
notations $(\cdot)^{\rm{T}}$, $(\cdot)^{*}$ represent the transpose and the
conjugate operations for a matrix, respectively; the blackboard bold letter
${\mathbb{E}}\left[{\cdot}\right]$, and ${\mathbb{C}}$ denote the expectation
operator and the complex number field, respectively.

##  II System Model

Let us consider a pair of single-carrier asynchronous NOMA uplink schemes
transmitting over block-fading channels. Specifically, we assume that there
are $K$ users and each user transmits $N$ information symbols, i.e.,
${{\bf{x}}_{k}}={\left[{{x_{k}}\left[0\right],{x_{k}}\left[1\right],\ldots,{x_{k}}\left[{N-1}\right]}\right]^{\rm{T}}}$,
for $1\leq k\leq K$. To model the asynchronous transmissions, we assume a
_random_ link delay $\tau\left[k\right],1\leq k\leq K$, for each user. We
adopt the common block-fading channel model of NOMA systems. Let $d_{k}$
denote the distance between the $k$-th user and the base station (BS) and
$\alpha$ represent the path loss factor. Then, the channel coefficient
${h_{k}\in{\mathbb{C}}},1\leq k\leq K$, of the $k$-th user is assumed to be
complex-valued Gaussian distributed with a zero mean and variance of
$\frac{1}{{1+d_{k}^{\alpha}}}$ [3, 23]. Let $T$ denote the Nyquist symbol
duration. Without loss of generality, we consider the root raised cosine (RRC)
pulse having an FD roll-off factor $0\leq\beta\leq 1$ as our signaling pulse
$p(t)$, which is bandlimited, real-valued, and $T$-orthogonal with a
normalized energy, i.e.,
$\int_{-\infty}^{\infty}{{{\left|{p\left(t\right)}\right|}^{\rm{2}}}}{\rm{d}}t=1$.
The Fourier transform of $p(t)$ is denoted by ${{H_{p}}\left(f\right)}$, which
is strictly bandlimited within the frequency interval of
$f\in\left[{-W,W}\right]$, with
$W\buildrel\Delta\over{=}\frac{{1+\beta}}{{2T}}$ denoting the baseband
bandwidth. In what follows, we will present the system models of both NOMA
schemes considered. For the ease of presentation, we will slightly abuse the
related notations without causing ambiguity.

###  II-A Asynchronous NOMA Scheme

For the aNOMA scheme, the $k$-th user’s transmitted signal is of the following
form [1]:

${s_{k}}\left(t\right)=\sqrt{{E_{s}}\left[k\right]}\sum\limits_{n=0}^{N-1}{{x_{k}}\left[n\right]p\left({t-nT}\right)},$
(1)

where ${{E_{s}}\left[k\right]}$ is the average symbol energy of the $k$-th
user. Then, the signal $r\left(t\right)$ received by the BS is given by

$r\left(t\right)=\sum\limits_{k=1}^{K}{{h_{k}}{s_{k}}\left({t-\tau\left[k\right]}\right)}+w\left(t\right)=\sum\limits_{k=1}^{K}{\sum\limits_{n=0}^{N-1}{{h_{k}}\sqrt{{E_{s}}\left[k\right]}{x_{k}}\left[n\right]p\left({t-nT-\tau\left[k\right]}\right)}}+w\left(t\right),$
(2)

where $w\left(t\right)\in{\mathbb{C}}$ is the additive white Gaussian noise
(AWGN) at the BS with zero mean and one-sided PSD $N_{0}$. For illustrating
the asynchronous transmission, we provide a brief diagram in Fig. 1(a), where
we consider the uplink transmission of $3$ users having the specific link
delays of $0$, $\frac{2}{5}T$, and $\frac{6}{5}T$, respectively.

(a) Diagram of aNOMA transmissions, where $K=3$ users are considered and their
link delays are $0$, $\frac{2}{5}T$, and $\frac{6}{5}T$, respectively.

(b) Diagram of aFTN-NOMA transmissions, where $K=3$ users are considered and
their link delays are $0$, $\frac{2}{5}T$, and $\frac{6}{5}T$, respectively.

(c) Diagram of NOMA transmissions, where $K=3$ users are considered.

Figure 1: The uplink transmission diagram of considered scheme, where $K=3$
users are considered.

Observe from the diagram that there is no ISI between the information symbols
of a given user due to the $T$-orthogonal property, while each information
symbol of the $k$-th user is interfered with all the information symbols of
the other users due to the asynchronous transmission. This is the ubiquitous
multi-user interference (MUI). By performing matched-filtering and Nyquist
rate sampling for $r\left(t\right)$, the $n$-th element of the received symbol
vector corresponding to the $k$-th user
${{\bf{y}}_{k}}={\left[{{y_{k}}\left[0\right],{y_{k}}\left[1\right],\ldots,{y_{k}}\left[{N-1}\right]}\right]^{\rm{T}}}$
is given by

$\displaystyle{y_{k}}\left[n\right]\\!$
$\displaystyle=\\!\int\limits_{-\infty}^{\infty}\\!\\!{r\left(t\right){p^{*}}\left({t-nT-\tau\left[k\right]}\right)}{\rm{d}}t=\\!\sum\limits_{l=1}^{K}{\sum\limits_{m=0}^{N-1}{{h_{l}}\sqrt{{E_{s}}\left[l\right]}{x_{l}}\left[m\right]g\left[{m\\!-\\!n,\tau\left[l\right]\\!-\\!\tau\left[k\right]}\right]}}\\!+\\!{\eta_{k}}\left[n\right].$
(3)

In (3), the term ${g\left[{m-n,\tau\left[l\right]-\tau\left[k\right]}\right]}$
represents the MUI between different users for the aNOMA scheme, which is
given by

$g\left[{\Delta
k,{\Delta\tau}}\right]\buildrel\Delta\over{=}\int\limits_{-\infty}^{\infty}{p\left(t\right){p^{*}}\left({t+\Delta
kT+{\Delta\tau}}\right)}{\rm{d}}t=\int\limits_{-\infty}^{\infty}{{{\left|{{H_{p}}\left(f\right)}\right|}^{2}}\exp\left({j2\pi
f\left({\Delta kT+{\Delta\tau}}\right)}\right)}{\rm{d}}f,$ (4)

where the second equation is due to the Parseval’s Theorem. The term
${\eta_{k}}\left[n\right]$ in (3) denotes the corresponding colored noise
sample, where
$\mathbb{E}\left\\{{{\eta_{k}}\left[n\right]\eta_{l}^{*}\left[m\right]}\right\\}={N_{0}}g\left[{m-n,\tau\left[l\right]-\tau\left[k\right]}\right]$.
For the ease of presentation, (3) can be equivalently expressed in the matrix
form of

${{\bf{y}}_{k}}=\sum\limits_{l=1}^{K}{{h_{l}}\sqrt{{E_{s}}\left[l\right]}{{\bf{G}}_{l,k}}{{\bf{x}}_{l}}+{{\bm{\eta}}_{k}}},$
(5)

where ${{{\bf{G}}_{l,k}}}$ is the _MUI channel matrix_ of the aNOMA scheme,
characterizing the MUI inflicted by the $l$-th user upon the $k$-th user,
given by

${{\bf{G}}_{l,k}}=\left[{\begin{array}[]{*{20}{c}}{g\left[{0,\tau\left[l\right]-\tau\left[k\right]}\right]}&{g\left[{1,\tau\left[l\right]-\tau\left[k\right]}\right]}&\cdots&{g\left[{N-1,\tau\left[l\right]-\tau\left[k\right]}\right]}\\\
{g\left[{-1,\tau\left[l\right]-\tau\left[k\right]}\right]}&{g\left[{0,\tau\left[l\right]-\tau\left[k\right]}\right]}&\cdots&{g\left[{N-2,\tau\left[l\right]-\tau\left[k\right]}\right]}\\\
\vdots&{}\hfil&\ddots&\vdots\\\
{g\left[{1-N,\tau\left[l\right]-\tau\left[k\right]}\right]}&{g\left[{2-N,\tau\left[l\right]-\tau\left[k\right]}\right]}&\cdots&{g\left[{0,\tau\left[l\right]-\tau\left[k\right]}\right]}\end{array}}\right].$
(6)

It can be shown that ${\bf{G}}_{l,k}$ is a Toeplitz matrix and we have
${{\bf{G}}_{k,k}}={{\bf{I}}_{N\times N}}$ for $1\leq k\leq K$. Meanwhile, the
noise vector ${{\bm{\eta}}_{k}}$ is given by
${{\bm{\eta}}_{k}}={\left[{{\eta_{k}}\left[0\right],{\eta_{k}}\left[1\right],...,{\eta_{k}}\left[{N-1}\right]}\right]^{\rm{T}}}$,
for $1\leq k\leq K$, and it can be shown that
$\mathbb{E}\left\\{{{\eta_{k}}\left[m\right]\eta_{k}^{*}\left[n\right]}\right\\}={N_{0}}$,
for $1\leq k\leq K$ and $0\leq n,m\leq N-1$.

###  II-B Asynchronous FTN-NOMA Scheme

For the aFTN-NOMA scheme, the $k$-th user’s transmitted signal is given by

${\tilde{s}_{k}}\left(t\right)=\sqrt{{E_{s}}\left[k\right]}\sum\limits_{n=0}^{N-1}{{x_{k}}\left[n\right]p\left({t-n\zeta
T}\right)},$ (7)

where $\zeta\in\left[{0,1}\right]$ denotes the TD compression factor and the
symbol period of the aFTN-NOMA scheme is $\zeta T$ [24, 25]. Similar to the
previous subsection, the signal ${\tilde{r}}\left(t\right)$ received by the BS
is given by

$\tilde{r}\left(t\right)=\sum\limits_{k=1}^{K}{{h_{k}}{{\tilde{s}}_{k}}\left({t-\tau\left[k\right]}\right)}+w\left(t\right)=\sum\limits_{k=1}^{K}{\sum\limits_{n=0}^{N-1}{{h_{k}}\sqrt{{E_{s}}\left[k\right]}{x_{k}}\left[n\right]p\left({t-n\zeta
T-\tau\left[k\right]}\right)}}+w\left(t\right).$ (8)

The transmission diagram of the aFTN-NOMA scheme having $\zeta=0.5$ is shown
in Fig. 1(b), where $3$ users having specific link delays $0$, $\frac{2}{5}T$,
and $\frac{6}{5}T$ are considered. In contrast to Fig. 1(a), each information
symbol is interfered by all the other information symbols among all users
owing to both the FTN symbol rate and the asynchronous transmission. For
matched-filtering and FTN-rate sampling, the $n$-th element of the received
symbol vector corresponding to the $k$-th user
${{\bf{y}}_{k}}={\left[{{y_{k}}\left[0\right],{y_{k}}\left[1\right],\ldots,{y_{k}}\left[{N-1}\right]}\right]^{\rm{T}}}$
is given by

$\displaystyle{y_{k}}\left[n\right]$
$\displaystyle=\int\limits_{-\infty}^{\infty}{{\tilde{r}}\left(t\right){p^{*}}\left({t-n\zeta
T-\tau\left[k\right]}\right)}{\rm{d}}t$
$\displaystyle=\sum\limits_{l=1}^{K}{\sum\limits_{m=0}^{N-1}{{h_{l}}\sqrt{{E_{s}}\left[l\right]}{x_{l}}\left[m\right]{\tilde{g}}_{\zeta}\left[{m-n,\tau\left[l\right]-\tau\left[k\right]}\right]}}+{{\tilde{\eta}}_{k}}\left[n\right].$
(9)

In (9), the term ${\tilde{g}}_{\zeta}\left[{\Delta k,{\Delta\tau}}\right]$
represents the MUI between different information symbols given by

${\tilde{g}}_{\zeta}\left[{\Delta
k,{\Delta\tau}}\right]\buildrel\Delta\over{=}\\!\\!\\!\int\limits_{-\infty}^{\infty}{p\left(t\right){p^{*}}\left({t+\Delta
k{\zeta}T+{\Delta\tau}}\right)}{\rm{d}}t\\!=\\!\\!\\!\int\limits_{-\infty}^{\infty}{{{\left|{{H_{p}}\left(f\right)}\right|}^{2}}\exp\left({j2\pi
f\left({\Delta k{\zeta}T+{\Delta\tau}}\right)}\right)}{\rm{d}}f.$ (10)

The term ${{\tilde{\eta}}_{k}}\left[n\right]$ in (9) denotes the corresponding
colored noise sample, where
$\mathbb{E}\left\\{{{{\tilde{\eta}}_{k}}\left[n\right]{\tilde{\eta}}_{l}^{*}\left[m\right]}\right\\}={N_{0}}{\tilde{g}}_{\zeta}\left[{m-n,\tau\left[l\right]-\tau\left[k\right]}\right]$.
Similar to the previous subsection, we consider the equivalent matrix
expression of (9), i.e.,

${{\bf{y}}_{k}}=\sum\limits_{l=1}^{K}{{h_{l}}\sqrt{{E_{s}}\left[l\right]}{\tilde{\bf{G}}_{l,k}}{{\bf{x}}_{l}}+{\tilde{\bm{\eta}}_{k}}},$
(11)

where ${\tilde{\bf{G}}_{l,k}}$ is the _MUI channel matrix_ for the aFTN-NOMA
scheme, characterizing the interference inflicted by the $l$-th user on the
$k$-th user, given by

${\tilde{\bf{G}}_{l,k}}=\left[{\begin{array}[]{*{20}{c}}{{\tilde{g}}_{\zeta}\left[{0,\tau\left[l\right]-\tau\left[k\right]}\right]}&{{\tilde{g}}_{\zeta}\left[{1,\tau\left[l\right]-\tau\left[k\right]}\right]}&\cdots&{{\tilde{g}}_{\zeta}\left[{N-1,\tau\left[l\right]-\tau\left[k\right]}\right]}\\\
{{\tilde{g}}_{\zeta}\left[{-1,\tau\left[l\right]-\tau\left[k\right]}\right]}&{{\tilde{g}}_{\zeta}\left[{0,\tau\left[l\right]-\tau\left[k\right]}\right]}&\cdots&{{\tilde{g}}_{\zeta}\left[{N-2,\tau\left[l\right]-\tau\left[k\right]}\right]}\\\
\vdots&{}\hfil&\ddots&\vdots\\\
{{\tilde{g}}_{\zeta}\left[{1-N,\tau\left[l\right]-\tau\left[k\right]}\right]}&{{\tilde{g}}_{\zeta}\left[{2-N,\tau\left[l\right]-\tau\left[k\right]}\right]}&\cdots&{{\tilde{g}}_{\zeta}\left[{0,\tau\left[l\right]-\tau\left[k\right]}\right]}\end{array}}\right].$
(12)

Again, ${\tilde{\bf{G}}_{l,k}}$ is a Toeplitz matrix and the noise vector
${\tilde{\bm{\eta}}}_{k}$ is given by
${\tilde{\bm{\eta}}}_{k}={\left[{{{\tilde{\eta}}_{k}}\left[0\right],{{\tilde{\eta}}_{k}}\left[1\right],...,{{\tilde{\eta}}_{k}}\left[{N-1}\right]}\right]^{\rm{T}}}$,
where
${\mathbb{E}}\left\\{{{{\tilde{\bm{\eta}}}_{k}}{\tilde{\bm{\eta}}}_{k}^{H}}\right\\}={N_{0}}{\widetilde{\bf{G}}_{k,k}}$.

###  II-C Connections to the Conventional Synchronous NOMA Scheme

Conventionally, the impact of link delay difference is assumed to be perfectly
eliminated by adaptive time frame alignment schemes at the BS [3, 26] for
synchronous NOMA transmission. Consequently, the signals transmitted from
different users are perfectly aligned with each other at the BS, as shown in
Fig. 1(c). By comparing aNOMA, aFTN-NOMA, and conventional synchronous NOMA
schemes, it is plausible that the aFTN-NOMA scheme is the most general scheme.
More specifically, when the compression factor is $\zeta=1$, the aFTN-NOMA
scheme degenerates to the aNOMA scheme. When there is no link delay difference
among the users, the aNOMA scheme degenerates to the conventional synchronous
NOMA scheme.

On the other hand, we notice that both the aNOMA and aFTN-NOMA schemes have at
most $KN$ received symbols at the BS, while the conventional synchronous NOMA
only has $N$ received symbols. Furthermore, we also notice that the aNOMA,
aFTN-NOMA and conventional synchronous NOMA schemes generally occupy different
time resources. Let
${\tau_{\max}}=\max\left\\{{\tau[1],\tau[2],...,\tau[K]}\right\\}$ be the
maximum link delay, which is usually negligible compared to the frame duration
of the signals transmitted in practical systems [26, 27]. To support each user
transmitting $N$ information symbols, the conventional synchronous NOMA scheme
roughly requires $NT$ seconds for its transmission, aNOMA scheme requires
$NT+\tau_{\max}$ seconds, while the aFTN-NOMA scheme only requires $N\zeta
T+\tau_{\max}$ [28, 29].

In the following, we investigate the achievable rates of both the aNOMA and
aFTN-NOMA schemes based on (5) and (11).

##  III Achievable Rate Analysis

In this section, we focus our attention on the achievable rates of both the
aNOMA and aFTN-NOMA schemes. We will first derive the closed-form expression
of the mutual information for the uplink transmission and then apply Szegö’s
Theorem [22, 30] to obtain further important insights. Particularly, Szegö’s
Theorem is closely related to the DTFT of the underlying Toeplitz
coefficients. Therefore, we will also investigate the characteristics of the
DTFT with respect to the link delay and symbol rate. For the ease of
derivation, we assume that the elements in the transmitted symbol vector
${\bf{x}}_{k}$ are independent and identically distributed (i.i.d.) complex
Gaussian variables with average symbol energy $E_{s}[k]$, for $\forall k$,
$1\leq k\leq K$. Since the aNOMA scheme can be viewed as a special case of the
aFTN-NOMA scheme with $\zeta=1$, we will commence with the analysis of the
aFTN-NOMA scheme.

Without loss of generality, let us assume that the channel coefficients are
sorted in descending order, i.e.,
$|h_{1}|^{2}\geq|h_{2}|^{2}\geq...\geq|h_{K}|^{2}$. Conventionally, SIC
detection is applied at the BS for general NOMA systems444We note that some
lattice-coding-based approaches can be applied to replace the SIC detection
[31, 32]. [3]. To analyze the achievable rates, it is commonly assumed that
the MUI introduced by users $1,2,\ldots,k-1$ is perfectly cancelled for the
detection of the $k$-th user [3]. Therefore, the asymptotic instantaneous
achievable rate for the $k$-th user under SIC detection is given by

$R_{{\bf{h}},{\bm{\tau}},\zeta}^{{k}}\buildrel\Delta\over{=}\mathop{\lim}\limits_{N\to\infty}\frac{1}{N}{{I_{{\bf{h}},{\bm{\tau}},\zeta}}}\left({{{\bf{y}}_{k}};{{\bf{x}}_{k}}|{{\bf{x}}_{1}},\ldots,{{\bf{x}}_{k-1}}}\right)\quad{\rm
bits\;per}\;{\rm{channel\;use}}.$ (13)

In particular, the closed-form expression of
${{I_{{\bf{h}},{\bm{\tau}},\zeta}}}\left({{{\bf{y}}_{k}};{{\bf{x}}_{k}}|{{\bf{x}}_{1}},\ldots,{{\bf{x}}_{k-1}}}\right)$
is formulated in the following lemma.

Lemma 1 (_Conditional Mutual Information for SIC Detection_): For SIC
detection, the conditional mutual information
${{I_{{\bf{h}},{\bm{\tau}},\zeta}}}\left({{{\bf{y}}_{k}};{{\bf{x}}_{k}}|{{\bf{x}}_{1}},\ldots,{{\bf{x}}_{k-1}}}\right)$
of the aFTN-NOMA scheme is given by

$\displaystyle{{I_{{\bf{h}},{\bm{\tau}},\zeta}}}\left({{{\bf{y}}_{k}};{{\bf{x}}_{k}}|{{\bf{x}}_{1}},\ldots,{{\bf{x}}_{k-1}}}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\log_{2}\det\left[{{{\bf{I}}_{N\times
N}}+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{E_{s}}\left[k\right]{{{\bf{\tilde{G}}}}_{k,k}}{\bf{\tilde{G}}}_{k,k}^{\rm{T}}}}{{{N_{0}}}}{{\left({{{{\bf{\tilde{G}}}}_{k,k}}+\frac{{\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]}}}{{{N_{0}}}}{{{\bf{\tilde{G}}}}_{l,k}}{\bf{\tilde{G}}}_{l,k}^{\rm{T}}}\right)}^{-1}}}\right].$
(14)

_Proof_ : The proof is given in Appendix A.

The above equation is essentially the mutual information calculation over the
channel with colored Gaussian noise, where the covariance matrix of the noise
samples plus the interference is given by
${{N_{0}}{{{\bf{\tilde{G}}}}_{k,k}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]}{{{\bf{\tilde{G}}}}_{l,k}}{\bf{\tilde{G}}}_{l,k}^{\rm{T}}}$.
It can be observed from Lemma 1 that due to the link delay and the symbol rate
of each user, the corresponding interference term of the aFTN-NOMA systems for
the $k$-th user is different from that of the conventional synchronous NOMA
systems. With the help of Lemma 1, we now proceed to analyze the asymptotic
instantaneous achievable rate $R_{{\bf{h}},{\bm{\tau}},\zeta}^{{k}}$ by
invoking Szegö’s Theorem in order to obtain further important insights. For
reference, Szegö’s Theorem is stated as follows.

Lemma 2 (_Szegö’s Theorem[22, 30]_): Let ${\bf{V}}$ denote a size $N\times N$
positive definite Toeplitz matrix ${\bf{V}}$, i.e.,

${\bf{V}}=\left[{\begin{array}[]{*{20}{c}}{{v_{0}}}&{{v_{1}}}&\cdots&{{v_{N-1}}}\\\
{{v_{-1}}}&{{v_{0}}}&\cdots&{{v_{N-2}}}\\\ \vdots&{}\hfil&\ddots&\vdots\\\
{{v_{1-N}}}&{{v_{2-N}}}&\cdots&{{v_{0}}}\end{array}}\right],$ (15)

whose eigenvalues are given by
$\left\\{{{\lambda_{0}},{\lambda_{1}},\ldots{\lambda_{N-1}}}\right\\}$. Then,
for an arbitrary continuous function $f_{c}(\cdot)$, we have

$\mathop{\lim}\limits_{N\to\infty}\frac{1}{N}\sum\limits_{n=0}^{N-1}{{f_{c}}\left({{\lambda_{n}}}\right)=\frac{1}{{2\pi}}\int_{-\pi}^{\pi}{{f_{c}}\left({V\left(\omega\right)}\right){\rm{d}}\omega}},$
(16)

where ${V\left(\omega\right)}$ is the corresponding DTFT of the Toeplitz
coefficients
$\left\\{{\ldots,{v_{-2}},{v_{-1}},{v_{0}},{v_{1}},{v_{2}},\ldots}\right\\}$,
and it is given by

$V\left(\omega\right)=\sum\limits_{k=-\infty}^{\infty}{{v_{k}}{e^{-jk\omega}}}.$
(17)

Szegö’s Theorem is a classic tool eminently suitable for analyzing the
determinant of Toeplitz matrices, which is rooted in the FD characteristics of
the Toeplitz coefficients, i.e., the DTFT. In particular, DTFT analysis has
been widely applied in the research of signal sampling, which describes the FD
representation of the underlying samples. Let us define
${{\bf{T}}_{l,k}}\buildrel\Delta\over{=}{{{\bf{\tilde{G}}}}_{l,k}}{\bf{\tilde{G}}}_{l,k}^{\rm{T}}$
and

${{\bf{P}}_{k}}\buildrel\Delta\over{=}{{\bf{I}}_{N\times
N}}+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{E_{s}}\left[k\right]{{\bf{T}}_{k,k}}}}{{{N_{0}}}}{\left({{{{\bf{\tilde{G}}}}_{k,k}}+\frac{{\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]}}}{{{N_{0}}}}{{\bf{T}}_{l,k}}}\right)^{-1}}.$
(18)

To apply Szegö’s Theorem, we first have to verify that ${{\bf{P}}_{k}}$ is a
positive definite Toeplitz matrix in the asymptotic regime, i.e.,
$N\to\infty$, for any $1\leq k\leq K$. Specifically, we have the following
lemma.

Lemma 3 (_Positive Definiteness of the Asymptotical Toeplitz Matrix_): As
$N\to\infty$, both ${{{\bf{\tilde{G}}}}_{l,k}}$ and ${{\bf{T}}_{l,k}}$ are
asymptotically positive definite Toeplitz matrices for any $1\leq k\leq K$.
Furthermore, ${{\bf{P}}_{k}}$ is also an asymptotically positive definite
Toeplitz matrix for $1\leq k\leq K$ as $N\to\infty$.

_Proof_ : The proof is given in Appendix B.

Next, we apply Szegö’s Theorem to (14). The application of Szegö’s Theorem
requires the derivation of the DTFT of the Toeplitz coefficients. As shown in
(14), there are two types of Toeplitz matrices, namely,
${{{\bf{\tilde{G}}}}_{l,k}}$ and ${{\bf{T}}_{l,k}}$. In particular, the
Toeplitz coefficients of ${{{\bf{\tilde{G}}}}_{l,k}}$ are given by
$\left\\{{{{\tilde{g}}_{\zeta}}\left[{n,\tau\left[l\right]-\tau\left[k\right]}\right]}\right\\}$.
On the other hand, it can be shown that in the asymptotic regime, the Toeplitz
coefficients $\left\\{{{t_{l,k}}\left[n\right]}\right\\}$ of the asymptotical
Toeplitz matrix ${{\bf{T}}_{l,k}}$ are given by

${t_{l,k}}\left[n\right]=\sum\limits_{m=-\infty}^{\infty}{{\tilde{g}}_{\zeta}\left[{m,\tau\left[l\right]-\tau\left[k\right]}\right]{\tilde{g}}_{\zeta}\left[{m-n,\tau\left[l\right]-\tau\left[k\right]}\right]}.$
(19)

Correspondingly, the DTFTs of the Toeplitz coefficients
$\left\\{{{{\tilde{g}}_{\zeta}}\left[{n,\tau\left[l\right]-\tau\left[k\right]}\right]}\right\\}$
and $\left\\{{{t_{l,k}}\left[n\right]}\right\\}$ are given by

${{\tilde{G}}_{l,k}}\left({2\pi f\zeta
T}\right)=\sum\limits_{n=-\infty}^{\infty}{{{\tilde{g}}_{\zeta}}\left[{n,\tau\left[l\right]-\tau\left[k\right]}\right]{e^{-j2\pi
n\zeta Tf}}},$ (20)

and

${{\tilde{T}}_{l,k}}\left({2\pi f\zeta
T}\right)=\sum\limits_{n=-\infty}^{\infty}{\sum\limits_{m=-\infty}^{\infty}{{\tilde{g}}_{\zeta}\left[{m,\tau\left[l\right]-\tau\left[k\right]}\right]{\tilde{g}}_{\zeta}\left[{m-n,\tau\left[l\right]-\tau\left[k\right]}\right]}}{e^{-j2\pi
n\zeta Tf}},$ (21)

respectively, where $\omega\buildrel\Delta\over{=}2\pi f\zeta T$. We note that
(20) and (21) depend on both the difference between the link delays of each
user and the compression factor $\zeta$. However, the link delays’ difference
is time-variant and it is therefore generally intractable. As an alternative,
we apply bounding techniques to the DTFTs to facilitate the achievable rate
analysis. In particular, the bounds of DTFT depend on the corresponding
spectra of the signaling pulse adopted. Specifically, the spectrum of the RRC
pulse with a roll-off factor $0\leq\beta\leq 1$ is given by

${\left|{{H_{p}}\left(f\right)}\right|^{2}}=\left\\{\begin{array}[]{l}T,\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left|f\right|<\left({1-\beta}\right)/\left({2T}\right),\\\
T{\cos^{2}}\left({\frac{{\pi
T}}{{2\beta}}\left({\left|f\right|-\frac{{1-\beta}}{{2T}}}\right)}\right),\quad\left({1-\beta}\right)/\left({2T}\right)\leq\left|f\right|\leq\left({1+\beta}\right)/\left({2T}\right),\\\
0,\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\left|f\right|>\left({1+\beta}\right)/\left({2T}\right).\end{array}\right.$
(22)

As a building block for our rate analysis, we consider three FD signals
related to ${\left|{{H_{p}}\left(f\right)}\right|^{2}}$ and the symbol rate
$1/\zeta T$.

Definition 1 (_Folded-Spectrum_): Given the symbol rate $1/\zeta T$ and the
underlying signaling pulse spectrum
${\left|{{H_{p}}\left(f\right)}\right|^{2}}$, the _folded-spectrum_ is defined
by

${\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}\buildrel\Delta\over{=}\sum\limits_{k=-\infty}^{\infty}{{{\left|{H_{p}\left({f-\frac{k}{{\zeta
T}}}\right)}\right|}^{2}}},$ (23)

for $f\in\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$ and zero
otherwise.

Definition 2 (_Twisted Folded-Spectrum_): Given the symbol rate $1/\zeta T$
and the underlying signaling pulse spectrum
${\left|{{H_{p}}\left(f\right)}\right|^{2}}$, the _twisted folded-spectrum_ is
defined by

${\left|{{{H}_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}\buildrel\Delta\over{=}{\left|{H_{p}\left(f\right)}\right|^{2}}-\sum\limits_{\scriptstyle
k=-\infty\hfill\atop\scriptstyle k\neq
0\hfill}^{\infty}{{{\left|{H_{p}\left({f-\frac{k}{{\zeta
T}}}\right)}\right|}^{2}}},$ (24)

for $f\in\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$ and zero
otherwise.

Definition 3 (_Interference-Reducing-Spectrum_): Given the symbol rate $\zeta
T$ and the underlying signaling pulse spectrum
${\left|{{H_{p}}\left(f\right)}\right|^{2}}$, the _interference-reducing-
spectrum_ is defined by

$\rho\left(f\right)\buildrel\Delta\over{=}\frac{{{{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}}}}{{{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}},$
(25)

for $f\in\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$ and zero
otherwise.

Indeed, the folded-spectrum is commonly considered in the literature of
faster-than-Nyquist signaling [33, 34] for the associated capacity analysis.
The folded-spectrum indicates that the frequency components outside the
interval $\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$ are
“folded-in” the interval to form an equivalent FD representation of the
transmitted signal. In particular, we refer to this folding effect as
“spectral aliasing”. Spectral aliasing occurs, when the symbol rate is lower
than twice the bandwidth of the signaling pulse, i.e., $\frac{1}{{2\zeta
T}}<W$. On the other hand, the twisted folded-spectrum can be viewed as a
phase-rotated version of the folded-spectrum, which is useful for
characterizing the FD phase rotation corresponding to the time delay.
Furthermore, the interference-reducing-spectrum is the ratio between the
aforementioned two spectra, which can be viewed as an indicator of how
substantially the interference power is reduced due to the phase-rotation.
Noticing that the RRC pulse is strictly bandlimited within the frequency
interval of $f\in\left[-W,W\right]$, it can be shown that
${\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}$ becomes the spectrum of
the _sinc_ pulse ${\left|{H_{\rm sinc}\left(f\right)}\right|^{2}}$, i.e., the
RRC pulse associated with $\beta=0$, when $\zeta=1$. On the other hand, both
${\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}$ and
${\left|{{{H}_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}$ become the exact RRC
spectrum ${\left|{H_{p}\left(f\right)}\right|^{2}}$, when $\zeta\leq
1/(1+\beta)$. For reference, the plots of the folded-spectrum and twisted
folded-spectrum for $\beta=0.5$, $\zeta=1$ and $\beta=0.5$, $\zeta<2/3$ are
provided in Fig. 2(a) and Fig. 2(b), respectively. Furthermore, it may be
readily seen that upon reducing $\zeta$, the value of the interference-
reducing-spectrum $\rho\left(f\right)$ tends to $1$ for
$f\in\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$. In
particular, we have $\rho\left(f\right)=1$ for $f\in\left[{-\frac{1}{{2\zeta
T}},\frac{1}{{2\zeta T}}}\right]$, when $\zeta\leq 1/(1+\beta)$. This
interesting fact actually indicates that when the symbol rate is sufficiently
high, the impact of link delay tends to vanish as will be discussed in Section
III-B. We note that the folded-spectrum, the twisted folded-spectrum and the
interference-reducing-spectrum are important for our analysis, because they
are related to the signaling pulse, but they are affected differently with
respected to the symbol rate $\frac{1}{\zeta T}$. In the following lemma, we
will unveil the intricate relationship between the inverse Fourier series
corresponding to ${\left|{{H_{p}}\left(f\right)}\right|^{2}}$ and the
aforementioned spectra.

(a) ${\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}$ for $\beta=0.5$,
$\zeta=1$ and $\beta=0.5$, $\zeta\leq 2/3$.

(b) ${\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}$ for $\beta=0.5$,
$\zeta=1$ and $\beta=0.5$, $\zeta\leq 2/3$.

Figure 2: Folded-spectrum and twisted folded-spectrum for $\beta=0.5$,
$\zeta=1$ and $\beta=0.5$, $\zeta<2/3$, where $T=1$.

Lemma 4 (_Bounds on the Infinite Fourier Series_): Let $\gamma$ be an
arbitrary constant number. Then, within the frequency interval
$f\in\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$, the infinite
series
$\sum\limits_{k=-\infty}^{\infty}{{{\left|{{H_{p}}\left({f-\frac{k}{\zeta
T}}\right)}\right|}^{2}}}{e^{-j2\pi\gamma k}}$ can be upper-bounded and lower-
bounded by

${\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}\leq\sum\limits_{k=-\infty}^{\infty}{{{\left|{{H_{p}}\left({f-\frac{k}{\zeta
T}}\right)}\right|}^{2}}}{e^{-j2\pi\gamma
k}}\leq{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}},$ (26)

where the bounds in (26) become exact if $\beta=0$, i.e., $p\left(t\right)$ is
the sinc pulse, or $\zeta\leq\frac{1}{1+\beta}$. Meanwhile, the upper-bound
also becomes exact if $\gamma=0$.

_Proof_ : The proof is given in Appendix C.

Lemma 4 characterizes the effect of phase-rotation on the folded-spectrum,
showing that the phase-rotation may potentially change the shape of the
spectrum. Observe that the effect of spectral aliasing vanishes for $\beta=0$
or $\zeta\leq\frac{1}{1+\beta}$. Therefore, Lemma 4 implies that the change
due to the phase-rotation will no longer exist, when there is no spectral
aliasing. This is not unexpected, because when the spectra are sufficiently
separated in the FD, only the spectrum corresponding to $k=0$, i.e.,
${{{\left|{{H_{p}}}(f)\right|}^{2}}}$, has non-zero values in the frequency
interval $f\in\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$. In
this case, the infinite series
$\sum\limits_{k=-\infty}^{\infty}{{{\left|{{H_{p}}\left({f-\frac{k}{\zeta
T}}\right)}\right|}^{2}}}{e^{-j2\pi\gamma k}}$ reduces to
${\left|{{H_{p}}\left(f\right)}\right|^{2}}$, which is independent of the
phase-rotation. Therefore, introducing phase-rotations (link delay) can no
longer affect the value of the folded-spectrum, if there is no spectral
aliasing. Given Lemma 4, the DTFTs with respect to (20) and (21) can be upper-
and lower-bounded for our analysis, as shown in the following theorems.

Theorem 1 (_Bounds on DTFT ${{\tilde{G}}_{l,k}}\left({2\pi f\zeta
T}\right)$_): Given an arbitrary link delay difference
$\Delta\tau\buildrel\Delta\over{=}\tau\left[l\right]-\tau\left[k\right]$, the
DTFT ${{\tilde{G}}_{l,k}}\left({2\pi f\zeta T}\right)$ of the form (20) can be
upper- and lower-bounded by

$\frac{1}{{\zeta
T}}{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}\leq{{\tilde{G}}_{l,k}}\left({2\pi
f\zeta T}\right)\leq\frac{1}{{\zeta
T}}{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}},$ (27)

where the bounds in (27) become exact if $\beta=0$, i.e., when
$p\left(t\right)$ is the sinc pulse, or $\zeta\leq\frac{1}{1+\beta}$.
Meanwhile, the upper-bound also becomes exact if $\Delta\tau=0$, e.g., $l=k$.

_Proof_ : The proof is given in Appendix D.

Theorem 2 (_Bounds on DTFT ${{\tilde{T}}_{l,k}}\left({2\pi f\zeta
T}\right)$_): Given an arbitrary link delay difference
$\Delta\tau\buildrel\Delta\over{=}\tau\left[l\right]-\tau\left[k\right]$, the
DTFT ${{\tilde{T}}_{l,k}}\left({2\pi f\zeta T}\right)$ of the form (21) can be
upper- and lower-bounded by

${\left({\frac{1}{{\zeta
T}}{{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}}}\right)^{2}}\leq{\tilde{T}_{l,k}}\left({2\pi
f\zeta T}\right)\leq{\left({\frac{1}{{\zeta
T}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}\right)^{2}},$ (28)

where the bounds in (27) become exact if $\beta=0$, i.e., if $p\left(t\right)$
is the sinc pulse, or $\zeta\leq\frac{1}{1+\beta}$. Meanwhile, the upper-bound
also becomes exact if $\Delta\tau=0$, e.g., $l=k$.

_Proof_ : The proof is given in Appendix E.

Based on the bounds on the DTFTs of the Toeplitz coefficients, we are ready to
derive the bounds for the achievable rates. In particular, the main result is
given in the following theorem.

Theorem 3 (_Bounds on the Achievable Rates of aFTN-NOMA Scheme_): Let
${P_{k}}\buildrel\Delta\over{=}\frac{{{E_{s}}\left[k\right]}}{{\zeta T}}$
denote the transmit power of the $k$-th user. Then, the asymptotic
instantaneous achievable rate of aFTN-NOMA for the $k$-th user
$R_{{\bf{h}},{\bm{\tau}},\zeta}^{{k}}$ under SIC detection is lower-bounded by

$R_{{\bf{h}},{\bm{\tau}},\zeta}^{{k}}\geq\frac{1}{{2W}}\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{\left|{{h_{l}}}\right|}^{2}}{P_{l}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}}\right)}{\rm{d}}f\quad{\rm{bits/s/Hz}}$
(29)

and upper-bounded by

$\displaystyle
R_{{\bf{h}},{\bm{\tau}},\zeta}^{{k}}\leq\frac{1}{{2W}}\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{\left|{{h_{l}}}\right|}^{2}}{P_{l}}{{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}}\rho\left(f\right)}}}\right)}{\rm{d}}f\quad{\rm{bits/s/Hz}}.$
(30)

_Proof_ : The proof is given in Appendix F.

With the help of Theorem 3, we now investigate the achievable rates of both
the aNOMA and aFTN-NOMA schemes.

###  III-A Achievable Rates of Asynchronous NOMA Schemes

For the aNOMA scheme, we have $\zeta=1$, where the folded-spectrum satisfies
${\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}=T$ within the frequency
interval $f\in\left[{-\frac{1}{{2T}},\frac{1}{{2T}}}\right]$. Based on Theorem
3, the following corollary summarizes the bounds of the achievable rate for
aNOMA schemes.

Corollary 1 (_Bounds on the Normalized Achievable Rates of aNOMA Scheme_): The
normalized asymptotic instantaneous achievable rate
$R_{{\bf{h}},{\bm{\tau}},\zeta=1}^{{k}}$ of the aNOMA scheme for the $k$-th
user under SIC detection is lower-bounded by

$R_{{\bf{h}},{\bm{\tau}},\zeta=1}^{{k}}\geq\frac{1}{{2WT}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}T}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}}{P_{l}}T}}}\right)}\quad{\rm{bits/s/Hz}}$
(31)

and upper-bounded by

$\displaystyle
R_{{\bf{h}},{\bm{\tau}},\zeta=1}^{{k}}\leq\frac{1}{{2W}}\int_{-\frac{1}{{2T}}}^{\frac{1}{{2T}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}T}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}}{P_{l}}{{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}}\rho\left(f\right)}}}\right)}{\rm{d}}f\quad{\rm{bits/s/Hz}}.$
(32)

_Proof_ : The corollary is a straightforward extension of Theorem 3 and thus
the proof is omitted here.$\hfill\blacksquare$

According to Corollary 1, some interesting observations and insights can be
revealed.

  * •

Recalling Lemma 4, we observe that both the upper-bound and the lower-bound in
Corollary 1 are achievable. Theoretically, the upper-bound can be achieved if
the signaling pulse’s FD roll-off factor is $\beta=0$, i.e., the sinc pulse,
while the lower-bound can be achieved, if all the users share the same link
delay, corresponding to the conventional synchronous NOMA system.

  * •

For practical RRC pulses, i.e., $\beta\neq 0$, the asynchronous transmission
leads to an improved achievable rate region compared to that of the
conventional synchronous NOMA systems. Moreover, the upper-bound indicates
that the potential data rate improvement of aNOMA systems is due to its
reduced MUI energy, yielding an SINR improvement, which is the result of
different link delays. An intuitive explanation of this observation is that
the aNOMA system naturally avoids the full superposition of maximum MUI owing
to the diverse link delays. Hence, aNOMA system is unlikely to suffer from the
peak interference energy at each sampling instant, which is consistent with
the observations in Fig. 1(a). However, for the sinc pulse, i.e., $\beta=0$,
the asynchronous transmission does not provide any rate improvement. This is
because the symbol rate is consistent with the bandwidth of the sinc pulse.
Hence, no spectral aliasing occurs and thus the introduction of phase-
rotations cannot improve the achievable rate. This observation indicates that
compared to conventional synchronous NOMA systems, the aNOMA system suffers
from less severe MUI caused by the different link delays and offers the
potential of achieving higher rates.

  * •

The instantaneous achievable rate region of the aNOMA system is directly
determined by both the folded-spectrum and the twisted folded-spectrum. In
particular, the achievable rate improvement due to the asynchronous
transmission increases upon increasing $\beta$, since the corresponding
twisted folded-spectrum has a low energy in the frequency interval
$f\in\left[{-\frac{1}{{2T}},\frac{1}{{2T}}}\right]$. However, compared to the
zero excess bandwidth of $\beta=0$, the normalized achievable rates of both
the aNOMA scheme and the conventional synchronous NOMA scheme are reduced upon
increasing of $\beta$ due to the normalization.

###  III-B Achievable Rates of Asynchronous FTN-NOMA Schemes

We have already formulated the achievable rates of the aFTN-NOMA schemes in
Theorem 3. In particular, for $\zeta<1$, we observe that the aFTN-NOMA scheme
enjoys both an SINR gain granted by the asynchronous transmissions
(corresponding to the interference-reducing-spectrum) and a DoF gain
introduced by the FTN transmission (corresponding to the integral range). To
further explain advantages of aFTN-NOMA, let use formally define the SINR gain
and DoF gain of aFTN-NOMA schemes as follows.

Definition 4 (_SINR Gain over Synchronous Transmission_): The SINR gain of
aFTN-NOMA schemes over the synchronous schemes having the same symbol rate is
defined by

${\rm{Gai}}{{\rm{n}}_{{\rm{SINR}}}}\buildrel\Delta\over{=}\frac{{\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{P_{l}}{{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}}\rho\left(f\right)}}}}{\rm{d}}f}}{{\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{P_{l}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}}}{\rm{d}}f}}=\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{\frac{{{N_{0}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{P_{l}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{4}}}}}{{{N_{0}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{P_{l}}{{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{4}}}}}}{\rm{d}}f.$
(33)

Definition 5 (_DoF Gain over Conventional NOMA_): Let us define the _effective
bandwidth_ ${\rm{B}}{{\rm{W}}_{{\rm{eff}}}}\left({\frac{1}{{\zeta T}}}\right)$
with respect to the symbol rate ${\frac{1}{{\zeta T}}}$ as the frequency
interval, where both the folded-spectrum and the twisted folded-spectrum have
non-zero values, i.e., ${\rm{B}}{{\rm{W}}_{{\rm{eff}}}}\left({\frac{1}{{\zeta
T}}}\right)\buildrel\Delta\over{=}\min\left\\{{\frac{1}{{\zeta
T}},2W}\right\\}$. Then, the DoF gain of the aFTN-NOMA scheme over the
conventional NOMA scheme is defined by the ratio between the effective
bandwidths of the two schemes, i.e.,

${\rm{Gai}}{{\rm{n}}_{{\rm{DoF}}}}\buildrel\Delta\over{=}\frac{{{\rm{B}}{{\rm{W}}_{{\rm{eff}}}}\left({\frac{1}{{\zeta
T}}}\right)}}{{{\rm{B}}{{\rm{W}}_{{\rm{eff}}}}\left({\frac{1}{T}}\right)}}=T\times\min\left\\{{\frac{1}{{\zeta
T}},2W}\right\\}.$ (34)

Observe that with the reduction of $\zeta$, the SINR gain vanishes according
to the properties of ${\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}$ and
${\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}$, i.e.,
${\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}-{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}$
is a non-increasing function in the range of $0\leq\zeta\leq 1$. Furthermore,
we can also observe that the DoF gain increases upon reducing $\zeta$.
Therefore, we can see that there exists an intriguing trade-off between the
SINR gain and DoF gain of the aFTN-NOMA schemes with respect to the symbol
rate (compression factor).

Proposition 1 (_Trade-off Between SINR Gain and DoF Gain_): Upon increasing
the symbol rate from $\zeta=1$ to $\zeta=1/(1+\beta)$, the SINR gain of the
aFTN-NOMA scheme decreases, while the DoF gain increases, and _vice versa_.

Particularly, it can be shown that the SINR gain achieves its maximum value
when $\zeta=1$, i.e., for the aNOMA scheme, where there is no DoF gain.
Furthermore, the DoF gain achieves its maximum when $\zeta\leq 1/(1+\beta)$,
where there is no SINR gain. Specifically, Definition 1 and Definition 2 have
shown that both the folded-spectrum and the twisted folded-spectrum become
exactly the same as the RRC spectrum within the frequency interval of
$f\in\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$ for $\zeta\leq
1/(1+\beta)$, in which case the upper- and lower-bounds in Theorem 3 are
merged together and the corresponding maximum DoF gain is of value $2WT$.
Consequently, $R_{{\bf{h}},{\bm{\tau}},\zeta\leq 1/(1+\beta)}^{{k}}$ of the
aFTN-NOMA schemes associated with $\zeta\leq 1/(1+\beta)$ is given by

$R_{{\bf{h}},{\bm{\tau}},\zeta\leq\frac{1}{{1+\beta}}}^{{k}}=\frac{1}{{2W}}\int_{-W}^{W}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}{{\left|{{H_{p}}\left(f\right)}\right|}^{2}}}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}}{P_{l}}{{\left|{{H_{p}}\left(f\right)}\right|}^{2}}}}}\right)}{\rm{d}}f\quad{\rm{bits/s/Hz}}.$
(35)

Given (35), we can characterize the rate improvement of the aFTN-NOMA scheme
over the conventional synchronous NOMA scheme in the high-SNR regime by the
following corollary.

Corollary 3 (_Achievable Rate Improvement of aFTN-NOMA Schemes_): Given a
sufficiently high SNR, the asymptotic instantaneous achievable rate of aFTN-
NOMA schemes is $1+\beta$ times higher than that of the conventional
synchronous NOMA scheme.

_Proof_ : Considering the asymptotic instantaneous achievable rate of the
conventional synchronous NOMA scheme given in (31), we have

$\displaystyle\mathop{\lim}\limits_{{N_{0}}\to
0}\frac{{\frac{T}{{1+\beta}}\int_{-\frac{{1+\beta}}{{2T}}}^{\frac{{1+\beta}}{{2T}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}{{\left|{{H_{p}}\left(f\right)}\right|}^{2}}}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}}{P_{l}}{{\left|{{H_{p}}\left(f\right)}\right|}^{2}}}}}\right){\rm{d}}f}}}{{\frac{1}{{2WT}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}T}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}}{P_{l}}T}}}\right)}}=\frac{{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}}}{{\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}}{P_{l}}}}}\right)}}{{\frac{1}{{2WT}}{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}}}{{\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}}{P_{l}}}}}\right)}}={1+\beta}.$
(36)

This completes the proof of Corollary 3.

According to the conclusions from Theorem 3, Proposition 1 and Corollary 3,
some important insights can be revealed for the family of aFTN-NOMA schemes.

  * •

Similar to the aNOMA scheme, the achievable rate improvement of aFTN-NOMA
schemes stems from the excess bandwidth of the signaling pulse, where both the
upper-bound and the lower-bound in Theorem 3 are achievable according to Lemma
4. Given a sufficiently high symbol rate, the upper- and lower-bounds in
Theorem 3 are merged together, as suggested in (35).

  * •

Proposition 1 has demonstrated the trade-off between the SINR gain and DoF
gain. The physical interpretation of this trade-off is as follows. Given a
higher symbol rate, the effect of spectral aliasing is mitigated, in which
case the change of the folded-spectrum due to the phase-rotation is limited.
In particular, when $\zeta\leq 1/(1+\beta)$, the spectral aliasing no longer
exists and thus the SINR gain vanishes.

  * •

Compared to the SINR gain, the DoF gain essentially leads to a higher
achievable rate in the high-SNR regime, as shown in Corollary 3. In fact, the
rate in (35) is essentially the ultimate achievable rate for a given signaling
pulse and an SINR [20]. This is because the symbol rate is no lower than the
bandwidth of the signaling pulse and therefore both the folded-spectrum and
the twisted folded-spectrum become exactly the same as the underlying RRC
spectrum, yielding the maximum capacity promised by the signaling pulse.
However, for the sinc pulse, i.e., $\beta=0$, a higher symbol rate does not
provide any improvement in terms of achievable rates, since the Nyquist symbol
rate is simply twice the bandwidth of the signaling pulse, i.e., there is no
spectral aliasing. In contrast to the aNOMA scheme and to the conventional
synchronous NOMA scheme, the normalized achievable rate of the aFTN-NOMA
scheme attained at a sufficiently high symbol rate only exhibits a constant
gap to with respect to the $\beta=0$ case in the high-SNR regime. This is
because the FTN transmission successes in fully exploiting the DoF promised by
the siganling pulse [20].

###  III-C Implementations, Comparisons, and Extensions of the Considered
Schemes

We have shown the advantages of aFTN-NOMA and aNOMA over the conventional
synchronous NOMA scheme in terms of their achievable rate. However, it should
be noted that both aFTN-NOMA and aNOMA suffer from ISI and therefore, they
tend to impose an increased detection complexity [12]. A promising detector
design could be based on the combination of both the MUI and ISI detections.
In particular, the MUI can be efficiently dealt with by the SIC technique,
given the channel disparities [3], while the ISI arising from both FTN and
asynchronous transmissions can be mitigated by various mature detection
methods conceived for ISI channels, e.g., [35, 16]. Although the related
research on the detection issue is at its early stage, several potent
detectors are available in the literature. We refer the interested readers to
[12] and [36] for more details.

Note that our previous analysis in this section is purely based on baseband
signaling, where we show that both aNOMA and aFTN-NOMA are superior to the
conventional synchronous NOMA in terms of their achievable rates with
arbitrarily given channel coefficients. Therefore, it is expected that both
aFTN-NOMA and aNOMA will outperform conventional NOMA with any given
distribution of channel coefficients. For a better understanding of aNOMA and
aFTN-NOMA, we briefly compare them to similar MA schemes as follows.

  * •

aFTN-NOMA vs. OMA with FTN signaling: According to the previous analysis in
this section, the achievable rate improvements attained by asynchronous
transmission and FTN signaling accrue from the excess bandwidth of the
signaling pulse, which is independent from the gain of NOMA gleaned from
exploiting power discrepancies among different users. Furthermore, NOMA allows
the information from different users to be transmitted in a time-sharing
manner, which can be shown to have a higher achievable rate region than OMA
[37]. Therefore, aFTN-NOMA generally has a better performance than OMA with
FTN signaling in terms of achievable rates, because OMA cannot exploit the
power discrepancies and does not allow time-sharing among different users.

  * •

aNOMA/aFTN-NOMA vs. RSMA: The success of RSMA lies in the rate-splitting,
where the message of each user is divided into two parts, namely, a common
part and a private part [38]. As the common part is supposed to be decoded by
all the users, RSMA generally enjoys a reduced MUI compared to the
conventional power-domain NOMA [38]. Compared to RSMA, both aNOMA and aFTN-
NOMA reduce the MUI by relying on asynchronous transmission, which is
different from the principle of RSMA. However, it is generally not fair or
practical to directly compare whether aNOMA/aFTN-NOMA or RSMA has inflicts
lower MUI, because they both rely on the channel conditions, including the
distributions of the channel coefficients and link delays. It is also worth
mentioning that the advantages of both aNOMA and aFTN-NOMA become more
pronounced for a higher excess bandwidth of the shaping pulse, while RSMA
cannot make use of the excess bandwidth. An interesting discussion at this
point may be the combination of asynchronous transmission and FTN signaling
with RSMA. As RSMA and aNOMA/aFTN-NOMA enjoy advantages over NOMA from a range
of different perspectives, their combination might lead to further rate
improvements, which will be considered in our future work.

Now, we briefly discuss the potential extensions of the analysis in the
previous subsections to more practical systems, including multi-carrier,
multi-antenna, and multi-cell systems.

  * •

Extension to multi-carrier systems: In multi-carrier systems, the signaling
pulse is usually time-limited instead of being bandlimited. Thus, the schemes
considered may be extended to multi-carrier systems by allowing asynchronous
transmission and FTN signaling in the FD instead of the TD, which is
essentially a type of spectrally efficient frequency domain multiplexing (FDM)
signals [17, 18] with asynchronous transmissions. Our previous analysis could
be extended to this case by interchanging the corresponding analysis between
the FD and the TD.

  * •

Extension to multi-antenna systems: Assume that the BS is equipped with
multiple receive antennas, while the user has only a single transmit antenna.
In this case, the BS may receive multiple copies of the transmitted signal (2)
or (8) of each user at different link delays and channel coefficients.
Naturally, SIC detection could be applied at the receiver for multiuser signal
detection. The achievable rate analysis of such a system may also rely on the
Toeplitz structure of the corresponding channel matrix after suitable
combining of the signals received from different antennas.

  * •

Extension to multi-cell systems: In multi-cell systems, the transmitted
signals could be received by multiple cells. Then, depending on whether the
cooperation between different cells is allowed, the inter-cell interference
could be either exploited by cooperation or simply treated as noise for low-
complexity processing. It should be noted that the signals transmitted by
different users cannot be received by more than two BSs with perfect
synchronization in practice, hence the considered asynchronous transmissions
are permanently suitable for cooperative multi-cell systems. The achievable
rate analysis of multi-cell systems may also rely on the analysis of single-
cell settings. However, how the extra channel diversity gleaned from the
potential multi-cell cooperations will improve the achievable rate may require
further investigations.

Unfortunately, we have to leave the above interesting issues for our future
works due to the page limitation.

##  IV Numerical Results

In this section, we compare the normalized achievable rates of the aNOMA
scheme and the aFTN-NOMA scheme to that of the conventional synchronous NOMA
scheme, where the actual achievable rate of the considered schemes are
obtained based on (14) via the classic Monte Carlo method. In particular, we
compare both the instantaneous rates and the ergodic rates relying on the
randomly generated link delay for each user, where the link delay is assumed
to follow a uniform distribution within the interval $[0,2T]$ for each Monte
Carlo realization. In order to verify our previous discussions, the
instantaneous rates are calculated based on a typical NOMA transmission
supporting $K=2$ and $K=3$ users, and the number of transmitted symbols for
each user is set to $N=100$. On the other hand, the ergodic rates are
calculated based on a typical single-cell settings from [3]. Without loss of
generality, we adopt the equal power allocation for the different users for
all the related simulations, i.e., $P_{k}=P$, for $k=1,2,...K$.

###  IV-A Normalized Instantaneous Achievable Rates for the Two-User Case

We consider a specific channel realization, where the channel coefficients for
the two users are given by ${{\left|{{h_{1}}}\right|}^{2}}=0.5$ and
${{\left|{{h_{2}}}\right|}^{2}}=0.5$ and we have
$\frac{{{{{\left|{{h_{1}}}\right|}^{2}}{P_{1}}}}}{{{N_{0}}}}=\frac{{{{{\left|{{h_{2}}}\right|}^{2}}{P_{2}}}}}{{{N_{0}}}}=10$
dB. In order to obtain a general conclusion, we assume that each user has a
random link delay. Given the channel coefficients, we adopt the Monte Carlo
method to average the achievable rate with different link delays.

Figure 3: The achievable rate regions of the conventional synchronous NOMA,
the aNOMA, and the aFTN-NOMA schemes for $K=2$ users, where
$\frac{{{{{\left|{{h_{1}}}\right|}^{2}}{P_{1}}}}}{{{N_{0}}}}=\frac{{{{{\left|{{h_{2}}}\right|}^{2}}{P_{2}}}}}{{{N_{0}}}}=10$
dB. The signaling pulse is the RRC pulse with $\beta=0.3$.

The achievable rate regions of the conventional synchronous NOMA, the aNOMA,
and the aFTN-NOMA schemes are compared in Fig. 3, where the signaling pulse is
the RRC pulse using $\beta=0.3$ and the compression factor for the aFTN-NOMA
scheme is $\zeta=0.75$. As shown in the figure, the conventional synchronous
NOMA has the smallest achievable rate region among all the three schemes,
while the aNOMA scheme only shows a marginal improvement. On the other hand,
the aFTN-NOMA scheme can considerably improve the achievable rate as shown in
Fig. 3, which is consistent with our previous analysis.

###  IV-B Normalized Instantaneous Achievable Rates for the Three-User Case

Similar to the previous subsection, we consider a specific channel
realization, where the channel coefficients of the three users are given by
${{\left|{{h_{1}}}\right|}^{2}}=0.5$, ${{\left|{{h_{2}}}\right|}^{2}}=0.4$,
and ${{\left|{{h_{3}}}\right|}^{2}}=0.1$, respectively. We are interested in
the achievable rate vs. the received SNR at the BS, which is defined by
$\frac{{\sum\nolimits_{k=1}^{K}{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}}}}{{{N_{0}}}}=\frac{P}{{{N_{0}}}}$.

Figure 4: The instantaneous achievable rate of aFTN-NOMA scheme for
$\zeta=0.95$, where three users with equal power allocation are considered.
The channel coefficients are given by ${{\left|{{h_{1}}}\right|}^{2}}=0.5$,
${{\left|{{h_{2}}}\right|}^{2}}=0.4$, and
${{\left|{{h_{3}}}\right|}^{2}}=0.1$, respectively. The red dash-dotted lines
and the green dashed lines are the upper- and lower-bounds derived, while the
blue solid line is the actual achievable rate. The signaling pulse is the RRC
pulse with $\beta=0.3$.

Fig. 4 shows the achievable rates of each user for the aFTN-NOMA scheme with
$\zeta=0.95$, and $\beta=0.3$. As shown in the figure, the achievable rates of
the aFTN-NOMA scheme are perfectly bounded by the upper- and lower-bounds
derived. On the other hand, we observe that asynchronous FTN transmission
indeed attains rate improvements. Specifically, there is a $1.3$ dB gain for
the aFTN-NOMA scheme with $\zeta=0.95$ compared to the conventional
synchronous NOMA scheme at a rate of $5$ bits/s/Hz.

Figure 5: An illustration of the trade-off between the SINR gain and the DoF
gain for aFTN-NOMA schemes with different values of $\zeta$, where three users
with equal power allocation are considered. The channel coefficients are given
by ${{\left|{{h_{1}}}\right|}^{2}}=0.5$, ${{\left|{{h_{2}}}\right|}^{2}}=0.4$,
and ${{\left|{{h_{3}}}\right|}^{2}}=0.1$, respectively. The signaling pulse is
the RRC pulse with $\beta=0.5$.

Let us demonstrate the SINR vs. DoF trade-off with $\beta=0.5$ in Fig. 5,
where we show the sum-rates of the aFTN-NOMA scheme, the aNOMA scheme, and the
conventional synchronous NOMA scheme. For comparison, we also provide the
corresponding synchronous rates without link delays. Specifically, we consider
three cases at different symbol rates, i.e., $\zeta=1$, $\zeta=0.8$, and
$\zeta=2/3$, respectively. As indicated in Proposition 1, the SINR gain
reduces with the reduction of $\zeta$ from $\zeta=1$ to
$\zeta=\frac{1}{{1+\beta}}=\frac{2}{3}$, while the DoF gain increases. As
observed from the figure, the SINR gain indeed decreases (corresponding to the
shift along the x-axis) for a smaller $\zeta$, while the DoF gain
(corresponding to the slope of the curves) increases. In particular, we notice
that with $\zeta=2/3$, the curves of the aFTN-NOMA schemes operating with or
without link delay are almost overlapped, which indicates that the SINR gain
due to the link delay vanishes in this case. The observations confirm the
accuracy of our derivations in Section III.

###  IV-C Normalized Ergodic Achievable Rates for Single-Cell Setups

In this subsection, we focus our attention on the ergodic achievable rates of
both aFTN-NOMA and aNOMA, and compare them to that of the conventional power-
domain NOMA in a single-cell system. In particular, we adopt the system
settings from [3] for our simulations, where we assume that the cell is
modeled by a pair of concentric ring-shaped discs. The inner radius $D_{0}$ is
introduced to model the minimum propagation path loss [3], while the outer
radius $D_{1}$ represents the cell size. Furthermore, we assume that the BS is
located at the center of the cell and all the users are uniformly scattered
within the two concentric ring-shaped discs. To characterize the system’s SNR,
we adopt the definitions from [3], where the total average received SNR of all
the users at the BS is defined by

$\displaystyle{\rm{SN}}{{\rm{R}}_{{\rm{sum}}}}\buildrel\Delta\over{=}\frac{{{P_{\max}}}}{{{N_{0}}}}\overline{{{\left|h\right|}^{2}}}.$
(37)

In (37), ${\overline{\left|h\right|^{2}}}$ denotes the average channel power
gain with respect to the cell size and path loss model and it is calculated
based on Equation (12) of [3]. The term $P_{\max}$ in (37) denotes the total
transmit power of the BS, which is adjusted adaptively for different cell
sizes to provide the required ${\rm{SN}}{{\rm{R}}_{{\rm{sum}}}}$. Meanwhile,
the noise PSD in (37) is set to be $N_{0}=-80$ dBm. For reference, we
summarize the related parameters in Table II.

TABLE II: Related Parameters for Simulations  Packet length $N$ |  $100$
---|---
Nyquist symbol period $T$ |  $1$
Maximum value of link delay |  $2T$
Inner cell radius $D_{0}$ |  $50$ $\rm{m}$
Outer cell radius $D_{1}$ |  $[75,100,200,300,400,500]$ $\rm{m}$
Number of users |  $[2,4,8,16,32,64,128]$
Path loss exponent $\alpha$ |  $3.76$
Noise PSD $N_{0}$ |  $-80$ dBm

We show the ergodic sum-rates of both aFTN-NOMA and aNOMA in comparison to
that of NOMA in Fig. 6(a) versus ${\rm{SN}}{{\rm{R}}_{{\rm{sum}}}}$ and the
numbers of users, where $\beta=0.3$, $\tau=0.75$, and $D_{1}=75$. As observed
from Fig. 6(a), the ergodic sum-rates of both aFTN-NOMA and aNOMA are higher
than the synchronous NOMA benchmark for various system SNRs, where the sum-
rate improvements increase with ${\rm{SN}}{{\rm{R}}_{{\rm{sum}}}}$. Indeed,
both the DoF and the MUI are dominant factors in determining the achievable
rates in the high-SNR regime. Therefore, FTN signaling and asynchronous
transmission lead to beneficial rate improvements due to the exploitations of
DoF and the mitigation of MUI. On the other hand, we also observe from Fig.
6(a) that aNOMA achieves a higher sum-rate improvement for more users, while
the sum-rate gap between aFTN-NOMA and NOMA is relatively constant for more
than $8$ users. This is because the rate improvement of aNOMA arises from the
MUI mitigation, while the rate improvement of aFTN-NOMA comes from its DoF
gain. As the MUI increases with more users in the cell, the MUI mitigation
leads to an increased rate improvement. However, as the DoF gain of aFTN-NOMA
comes from the excess bandwidth of the signaling pulse, which does not change
with the number of users in the cell, the rate improvement remains relatively
constant for different number of users.

We portray the performance comparisons among NOMA, aNOMA, and aFTN-NOMA in
terms of the cell size in Fig. 6(b), where $\beta=0.3$, $\tau=0.75$, $K=128$,
and ${\rm{SN}}{{\rm{R}}_{{\rm{sum}}}}=20$ dB. As indicated in Fig. 6(b), the
sum-rate gap between aFTN-NOMA and NOMA is relatively constant, while the sum-
rate improvement of aNOMA is reduced for large cells. This observation is not
unexpected because the DoF gain of aFTN-NOMA does not change with the channel
characteristics. However, with the transmitted power fixed, the MUI generally
reduces for larger cells and therefore, the rate improvement of aNOMA also
reduces.

(a) Normalized sum-rate vs. number of users with different SNRs.

(b) Normalized sum-rate vs. cell range.

Figure 6: Ergodic sum-rate analysis for the considered schemes, where the
related simulation parameters are given in Table II.

The sum-rate performances versus roll-off factors are demonstrated in Fig.
7(a), where $K=16$, $D_{1}=75$, and ${\rm{SN}}{{\rm{R}}_{{\rm{sum}}}}=40$ dB.
In particular, we set $\tau=0.5$ for aFTN-NOMA system as it is sufficient to
obtain the full DoF gains for $\beta\in\left[{0,1}\right]$. We observe that
the sum-rate of all three schemes decreases for a larger $\beta$ due to the
bandwidth normalization. However, the sum-rates of both NOMA and aNOMA reduce
significantly compared to that of the aFTN-NOMA. This is because aFTN-NOMA
efficiently exploits the DoF gain based on the excess bandwidth, which is
consistent with our analysis in Section III-B. On the other hand, the sum-rate
gap between NOMA and aNOMA increases for a larger roll-off factor. This is due
to the fact that a larger excess bandwidth offers a stronger interference
mitigation capability for aNOMA, which is also consistent with our discussions
in Section III-A.

The comparison of complementary cumulative distribution functions (CCDFs) of
different users is given in Fig. 7(b), where $K=8$, $\beta=0.3$, $\tau=0.75$,
$D_{1}=500$, and ${\rm{SN}}{{\rm{R}}_{{\rm{sum}}}}=20$ dB. Specifically, we
show the CCDFs of the strongest user, a moderate-power user, and the weakest
user in the schemes considered. As indicated from the figure, the CCDFs of
both aNOMA and aFTN-NOMA show better performance than that of NOMA for both
the strongest user and moderate-power user. However, the CCDFs of the weakest
users are almost the same for the three schemes. This is because the weakest
user generally has low received SNR while the MUI is eliminated thanks to the
SIC detection. In this case, neither the MUI mitigation, nor the DoF gain may
be able to offer large rate improvements. Consequently, the performances of
aFTN-NOMA, aNOMA, and NOMA are similar.

(a) Sum rate vs. roll-off factors.

(b) CCDFs for different schemes.

Figure 7: Achievable rate analysis for the considered schemes, where the
related simulation parameters are given in Table II.

##  V Conclusions

In this paper, we investigated the aNOMA and aFTN-NOMA schemes with the
objective of improving the achievable rate of conventional NOMA transmissions.
Specifically, we derived the corresponding achievable rate upper- and lower-
bounds by invoking Szegö’s Theorem. We showed that asynchronous transmissions
result in an SINR gain, while increasing the symbol rate may potentially lead
to a DoF gain. More importantly, we unveiled that the associated SINR vs. DoF
gain trade-off. In particular, we also showed that the SINR or DoF gains are
related to the potential spectral aliasing and discussed the connections
between the effect of spectral aliasing and the link delay as well as the
symbol rate. Our simulation results agreed with our analysis and demonstrated
a significant achievable rate gain compared to the conventional NOMA
transmission.

##  Appendix A Proof of Lemma 1

According to the chain rule and the calculation of the entropy of a
multivariate normal distribution [37], we have

$\displaystyle{{I_{{\bf{h}},{\bm{\tau}},\zeta}}}\left({{{\bf{y}}_{k}};{{\bf{x}}_{k}}|{{\bf{x}}_{1}},\ldots,{{\bf{x}}_{k-1}}}\right)=$
$\displaystyle{h_{{\bf{h}},{\bm{\tau}},\zeta}\left({{{\bf{y}}_{k}}\left|{{{\bf{x}}_{1}},\ldots,{{\bf{x}}_{k-1}}}\right.}\right)}-{h_{{\bf{h}},{\bm{\tau}},\zeta}\left({{{\bf{y}}_{k}}\left|{{{\bf{x}}_{1}},\ldots,{{\bf{x}}_{k}}}\right.}\right)}$
$\displaystyle=$ $\displaystyle\frac{1}{2}\log_{2}{\left({2\pi
e}\right)^{N}}\det\left({\sum\limits_{l=k}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]{{{\bf{\tilde{G}}}}_{l,k}}{\bf{\tilde{G}}}_{l,k}^{\rm{T}}+{N_{0}}{{{\bf{\tilde{G}}}}_{k,k}}}}\right)$
$\displaystyle\quad\\!\\!\\!\\!\\!\\!\\!\\!-\frac{1}{2}\log_{2}{\left({2\pi
e}\right)^{N}}\det\left({\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]{{{\bf{\tilde{G}}}}_{l,k}}{\bf{\tilde{G}}}_{l,k}^{\rm{T}}+{N_{0}}{{{\bf{\tilde{G}}}}_{k,k}}}}\right).$
(38)

Furthermore, according to the property of the matrix determinant, we have

$\displaystyle{{I_{{\bf{h}},{\bm{\tau}},\zeta}}}\left({{{\bf{y}}_{k}};{{\bf{x}}_{k}}|{{\bf{x}}_{1}},\ldots,{{\bf{x}}_{k-1}}}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\log_{2}\det\left[{\left({\sum\limits_{l=k}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]{{{\bf{\tilde{G}}}}_{l,k}}{\bf{\tilde{G}}}_{l,k}^{\rm{T}}+{N_{0}}{{{\bf{\tilde{G}}}}_{k,k}}}}\right){{\left({\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]{{{\bf{\tilde{G}}}}_{l,k}}{\bf{\tilde{G}}}_{l,k}^{\rm{T}}+{N_{0}}{{{\bf{\tilde{G}}}}_{k,k}}}}\right)}^{-1}}}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\log_{2}\det\left[{{{\bf{I}}_{N\times
N}}+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{E_{s}}\left[k\right]{{{\bf{\tilde{G}}}}_{k,k}}{\bf{\tilde{G}}}_{k,k}^{\rm{T}}}}{{{N_{0}}}}{{\left({{{{\bf{\tilde{G}}}}_{k,k}}+\frac{{\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]}}}{{{N_{0}}}}{{{\bf{\tilde{G}}}}_{l,k}}{\bf{\tilde{G}}}_{l,k}^{\rm{T}}}\right)}^{-1}}}\right].$
(39)

This completes the proof of Lemma 1.

##  Appendix B Proof of Lemma 3

According to the definition of ${{\bf{T}}_{l,k}}$, to verify the positive
definiteness of ${{\bf{T}}_{l,k}}$ is equivalent to verify that
${\tilde{\bf{G}}_{l,k}}$ has a positive determinant. It can be observed from
(12) that ${\tilde{\bf{G}}_{l,k}}$ is a Gram matrix of nonzero energy
functions $p\left({t+n\zeta T+\tau\left[l\right]-\tau\left[k\right]}\right)$,
for $n=0,\ldots,N-1$, where the element of the $i$-th row and $j$-th column is
given by the inner product of $p\left({t+i\zeta
T+\tau\left[l\right]-\tau\left[k\right]}\right)$ and $p\left({t+j\zeta
T+\tau\left[l\right]-\tau\left[k\right]}\right)$. Note that the determinant of
${\tilde{\bf{G}}_{l,k}}$ is non-negative [39]. Therefore, we only have to
verify that ${\tilde{\bf{G}}_{l,k}}$ has a nonzero determinant. Gram’s
criterion [39] indicates that for a set of strictly bandlimited functions
$p\left({t+n\zeta T+\tau\left[l\right]-\tau\left[k\right]}\right)$ having a
finite energy in their frequency interval, the corresponding Gram matrix
${\tilde{\bf{G}}_{l,k}}$ has a nonzero determinant if and only if the set of
functions $p\left({t+n\zeta T+\tau\left[l\right]-\tau\left[k\right]}\right)$,
for $n=0,\ldots,N-1$ are linearly independent. In order to prove the linear
independence, we consider Proposition 5.1.1 of [40], which indicates that a
sufficient condition for the function set to be linearly independent is that

$\displaystyle\mathop{\lim}\limits_{n\to\infty}{\tilde{g}}\left[{n,\tau\left[l\right]-\tau\left[k\right]}\right]=0,$
(40)

for any $1\leq l,k\leq K$ [33]. Upon recalling (10), to prove (40), we have to
verify

$\displaystyle\mathop{\lim}\limits_{n\to\infty}\int\limits_{-\infty}^{\infty}{{{\left|{{H_{p}}\left(f\right)}\right|}^{2}}\exp\left({j2\pi
f\left({n\zeta
T+\tau\left[l\right]-\tau\left[k\right]}\right)}\right)}{\rm{d}}f=0.$ (41)

Note that ${\tau\left[l\right]-\tau\left[k\right]}$ is constant for any given
$l$ and $k$. Therefore, (41) holds due to the Riemann-Lebesgue Lemma [41].
Furthermore, since ${\tilde{\bf{G}}_{l,k}}$ is a Toeplitz matrix,
${{\bf{T}}_{l,k}}$ is asymptotically a Toeplitz matrix, due to the fact that
the product of two Toeplitz matrices is also asymptotically Toeplitz [22]. On
the other hand, it can be shown that the summation of two Toeplitz matrices is
also a Toeplitz matrix, while the inverse of a Toeplitz matrix is
asymptotically a Toeplitz matrix [22]. Therefore, it can be shown that ${\bf
P}_{k}$ is asymptotically a Toeplitz matrix. Meanwhile, we have verified that
${\tilde{\bf{G}}_{l,k}}$ is a positive definite Toeplitz matrix. Then, it can
be shown that ${\bf P}_{k}$ is also positive definite, because the product of
positive definite matrices is also positive definite. This completes the proof
of Lemma 3.

##  Appendix C Proof of Lemma 4

As we know that the spectrum of RRC pulse is
${\left|{{H_{p}}\left(f\right)}\right|^{2}}$ strictly non-negative, we have

$\displaystyle\sum\limits_{k=-\infty}^{\infty}{{{\left|{{H_{p}}\left({f-\frac{k}{\zeta
T}}\right)}\right|}^{2}}}{e^{-j2\pi\gamma
k}}\leq\sum\limits_{k=-\infty}^{\infty}{{{\left|{{H_{p}}\left({f-\frac{k}{\zeta
T}}\right)}\right|}^{2}}}{\left|{e^{-j2\pi\gamma
k}}\right|}={\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}},$ (42)

where the bound becomes exact if $\gamma=0$. On the other hand, notice that
${\left|{{H_{p}}\left(f\right)}\right|^{2}}$ is strictly bandlimited within
the frequency interval $\left|f\right|\leq\frac{{1+\beta}}{{2T}}$. Thus, for
$f\in\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$, we have

$\displaystyle\sum\limits_{k=-\infty}^{\infty}{{{\left|{{H_{p}}\left({f-\frac{k}{\zeta
T}}\right)}\right|}^{2}}}{e^{-j2\pi\gamma k}}=$
$\displaystyle{\left|{{H_{p}}\left(f\right)}\right|^{2}}+{\left|{{H_{p}}\left({f-\frac{1}{\zeta
T}}\right)}\right|^{2}}{e^{-j2\pi\gamma}}+{\left|{{H_{p}}\left({f+\frac{1}{\zeta
T}}\right)}\right|^{2}}{e^{j2\pi\gamma}}$ $\displaystyle\geq$
$\displaystyle{\left|{{H_{p}}\left(f\right)}\right|^{2}}-{\left|{{H_{p}}\left({f-\frac{1}{\zeta
T}}\right)}\right|^{2}}-{\left|{{H_{p}}\left({f+\frac{1}{\zeta
T}}\right)}\right|^{2}},$ $\displaystyle=$
$\displaystyle{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}.$ (43)

Next, we discuss the achievability of the derived bounds. For $\beta=0$, it is
not hard to notice that both
${\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}$ and
${\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}$ become the same as the
_sinc_ spectrum ${\left|{H_{\rm sinc}\left(f\right)}\right|^{2}}$. In this
case, both the upper-bound of (42) and the lower-bound of (43) are achieved.
Furthermore, we note that both
${\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}$ and
${\left|{{{H}_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}$ become the exact RRC
spectrum ${\left|{H_{p}\left(f\right)}\right|^{2}}$, when $\zeta\leq
1/(1+\beta)$. Thus, both the upper-bound of (42) and the lower-bound of (43)
are also achieved in this case. This completes the proof of Lemma 4.

##  Appendix D Proof of Theorem 1

Upon recalling (10), we have

$\displaystyle{{\tilde{G}}_{l,k}}\left({2\pi f\zeta
T}\right)=\sum\limits_{n=-\infty}^{\infty}{{{\tilde{g}}_{\zeta}}\left[{n,\Delta\tau}\right]{e^{-j2\pi
n\zeta
Tf}}}=\int_{-\infty}^{\infty}{{{\left|{{H_{p}}\left(\lambda\right)}\right|}^{2}}}{e^{j2\pi\lambda\Delta\tau}}\sum\limits_{n=-\infty}^{\infty}{{e^{j2\pi
n\zeta T\left({\lambda-f}\right)}}{\rm{d}}\lambda}.$ (44)

Substituting the Poisson summation formula, i.e.,
$\sum\nolimits_{k=-\infty}^{\infty}{{e^{j2\pi
kx}}}=\sum\nolimits_{k=-\infty}^{\infty}{\delta\left({x+k}\right)}$, into (44)
yields

$\displaystyle{{\tilde{G}}_{l,k}}\left({2\pi f\zeta T}\right)$
$\displaystyle=\int_{-\infty}^{\infty}{{{\left|{{H_{p}}\left(\lambda\right)}\right|}^{2}}}{e^{j2\pi\lambda\Delta\tau}}\sum\limits_{n=-\infty}^{\infty}{\delta\left({\zeta
T\left({\lambda-f}\right)+n}\right){\rm{d}}\lambda}$
$\displaystyle=\frac{1}{{\zeta
T}}\int_{-\infty}^{\infty}{{{\left|{{H_{p}}\left(\lambda\right)}\right|}^{2}}}{e^{j2\pi\lambda\Delta\tau}}\sum\limits_{n=-\infty}^{\infty}{\delta\left({\lambda-\left({f-\frac{n}{{\zeta
T}}}\right)}\right){\rm{d}}\lambda}$ (45) $\displaystyle=\frac{1}{{\zeta
T}}\sum\limits_{n=-\infty}^{\infty}{{{\left|{{H_{p}}\left({f-\frac{n}{{\zeta
T}}}\right)}\right|}^{2}}{e^{j2\pi\left({f-\frac{n}{{\zeta
T}}}\right)\Delta\tau}}},$ (46)

where (45) is due to the property of the Dirac delta function. Therefore, by
considering Lemma 4, (46) can be bounded by

$\displaystyle\frac{1}{{\zeta
T}}{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}\leq{{\tilde{G}}_{l,k}}\left({2\pi
f\zeta T}\right)\leq\frac{1}{{\zeta
T}}{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}.$ (47)

It should be noted that the bounds derived are based on the conclusions from
Lemma 4. Therefore, those bounds become exact when the conditions stated in
Lemma 4 are satisfied. This completes the proof of Theorem 1.

##  Appendix E Proof of Theorem 2

Similar to the proof of Theorem 1, we substitute (10) into (21) and obtain

$\displaystyle{{\tilde{T}}_{l,k}}\left({2\pi f\zeta T}\right)$
$\displaystyle=\sum\limits_{n=-\infty}^{\infty}{\sum\limits_{m=-\infty}^{\infty}{{{\tilde{g}}_{\zeta}}\left[{m,\Delta\tau}\right]{{\tilde{g}}_{\zeta}}\left[{m-n,\Delta\tau}\right]}}{e^{-j2\pi
n\zeta Tf}}$
$\displaystyle=\sum\limits_{m=-\infty}^{\infty}{{{\tilde{g}}_{\zeta}}\left[{m,\Delta\tau}\right]}\int_{-\infty}^{\infty}{{{\left|{{H_{p}}\left(\lambda\right)}\right|}^{2}}}{e^{j2\pi\lambda\left({m\zeta
T+\Delta\tau}\right)}}\sum\limits_{n=-\infty}^{\infty}{{e^{-j2\pi n\zeta
T\left({\lambda+f}\right)}}}{\rm{d}}\lambda.$ (48)

Upon considering the Poisson summation formula, we have

$\displaystyle{{\tilde{T}}_{l,k}}\left({2\pi f\zeta T}\right)=$
$\displaystyle\sum\limits_{m=-\infty}^{\infty}{{{\tilde{g}}_{\zeta}}\left[{m,\Delta\tau}\right]}\int_{-\infty}^{\infty}{{{\left|{{H_{p}}\left(\lambda\right)}\right|}^{2}}}{e^{j2\pi\lambda\left({m\zeta
T+\Delta\tau}\right)}}\sum\limits_{n=-\infty}^{\infty}{\delta\left({n-\zeta
T\left({\lambda+f}\right)}\right)}{\rm{d}}\lambda$ $\displaystyle=$
$\displaystyle\frac{1}{{\zeta
T}}\sum\limits_{m=-\infty}^{\infty}{{{\tilde{g}}_{\zeta}}\left[{m,\Delta\tau}\right]}{e^{j2\pi
f\left({m\zeta
T+\Delta\tau}\right)}}\sum\limits_{n=-\infty}^{\infty}{{{\left|{{H_{p}}\left({f-\frac{n}{{\zeta
T}}}\right)}\right|}^{2}}}{e^{-j2\pi mn-\frac{{n\Delta\tau}}{{\zeta T}}}}.$
(49)

Upon recalling Lemma 4, (49) can be upper-bounded by

$\displaystyle{{\tilde{T}}_{l,k}}\left({2\pi f\zeta
T}\right)\leq\frac{1}{{\zeta
T}}{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}\sum\limits_{m=-\infty}^{\infty}{{{\tilde{g}}_{\zeta}}\left[{m,\Delta\tau}\right]}{e^{j2\pi
f\left({m\zeta T+\Delta\tau}\right)}}.$ (50)

Moreover, by considering Theorem 1, (50) can be further upper-bounded by

$\displaystyle{{\tilde{T}}_{l,k}}\left({2\pi f\zeta
T}\right)\leq{\left({\frac{1}{{\zeta
T}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}\right)^{2}}.$ (51)

On the other hand, (49) can be lower-bounded according to Lemma 4 by

$\displaystyle{{\tilde{T}}_{l,k}}\left({2\pi f\zeta
T}\right)\geq\frac{1}{{\zeta
T}}{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|^{2}}\sum\limits_{m=-\infty}^{\infty}{{{\tilde{g}}_{\zeta}}\left[{m,\Delta\tau}\right]}{e^{j2\pi
f\left({m\zeta T+\Delta\tau}\right)}}.$ (52)

Again, by considering Theorem 1, (50) can be further lower-bounded by

$\displaystyle{{\tilde{T}}_{l,k}}\left({2\pi f\zeta
T}\right)\geq{\left({\frac{1}{{\zeta
T}}{{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}}}\right)^{2}}.$ (53)

It should be noted that the bounds derived are based on the conclusions from
Lemma 4. Therefore, those bounds become exact when the conditions stated in
Lemma 4 are met. This completes the proof of Theorem 2.

##  Appendix F Proof of Theorem 3

We apply Szegö’s Theorem to (14) and obtain

$\displaystyle R_{{\bf{h}},{\bm{\tau}},\zeta}^{{k}}\buildrel\Delta\over{=}$
$\displaystyle\mathop{\lim}\limits_{N\to\infty}\frac{1}{N}{I_{{\bf{h}},\tau,\zeta=1}}\left({{{\bf{y}}_{k}};{{\bf{x}}_{k}}|{{\bf{x}}_{1}},\ldots,{{\bf{x}}_{k-1}}}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{{4\pi}}\int_{-\pi}^{\pi}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{E_{s}}\left[k\right]{{\tilde{T}}_{k,k}}\left(\omega\right)}}{{{N_{0}}}}{{\left({{{\tilde{G}}_{k,k}}\left(\omega\right)+\frac{{\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]{{\tilde{T}}_{l,k}}\left(\omega\right)}}}{{{N_{0}}}}}\right)}^{-1}}}\right)}{\rm{d}}\omega$
$\displaystyle=$ $\displaystyle\frac{{\zeta T}}{2}\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{E_{s}}\left[k\right]{{\tilde{T}}_{k,k}}\left({2\pi\zeta
Tf}\right)}}{{{N_{0}}{{\tilde{G}}_{k,k}}\left({2\pi\zeta
Tf}\right)+\sum\limits_{l=k+1}^{K}{{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]{{\tilde{T}}_{l,k}}\left({2\pi\zeta
Tf}\right)}}}}\right)}{\rm{d}}f.$ (54)

Note that the integral range is within the frequency interval
$f\in\left[{-\frac{1}{{2\zeta T}},\frac{1}{{2\zeta T}}}\right]$. Therefore,
the bounds in Theorem 1 and Theorem 2 can be applied for analysis. By
observing that ${{\tilde{G}}_{k,k}}\left({{2\pi\zeta
Tf}}\right)=\frac{1}{\zeta
T}{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|^{2}}$ and
${{\tilde{T}}_{k,k}}\left({{2\pi\zeta Tf}}\right)={\left({\frac{1}{\zeta
T}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}\right)^{2}}$, we have

$\displaystyle R_{{\bf{h}},{\bm{\tau}},\zeta}^{{k}}\leq$
$\displaystyle\frac{{\zeta T}}{2}\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{E_{s}}\left[k\right]{{\left({\frac{{{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{\zeta
T}}}\right)}^{2}}}}{{{N_{0}}\frac{{{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{\zeta
T}}+\sum\limits_{l=k+1}^{K}{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]{{\left({\frac{{{{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}}}}{{\zeta
T}}}\right)}^{2}}}}}\right)}{\rm{d}}f,$ (55)

which can be further simplified as

$\displaystyle R_{{\bf{h}},{\bm{\tau}},\zeta}^{{k}}\leq$
$\displaystyle\frac{{\zeta T}}{2}\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{\left|{{h_{l}}}\right|}^{2}}{P_{l}}{{\left|{{H_{{\rm{tfo}}}}\left(f\right)}\right|}^{2}}\rho\left(f\right)}}}\right)}{\rm{d}}f.$
(56)

On the other hand, we have

$\displaystyle R_{{\bf{h}},{\bm{\tau}},\zeta}^{{k}}\geq$
$\displaystyle\frac{{\zeta T}}{2}\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{E_{s}}\left[k\right]{{\left({\frac{{{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{\zeta
T}}}\right)}^{2}}}}{{{N_{0}}\frac{{{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{\zeta
T}}+\sum\limits_{l=k+1}^{K}{{\left|{{h_{l}}}\right|}^{2}}{E_{s}}\left[l\right]{{\left({\frac{{{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{\zeta
T}}}\right)}^{2}}}}}\right)}{\rm{d}}f$ $\displaystyle=$
$\displaystyle\frac{{\zeta T}}{2}\int_{-\frac{1}{{2\zeta
T}}}^{\frac{1}{{2\zeta
T}}}{{{\log}_{2}}\left({1+\frac{{{{\left|{{h_{k}}}\right|}^{2}}{P_{k}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}{{{N_{0}}+\sum\limits_{l=k+1}^{K}{{\left|{{h_{l}}}\right|}^{2}}{P_{l}}{{\left|{{H_{{\rm{fo}}}}\left(f\right)}\right|}^{2}}}}}\right)}{\rm{d}}f.$
(57)

Furthermore, by considering the symbol rate $\frac{1}{{\zeta T}}$, the signal
dimension, and the signal bandwidth $2W$, the bounds in (56) and (57) can be
normalized as shown in (29) and (30). Finally, it can be shown that the bounds
derived become exact when the conditions stated in Lemma 4 are met. This
completes the proof of Theorem 3.

## References

  * [1] S. Li, Z. Wei, W. Yuan, J. Yuan, B. Bai, and D. W. K. Ng, “On the achievable rates of uplink NOMA with asynchronized transmission,” in _Proc. IEEE Wireless Commun. Net. Conf._ , 2020, pp. 1–6.
  * [2] Z. Ding, X. Lei, G. K. Karagiannidis, R. Schober, J. Yuan, and V. K. Bhargava, “A survey on non-orthogonal multiple access for 5G networks: Research challenges and future trends,” _IEEE J. Sel. Areas Commun._ , vol. 35, no. 10, pp. 2181–2195, Oct. 2017.
  * [3] Z. Wei, L. Yang, D. W. K. Ng, J. Yuan, and L. Hanzo, “On the performance gain of NOMA over OMA in uplink communication systems,” _IEEE Trans. Commun._ , vol. 68, no. 1, pp. 536–568, Jan. 2020.
  * [4] Q. Wu and R. Zhang, “Towards smart and reconfigurable environment: Intelligent reflecting surface aided wireless network,” _IEEE Commun. Mag._ , vol. 58, no. 1, pp. 106–112, Nov. 2020.
  * [5] Y. Wang, J. Wang, D. W. K. Ng, R. Schober, and X. Gao, “A minimum error probability NOMA design,” _IEEE Trans. Wireless Commun._ , Jul. 2021.
  * [6] B. Rimoldi and R. Urbanke, “A rate-splitting approach to the Gaussian multiple-access channel,” _IEEE Trans. Inf. Theory_ , vol. 42, no. 2, pp. 364–375, Mar. 1996.
  * [7] B. Clerckx, H. Joudeh, C. Hao, M. Dai, and B. Rassouli, “Rate splitting for MIMO wireless networks: A promising PHY-layer strategy for LTE evolution,” _IEEE Commun. Mag._ , vol. 54, no. 5, pp. 98–105, May 2016\.
  * [8] Z. Ding and H. Vincent Poor, “A simple design of IRS-NOMA transmission,” _IEEE Commun. Lett._ , vol. 24, no. 5, pp. 1119–1123, Feb. 2020.
  * [9] M. Moltafet, N. M. Yamchi, M. R. Javan, and P. Azmi, “Comparison study between PD-NOMA and SCMA,” _IEEE Trans. Veh. Technol._ , vol. 67, no. 2, pp. 1830–1834, Feb. 2018.
  * [10] H. Haci, H. Zhu, and J. Wang, “Performance of non-orthogonal multiple access with a novel asynchronous interference cancellation technique,” _IEEE Trans. Commun._ , vol. 65, no. 3, pp. 1319–1335, Mar. 2017.
  * [11] X. Zou, B. He, and H. Jafarkhani, “An analysis of two-user uplink asynchronous non-orthogonal multiple access systems,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 2, pp. 1404–1418, Jan. 2019.
  * [12] W. Yuan, N. Wu, Q. Guo, D. W. K. Ng, J. Yuan, and L. Hanzo, “Iterative joint channel estimation, user activity tracking, and data detection for FTN-NOMA systems supporting random access,” _IEEE Trans. Commun._ , vol. 68, no. 5, pp. 2963–2977, May 2020.
  * [13] J. B. Anderson, F. Rusek, and V. Öwall, “Faster-than-Nyquist signaling,” _Proc. IEEE_ , vol. 101, no. 8, pp. 1817–1830, Aug. 2013.
  * [14] S. Li, J. Yuan, B. Bai, and N. Benvenuto, “Code-based channel shortening for faster-than-Nyquist signaling: Reduced-complexity detection and code design,” _IEEE Trans. Commun._ , vol. 68, no. 7, pp. 3996–4011, Jul. 2020.
  * [15] S. Sugiura and L. Hanzo, “Frequency-domain-equalization-aided iterative detection of faster-than-Nyquist signaling,” _IEEE Trans. Veh. Technol._ , vol. 64, no. 5, pp. 2122–2128, May 2014.
  * [16] T. Ishihara, S. Sugiura, and L. Hanzo, “The evolution of faster-than-Nyquist signaling,” __to appear in_ IEEE Access_, 2021.
  * [17] I. Kanaras, A. Chorti, M. R. Rodrigues, and I. Darwazeh, “Spectrally efficient FDM signals: Bandwidth gain at the expense of receiver complexity,” in _IEEE Int. Conf. Commun._ , 2009, pp. 1–6.
  * [18] I. Darwazeh, T. Xu, T. Gui, Y. Bao, and Z. Li, “Optical SEFDM system; bandwidth saving using non-orthogonal sub-carriers,” _IEEE Photonics Technol. Lett._ , vol. 26, no. 4, pp. 352–355, 2013.
  * [19] S. Li, B. Bai, J. Zhou, Q. He, and Q. Li, “Superposition coded modulation based faster-than-Nyquist signaling,” _Wireless Commun. Mobile Comput._ , vol. 2018, 2018.
  * [20] F. Rusek and J. B. Anderson, “Constrained capacities for faster-than-Nyquist signaling,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 2, pp. 764–775, Feb. 2009.
  * [21] L. Dai, B. Wang, Z. Ding, Z. Wang, S. Chen, and L. Hanzo, “A survey of non-orthogonal multiple access for 5G,” _IEEE Commun. Sur. & Tut._, vol. 20, no. 3, pp. 2294–2323, May 2018.
  * [22] R. M. Gray, _Toeplitz and Circulant Matrices: A Review_. Now Foundations and Trends, 2006.
  * [23] Z. Ding, Z. Yang, P. Fan, and H. V. Poor, “On the performance of non-orthogonal multiple access in 5G systems with randomly deployed users,” _IEEE Signal Process. Lett._ , vol. 21, no. 12, pp. 1501–1505, 2014\.
  * [24] S. Li, B. Bai, J. Zhou, P. Chen, and Z. Yu, “Reduced-complexity equalization for faster-than-Nyquist signaling: New methods based on Ungerboeck observation model,” _IEEE Trans. Commun._ , vol. 66, no. 3, pp. 1190–1204, Mar. 2017.
  * [25] S. Li, W. Yuan, J. Yuan, B. Bai, D. W. K. Ng, and L. Hanzo, “Time-domain vs. frequency-domain equalization for FTN signaling,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 8, pp. 9174–9179, Jun. 2020.
  * [26] Z. Wei, D. W. K. Ng, J. Yuan, and H. Wang, “Optimal resource allocation for power-efficient MC-NOMA with imperfect channel state information,” _IEEE Trans. Commun._ , vol. 65, no. 9, pp. 3944–3961, May 2017.
  * [27] Z. Wei, D. W. K. Ng, and J. Yuan, “NOMA for hybrid mmWave communication systems with beamwidth control,” _IEEE J. Sel. Topics Signal Process._ , vol. 13, no. 3, pp. 567–583, Jun. 2019.
  * [28] W. Yuan, N. Wu, J. Yuan, D. W. K. Ng, and L. Hanzo, “Joint data and active user detection for grant-free FTN-NOMA in dynamic networks,” in _IEEE Int. Conf. Commun._ , 2020, pp. 1–6.
  * [29] W. Yuan, N. Wu, A. Zhang, X. Huang, Y. Li, and L. Hanzo, “Iterative receiver design for FTN signaling aided sparse code multiple access,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 2, pp. 915–928, Nov. 2020.
  * [30] B. Simon, _Szegő’s Theorem and Its Descendants: Spectral Theory for L2 Perturbations of Orthogonal Polynomials_. Princeton university press, 2010, vol. 6.
  * [31] M. Qiu, Y.-C. Huang, and J. Yuan, “Downlink non-orthogonal multiple access without SIC for block fading channels: An algebraic rotation approach,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 8, pp. 3903–3918, Jun. 2019\.
  * [32] M. Qiu, Y.-C. Huang, J. Yuan, and C.-L. Wang, “Lattice-partition-based downlink non-orthogonal multiple access without SIC for slow fading channels,” _IEEE Trans. Commun._ , vol. 67, no. 2, pp. 1166–1181, Oct. 2018\.
  * [33] Y. J. D. Kim, “Properties of faster-than-Nyquist channel matrices and folded-spectrum, and their applications,” in _Proc. IEEE Wireless Commun. Net. Conf._ , 2016, pp. 1–7.
  * [34] Y. J. D. Kim, J. Bajcsy, and D. Vargas, “Faster-than-Nyquist broadcasting in Gaussian channels: Achievable rate regions and coding,” _IEEE Trans. Commun._ , vol. 64, no. 3, pp. 1016–1030, 2016.
  * [35] F. Rusek and A. Prlja, “Optimal channel shortening for MIMO and ISI channels,” _IEEE Trans. Wireless Commun._ , vol. 11, no. 2, pp. 810–818, Dec. 2011.
  * [36] A. T. Abebe and C. G. Kang, “Iterative decoders for FTN-based NOMA scheme to multiplex sporadic and broadband transmission,” in _Int. Conf. Inf. Commun. Techn. Conv. (ICTC)_ , 2018, pp. 813–817.
  * [37] T. M. Cover and J. A. Thomas, _Elements of Information Theory_. John Wiley & Sons, 2012.
  * [38] B. Clerckx, Y. Mao, R. Schober, E. A. Jorswieck, D. J. Love, J. Yuan, L. Hanzo, G. Y. Li, E. G. Larsson, and G. Caire, “Is NOMA efficient in multi-antenna networks? A critical look at next generation multiple access techniques,” _IEEE Open J. Commun. Soc._ , vol. 2, pp. 1310–1343, Jun. 2021.
  * [39] F. R. Gantmakher, _The Theory of Matrices_. American Mathematical Soc., 1959, vol. 131.
  * [40] P. J. Brockwell, R. A. Davis, and S. E. Fienberg, _Time Series: Theory and Methods_. Springer Science & Business Media, 1991.
  * [41] W. Rudin, _Real and Complex Analysis_. Tata McGraw-hill education, 2006.