Message Passing Based Detection for Orthogonal Time Frequency Space Modulation

Figure 1 Modulation and demodulation in an orthogonal time frequency space (OTFS) system^[2]

X_{t f} [n, m] = \frac{1}{\sqrt[]{M N}} \sum_{k = 0}^{N - 1} \sum_{l = 0}^{M - 1} x [k, l] e^{j 2 π (\frac{n k}{N} - \frac{m l}{M})}

.(1)

After that, the signals $X_{t f} [m, n]$ in the TF domain are converted to a continuous-time waveform $s (t)$ using the Heisenberg transform with a transmit waveform $g_{t x} (t)$ ^[2], i.e.,

s (t) = \sum_{n = 0}^{N - 1} \sum_{m = 0}^{M - 1} X_{t f} [n, m] g_{t x} (t - n T) e^{j 2 π m Δ f (t - n T)}

,(2)

where $Δ f$ is subcarrier spacing and $T = 1 / Δ f$ . Then the signal $s (t)$ is transmitted over a time-varying channel and the received signal in the time domain is given as:

r (t) = \int \int h (τ, ν) s (t - τ) e^{j 2 π ν (t - τ)} d τ d ν

,(3)

where $h (τ, ν)$ is the channel impulse response in the continuous DD domain, and it can be expressed as^[1]:

h (τ, ν) = \sum_{i = 0}^{P - 1} h_{i} δ (τ - τ_{i}) δ (ν - ν_{i})

,(4)

with $δ (\cdot)$ being the Dirac delta function, $P$ being the number of channel paths, and $h_{i}$ , $τ_{i}$ and $ν_{i}$ being the gain, delay and Doppler shift associated with the i-th path, respectively. The delay and Doppler-shift taps for the i-th path are given by

τ_{i} = \frac{l_{i}}{M Δ f}

ν_{i} = \frac{k_{i} + κ_{i}}{N T}

,(5)

where $l_{i}$ and $k_{i}$ are the delay and Doppler indices of the i-th path, and $κ_{i} \in [- 1 / 2, 1 / 2]$ is a fractional Doppler associated with the i-th path. In the above equation, $M Δ f$ is the system bandwidth and $N T$ is the duration of an OTFS block.

At the receiver, a receive waveform $g_{r x} (t)$ is used to transform the received signal $r (t)$ to the TF domain, i.e.,

Y (t, f) = \int g_{r x}^{*} (t^{'} - t) r (t^{'}) e^{- j 2 π f (t^{'} - t)} d t^{'}

,(6)

which is then sampled at $t = n T$ and $f = m Δ f$ , yielding $Y [n, m]$ . Then SFFT is applied to $Y [n, m]$ to generate the DD domain signal $y [k, l]$ , i.e.,

y [k, l] = \frac{1}{\sqrt[]{M N}} \sum_{n = 0}^{N - 1} \sum_{m = 0}^{M - 1} Y [n, m] e^{- j 2 π (\frac{n k}{N} - \frac{m l}{M})}

.(7)

Assuming that the transmitted waveform and the received waveform satisfy the bi-orthogonal property^[1], in the DD domain we have the input-output relationship^[2].

y [k, l] = \sum_{i = 0}^{P - 1} \sum_{c = - N_{i}}^{N_{i}} h_{i} x ([k - k_{i} {+ c]}_{N}, [l - l_{i}]_{M}) \frac{1}{N} \frac{1 - e^{- j 2 π (- c - κ_{i})}}{1 - e^{- j 2 π \frac{- c - κ_{i}}{N}}} e^{- j 2 π \frac{l_{i} (k_{i} + κ_{i})}{M N}} + ω [k, l]

,(8)

where $N_{i} < N$ is an integer, and $ω [k, l]$ is the noise in the DD domain. We can see that for each path, the transmitted signal is circularly shifted, and scaled by a corresponding channel gain. We arrange { $x [k, l]$ } as a vector $x \in C^{M N \times 1}$ , where the j-th element $x_{j}$ is $x [k, l]$ with $j = k M + l$ . Similarly, a vector $y \in C^{M N \times 1}$ can also be constructed based on $y [k, l]$ . Then Eq. (8) can be rewritten in a vector form as:

y = H x + ω

,(9)

where $H \in C^{M N \times M N}$ is the effective channel matrix in the DD domain, and $ω$ denotes a white Gaussian noise with mean 0 and variance $ϵ^{- 1}$ (or precision $ϵ$ ). The channel matrix $H$ in Eq. (9) can be represented as^[25]:

H = \sum_{i = 0}^{P - 1} \sum_{c = - N_{i}}^{N_{i}} I_{N} (- [c - k_{i}]_{N}) \otimes [I_{M} (l_{i}) h_{i} \times \frac{1 - e^{- j 2 π (- c - κ_{i})}}{N - N e^{- j 2 π \frac{- c - κ_{i}}{N}}} e^{- j 2 π \frac{l_{i} (k_{i} + κ_{i})}{M N}}]

,(10)

where $I_{N} (- [q - k_{i}]_{N})$ denotes an $N \times N$ matrix obtained by circularly shifting the rows of the identity matrix by $- [q - k_{i}]_{N}$ , and $I_{M} (l_{i})$ is obtained similarly. Without fractional Doppler, i.e., $κ_{i} = 0$ , the channel matrix $H$ is reduced to

H = \sum_{i = 0}^{P - 1} I_{N} (k_{i}) \otimes [I_{M} (l_{i}) h_{i} e^{- j 2 π \frac{l_{i} k_{i}}{M N}}]

.(11)

3 Message Passing (MP) Based Detectors

Based on the model (9) in the DD domain, several detectors have been proposed using the message passing techniques.

3.1 MP Detector in Ref. [2]

In model (9), the $M N \times M N$ DD domain complex channel matrix $H$ is sparse (especially in the case without fractional Doppler shifts), which makes belief propagation suitable for implementing the OTFS detectors. In Eq. (2), $y$ and $ω$ are length-MN complex vectors with elements denoted by $y [d]$ and $ω [d]$ , $1 \leq d \leq M N$ , the element of $H$ is denoted by $H [d, c]$ , $1 \leq d, c \leq M N$ , $x$ is a length-MN symbol vector with elements $x [c] \in A$ , $1 \leq c \leq M N$ , and $𝒜$ denotes the modulation alphabet.

Thanks to the sparsity of $H$ , the joint distribution of the random variables in model (9) can be represented with a sparsely-connected factor graph with $M N$ variable nodes corresponding to $x$ and $M N$ observation nodes corresponding to $y$ . As shown in Fig. 2, each observation node $y [d]$ is connected to a set of variable nodes ${x [e_{s}], e_{s} \in ℐ (d)}$ , and similarly, each variable node $x [c]$ is connected to a set of observation nodes $y [e_{s}], e_{s} \in 𝒥 [c]$ , where $ℐ (d)$ and $𝒥 (c)$ respectively denote the sets of indexes of non-zero elements in the d-th row and c-th columns of $H$ , $|ℐ (d)| = |𝒥 (c)| = S$ and $1 \leq s \leq S$ . The probability mass function (PMF) $p_{c, e_{s}} = {p_{c, e_{s}} (a_{j}) | a_{j} \in A}$ represents the messages from variable nodes $x [c]$ to factor nodes $y [e_{s}]$ .

Figure 2

Figure 2 Graph representation used to derive the message passing (MP) detector in Ref. [2]

Based on the factor graph in Fig. 2, a message passing algorithm was proposed in Ref. [2], and the detector is called MP detector in this paper. The following is a brief derivation of the message computations in the i-th iteration of the message computations.

1) Messages passing from observation node $y [d]$ to variable node $x [e_{s}]$

The message is approximated to be Gaussian, and the mean $μ_{d, e_{s}}^{i}$ and variance $(σ_{d, e_{s}}^{i})^{2}$ are computed as

μ_{d, e_{s}}^{i} = \sum_{e \in 𝒥_{d}, e \neq e_{s}} \sum_{j = 1}^{Q} p_{e, d}^{i - 1} (a_{j}) a_{j} H [d, e]

,(12)

(σ_{d, e_{s}}^{i})^{2} = \sum_{e \in 𝒥_{d}, e \neq e_{s}} (\sum_{j = 1}^{Q} p_{e, d}^{i - 1} (a_{j}) | a_{j} |^{2} | H [d, e] |^{2} - {|\sum_{j = 1}^{Q} p_{e, d}^{i - 1} (a_{j}) a_{j} H [d, e]|}^{2}) + ϵ^{- 1}

.(13)

2) Messages passing from variable node $x [c]$ to observation node $y [e_{s}]$

The PMF $p_{c, d}^{i}$ can be updated as

p_{c, e_{s}}^{i} (a_{j}) = Δ \cdot {\tilde{p}}_{c, e_{s}}^{i} (a_{j}) + (1 - Δ) \cdot {\tilde{p}}_{c, e_{s}}^{i - 1} (a_{j})

,(14)

where $Δ \in [0,1]$ is the damping factor and

{\tilde{p}}_{c, e_{s}}^{i} (a_{j}) \propto \prod_{e \in 𝒥 (c), e \neq e_{s}} P r (y [e] | x [c] = a_{j}, H) = \prod_{e \in 𝒥 (c), e \neq e_{s}} \frac{ς^{i} (e, c, j)}{\sum_{k = 1}^{Q} ς^{i} (e, c, j)}

,(15)

with

ς^{i} (e, c, k) = e x p (\frac{- {|y [e] - μ_{e, c}^{i} - H [e, c] a_{k}|}^{2}}{(σ_{e, c}^{i})^{2}})

.(16)

After a certain number of iterations by repeating 1) and 2), the decision on the transmitted symbol can be obtained, i.e.,

\hat{x} [c] = a r g m i n_{a_{j} \in A} p_{c}^{i} (a_{j}), c = 1, . . ., M N

,(17)

where

p_{c}^{i} (a_{j}) = \prod_{e \in 𝒥 (c)} \frac{ς^{i} (e, c, j)}{\sum_{k = 1}^{Q} ς^{i} (e, c, j)}

.(18)

The MP detector is summarized in Algorithm 1.

Algorithm 1. MPA detector in Ref. [2]

Input: $y$ , $H$ , Initialize: $p_{c, e_{s}}^{0} = 1 / | A | |$ , $c = 1, . . ., M N$ , $e_{s} \in 𝒥 (c)$ , $i = 1$

1: Repeat

2: $\forall d :$ update $μ_{d, e_{s}}^{i}$ and $(σ_{d, e_{s}}^{i})^{2}$ with Eqs. (12) and (13)

3: $\forall c :$ update ${p_{c, d}}^{i}$ with Eq. (14)

4: $i = i + 1$

5: Until terminate

Output: The decision on transmitted symbols $\hat{x} [c]$ using Eq. (17)

The MP algorithm shown above is an approximation to loopy belief propagation since it approximates the interference to be Gaussian to achieve lower complexity. The complexity of the algorithm is $𝒪 (M N S | 𝒜 |)$ per iteration, which depends on the sparsity of the channel, i.e., the value of S. When S is small, the detector is very attractive because it has low complexity and the detector delivers a good performance as no short loops in the factor graph model. However, in the case of rich-scatting environments and fractional Doppler shifts, the value of S can be large, leading to a denser factor graph model, which can affect the performance of the MP detector and result in a significant increase in computational complexity.

3.2 VB Detector

The VB detector was proposed in Ref. [17] to guarantee the convergence of the iterative detector, which can be implemented with variational message passing. With model (9), the optimal MAP detection can be formulated as:

\hat{x} = a r g m a x_{x} p (x | y)

.(19)

However, the complexity of solving the above optimization problem increases exponentially with the size of $x$ . VB is adopted to achieve low complexity approximate detection. In this method, a distribution $q (x)$ from a tractable distribution family $𝒬$ is found as an approximation to the a posteriori distribution $p (x | y)$ . The trial distribution $q (x)$ can be obtained by minimizing the Kullback-Leibler divergence $𝒟 (q | | p)$ , i.e.,

q^{*} (x) = \underset{q \in 𝒬}{a r g m a x} 𝒟 (q | | p) = \underset{q \in 𝒬}{a r g m a x} \underset{ℒ}{\underset{︸}{𝔼_{q} [- l n q (x) + l n p (x | y)]}}

,(20)

where the expectation is taken over $x$ according to the trial distribution $q (x)$ .

To simplify the optimization problem, q(x) is assumed to be fully factorized, i.e.,

q (x) = \prod_{k, l} q_{k, l} (x_{k, l})

,(21)

where $k \in [0, N - 1]$ , $M \in [0, M - 1]$ and $x_{k, l}$ denotes the $(k M + l)$ -th entry of $x$ . With this assumption, $q (x)$ can be updated iteratively by maximizing $ℒ$ . Since the noise sample $ω_{k, l}$ and data symbol $x_{k, l}$ , $\forall k, l$ are independent, and $ω_{k, l} ~ 𝒞 𝒩 (ω_{k, l}; 0, ϵ^{- 1})$ , $p (x | y)$ can be rewritten as:

p (x | y) \propto \prod_{k, l} p (x_{k, l}) p (y_{k, l} | y)

,(22)

where $y_{k, l} = h_{k, l}^{T} x + ω_{k, l}$ , $h_{k, l}$ denotes the equivalent channel vector whose $(k M + l)$ -th entry is $h_{k, l} [k, l]$ . Then the distribution $p (x | y)$ can be further rewritten as:

p (x | y) \propto \prod_{k, l} ζ_{k, l} (x_{k, l}) \prod_{k^{'}, l^{'}} ψ_{k, l} (x_{k, l}, x_{k^{'}, l^{'}})

,(23)

where

ζ_{k, l} (x_{k, l}) = p (x_{k, l}) e x p (- \frac{ρ_{k, l} | x_{k, l} |^{2} + η_{k, l} x_{k, l}}{ϵ^{- 2}})

,(24)

ψ_{k, l} (x_{k, l}, x_{k^{'}, l^{'}}) = e x p (- \frac{ϱ_{k, l, k^{'}, l^{'}} x_{k, l} x_{k^{'}, l^{'}}}{ϵ^{- 2}})

,(25)

with $ρ_{k, l} = \sum_{k^{'}, l^{'}} | h_{k^{'}, l^{'}} (k, l) |^{2}$ , $η_{k, l} = 2 \sum_{k^{'}, l^{'}} R [h_{k^{'}, l^{'}} [k, l] \cdot y_{k, l^{'}}]$ , and $ϱ_{k, l, k^{'}, l^{'}} = 2 ℛ [h_{k, l} [k, l] h_{k, l}^{*} [k^{'}, l^{'}]]$ . Substituting $p (x | y)$ in Eq. (23) and $q (x)$ into $ℒ$ yields

\begin{array}{l} ℒ = 𝔼_{q} [\sum_{k, l} l n ψ_{k, l} (x_{k, l}, x_{k^{'}, l^{'}}) - \sum_{k, l} l n \frac{q_{k, l} (x_{k, l})}{ζ_{k, l} (x_{k, l})}] = \\ 𝔼_{q} [- \frac{\sum_{k, l} ϱ_{k, l, k^{'}, l^{'}} x_{k, l} x_{k^{'}, l^{'}}}{ϵ^{- 2}} - \sum_{k, l} l n \frac{q_{k, l} (x_{k, l})}{ζ_{k, l} (x_{k, l})}] \end{array}

.(26)

To find a stationary point of $ℒ$ , the partial derivations of $ℒ$ with respect to all local functions $q_{k, l} (x_{k, l})$ , $\forall k, l$ need to be zero. Take the latent variable $x_{k, l}$ as an example. Setting the partial derivation $\partial ℒ / \partial q_{k, l} (x_{k, l})$ to zero leads to:

𝔼_{q \ k, l} [- \frac{\sum_{k^{'}, l^{'}} ϱ_{k, l, k^{'}, l^{'}} x_{k, l} x_{k^{'}, l^{'}}}{ϵ^{- 2}}] + l n ζ_{k, l} (x_{k, l}) - l n q_{k, l}^{i t e r} (x_{k, l}) + C = 0

,(27)

where $q_{k, l} = \prod_{(k^{'}, l^{'}) \neq (k, l)} q_{k^{'}, l^{'}}^{i t e r - 1} (x_{k, l})$ , $q_{k^{'}, l^{'}}^{i t e r - 1} (x_{k, l})$ is obtained in the $(i t e r - 1)$ -th iteration and $C$ denotes a constant.

Then, solving Eq. (27) for $q_{k, l} (x_{k, l})$ results in the local distribution, which can be expressed as:

q_{k, l}^{i t e r} (x_{k, l}) \propto ζ_{k . l} (x_{k, l}) e x p (𝔼_{q \ k, l} [- \frac{\sum_{k^{'}, l^{'}} ϱ_{k, l, k^{'}, l^{'}} x_{k, l} x_{k^{'}, l^{'}}}{ϵ^{- 2}}]) \propto p (x_{k, l}) e x p (- \frac{ρ_{k, l} | x_{k, l} |^{2} - m_{k, l} d_{k, l}}{ϵ^{- 2}})

,(28)

where $m_{k, l} = η_{k, l} - \sum_{(k^{'}, l^{'}) \neq (k, l)} ϱ_{k, l, k^{'}, l^{'}} 𝔼_{q_{k^{'}, l^{'}}^{i t e r - 1}} x [k^{'}, l^{'}]$ .

It is noted that the variance of $x_{k, l}$ is underestimated and only the noise variance is considered in Eq. (28). To fix the underestimation, a practical solution is to repeat the above procedure to approximate the a posteriori distribution for all the data symbols iteratively, resulting in the approximate marginal $q_{k, l}^{*} (x_{k, l})$ , $\forall k, l$ . Then, the decision on the symbols can be made by maximizing the approximate marginal distribution $q_{k, l}^{*} (x_{k, l})$ , i.e.,

{\hat{x}}_{k, l} = \underset{x_{k, l} \in A}{a r g m a x} q_{k, l}^{*} (x_{k, l})

.(29)

The complexity of the algorithm per iteration is $𝒪 (M N S | 𝒜 |)$ .

3.3 UAMP Detector

Leveraging the UAMP algorithm, the UAMP detector was developed in Ref.[25], where the BCCB structure of the DD domain channel matrix is exploited, leading to a highly efficient OTFS detector with 2D FFT. It can be seen from Eqs. (10) and (11) that the DD domain channel matrix $H$ has a BCCB structure. A useful property of the BCCB matrix $H$ is that it can be diagonalized using 2D Discrete Fourier Transform matrix, i.e.,

H = F^{H} Λ F

,(30)

where $F = F_{N} \otimes F_{M}$ with $F_{N}$ and $F_{M}$ being respectively the normalized $N$ -point and $M$ -point DFT matrices. In Eq. (30), matrix $Λ$ is a diagonal matrix, i.e., $Λ = d i a g (d)$ , and $d$ is a length- $M N$ vector that can be computed using 2D FFT.

d = v e c (F F T 2 (C))

,(31)

where $F F T 2 (\cdot)$ represents the 2D FFT operation, $C = r e s h a p e_{M} (H (:, 1))$ is an $M \times N$ matrix, and $H (:, 1)$ with length- $M N$ is the first column of matrix $H$ .

The above property is exploited in the design of the UAMP detector, leading to high computational efficiency while with outstanding performance compared with the existing detectors. Instead of using model (9) directly, the UAMP algorithm^[27–29] works with the unitary transform of the model. The channel matrix $H$ admits the diagonalization in Eq. (30), leading to the following unitary transform of the OTFS system model:

r = Λ F x + ω'

,(32)

where $r = F y$ , $ω' = F ω$ , and the noise $ω'$ has the same distribution with $ω$ as $F$ is an unitary matrix. The precision of the noise is still denoted by $ϵ$ , which needs to be estimated. Define $Φ = Λ F$ and an auxiliary vector $z = Φ x$ . Then we can factorize the joint distribution of the unknown variables $x, z, ϵ$ given $r$ as

\begin{array}{l} p (x, z, ϵ | r) = p (ϵ) p (r | z, ϵ) p (z | x) p (x) = \\ p (ϵ) \prod_{j} p (r_{j} | z_{j}, ϵ) p (z_{j} | x) \prod_{i} p (x_{i}) = \\ f_{ϵ} \prod_{j} f_{r_{j}} (z_{j}, ϵ) f_{δ_{j}} (z_{j}, x) \prod_{i} f_{x_{i}} (x_{i}) \end{array}

,(33)

where indices $i, j \in [1 : M N]$ . To facilitate the factor graph representation of the factorization in Eq. (33), the relevant notations are listed in Table 1, which shows the correspondence between the factor nodes and their associated distributions. The factor graph representation for the factorization in Eq. (33) is depicted in Fig. 3.

Table 1 Factors, underlying distributions and functional forms associated with Eq. (31)

Factor	Distribution	Function Form
$f_{r_{j}}$	$p (r_{j} \| z_{j}, ϵ)$	$N (z_{j}; r_{j}, ϵ^{- 1})$
$f_{δ_{j}}$	$p (z_{j} \| x)$	$δ (z_{j} - Φ_{j} x)$
$f_{x_{i}}$	$p (x_{i})$	$(1 / \| A \|) \sum_{a = 1}^{A} δ (x_{i} - α_{a})$
$f_{ϵ}$	$p (ϵ)$	$ϵ^{- 1}$

New window| CSV

Figure 3

Figure 3 Factor graph representation of Eq. (31)

Following the UAMP algorithm, a UAMP based iterative detector can be designed, which is summarized in Algorithm 2. According to the derivation of (U)AMP using loopy belief propagation, UAMP provides the message from variable node $z_{j}$ to function node $f_{r_{j}}$ , which is Gaussian and denoted by $m_{z_{j} \to f_{r_{j}}} (z_{j}) = 𝒩 (z_{j} | p_{j}, ν_{p_{j}})$ . Here, the mean $p_{j}$ and the variance $ν_{p_{j}}$ are given in Lines 1 and 2 of the Algorithm in a vector form. With the mean field rule^[23] at the function node $f_{r_{j}}$ , we can compute the message passed from function node $f_{r_{j}}$ to variable node $ϵ$ , i.e.,

m_{f_{r_{j}} \to ϵ} (ϵ) \propto e x p \{{〈l o g f_{r_{j}} (r_{j} | z_{j}, ϵ)〉}_{b (z_{j})}\} \propto ϵ e x p \{- ϵ (| r_{j} - {\hat{z}}_{j} |^{2} + v_{z_{j}})\}

,(34)

where $b (z_{j})$ is the belief of $z_{j}$ . It turns out that $b (z_{j})$ is also Gaussian with its variance and mean given by

ν_{z_{j}} = 1 / (1 / ν_{p_{j}} + \hat{ϵ})

\hat{z} = ν_{z_{j}} (p_{j} / ν_{p_{j}} + \hat{ϵ} r_{j})

,(35)

respectively, where $\hat{ϵ}$ is the estimate of $ϵ$ in the last iteration. They can be expressed in a vector form shown in Lines 3 and 4 in Algorithm 2. The estimate of $ϵ$ can be obtained based on the belief $b (ϵ)$ at the variable node $ϵ$ shown in Fig. 3, i.e.,

b (ϵ) \propto f_{ϵ} (ϵ) \prod_{j = 1}^{M N} m_{f_{r_{j}} \to ϵ} (ϵ)

.(36)

And the estimate is given as

\hat{ϵ} = \int_{0}^{\infty} ϵ b (ϵ) d ϵ = M N / \sum_{j = 1}^{M N} (| r_{j} - {\hat{z}}_{j} |^{2} + ν_{z_{j}})

,(37)

which can be rewritten in a vector form shown in Line 5 of the algorithm. With the mean field rule at the function node $f_{r_{j}}$ again, the message passed from the function node $f_{r_{j}}$ to the variable node $z_{j}$ can be computed as:

m_{f_{r_{j}} \to z_{j}} (z_{j}) \propto e x p \{{〈l o g f_{r_{j}} (r_{j} | z_{j}, \hat{ϵ})〉}_{b (ϵ)}\} \propto 𝒩 (h_{j} | r_{j}, {\hat{ϵ}}^{- 1})

.(38)

Then the UAMP algorithm with known noise can be used as if the true noise precision is $\hat{ϵ}$ , leading to Lines 6–15 and Lines 1–2 of the Algorithm 2. In Lines 10–13, the Gaussian message is combined with the discrete prior to obtain the MMSE estimates of the symbols in terms of their posterior means and variances. There is an extra operation in Line 14, which averages the variances of $x_{j}$ . Thanks to the special form of the unitary matrix $F$ , 2D FFT is used in the implementations in Lines 2 and 9. It can be seen that the UAMP detector does not require any matrix-vector products, the algorithm requires only element-wise vector operations or scalar operations, except Lines 2 and 9, which are implemented with FFT. So the complexity of the UAMP detector is $𝒪 (M N l o g (M N)) + 𝒪 (M N | 𝒜 |)$ per OTFS block per iteration, which is independent of $S$ .

Algorithm 2. UAMP detector for OTFS

Unitary transform: $r = F y = Λ F x + ω$ with $F = F_{N} \otimes F_{M}$ . Calculated $d$ with Eq. (29), and define vector $Λ = d \cdot d^{*}$ .

Initialize $s^{- 1} = 0$ , $\hat{x} = 0$ , ${\hat{ϵ}}^{(0)} = 1$ , $ν_{x}^{(0)} = 1$ , and $t = 0$ .

Input: $y$ , $H$

Repeat

1: $ν_{p} = ν_{x}^{t} Λ$

2: $p = d \cdot v e c (F F T 2 (r e s h a p e_{M} ({\hat{x}}^{t}))) - ν_{p} \cdot s^{t - 1}$

3: $ν_{z} = 1 . / (1 . / ν_{p} + {\hat{ϵ}}^{t})$

4: $z = ν_{z} \cdot (p . / ν_{p} + {\hat{ϵ}}^{t} r)$

5: ${\hat{ϵ}}^{t + 1} = M N / ({‖r - z‖}_{2}^{2} + 1^{T} ν_{z})$

6: $ν_{s} = 1 . / (ν_{p} + 1 / ϵ^{t + 1} 1)$

7: $s^{t} = ν_{s} \cdot (r - \hat{p})$

8: $ν_{q} = Λ^{T} ν_{s} / (M N)$

9: $q = {\hat{x}}^{(t)} + ν_{q} v e c (I F F T 2 (r e s h a p e_{M} (d \cdot s^{t})))$

10: $\forall j : ξ_{j, a} = e x p (- ν_{q}^{- 1} | α_{a} - q_{j} |^{2})$

11: $\forall j : β_{j, a} = ξ_{j, a} / \sum_{a = 1}^{| A |} ξ_{j, a}$

12: $\forall j : {\hat{x}}_{j}^{t + 1} = \sum_{a = 1}^{| A |} α_{a} β_{j, a}$

13: $\forall j : ν_{x_{j}}^{t + 1} = \sum_{a = 1}^{| A |} β_{j, a} | α_{a} - {\hat{x}}_{j}^{t + 1} |^{2}$

14: $ν_{x}^{t + 1} = \frac{1}{M N} \sum_{j = 1}^{M N} ν_{x_{j}}^{t + 1}$

15: $t = t + 1$

Until terminated

Output: the estimate of $x$ i.e., $\hat{x}$

Compared with the UAMP detector, the MP and VB detectors have a complexity of $𝒪 (M N S | 𝒜 |)$ per OTFS block per iteration, which can be considerably higher than that of the UAMP detector in the case of rich scattering environments and when fractional Doppler shifts have to be considered (leading to a large $S$ ). Moreover, the UAMP detector can deliver much better performance when the number of paths is relatively large. In particular, the UAMP detector with estimated noise precision can significantly outperform other detectors with perfect noise precision. We note that, the OTFS detector can be implemented directly with the AMP algorithm. However, due to the deviation of the channel matrix from the i.i.d. Gaussian matrix, the AMP detector may perform poorly.

4 Turbo Processing in Coded Systems

It is well known that joint decoding and detection can bring significant system performance improvement, and it can be realized in a way that the detector and decoder exchange information iteratively, i.e., the turbo processing^[30–31]. The OTFS detectors can be incorporated into a turbo receiver by endowing the OTFS detectors with the capabilities of taking the output log-likelihood ratios (LLRs) of the decoder as (soft) input and producing (soft) output in the form of extrinsic LLRs of the coded bits, i.e., the so-called soft input soft output (SISO) detector.

A typical turbo system is shown in Fig. 4, where $Π$ and $Π^{- 1}$ represent interleaver and de-interleaver, respectively. The information bits are encoded and interleaved before symbol mapping, where each symbol $x_{j} \in A = {α_{1}, . . ., α_{| A |}}$ in the DD domain is mapped from a sub-sequence of the coded bit sequence, which is denoted by $c_{j} = [c_{j}^{1}, . . ., c_{j}^{l o g | A |}]$ . Each $α_{a}$ corresponds to a length- $𝒜 l o g | 𝒜 |$ binary sequence, which is denoted by $\{α_{a}^{1}, . . ., α_{a}^{l o g | A |}\}$ . Based on the LLRs provided by the SISO decoder and the output of the OTFS demodulator as shown in Fig. 4, the task of the SISO OTFS detector is to compute the extrinsic LLR for each coded bit, i.e.,

L^{e} (c_{j}^{q}) = l n \frac{P (c_{j}^{q} = 0 | r)}{P (c_{j}^{q} = 1 | r)} - L^{a} (c_{j}^{q})

,(39)

Figure 4

Figure 4 Iterative joint detection and decoding in a coded OTFS system^[25]

where $L^{a} (c_{j}^{q})$ is the output extrinsic LLR of the decoder in the last iteration. The extrinsic LLR $L^{e} (c_{j}^{q})$ is passed to the decoder. The extrinsic LLR $L^{e} (c_{j}^{q})$ can be expressed in terms of extrinsic mean and variance of the symbols^[32], i.e.,

L^{e} (c_{j}^{q}) = l n \frac{\sum_{α_{a} \in A_{q}^{0}} e x p (- \frac{| α_{a} - m_{j}^{e} |^{2}}{v_{j}^{e}}) \prod_{q^{'} \neq q} P (c_{j}^{q^{'}} = α_{a}^{q^{'}})}{\sum_{α_{a} \in A_{q}^{1}} e x p (- \frac{| α_{a} - m_{j}^{e} |^{2}}{v_{j}^{e}}) \prod_{q^{'} \neq q} P (c_{j}^{q^{'}} = α_{a}^{q^{'}})}

,(40)

where $m_{j}^{e}$ and $v_{j}^{e}$ are the extrinsic mean and variance of $x_{j}$ , and $𝒜_{q}^{0}$ and $𝒜_{q}^{0}$ represent the subsets of all $α_{a}$ corresponding to $c_{j}^{q} = 0$ and $c_{j}^{q} = 1$ , respectively. The extrinsic variance and mean are defined in Ref. [32].

v_{j}^{e} = (1 / v_{j}^{p} - 1 / v_{j})^{- 1}, m_{j}^{e} = v_{j}^{e} (m_{j}^{p} / v_{j}^{p} - m_{j} / v_{j})

,(41)

where $m_{j}$ and $v_{j}$ are the a priori mean and variance of $x_{j}$ calculated based on the output LLRs of the SISO decoder^[30]and $m_{j}^{p}$ and $v_{j}^{p}$ are a posteriori mean and variance of $x_{j}$ .

Taking the UAMP detector as an example, we show the incorporation of the OTFS detector into a turbo receiver. According to the derivation of the UAMP algorithm, we can find that $q$ and $ν_{q}$ consist of the extrinsic means and variances of the symbols in $x$ as they are the messages passed from the observation side and do not contain the immediate a priori information about $x$ . Hence we have $m_{j}^{e} = q_{j}$ and $v_{j}^{e} = ν_{q}$ . Then Eq. (40) can be readily used to compute the extrinsic LLRs of the coded bits. With the LLRs provided by the SISO decoder, one can compute the probability $p (x_{j} = α_{a})$ for each $x_{j}$ , which is no longer the “non-informative prior ” in Algorithm 2. Therefore, $ξ_{j, a}$ in Line 7 of the algorithm is changed to

ξ_{j, a} = p (x_{j} = α_{a}) e x p (- ν_{q}^{- 1} | α_{a} - q_{j} |^{2})

.(42)

In addition, the iteration of the UAMP detector can be combined with the iteration between the SISO decoder and detector, which leads to a single loop iteration (i.e., inner iterations are not required).

The computational complexity of the detectors is summarized in Table 2. In the above discussion, we focus on the bi-orthogonal waveform. The detectors can be extended to OTFS systems with other waveforms, such as the simple rectangular waveform^[25].

Table 2 Computational complexity of various detectors per iteration

Detectors	Complexity
MP detector	$O (M N S \| A \|)$
VB detector	$O (M N S \| A \|)$
UAMP detector	$O (M N l o g (M N)) + O (M N \| A \|)$

MP: message passing UAMP: unitary approximate message passing

VB: variational Bayes

New window| CSV

5 Simulation Results

In this section, we compare the performance of the message passing based detectors. The low complexity MRC detector in Ref. [14] is also included. We set $M = 256$ and $N = 32$ , i.e., there are $32$ time slots and $256$ subcarriers in the TF domain. Both quadrature phase shift keying (QPSK) modulation and 16-quadrature amplitude modulation (QAM) are considered. The carrier frequency is 3 GHz, and the subcarrier spacing is 2 kHz. The speed of the mobile user is set to $v = 135 k m / h$ , leading to a maximum Doppler frequency shift index $k_{m a x} = 6$ . We assume that the maximum delay index is $l_{m a x}$ =14. The Doppler index of the i-th path is uniformly drawn from the set $[- k_{m a x}, k_{m a x}]$ and the delay index is in the range of $[1, l_{m a x}]$ excluding the first path ( $l_{1} = 0$ ). We assume that the fractional Doppler $κ_{i}$ is uniformly distributed within $[- 1 / 2,1 / 2]$ , and the channel coefficients $h_{i}$ are independently drawn from a complex Gaussian distribution with mean 0 and variance $η^{l_{i}}$ , where the normalized power delay profile $η^{i} = e x p (- α l_{i}) / \sum_{i} e x p (- α l_{i})$ with $α$ being 0 or 0.1. The maximum number of iterations is set to 15 for all iterative detectors. We note that, all detectors except the MRC detector require the noise variance. The UAMP detector performs noise precision estimation, while the other detectors (except the MRC detector) including the AMP detector assume perfect noise precision. We evaluate the performance of the detectors in a variety of scenarios including the bi-orthogonal and rectangular waveforms with integer or fractional Doppler shifts, and QPSK or 16-QAM for modulations. In addition, both uncoded and coded systems are evaluated.

Fig. 5 shows the BER performance of various detectors in the case of the bi-orthogonal waveform with different numbers of paths, where we assume no fractional Doppler shifts, i.e., $S = P$ . We also assume $α = 0$ , and QPSK is used. From this figure, we can see that, the MP detector performs well when $P = 6$ , but with the increase of $P$ , its performance becomes worse. The VB detector has a similar trend. The MRC detector performs similarly to the MP and VB detectors when P=6 and delivers better performance than the MP and VB detectors with larger P. The AMP and UAMP detectors perform well, where we can see that they enjoy the diversity gain and achieve better performance with the increase of $P$ . In all cases, the UAMP based detector delivers the best performance and significantly outperforms other detectors.

Figure 5

Figure 5 BER performance of detectors with bi-orthogonal waveform and integer Doppler shifts (results are based on Ref. [25])

With the rectangular waveform and factional Doppler shifts, we compare the bit error ratio (BER) performance of the AMP, UAMP and MRC detectors in Fig. 6, where the number of paths $P = 9$ and $α = 0.1$ is used for the power delay profile. Both QPSK and 16-QAM are considered. Due to the deviation of the channel matrix from the i.i.d. (sub-) Gaussian matrix, AMP exhibits performance loss, leading to significantly worse performance compared with the UAMP detector. Thanks to the robustness of UAMP against a general matrix, UAMP performs well. We can see that the MRC detector performs better than the AMP detector. The UAMP detector performs the best and the gaps between other detectors with the UAMP detector become larger in the case of higher order modulation 16-QAM, compared with QPSK.

Figure 6

Figure 6 BER performance of detectors with the rectangular waveform and fractional Doppler shifts (results are based on Ref. [25])

We then evaluate the performance of the detectors in a coded OTFS system, where the turbo receiver in Fig. 4 is employed. The number of paths P=14, and a rectangular waveform is used. In Fig. 7(a), we show the performance of the uncoded system with the AMP and UAMP detectors. In Fig. 7(b), we use a rate-1/2 convolutional code with a generator ${[5,7]}_{8}$ followed by a random interleaver and QPSK modulation. The length of the codeword is $M N$ . The BCJR algorithm is used for the SISO decoder. We can find that the performance gaps between the AMP detector and the UAMP detector become larger in the coded system. The turbo receiver can achieve much better performance (about $3.5 - 4$ dB at the BER of $10^{- 4}$ ) thanks to the joint processing of decoding and detection. In Fig. 7(c), we investigate the performance of the system with a more powerful LDPC. The 8 192 information bits are coded at rate R=1/2 by an irregular LDPC code with an average column weight of 3, then the coded bits are randomly interleaved and mapped. As expected, the system performance is improved considerably when the LDPC is used. From Fig. 7(c), we can see that the use of the LDPC code can improve the performance of the UAMP based detector significantly and the performance gap between AMP and UAMP increases when the LDPC is used.

Figure 7

Figure 7 BER performance comparison of coded and uncoded system with rectangular waveform (part of the results is based on Ref. [25])

6 Conclusions and Potential Future Work

In this paper, we review and compare the recently proposed message passing based OTFS detectors, which exploit the structures of the OTFS channel matrices, such as sparsity and BCCB. According to the results, the MP and VB detectors are more suitable in the scenarios that the number of paths is relatively small and the modulation order is low, where they deliver good performance while with relatively low complexity. The UAMP detector seems very promising especially in the case of rich-scattering environments and/or when fractional Doppler shifts have to be considered, where the UAMP detector is attractive in both computational complexity and performance. The results also show that the OTFS system with a turbo receiver can provide significant performance gain.

The message passing techniques seem promising in the design of OTFS receivers. In this paper, we assume the OTFS channel matrix is known, which however has to be estimated for practical applications. Message passing based OTFS channel estimation has been investigated in the literature, such as the work in Ref. [33]. With the message passing techniques, channel estimation and detection can be integrated for joint channel estimation and detection, which is expected to lead to superior system performance and/or significant reduction of the training overhead. This is because the data symbols can be used to serve as a virtual training sequence and the guard band between the training symbols and data symbols is not necessary.

It has been shown that joint decoding and detection based on a turbo receiver can significantly improve the system performance. The system performance can be potentially further improved by optimizing the error control codes. This requires fast and accurate performance prediction of the iterative receiver, so that the error control codes, e.g., LDPC, can be optimized.

The message passing techniques could be used to implement sophisticated receivers in more complex systems, such as multi-user OTFS systems, grant-free multiple access with OTFS, multiple-output-multiple-input (MIMO)-OTFS, integrated sensing and communication with OTFS.

Reference

By original order

By published year

By cited within times

By Impact factor

[1]

HADANI

, RAKIB

, TSATSANIS

, et al.

Orthogonal time frequency space modulation

[C]//2017 IEEE Wireless Communications and Networking Conference (WCNC). San Francisco, USA: IEEE, 2017: 1–6. DOI: 10.1109/WCNC.2017.7925924

[Cited within: 5]

[2]

RAVITEJA

, PHAN

K T

, HONG

, et al.

Interference cancellation and iterative detection for orthogonal time frequency space modulation

[J]. IEEE transactions on wireless communications, 2018, 17(10): 6501–6515. DOI: 10.1109/TWC.2018.2860011

[Cited within: 11]

[3]

SURABHI

G D

, AUGUSTINE

R M

, CHOCKALINGAM

On the diversity of uncoded OTFS modulation in doubly-dispersive channels

[J]. IEEE transactions on wireless communications, 2019, 18(6): 3049–3063. DOI:10.1109/TWC.2019.2909205

[4]

HADANI

, MONK

OTFS: A new generation of modulation addressing the challenges of

5G [EB/OL]. [2021-10-01].

URL

[5]

S Y

, YUAN

J H

, YUAN

W J

, et al.

Performance analysis of coded OTFS systems over high-mobility channels

[J]. IEEE transactions on wireless communications, 2021, 20(9): 6033–6048. DOI: 10.1109/TWC.2021.3071493

[6]

WEI

Z Q

, YUAN

W J

, LI

S Y

, et al.

Orthogonal time-frequency space modulation: a promising next-generation waveform

[J]. IEEE wireless communications, 2021, 28(4): 136–144. DOI: 10.1109/MWC.001.2000408

[7]

FARHANG

, REZAZADEHREYHANI

, DOYLE

L E

, et al.

Low complexity modem structure for OFDM-based orthogonal time frequency space modulation

[J]. IEEE wireless communications letters, 2018, 7(3): 344–347. DOI: 10.1109/LWC.2017.2776942

[8]

, WEI

, HUANG

, et al.

A simple two-stage equalizer with simplified orthogonal time frequency space modulation over rapidly time-varying channels

[EB/OL]. [2021-10-10].

URL [Cited within: 1]

[9]

LONG

, NIU

, DONG

, et al.

Low complexity iterative LMMSE-PIC equalizer for OTFS

[C]//2019 IEEE International Conference on Communications (ICC). Shanghai, China: IEEE, 2019: 1–6. DOI: 10.1109/ICC.2019.8761635

[10]

ZEMEN

, HOFER

, LOESCHENBRAND

Low-complexity equalization for orthogonal time and frequency signaling (OTFS)

[EB/OL]. [2021-10-10].

URL [Cited within: 1]

[11]

SURABHI

G D

, CHOCKALINGAM

Low-complexity linear equalization for OTFS modulation

[J]. IEEE communications letters, 2020, 24(2): 330–334. DOI: 10.1109/LCOMM.2019.2956709

[12]

SINGH

, MISHRA

H B

, BUDHIRAJA

Low-complexity linear MIMO-OTFS receivers

[C]//2021 IEEE International Conference on Communications Workshops (ICC Workshops). Montreal, Canada: IEEE, 2021: 1–6. DOI: 10.1109/ICCWorkshops50388.2021.9473839

[13]

S Y

, YUAN

W J

, WEI

Z Q

, et al.

Cross domain iterative detection for orthogonal time frequency space modulation

[J]. IEEE transactions on wireless communications, 2021, (99): 1. DOI: 10.1109/TWC.2021.3110125

[14]

THAJ

, VITERBO

Low complexity iterative rake decision feedback equalizer for zero-padded OTFS systems

[J]. IEEE transactions on vehicular technology, 2020, 69(12): 15606–15622. DOI: 10.1109/TVT.2020.3044276

[15]

KSCHISCHANG

F R

, FREY

B J

, LOELIGER

H A

Factor graphs and the sum-product algorithm

[J]. IEEE transactions on information theory, 2001, 47(2): 498–519. DOI: 10.1109/18.910572

[16]

, DONG

Y Y

, GONG

C H

, et al.

Low complexity receiver via expectation propagation for OTFS modulation

[J]. IEEE communications letters, 2021, 25(10): 3180–3184. DOI: 10.1109/LCOMM.2021.3101827

[17]

YUAN

W J

, WEI

Z Q

, YUAN

J H

, et al.

A simple variational Bayes detector for orthogonal time frequency space (OTFS) modulation

[J]. IEEE transactions on vehicular technology, 2020, 69(7): 7976–7980. DOI:10.1109/TVT.2020.2991443

[Cited within: 3]

[18]

ZHANG

H J

, ZHANG

T T

A low-complexity message passing detector for OTFS modulation with probability clipping

[J]. IEEE wireless communications letters, 2021, 10(6): 1271–1275. DOI: 10.1109/LWC.2021.3063904

[19]

TIWARI

, DAS S S, RANGAMGARI

Low complexity LMMSE Receiver for OTFS

[J]. IEEE communications letters, 2019, 23(12): 2205–2209. DOI: 10.1109/LCOMM.2019.2945564

[20]

RAVITEJA

, VITERBO

, HONG

OTFS performance on static multipath channels

[J]. IEEE wireless communications letters, 2019, 8(3): 745–748. DOI: 10.1109/LWC.2018.2890643

[21]

DONOHO

D L

, MALEKI

, MONTANARI

Message passing algorithms for compressed sensing: motivation and construction

[C]//2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo). Cairo, Egypt: IEEE, 2010: 1–5. DOI: 10.1109/ITWKSPS.2010.5503193

[22]

DONOHO

D L

, MALEKI

, MONTANARI

Message passing algorithms for compressed sensing: analysis and validation

[C]//2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo). Cairo, Egypt: IEEE, 2010: 1–5. DOI: 10.1109/ITWKSPS.2010.5503228

[23]

WINN

, BISHOP

C M

Variational message passing

[J]. Journal of machine learning research, 2005, 6(4): 661–694.

[24]

MONK

, HADANI

, TSATSANIS

, et al.

OTFS - Orthogonal Time Frequency Space

[EB-OL]. [2021-10-10]. .

URL [Cited within: 1]

[25]

YUAN

Z D

, LIU

, YUAN

W J

, et al.

Iterative detection for orthogonal time frequency space modulation with unitary approximate message passing

[J]. IEEE transactions on wireless communications, 2021. DOI:10.1109/TWC.2021.3097173

[Cited within: 11]

[26]

LIU

, YUAN

Z D

, GUO

Q H

, WANG

Z Y

, et al.

Multi-block UAMP based detection for OTFS with rectangular waveform

[J]. IEEE wireless communications letters, 2021. DOI: 10.1109/LWC.2021.3126871

[27]

GUO

Q H

, XI

J T

Approximate message passing with unitary transformation

[EB/OL]. [2021-10-10].

URL [Cited within: 5]

[28]

YUAN

Z D

, GUO

Q H

, LUO

Approximate message passing with unitary transformation for robust bilinear recovery

[J]. IEEE transactions on signal processing, 2021, 69: 617–630. DOI: 10.1109/TSP.2020.3044847

[29]

LUO

, GUO

Q H

, JIN

, et al.

Unitary approximate message passing for sparse Bayesian learning

[J]. IEEE transactions on signal processing, 2021, 69: 6023–6039. DOI: 10.1109/TSP.2021.3114985

[Cited within: 3]

[30]

TUCHLER

, SINGER

A C

, KOETTER

Minimum mean squared error equalization using a priori information

[J]. IEEE transactions on signal processing, 2002, 50(3): 673–683. DOI: 10.1109/78.984761

[31]

GUO

Q H

, PING

LMMSE turbo equalization based on factor graphs

[J]. IEEE journal on selected areas in communications, 2008, 26(2): 311–319. DOI: 10.1109/JSAC.2008.080208

[32]

GUO

Q H

, HUANG

D D

A concise representation for the soft-in soft-out LMMSE detector

[J]. IEEE communications letters, 2011, 15(5): 566–568. DOI: 10.1109/LCOMM.2011.032811.102073

[33]

LIU

, YUAN

Z D

, GUO

Q H

, et al.

Message passing based structured sparse signal recovery for estimation of OTFS channels with fractional Doppler shifts

[J]. IEEE transactions on wireless communications, 2021. DOI: 10.1109/TWC.2021.3087501