capbtabboxtable[][0.4]

# Graph-based Untrained Neural Network Detector for OTFS Systems

Hao Chang, Branka Vucetic, and Wibowo Hardjawana,
Centre for IoT and Telecommunications, The University of Sydney, Sydney,
Australia.
<EMAIL_ADDRESS>
###### Abstract

Inter-carrier interference (ICI) caused by mobile reflectors significantly
degrades the conventional orthogonal frequency division multiplexing (OFDM)
performance in high-mobility environments. The orthogonal time frequency space
(OTFS) modulation system effectively represents ICI in the delay-Doppler
domain, thus significantly outperforming OFDM. Existing iterative and neural
network (NN) based OTFS detectors suffer from high complex matrix operations
and performance degradation in untrained environments, where the real wireless
channel does not match the one used in the training, which often happens in
real wireless networks. In this paper, we propose to embed the prior knowledge
of interference extracted from the estimated channel state information (CSI)
as a directed graph into a decoder untrained neural network (DUNN), namely
graph-based DUNN (GDUNN). We then combine it with Bayesian parallel
interference cancellation (BPIC) for OTFS symbol detection, resulting in
GDUNN-BPIC. Simulation results show that the proposed GDUNN-BPIC outperforms
state-of-the-art OTFS detectors under imperfect CSI.

###### Index Terms:

orthogonal time frequency space, symbol detection, Bayesian parallel
interference cancellation, untrained neural network.

††Part of this work has been published as an MPhil thesis in [1].

##  I Introduction

In high-mobility environments, Doppler shifts lead to high inter-carrier
interference (ICI) in the 5G air interface that is based on orthogonal
frequency division multiplexing (OFDM) system [2] and [3]. The orthogonal time
frequency space (OTFS) proposed in [2] as a 6G air interface addresses ICI by
multiplexing symbols in the delay-Doppler (DD) domain. The DD domain captures
the geometry of the channel paths generated by mobile reflectors (e.g., delay
and Doppler shift) and thus tracks the ICI, allowing the construction of a
time-invariant channel matrix [3] for detectors. Multiple OTFS detectors [4,
5, 6, 7, 8] in the literature can be categorized as 1) iterative and 2) neural
network (NN) based detectors.

Iterative OTFS detectors with good symbol error rate (SER) performances have
been proposed in [4] and [5], referred to as unitary approximate message
passing (UAMP) and Bayesian parallel interference cancellation with minimum-
mean-square-error (MMSE-BPIC) detectors, respectively. UAMP performs unitary
transformation operations on the OTFS channel matrix and received signal using
a singular value decomposition (SVD). The results of this transformation are
used in the AMP algorithm [4] to estimate transmitted OTFS symbols
iteratively. MMSE-BPIC first performs a matrix inversion operation to compute
MMSE symbol estimates, which are used as initial symbol estimates of BPIC in
the first iteration. Throughout the iterative process, the PIC scheme is used
to subtract interference from the received signal using the symbol estimates
from the previous iteration. The Bayesian concept is applied to estimate the
mean and variance of posterior symbols, and these estimates are weighted with
their estimation in the previous iteration through decision statistic
combining (DSC). A near-optimal SER performance that is close to the one of
maximum likelihood (ML) detector is achieved using the expectation propagation
(EP) [6] scheme. EP uses a matrix inversion and Bayesian concept to estimate
the mean and variance of posterior symbols iteratively. As the granularity of
delay and Doppler shift to improve the tracking accuracy of the channel paths
increases, the size of the DD domain time-invariant channel matrix also
increases. This poses a challenge in complex matrix operations (e.g., SVD and
matrix inversion) for the above detectors.

NN based detectors can be categorized as 1) trained NN and 2) untrained NN
(UNN). Trained NN detectors [7] and [8] require a training process with a
large amount of training data before implementation. Also, these detectors
rely on the fidelity of the training data. The performance degradation will
happen in untrained channel environments where the real wireless channel does
not match the one used in the training, which often happens in real wireless
networks. UNN was first proposed in [9] for image inverse problems without
training, which uses an auto-encoder (AE) NN architecture consisting of an NN
encoder followed by an NN decoder. The encoder and decoder consist of NN
layers with decreasing and increasing sizes, respectively. The AE used in [9]
consists of tens of layers for solving the image inverse problem iteratively,
resulting in high computational complexity. Our recently proposed decoder UNN
OTFS detector, in combination with the BPIC scheme [10], referred to as DUNN-
BPIC, uses only the decoder part of the AE to reduce the computational
complexity. It performs symbol detection without any training and achieves a
close to EP SER performance in the presence of perfect channel state
information (CSI) at the receiver. However, this is at the cost of large
iteration numbers. The authors in [11] embed prior knowledge as an undirected
graph into a decoder UNN design and use it for iterative signal denoising.
Downsampling of the graph representing prior knowledge to create a sub-graph
is required to cater for decoder UNN layers with different sizes. This graph
processing adds computational complexity. To date, the graph-based decoder UNN
concept has not been applied in the OTFS systems under imperfect CSI
estimates.

In this paper, we propose a graph-based decoder UNN (GDUNN) detector in the
presence of imperfect CSI estimates at the OTFS receiver, in contrast to the
perfect CSI assumption in [10]. We first transmit both pilot and data symbols
at the transmitter. The symbols are then passed through a multi-path channel
and impacted by the Doppler shift and channel delay. The imperfect CSI
estimates due to the receiver noise are obtained by using the transmitted
pilot at the receiver. The estimated CSI is then used to construct a directed
graph representing the interference among the data symbols for GDUNN. The
directed graph is used due to a non-symmetrical channel matrix caused by
different delays and Doppler shifts of different channel paths, in contrast to
an undirected graph UNN in [11] for a symmetric matrix. We add an additional
NN layer after the DUNN output layer. The input of this layer is designed to
match the matrix representation of the directed graph, allowing the prior
knowledge of interference to be embedded without downsampling in contrast to
[11]. We then use the GDUNN output as the initial symbol estimates of BPIC for
symbol detection, resulting in GDUNN-BPIC. The simulation results show that
the proposed GDUNN needs significantly fewer iterations than DUNN.
Furthermore, GDUNN-BPIC outperforms EP and other state-of-the-art OTFS
detectors in the presence of imperfect CSI using lower complexity.

Notations: $a$, ${\bf a}$, and ${\bf A}$ denote scalar, vector, and matrix,
respectively. ${\bf A}^{T}$ represents the transpose of matrix ${\bf A}$.
$\mathbb{C}^{M\times N}$ and $\mathbb{R}^{M\times N}$ denote an $M\times N$
dimensional complex-valued and real-valued matrix, respectively. ${\bf I}_{M}$
represents an $M\times M$ dimensional identity matrix. $[\cdot]_{M}$
represents the mod-$M$ operation. The Kronecker product is denoted as
$\otimes$. $\|{\bf x}\|$ denotes the Frobenius norm of vector ${\bf x}$. We
use $\mathcal{N}(x:\mu,\sigma^{2})$ to express a single variate Gaussian
distribution of a random variable $x$ with mean $\mu$ and variance
$\sigma^{2}$. We define ${\bf a}={\sf vec}({\bf A})$ as the column-wise
vectorization of matrix ${\bf A}$, and ${\bf A}={\sf vec}^{-1}({\bf a})$
denotes the vector elements folded back into a matrix. ${\sf diag}(\cdot)$
denotes a diagonalization operation on a vector.

Figure 1: OTFS modulation system

(a) ${\bf X}_{\rm{DD}}$

(b) ${\bf Y}_{\rm{DD}}$

Figure 2: An example of the DD domain OTFS frames for
$k_{p}=l_{p}=3,N=M=8,k_{max}=1,l_{max}=2$

##  II OTFS system model

In this section, we consider the OTFS system model and formulation in [12,
13], as illustrated in Fig. 1. At the transmitter side, we first define a DD
domain OTFS frame with $N$ Doppler shift and $M$ delay indices, indicating the
tracking of Doppler shift and delay at $\frac{k}{NT}$ and $\frac{l}{M\Delta
f}$, $k=0,\dots,N-1,l=0,\dots,M-1$, respectively. $\Delta f$ is subcarrier
spacing, and $T=\frac{1}{\Delta f}$ is the time slot duration.

Following [13], we then allocate the pilot, guard, and data symbols in the DD
domain, denoted as ${\bf X}_{\rm DD}\in\mathbb{C}^{N\times M}$. $x[k,l]$
represents the $(k,l)$-th entry of ${\bf X}_{\rm DD}$, namely the symbol
transmitted in Doppler index $k$ and delay index $l$,

$x[k,l]=\begin{cases}x_{p}&k=k_{p},l=l_{p},\\\ x_{g1}&\begin{aligned}
k_{p}-k_{max}\leq k\leq k_{p}+k_{max},\\\ l_{p}\leq l\leq
l_{p}+l_{max},\end{aligned}\\\ x_{g2}&\begin{aligned} k_{p}-2k_{max}\leq k\leq
k_{p}+2k_{max},\\\ l_{p}-l_{max}\leq l<l_{p},or\\\ k_{p}-2k_{max}\leq
k<k_{p}-k_{max},or,\\\ k_{p}+k_{max}<k\leq k_{p}+2k_{max},\\\ l_{p}\leq l\leq
l_{p}+l_{max},\end{aligned}\\\ x_{d}&\rm{otherwise},\end{cases}$ (1)

where $x_{p}$ is the pilot following binary phase shift keying (BPSK) with
power $P_{p}$, and $k_{p}$ and $l_{p}$ represent the pilot position in the DD
domain frame. We only allocate one pilot in ${\bf X}_{\rm DD}$, as using
multiple pilots will result in interference among those pilots. The guard
$x_{g1}=0$ is used to ensure the Doppler shift and delay of $\frac{\pm
k_{max}\Delta f}{N}$ Hz and $\frac{l_{max}T}{M}$ second can be tracked by
using pilot $x_{p}$. The guard $x_{g2}=0$ is used to ensure the transmission
of data symbols $x_{d}$ does not interfere with the pilot symbol $x_{p}$ in
the presence of the previously stated Doppler shift and delay due to the
mobility of reflectors. $x_{d}$ is the ${\tilde{M}}$-ary quadrature amplitude
modulation (${\tilde{M}}$-QAM) data symbols with unit average power, and
${\tilde{M}}$ is the modulation order. $k_{max}$ and $l_{max}$ are the maximum
Doppler and delay indices for the OTFS multi-path channel. Here, we give an
example of the DD domain OTFS frames in Fig. 2(a).

${\bf X}_{\rm DD}$ is then transformed into the time-frequency (TF) domain by
using the inverse symplectic finite Fourier transform (ISFFT)[12], expressed
as

${\bf X}_{\rm TF}={\bf F}_{M}{\bf X}_{\rm DD}{\bf F}_{N}^{{\bf H}},$ (2)

where ${\bf F}_{M}\in\mathbb{C}^{M\times M}$ and ${\bf F}_{N}^{{\bf
H}}\in\mathbb{C}^{N\times N}$ are $M$-points DFT and $N$-points IDFT matrices,
and the $(p,q)$-th entries of them are $(\frac{1}{\sqrt{M}}e^{-j2\pi
pq/M})_{p,q=0,\cdots,M-1}$ and $(\frac{1}{\sqrt{N}}e^{j2\pi
pq/N})_{p,q=0,\cdots,N-1}$, respectively. ${\bf X}_{\rm
TF}\in\mathbb{C}^{M\times N}$ are the transmitted symbols in a TF domain OTFS
frame. The Heisenberg transform [12] is then applied to ${\bf X}_{\rm TF}$ to
generate the time domain transmitted signal, given as

${\bf s}={\sf vec}({\bf G}_{\rm tx}{\bf F}^{{\bf H}}_{M}{\bf X}_{\rm
TF})=({\bf F}^{{\bf H}}_{N}\otimes{\bf G}_{\rm tx}){\bf x}_{\rm DD},$ (3)

where ${\bf G}_{\rm tx}={\sf diag}\left[g_{\rm tx}(0),g_{\rm
tx}(\frac{T}{M}),\dots,g_{\rm tx}(\frac{(M-1)T}{M})\right]$. $g_{\rm tx}(t)$
is a rectangular waveform with a duration of $T$, leading to ${\bf G}_{\rm
tx}={\bf I}_{M}$ [12]. ${\bf x}_{\rm DD}=\sf{vec}({\bf X}_{\rm DD})$. We then
insert the cyclic prefix (CP) of length $l_{max}$ at the beginning of ${\bf
s}$ to prevent interference between different OTFS frames. They are then
sampled at $\frac{1}{M\Delta f}$ second and sent via a wireless channel. Thus,
${\bf s}$ occupies a total bandwidth of $M\Delta f$ Hz and a duration of $NT$
seconds.

The impulse response of the time-varying multi-path channel in OTFS is modeled
as [12]

$h(\tau,v)=\sum_{i=1}^{P}h_{i}\delta(\tau-\tau_{i})\delta(v-v_{i}),$ (4)

where $\delta(\cdot)$ is the Dirac delta function,
$h_{i}\sim\mathcal{N}(0,1/P)$ denotes the $i$-th path gain, and $P$ is the
total number of propagation paths. The delay and Doppler shift for path $i$
are $\tau_{i}=\frac{l_{i}T}{M}$ and $v_{i}=\frac{k_{i}\Delta f}{N}$,
respectively. Each mobile reflector contributes to one unique path with its
own delay index $l_{i}\in[0,l_{max}]$ and Doppler shift index
$k_{i}\in[-k_{max},k_{max}]$ for $i=1,\dots,P$. The maximum channel delay and
Doppler shift indices are set to $l_{max}\leq M-1$ and
$k_{max}\leq\frac{N}{2}$, respectively. This implies a maximum supported
channel delay of $\frac{(M-1)T}{M}$ seconds and a maximum Doppler shift of
$\frac{\Delta f}{2}$ Hz.

At the receiver, the time domain received signal is first sampled at intervals
of $\frac{1}{M\Delta f}$. After discarding the CP, the time domain received
signal $r(n)$ is then expressed as [12]

$r(n)=\sum^{P}_{i}h_{i}e^{j2\pi\frac{(n-l_{i})k_{i}}{NM}}s([n-l_{i}]_{NM})+w(n),$
(5)

where $n=0,\dots,MN-1$, and $w(n)$ is the noise with each entry following
$\mathcal{N}(0,\sigma^{2})$. We then can write the vector form of (5) as

${\bf r}=\tilde{{\bf H}}{\bf s}+{\bf w},$ (6)

where $\tilde{{\bf H}}=\sum_{i=1}^{P}h_{i}{\bf
I}_{MN}(l_{i}){\boldsymbol{\Delta}}^{k_{i}}$ is the time domain channel
matrix. The use of CP results in a cyclic shift matrix ${\bf I}_{MN}(l_{i})$
[12], which is obtained by circularly left shifting the columns of ${\bf
I}_{MN}$ by $l_{i}$. ${\boldsymbol{\Delta}}^{k_{i}}={\sf
diag}\left[z^{0},z^{1},\cdots,z^{MN-1}\right]$ is the $MN\times MN$ Doppler
shift diagonal matrix, where $z=e^{\frac{j2\pi k_{i}}{MN}}$. ${\bf w}$ is the
noise. The TF domain received signal ${\bf Y}_{\rm TF}\in\mathbb{C}^{N\times
M}$ is obtained by applying the Wigner transform to ${\bf r}$, shown as [12]

${\bf Y}_{\rm TF}={\bf F}_{M}{\bf G}_{\rm rx}{\bf R},$ (7)

where ${\bf G}_{\rm rx}={\sf diag}\left[g_{\rm rx}(0),g_{\rm
rx}(\frac{T}{M}),\dots,g_{\rm rx}(\frac{(M-1)T}{M})\right]$. $g_{\rm
rx}(t)=g_{\rm tx}(t)$ results in ${\bf G}_{\rm rx}={\bf G}_{\rm tx}={\bf
I}_{M}$ [12]. ${\bf R}={\sf vec}^{-1}({\bf r})$. The DD domain received signal
${\bf Y}_{\rm DD}\in\mathbb{C}^{M\times N}$ is obtained by applying the SFFT
to ${\bf Y}_{\rm TF}$ [12]

$\displaystyle{\bf Y}_{\rm DD}={\bf F}^{{\bf H}}_{M}{\bf Y}_{\rm TF}{\bf
F}_{N},$ (8)

and the $(k,l)$-th entry of ${\bf Y}_{\rm DD}$ is $y[k,l]$ for
$k=0,\cdots,N-1,l=0,\cdots,M-1$. We then substitute (3), (5), and (7) in (8)
and obtain

${\bf y}_{\rm DD}=\underbrace{({\bf F}_{N}\otimes{\bf G}_{\rm rx})\tilde{{\bf
H}}({\bf F}^{{\bf H}}_{N}\otimes{\bf G}_{\rm tx})}_{{\bf H}_{\rm DD}}{\bf
x}_{\rm DD}+{\bf w}_{\rm DD},$ (9)

where ${\bf y}_{\rm DD}=\sf{vec}({\bf Y}_{\rm DD})$, and ${\bf w}_{\rm
DD}=({\bf F}_{N}\otimes{\bf G}_{\rm rx}){\bf w}$ denotes the noise in the DD
domain. ${\bf H}_{\rm DD}$ is the real DD domain OTFS channel matrix.

##  III OTFS Channel estimation

We use the channel estimation scheme in [13]. Based on the guard $x_{g1}$ in
(1), only a part of the received symbols $y[k,l]$, for $k_{p}-k_{max}\leq
k\leq k_{p}+k_{max},l_{p}\leq l\leq l_{p}+l_{max}$, i.e., the $(k,l)$-th entry
of ${\bf Y}_{\rm{DD}}$ in (8) are used to estimate the path gain and the
corresponding delay and Doppler indices. The Doppler shift and channel delay
experienced by the transmitted pilot $x_{p}$ depends on the wireless channel
(4). Here, we give an example of ${\bf Y}_{\rm{DD}}$ in Fig. 2(b) based on the
symbol transmission in Fig. 2(a).

As shown in (9), the noise will impact the channel estimation process
explained below. For each of $y[k,l]\geq\epsilon$, we detect there is a path
$j,j=1,\dots,\hat{P}$ with Doppler index $\hat{k}_{j}=k-k_{p}$, delay index
$\hat{l}_{j}=l-l_{p}$ and path gain
$\hat{h}_{j}=\frac{y[k,l]}{x_{p}}e^{-j2\pi(l-\hat{l}_{j})\hat{k}_{j}}$ [13].
We set $\epsilon=3\sigma$, where $\sigma^{2}=10^{\frac{-SNR}{10}}$. We can
then obtain the estimated time domain channel matrix $\hat{{\bf H}}$ and the
estimated DD domain channel matrix $\hat{{\bf H}}_{\rm{DD}}$ by using (6) and
(9), and setting $l_{i}=\hat{l}_{j},k_{i}=\hat{k}_{j},h_{i}=\hat{h}_{j}$ and
$P=\hat{P}$. $\hat{{\bf H}}_{\rm{DD}}\neq{\bf H}_{\rm{DD}}$ as there is always
a channel estimation error due to the incorrect estimation of
$\hat{k}_{j},\hat{l}_{j}$, $\hat{h}_{j}$ and $\hat{P}$.

(a) GDUNN

(b) Directed graph

Figure 3: GDUNN architecture and graph design

##  IV Graph-based untrained neural network symbol detector

The OTFS transmission structure in (1) assumes the data symbols will be
shifted by maximum $\pm k_{max}$ Doppler and $l_{max}$ delay indices. Thus, we
will use all $y[k,l]$ in ${\bf Y}_{\rm{DD}}$ where
$k\notin[k_{p}-k_{max},k_{p}+k_{max}],l\notin[l_{p},l_{p}+l_{max}]$, which
corresponds to the indices of $x_{d}$ and $x_{g2}$ in (1). This is equal to
taking the $m$-th entry of ${\bf y}_{\rm DD}$ in (9) where
$m\neq(Np+q+1),p=l_{p},\dots,l_{p}+l_{max},q=k_{p}-k_{max},\dots,k_{p}+k_{max}$.
We write the received signal for data symbols as $\hat{{\bf y}}_{\rm{DD}}$.
The corresponding channel matrix for the data symbols can be written as
$\hat{{\bf H}}_{\rm{eff}}$, constructed by using the Doppler and delay indices
of $x_{d}$ and $x_{g2}$ in (1). This is equivalent to using the $m$-th row of
$\hat{{\bf H}}_{\rm{DD}}$, and $n$-th column of $\hat{{\bf H}}_{\rm{DD}}$,
where
$n\neq(N\hat{p}+\hat{q}+1),\hat{p}=l_{p}-l_{max},\dots,l_{p}+l_{max},\hat{q}=k_{p}-2k_{max},\dots,k_{p}+2k_{max}$.
Therefore, based on $\hat{{\bf y}}_{\rm{DD}}$ and $\hat{{\bf H}}_{\rm{eff}}$,
model (9) for data detection can be rewritten as

$\hat{{\bf y}}_{\rm{DD}}=\hat{{\bf H}}_{\rm{eff}}\hat{{\bf
x}}_{\rm{DD}}+\hat{{\bf w}}_{\rm{DD}}.$ (10)

where $\hat{{\bf x}}_{\rm{DD}}$ consists of only the data symbols in ${\bf
x}_{\rm{DD}}$, i.e., the $n$-th entry of ${\bf x}_{\rm{DD}}$. $\hat{{\bf
w}}_{\rm{DD}}$ is the noise, consisting of the relevant $m$-th entry of ${\bf
w}_{\rm{DD}}$. $\hat{{\bf y}}_{\rm{DD}},\hat{{\bf
w}}_{\rm{DD}}\in\mathbb{C}^{\frac{V}{2}\times 1}$, $\hat{{\bf
H}}_{\rm{eff}}\in\mathbb{C}^{\frac{V}{2}\times\frac{U}{2}}$, and $\hat{{\bf
x}}_{\rm{DD}}\in\mathbb{C}^{\frac{U}{2}\times 1}$ where
$V=2(NM-(l_{max}+1)(2k_{max}+1)),U=2(NM-(2l_{max}+1)(4k_{max}+1))$.

We then consider a real-valued equivalent model of (10) as

$\displaystyle{\bf y}={\bf H}{\bf x}+{\bf n},$ (11)

where ${\bf x}=\begin{bmatrix}\Re(\hat{{\bf x}}_{\rm DD})\ \Im(\hat{{\bf
x}}_{\rm DD})\end{bmatrix}^{T}$, ${\bf y}=\begin{bmatrix}\Re(\hat{{\bf
y}}_{\rm{DD}})\ \Im(\hat{{\bf y}}_{\rm{DD}})\end{bmatrix}^{T}$, ${\bf
n}=\begin{bmatrix}\Re(\hat{{\bf w}}_{\rm{DD}})\ \Im(\hat{{\bf
w}}_{\rm{DD}})\end{bmatrix}^{T}$, ${\bf H}=\begin{bmatrix}\Re(\hat{{\bf
H}}_{\rm{eff}})&-\Im(\hat{{\bf H}}_{\rm{eff}})\\\ \Im(\hat{{\bf
H}}_{\rm{eff}})&\Re(\hat{{\bf H}}_{\rm{eff}})\end{bmatrix}$, $\Re(\cdot)$ and
$\Im(\cdot)$ take the real and imaginary parts, respectively. ${\bf y},{\bf
n}\in\mathbb{R}^{V\times 1},{\bf x}\in\mathbb{R}^{U\times 1}$. ${\bf
H}\in\mathbb{R}^{V\times U}$. We consider the model (11) for the rest of the
paper.

###  IV-A GDUNN

The GDUNN architecture is shown in Fig. 3(a). It consists of $D$ FC layers,
and the Tanh activation function is used after each FC layer. We extract the
interference among DD domain symbols from the estimated DD domain channel
matrix ${\bf H}$ in (11) and embed it into the last GDUNN layer. Specifically,
we use a directed graph to represent the interference, as shown in Fig. 3(b),
where nodes feature $x_{1},\cdots,x_{U}$ represent the entries of the
transmitted symbol ${\bf x}$ in (11). $e_{i,j}$ is the edge representing the
interference between $x_{i}$ and $x_{j}$. $e_{i,j}\neq e_{j,i}$ as the
interference from $x_{i}$ to $x_{j}$ and from $x_{j}$ to $x_{i}$ are
different. The edge value is defined as $e_{i,j}=\frac{{\bf h}_{i}^{T}{\bf
h}_{j}}{\|{\bf h}_{j}\|^{2}}$, where ${\bf h}_{j}$ represents the $j$-th
column of channel matrix ${\bf H}$. Thus, the adjacency matrix of the graph is
expressed as ${\bf F}\in\mathbb{R}^{U\times U}$, where the $i,j$-th entry of
${\bf F}$ is $e_{i,j}$. The output of GDUNN at iteration $i$ is expressed as,

$\hat{{\bf x}}_{\rm GDUNN}^{(i)}=\alpha
f_{D}^{(i)}(f_{D-1}^{(i)}(\cdots(f_{1}^{(i)}({\bf z}_{1}^{(i)})))),$ (12)
$f_{d}^{(i)}({\bf z}_{d}^{(i)})=\begin{cases}{\rm{Tanh}}({\bf W}_{d}^{(i)}{\bf
z}_{d}^{(i)}+{\bf b}_{d}^{(i)}),d=1,\dots,D-1,\\\ {\rm{Tanh}}({\bf
W}_{d}^{(i)}({\bf F}{\bf z}_{d}^{(i)})+{\bf b}_{d}^{(i)}),d=D,\end{cases}$
(13)

where $f_{d}^{(i)}({\bf z}_{d}^{(i)})\in\mathbb{R}^{O_{d}\times 1}$ and ${\bf
z}_{d}^{(i)}\in\mathbb{R}^{I_{d}\times 1}$ are the output and input of $d$-th
FC layer at iteration $i$, respectively. $O_{d}$ and $I_{d}$ are the input and
output sizes of $d$-th FC layer, respectively. ${\bf z}_{1}^{(i)}$ is the
first FC layer input drawn from a normal distribution
$\mathcal{N}(\mathbb{0},\mathbb{1})$ and it is fixed during the iterative
process. $\alpha$ is a constant that restricts the GDUNN output range within
the minimum and maximum power of $\tilde{M}$-QAM symbol ${\bf x}$ in (11).
${\bf W}_{d}^{(i)}\in\mathbb{R}^{O_{d}\times I_{d}}$ and ${\bf
b}_{d}^{(i)}\in\mathbb{R}^{O_{d}\times 1}$ represent the weight matrix and
bias vector in $d$-th layer at iteration $i$. Each entry of ${\bf
W}_{d}^{(0)}$ and ${\bf b}_{d}^{(0)}$ are initialized following a uniform
distribution with a range of
$(\frac{-1}{\sqrt{O_{d}}},\frac{1}{\sqrt{O_{d}}})$ [14].

The stopping criteria in [10] is used to control the iterative process of
GDUNN by using the computed variance of its output in (12) for a fixed window
size $S$. This is given as

$\displaystyle\varsigma^{(i)}=\frac{1}{S}\sum_{j=i-S}^{i}\|\hat{{\bf x}}_{\rm
GDUNN}^{(j)}-\frac{1}{S}\sum_{j^{\prime}=i-S}^{i}\hat{{\bf x}}_{\rm
GDUNN}^{(j^{\prime})}\|^{2},i\geq S,$ (14)

where $\varsigma^{(i)}$ is the variance value at iteration $i$. When $i<S$,
the variance calculation is inactive. $S$ determines how many outputs are used
for calculating the variance. We compare $\varsigma^{(i)}$ with a threshold
$\Psi$. If $\varsigma^{(i)}<\Psi$, the iterative process of GDUNN will stop,
and $\hat{{\bf x}}_{\rm GDUNN}^{(i)},i=T_{\rm GDUNN}$ is the final estimated
symbol. Otherwise, we calculate the MSE between the output in (12) and the
received signal ${\bf y}$

$\mathcal{L}^{(i)}=\frac{1}{U}\|{\bf H}\hat{{\bf x}}_{\rm GDUNN}^{(i)}-{\bf
y}\|^{2}.$ (15)

Adam optimizer [15] is then used to calculate the gradient and update weights
${\bf W}_{d}^{(i)}$ and biases ${\bf b}_{d}^{(i)}$ used for iteration $i+1$ by
minimizing the calculated error in (15).

###  IV-B GDUNN-BPIC

In this section, we propose to combine the GDUNN and BPIC OTFS symbol
detection. A brief description of the BPIC algorithm proposed in [5] is shown,
consisting of Bayesian symbol observation (BSO), Bayesian symbol estimation
(BSE), and decision statistics combining (DSC). BSO is a matched filter based
PIC scheme that is used to estimate the transmitted symbols in iteration $t$
based on the estimated symbols $\hat{{\bf x}}^{(t-1)}$ from the previous
iteration, expressed as

$\mu_{q}^{(t)}=\hat{x}_{q}^{(t-1)}+\frac{{\bf h}_{q}^{T}\left({\bf y}-{\bf
H}\hat{{\bf x}}^{(t-1)}\right)}{\|{\bf h}_{q}\|^{2}},$ (16)

where $\mu_{q}^{(t)}$ is the soft estimate of $q$-th symbol $x_{q}$ in
iteration $t$, ${\bf h}_{q}$ is the $q$-th column of channel matrix ${\bf H}$.
$\hat{{\bf
x}}^{(t-1)}=[\hat{x}_{1}^{(t-1)},\cdots,\hat{x}_{q}^{(t-1)},\cdots,\hat{x}_{U}^{(t-1)}]^{T}$
is the vector of the estimated symbol. The MMSE scheme is used in [5] to
obtain the initial symbol estimates, as $\hat{{\bf x}}^{(0)}=({\bf H}^{T}{\bf
H}+\sigma^{2}{\bf I})^{-1}{\bf H}^{T}{\bf y}$ in the first BPIC iteration.
Here, we use the output of GDUNN as the initial symbol estimates of the BPIC,
i.e., $\hat{{\bf x}}^{(0)}=\tilde{{\bf x}}_{\rm GDUNN}^{(T_{\rm GDUNN})}$,
resulting in the GDUNN-BPIC OTFS detector. The variance $\Sigma_{q}^{(t)}$ of
the $q$-th symbol estimate is expressed as

$\displaystyle\Sigma_{q}^{(t)}$ $\displaystyle=\frac{1}{({\bf h}_{q}^{T}{\bf
h}_{q})^{2}}\left(\sum_{j=1\atop{j\neq{q}}}^{U}({\bf h}_{q}^{T}{\bf
h}_{q})^{2}v_{j}^{(t-1)}+({\bf h}_{q}^{T}{\bf h}_{q})\sigma^{2}\right),$ (17)

where $v_{j}^{(t-1)}$ is the $j$-th element in a vector of symbol estimates
variance ${\bf v}^{(t-1)}$ in iteration $t-1$ and ${\bf
v}^{(t-1)}=[v_{1}^{(t-1)},\cdots,v_{q}^{(t-1)},\cdots,v_{U}^{(t-1)}]^{T}$. We
set ${\bf v}^{(0)}=0$, as the prior knowledge of the variance is unknown at
the beginning. Then the estimated symbol
${\boldsymbol{\mu}}^{(t)}=[\mu_{1}^{(t)},\cdots,\mu_{q}^{(t)},\cdots,\mu_{U}^{(t)}]^{T}$and
variance
${\boldsymbol{\Sigma}}^{(t)}=[\Sigma_{1}^{(t)},\cdots,\Sigma_{q}^{(t)},\cdots,\Sigma_{U}^{(t)}]^{T}$
are forwarded to the BSE module.

The BSE module computes the Bayesian symbol estimates and the variance of the
$q$-th symbol obtained from the BSO module, given as [5]

$\hat{x}_{q}^{(t)}=\mathbb{E}\left[x_{q}\Big{|}\mu_{q}^{(t)},\Sigma_{q}^{(t)}\right]$
(18)
$v_{q}^{(t)}=\mathbb{E}\left[\left|x_{q}-\mathbb{E}\left[x_{q}\Big{|}\mu_{q}^{(t)},\Sigma_{q}^{(t)}\right]\right|^{2}\right].$
(19)

$\hat{x}_{q}^{(t)}$and $v_{q}^{(t)}$ are then sent to the following DSC
module.

The DSC module performs a linear combination of the symbol estimates and its
variance obtained in the BSE model in two consecutive iterations, shown as

$\hat{x}_{q}^{(t)}=\left(1-\rho_{q}^{(t)}\right)\hat{x}_{q}^{(t-1)}+\rho_{q}^{(t)}\hat{x}_{q}^{(t)}$
(20)
$v_{q}^{(t)}=\left(1-\rho_{q}^{(t)}\right)v_{q}^{(t-1)}+\rho_{q}^{(t)}v_{q}^{(t)},$
(21)

where
$\rho_{q}^{(t)}=\frac{\epsilon_{q}^{(t-1)}}{\epsilon_{q}^{(t)}+\epsilon_{q}^{(t-1)}}$
is the weighting coefficient, and $\epsilon_{q}^{(t)}=\left\|\frac{{\bf
h}_{q}^{T}}{\|{\bf h}_{q}\|^{2}}\left({\bf y}-{\bf H}\hat{{\bf
x}}^{(t)}\right)\right\|^{2}.$ The weighted symbol estimates $\hat{{\bf
x}}^{(t)}$ and the variance ${\bf v}^{(t)}$ are then returned to the BSO
module for the next iteration. After $T_{\rm BPIC}$ iterations, $\hat{{\bf
x}}^{(T_{\rm BPIC})}$ is taken as a vector of symbol estimates.

Detector |  Complexity order
---|---
MMSE[16] | $\mathcal{O}(VU^{2})$
UAMP[4] | $\mathcal{O}(VU^{2}+VUT_{\rm UAMP})$
MMSE-BPIC[5] | $\mathcal{O}(VU^{2}+VUT_{\rm BPIC})$
BPICNet[8] | $\mathcal{O}(VU^{2}+VUT_{\rm BPICNet})$
EP[6] | $\mathcal{O}(VU^{2}T_{\rm EP})$
DUNN-BPIC [10] | $\mathcal{O}(VUT_{\rm DUNN}+VUT_{\rm BPIC})$
GDUNN-BPIC | $\mathcal{O}(VUT_{\rm GDUNN}+VUT_{\rm BPIC})$
Table I: Computational complexity comparison

##  V Computational Complexity Analysis

The computational complexity of GDUNN depends on the FC layers and MSE
calculation, which are matrix-vector multiplications. The number of
multiplications used for GDUNN is $\mathcal{O}(VUT_{\rm GDUNN})$. The number
of multiplications of GDUNN-BPIC is $\mathcal{O}(VUT_{\rm GDUNN}+VUT_{\rm
BPIC})$. Table I shows the computational complexity order in terms of the
number of multiplications for different OTFS detectors, where $T_{\rm
UAMP},T_{\rm BPIC}$, and $T_{\rm EP}$ represent the iterations needed for the
UAMP, MMSE-BPIC, and EP, respectively. Our proposed GDUNN-BIPC has lower
computational complexity orders than MMSE, MMSE-BPIC, UAMP, and EP. Here, we
give a numerical example for $M=N=8,l_{max}=2,k_{max}=1,T_{\rm GDUNN}=100$,
and $T_{\rm BPIC}=T_{\rm UAMP}=T_{\rm EP}=10$ as suggested in [5], [8], [4],
and [6], respectively. Based on Table I, GDUNN-BPIC is less complex than [5,
8, 4], and it is approximately 10 times less complex than [6].

(a) SER performance regarding window size $S$

(b) CDF of iteration numbers

Figure 4: Convergence comparison of DUNN and GDUNN for $SNR=28$ dB

(a) SER vs SNR

(b) SER vs pilot power $P_{p}$

Figure 5: SER performance comparison of OTFS detectors

##  VI Numerical results

In this section, we first analyze the convergence of the proposed GDUNN in
comparison with DUNN [10]. We then compare the SER performance of our proposed
GDUNN-BPIC with state-of-the-art ones, including MMSE [16], UAMP[4], MMSE-BPIC
[5], BPICNet [8], EP[6], and DUNN-BPIC [10] under imperfect CSI. In the
simulations, we consider $\tilde{M}=16$, $N=M=8,l_{max}=2,k_{max}=1,P=4$.
Subcarrier spacing and carrier frequency are 15 KHz and 6 GHz, respectively,
resulting in a maximum tolerable mobility of 337 Km/h. The pilot is put in the
position of $(k_{p},l_{p})=(3,3)$ and $P_{p}=1$. Note that the transmitted
symbols have a unit average power, and therefore, we set
$\alpha=\frac{3}{\sqrt{10}}$. The learning rate of GDUNN is set to 0.01, and
$I_{d}=4,8,16,32,U$ and $O_{d}=8,16,32,U,U$ for $d=1,\dots D$, respectively,
and $D=5$. By deleting the last GDUNN layer (i.e., $d=D$ in (13)), we can get
DUNN as in [10]. $T_{\rm BPIC}=T_{\rm UAMP}=T_{\rm BPICNet}=T_{\rm EP}=10$.
The imperfect CSI is considered for all the simulations below.

Fig. 4(a) shows the SER performance of DUNN and GDUNN regarding window size
$S$ with threshold $\Psi=0.001$ in (14). Fig. 4(a) demonstrates that GDUNN and
DUNN achieve the best SER performance with minimum window sizes $S=90$ and
$S=150$, respectively. Fig. 4(b) shows the cumulative density function (CDF)
of the number of iterations needed for DUNN and GDUNN using the minimum window
sizes. It demonstrates that GDUNN needs approximately $40\%$ fewer iterations
than DUNN. Therefore, the proposed GDUNN-BPIC is less complex than DUNN-BPIC.
Fig. 5(a) shows the SER performance of the proposed OTFS detector, where
GDUNN-BPIC achieves a similar SER performance to DUNN-BPIC and outperforms the
others. In Fig. 5(b), we fix the $SNR=25$ dB and increase the power of the
pilot $P_{p}$, resulting in a decrease in CSI estimate error, as illustrated
in [13]. Fig. 5(b) demonstrates that the proposed GDUNN-BPIC still achieves
the best SER performance among all the state-of-the-art OTFS detectors when
the error of CSI estimates decreases. Therefore, the proposed GDUNN-BPIC is
robust to imperfect CSI estimates compared to others.

##  VII Conclusion

In conclusion, we proposed a graph-based decoder UNN OTFS detector in the
presence of imperfect CSI, referred to as GDUNN-BPIC. Simulation results
showed that GDUNN needs fewer iterations than DUNN due to the embedding of
prior knowledge. The proposed GDUNN-BPIC outperforms state-of-the-art OTFS
detectors using lower computational complexity under imperfect CSI.

## References

  * [1] H. Chang, “Untrained neural network based symbol detection for OTFS systems,” _MPhil Thesis, The University of Sydney, Australia_ , 2023.
  * [2] R. Hadani, S. Rakib, M. Tsatsanis, A. Monk, A. J. Goldsmith, A. F. Molisch, and R. Calderbank, “Orthogonal time frequency space modulation,” in _Proc. IEEE Wireless Commun. and Netw. Conf. (WCNC)_ , USA, Mar. 2017, pp. 1–6.
  * [3] P. Raviteja, K. T. Phan, Y. Hong, and E. Viterbo, “Interference cancellation and iterative detection for orthogonal time frequency space modulation,” _IEEE Trans. Wirel. Commun._ , vol. 17, no. 10, pp. 6501–6515, Aug. 2018.
  * [4] Z. Yuan, F. Liu, W. Yuan, Q. Guo, Z. Wang, and J. Yuan, “Iterative detection for orthogonal time frequency space modulation with unitary approximate message passing,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 2, pp. 714–725, 2022.
  * [5] X. Qu, A. Kosasih, W. Hardjawana, V. Onasis, and B. Vucetic, “Bayesian-based symbol detector for orthogonal time frequency space modulation systems,” in _Proc. IEEE Int. Symp. Pers. Indoor Mob. Radio Commun. (PIMRC)_ , Sep. 2021, pp. 1154–1159.
  * [6] F. Long, K. Niu, and J. Lin, “Low complexity block equalizer for OTFS based on expectation propagation,” _IEEE Wireless Commun. Lett._ , vol. 11, no. 2, pp. 376–380, Feb. 2022.
  * [7] X. Zhang, S. Zhang, L. Xiao, S. Li, and T. Jiang, “Graph neural network assisted efficient signal detection for OTFS systems,” _IEEE Commun. Lett._ , pp. 1–1, 2023.
  * [8] A. Kosasih, X. Qu, W. Hardjawana, C. Yue, and B. Vucetic, “Bayesian neural network detector for an orthogonal time frequency space modulation,” _IEEE Wireless Commun. Lett._ , vol. 11, no. 12, pp. 2570–2574, 2022.
  * [9] V. Lempitsky, A. Vedaldi, and D. Ulyanov, “Deep image prior,” in _Proc. IEEE/CVF Conf. Comput. Vis. Pattern Recognit._ , USA, Jun. 2018, pp. 9446–9454.
  * [10] H. Chang, A. Kosasih, W. Hardjawana, X. Qu, and B. Vucetic, “Untrained neural network based Bayesian detector for OTFS modulation systems,” in _Proc. IEEE INFOCOM Wkshps_ , 2023, pp. 1–6.
  * [11] S. Rey, S. Segarra, R. Heckel, and A. G. Marques, “Untrained graph neural networks for denoising,” _IEEE Trans. Signal Process._ , vol. 70, pp. 5708–5723, 2022.
  * [12] P. Raviteja, Y. Hong, E. Viterbo, and E. Biglieri, “Practical pulse-shaping waveforms for reduced-cyclic-prefix OTFS,” _IEEE Trans. Vehic. Technol._ , vol. 68, no. 1, pp. 957–961, Jan. 2019.
  * [13] P. Raviteja, K. T. Phan, and Y. Hong, “Embedded pilot-aided channel estimation for otfs in delay–doppler channels,” _IEEE Trans. Vehic. Technol._ , vol. 68, no. 5, pp. 4906–4917, 2019.
  * [14] K. He, X. Zhang, S. Ren, and J. Sun, “Delving deep into rectifiers: Surpassing human-level performance on imagenet classification,” in _Proc. IEEE Int. Conf. Comput. Vis. (ICCV)_ , Chile, Dec. 2015, pp. 1026–1034.
  * [15] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _Proc. Int. Conf. Learn. Represent. (ICLR)_ , USA, 2015, pp. 1–15.
  * [16] P. Singh, A. Gupta, H. B. Mishra, and R. Budhiraja, “Low-complexity ZF/MMSE MIMO-OTFS receivers for high-speed vehicular communication,” _IEEE Open J. Commun. Soc._ , vol. 3, pp. 209–227, 2022.