Message Passing Based Detection for Orthogonal Time Frequency Space Modulation

YUAN Zhengdao, LIU Fei, GUO Qinghua, WANG Zhongyong

Abstract： The orthogonal time frequency space （OTFS） modulation has emerged as a promising modulation scheme for wireless communications in high-mobility scenarios. An efficientdetector is of paramount importance to harvesting the time and frequency diversities promisedby OTFS. Recently， some message passing based detectors have been developed by exploitingthe features of the OTFS channel matrices. In this paper， we provide an overview of some re ?cent message passing based OTFS detectors， compare their performance， and shed some lighton potential research on the design of message passing based OTFS receivers.

Keywords： OTFS; detection; message passing; belief propagation; approximate message passing （AMP）; unitary AMP （UAMP）

Citation （IEEE Format）： Z. D. Yuan， F. Liu， Q. H. Guo， et al.，“Message passing based detection for orthogonal time frequency space modulation， ”ZTE Communications， vol. 19， no. 4， pp. 34 –44， Dec. 2021. doi： 10. 12142/ZTECOM.202104004.

1 Introduction

Recently the orthogonal time frequencyspace（OTFS） modulation has attracted much attention due to its ca? pability of achieving reliable communications in high mobilityscenarios[ 1 –6]. OTFSisatwo-dimensional modulation scheme， and the information is modulated in the delay Doppler （DD） domain， which is in contrast to the time frequency （TF） domain modulation in the orthogonal frequen ? cydivisionmultiplexing（OFDM）.InOTFS，eachsymbol spreads over the time and frequency domains through the two dimensional（2D） inverse symplectic finite Fourier transform （SFFT）， leading to both time and frequency diversities[ 1 –2]. It hasbeenshownthatOTFScansignificantlyoutperformOFDM in high mobility scenarios[7].

To harvest the diversities promised by OTFS， the design of a powerful detector is paramount. The optimal maximum a pos ? teriori（MAP）detectorisimpracticalduetoitscomplexity growing exponentially with the length of the OTFS block. Re ? cently， significant efforts have been devoted to the design of more efficient detectors. In Ref. [8]， an effective channel ma? trix in the DD domain was derived， based on which a low-com? plexity two-stage detector was proposed. The first-order Neu? mann series was used in Ref. [9] to approximately solve the matrix inverse problem involved in the linear minimum mean squared error （MMSE） estimation based detection. A detection scheme was developed in Ref. [ 10]， where the MMSE equaliza? tion was used in the first iteration， followed by parallel inter? ference cancellation with a soft-output sphere decoder in sub ? sequent iterations. A rectangular waveform was considered in Ref.[ 11]， where thesparsityandquasibandedstructureof channelmatriceswithoutfractionalDopplershiftswereex ? ploited to reduce the detection complexity. The linear equalizers were extended to the multiple input and multiple output （MIMO） -OTFS systems in Ref. [12]. A cross-domain method was proposed in Ref. [13]， where a conventional linear MMSE estimator is adopted for equalization in the time domain and a low-complexity symbol-by-symbol detection is utilized in the DD domain. A low complexity iterative rake decision feedback detector was proposed in Ref. [14]， which extracts and coher? ently combines the multiple copies of the symbols （due to mul? tipath propagation） in the DD grid using maximal ratio com ? bining （MRC）.

Another line of OTFS detector design is based on factor graphs and message passing techniques[15， 23]. When the num? ber of channel paths is small， the effective channel matrix in the DD domain is sparse， which allows efficient detection us ? ing the message passing algorithm （MPA） [2]. An expectation propagation （EP） algorithm was proposed in Ref. [16]， where EP is used for message update with Gaussian approximation. A variational Bayes （VB） based detector was proposed in Ref. [17] to achieve better convergence. Studying the matched fil? tering processing， the authors in Ref. [18] proposed a message passing detector， which is combined with a probability clip ? ping solution. The detectors in Refs. [2， 17， 19] take advan? tage of the sparsity of the channel matrix in the DD domain， and their complexity depends on the number of nonzero ele ? ments in each row of the channel matrix， which is denoted by S. Without considering fractional Doppler shifts， S is equal to the number of channel paths. In general， a wideband system can provide sufficient delay resolution. The Doppler resolu? tion depends on the time duration of the OTFS block. To fulfill the low latency requirement in wireless communications， the time duration of an OTFS block should be relatively small， where it is necessary to consider fractional Doppler shifts[2， 20]. In this case， the value of S can be significantly larger than the number of channel paths. In the case of rich scattering envi? ronments， the complexity of these detectors can be a concern and the short loops in the corresponding system graph model may result in significant performance. To overcome the above issues， the design of OTFS detectors based approximate mes ? sage passing （AMP）[21 –22] was investigated in Ref. [25]. AMP works well for independent and identically distributed （sub- ） Gaussian system transfer matrix， but it suffers from perfor? mance loss or even diverges for a general system transfer ma? trix[27 –29]. Instead， the works in Refs. [25 – 26] resort to the unitary AMP （UAMP） [27 –29]， which is a variant of AMP and was formerly called UTAMP[27]. In UAMP， a unitary transfor? mation of the original model is used， where the unitary matrix for transformation can be the conjugate transpose of the left singular matrix of the general system transfer matrix[27] ob? tained through singular value decomposition （SVD）. It is shown in Ref. [25] that UAMP is well suitable for OTFS due to the structure of block circulant matrix with circulant block （BCCB） of the DD domain channel matrices， where the 2D dis? crete Fourier transform is used for the unitary transformation，leading to very efficient implementation using the 2D fast Fou? rier transform （FFT） algorithm. In addition， as the noise vari? ance is normally unknown， the noise variance estimation is al? so incorporated into the UAMP-based detector in Ref. [25].

In this paper， we provide an overview of the message pass ? ing based detectors， provide some comparison results， and dis? cuss potential research on the design of message passing based OTFS receivers. The notations used in this paper are as follows. Boldface lower-case and upper-case letters denote vectors and matrices， respectively. We use （ ? ）Hand （ ? ）T to de? note the conjugate transpose and the transpose， respectively. The superscript * denotes the conjugate operation. We define [ ? ] Mas the mod M operation. We use N （x| ，νx ） to denote theprobability density function of a complex Gaussian variablewith meanand variance νx. The notationf （x ）q （x ） denotes the expectation of the functionf （x ） with respect to the distri? bution q （x ）. The relationf （x） = cg （x） for some positive con? stant c is written as f （x） ∝ g （x）. The notation ? represents the Kronecker product， and a ? b and a ? /b represent the com ? ponent-wise product and the division between vectors a and b， respectively. We use X = reshapeMxto denote that the vec? tor x is reshaped as an M × N matrix X column by column， where the length of x is MN， and use x = vecXto represent vectorization of matrix Xcolumn by column. The notation diag（a ） represents a diagonal matrix with the elements of a as its diagonal. We use |A|2 to denote the element-wise magni? tude squared operation for matrix A. The notations 1 and 0 are used to denote an all-ones vector and an all-zeros vector with a proper length， respectively. Thej-th entry of q is denoted by qj. The superscript t of st denotes the iteration index of the vari? able s involved in an iterative algorithm.

2 System Model

The modulation and demodulation for OTFS are illustratedin Fig. 1， which are implemented with the 2D inverse SFFT （ISFFT） and SFFT at the transmitter and receiver， respective? ly[1， 24]. Before the OTFS modulation， a （coded） bit sequence is mapped to symbols x [ k，l ] ，k = 0，...，N - 1， l = 0，...，M - 1 in the DD domain， where x [ k，l ] ∈ A = { α 1，...，α |A|}， |A| is the car? dinality of A， l and k denote the indices of the delay and Dop ? pler shifts， respectively， and N and M are the number of gridsof the DD plane. At the transmitter side， ISFFT is performed to convert the DD domain symbols to signals in the time-fre? quency （TF） domain.

Xtf[ n，m ] =∑ x [ k，l ] ej2π（-）.

After that， the signals Xtfm，nin the TF domain are con? verted to a continuous-time waveform s tusing the Heisen? berg transform with a transmit waveform gtxt[2]， i.e.，

s （t） =∑Xtf[ n，m ] gtx （t - nT ）ej2πmΔf （t - nT ） ，

where Δf is subcarrier spacing and T = 1/Δf. Then the signal s tis transmitted over a time-varying channel and the re? ceived signal in the time domain is given as：

r （t） =h （ τ ，ν ）s （t - τ ）ej2πν（t - τ ） dτdν ，（3）

where h（τ ，ν ） is the channel impulse response in the continu ? ous DD domain， and it can be expressed as[1]：

h（τ ，ν ） =hi δ （τ - τi ）δ （ν - ν i ） ，（4）

with δ （ ? ） being the Dirac delta function， P being the num? ber of channel paths， and hi， τiand ν ibeing the gain， delay and Doppler shift associated with the i-th path， respective? ly. The delay and Doppler-shift taps for the i-th path are giv? en by

li ki+ κ i（5）

where liand kiare the delay and Doppler indices of the i-th path， and κ i∈ [ -1 2 ， 1 2 ] is a fractional Doppler associat? ed with the i-th path. In the above equation， MΔf is the systembandwidth and NT is the duration of an OTFS block.

At the receiver， a receive waveform grxtis used to trans? form the received signal r tto the TF domain， i.e.，

Y （t，f ） =*rx （t′ - t）r （t′）e-j2πf （t′ - t）dt′，（6）

which is then sampled at t = nTand f = mΔf， yielding Y n，m. Then SFFT is applied to Y n，mto generate the DD domain signal y k，l， i.e.，

y [ k，l ] = Y [ n，m ] e-j2π（-）.

Assuming that the transmitted waveform and the received waveform satisfy the bi-orthogonal property[1]， in the DD do? main we have the input-output relationship[2].

y [ k，l ] =ci hi x [ k - ki+ c ] N ，

[ l - li ] M e-j2π+ ω [ k，l ]

1 - e-j2πN ，（8）

where Ni< N is an integer， and ω [ k，l ] is the noise in the DDdomain. We can see that for each path， the transmitted signalis circularly shifted， and scaled by a corresponding channelgain. We arrange {x k，l} as a vector x ∈ CMN × 1， where the jth element xjis x k，lwith j = kM + l. Similarly， a vectory ∈ CMN × 1 can also be constructed based on y [ k，l ]. Then Eq.（8） can be rewritten in a vector form as：

y = Hx + ω ， （9）

where H ∈ CMN × MNis 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]：

where IN （-[ q - ki ] N ） denotes an N × N matrix obtained by circularly shifting the rows of the identity matrix by -[ q - ki ] N， and IM （li ） is obtained similarly. Without fraction? al Doppler， i.e.， κ i= 0， the channel matrix H is reduced to

H =IN（ki ） ?IM （li ）hi e-j2π

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 MN × MN DD domain complex channel matrix H is sparse （especially in the case without fractional Doppler shifts）， which makes belief propagation suitable for im ? plementing the OTFS detectors. In Eq. （2）， y and ω are length- MN complex vectors with elements denoted by y [ d ] and ω [ d ]， 1 ≤ d ≤ MN， the element of H is denoted by H [ d，c ]， 1 ≤d，c≤MN，x is a length-MN symbol vector with elements x [ c ] ∈ A， 1 ≤ c ≤ MN， and denotes the modulation alphabet.

Thanks to the sparsity of H ， the joint distribution of the ran? dom variables in model （9） can be represented with a sparsely- connected factor graph with MN variable nodes corresponding to x and MN observation nodes corresponding to y. As shown inFig. 2， each observation node y [ d ] is connected to a set of vari ? ablenodes{ x [ es ] ，es∈（d ） }，andsimilarly，eachvariable nodex [ c ]isconnectedtoasetofobservationnodes y [ es ] ， es∈[ 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 ≤ s ≤ S. The proba? bility mass function （PMF） pc，es= { pc，es （ aj ）|aj∈ A } represents the messages from variable nodes x [ c ] to factor nodes y [ es ].

Based on the factor graph in Fig. 2， a message passing algo? rithm 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 com ? putations.

1）Messagespassingfromobservationnodey [ d ] tovariable node x es

The message is approximated to be Gaussian， and the mean μ d（i），esand variance （σ d（i），es ）2are computed as

2） Messages passing from variable node x [ c ] to observation node y [ es ]

The PMF pic，d can be updated as

pic，es （ aj ） = Δ ?ic，es （ aj ） + （1 - Δ） ?（ aj ），

where Δ∈ [ 0， 1 ] is the damping factor and

ic，es （ aj ） ∝∏Pr （ y [ e ] |x [ c ] = aj ，H ） =

（15）

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

TheMPalgorithmshownaboveisanapproximationto loopy belief propagation since it approximates the interfer? ence to be Gaussian to achieve lower complexity. The com? plexity of the algorithm is （MNS||） 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 perfor? mance as no short loops in the factor graph model. However， in the case of rich-scatting environments and fractional Dop ? pler 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 computa? tional complexity.

3.2 VB Detector

The VB detector was proposed in Ref. [ 17] to guarantee the convergence of the iterative detector， which can be implement? ed with variational message passing. With model （9）， the opti? mal MAP detection can be formulated as：

However， the complexity of solving the above optimization problem increases exponentially with the size of %. VB is adopted to achieve low complexity approximate detection. In this method， a distribution q （ x ） from a tractable distribution fami ? lyis found as an approximation to the a posteriori distribu? tion p （ x|y ）. The trial distribution q（ x ） can be obtained by min? imizing the Kullback-Leibler divergence （q||p）， i.e.，

where the expectation is taken over x according to the trial dis ? tribution q （ x ）.

To simplify the optimization problem， q（x） is assumed to be fully factorized， i.e.，

wherek ∈ [ 0，N - 1 ]，M ∈ [ 0，M - 1 ]andxk，ldenotesthe （ kM + l ）-th entry of x. With this assumption， q （ x ） can be up? dated iteratively by maximizing . Since the noise sample ω k，l anddatasymbolxk，l，?k，lareindependent，and ω k，l ～（ω k，l; 0，?- 1 ）， p （ x|y ） can be rewritten as：

where yk，l= h k，（T）l x + ω k，l，hk，ldenotestheequivalentchannel vector whose （ kM + l ）-th entry is hk，l [ k，l ]. Then the distribu? tion p （ x|y ） can be further rewritten as：

where

ζk，l （ xk，l ） = p （ xk，l ）exp -，

ψk，l （ xk，l ，xk′，l′） = exp -，

withρk，l=，l′|hk′，l′ （ k，l ）|2 ，ηk，l= 2′，l′hk′，l′ [ k，l ] ?yk，l′， and?k，l，k′，l′= 2hk，l [ k，l ] hk（*），l [ k′，l′] .Substituting p （ x|y ）in

Eq. （23） and q （ x ） into yields

= qlnψk，l （ xk，l ，xk′，l′） -ln=

?k，l，k′，l′xk，lxk′，l′qk，l （ xk，l ）

.

To find a stationary point of ， the partial derivations of with respect to all local functions qk，l （ xk，l ）， ?k， l need to be ze? ro. Take the latent variable xk，las an example. Setting the par? tial derivation ?/?qk，l （ xk，l ） to zero leads to：

whereqk，l= ∏（ k′，l′） ≠ （ k，l） q k（it）e′，l（r）′- 1 （ xk，l ），q k（it）e′，l（r）′- 1 （ xk，l ） isobtainedin the （iter - 1）-th iteration and C denotes a constant.

Then， solving Eq. （27） for qk，l （ xk，l ） results in the local distri ? bution， which can be expressed as：

It is noted that the variance of xk，lis underestimated and on? ly the noise variance is considered in Eq. （28）. To fix the un? derestimation， a practical solution is to repeat the above proce ? dure to approximate the a posteriori distribution for all the da? ta symbols iteratively， resulting in the approximate marginal q k（*），l （ xk，l ）， ?k，l. Then， the decision on the symbols can be made by maximizing the approximate marginal distribution q k（*），l （ xk，l ）， i.e.，

The complexity of the algorithm per iteration is （MNS||）.

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 effi ? cient OTFS detector with 2D FFT. It can be seen from Eqs. （ 10） and （11） that the DD domain channel matrix H has a BC ? CB structure. A useful property of the BCCB matrix H is that it can be diagonalized using 2D Discrete Fourier Transform matrix， i.e.，

where F = FN? FMwith FNand FMbeing respectively the normalized N-point and M-point DFT matrices. In Eq. （30），matrix Λ is a diagonal matrix， i. e.， Λ = diag （d ）， and d is a length-MN vector that can be computed using 2D FFT.

whereFFT2（?）representsthe2DFFToperation，C = reshapeMH （：， 1） is an M × N matrix， and H （：， 1） with length- MN 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：

where r = Fy， ω ' = Fω ， and the noise ω ' has the same distri? bution with ω as F is an unitary matrix. The precision of the noise is still denoted by ?， which needs to be estimated. De ? fine Φ = ΛF and an auxiliary vector z = Φx. Then we can fac ? torize the joint distribution of the unknown variables x，z，? giv? en r as

where indices i，j∈ [ 1：MN ]. To facilitate the factor graph rep ? resentation of the factorization in Eq. （33）， the relevant nota? tions are listed in Table1， which shows the correspondence between the factor nodes and their associated distributions. The factor graphrepresentation for the factorizationinEq.（33） is depicted in Fig. 3.

Following the UAMP algorithm， a UAMP based iterative de ? tector can be designed， which is summarized in Algorithm 2. According to the derivation of （U）AMP using loopy belief prop? agation， UAMP provides the message from variable node zjto functionnodefrj，whichisGaussiananddenotedby mzj→frj （ zj ） = （zj |pj ，νpj）. Here， the mean pjand the variance νpjare given in Lines1 and 2 of the Algorithm in a vectorform. With the mean field rule[23]at the function node frj， we can compute the message passed from function node frjto variable node ?， i.e.，

where b（zj ） is the belief of zj. It turns out that b（zj ） is also Gaussian with its variance and mean given by

respectively， whereis 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.，

And the estimate is given as

which can be rewritten in a vector form shown in Line 5 of the algorithm. With the mean field rule at the function node frj again， the message passed from the function node frjto thevariable node zj can be computed as：

Then the UAMP algorithm with known noise can be used as if the true noise precision is， leading to Lines 6 – 15 andLines 1 – 2 of the Algorithm 2. In Lines 10 – 13， the Gaussian messageiscombinedwiththediscretepriortoobtainthe MMSEestimates of thesymbolsin terms of their posterior means and variances. There is an extra operation in Line 14， which averages the variances of xj. Thanks to the special form of the unitary matrix F， 2D FFT is used in the implementa? tions in Lines 2 and 9. It can be seen that the UAMP detector does not require any matrix-vector products， the algorithm re? quiresonlyelement-wise vector operationsorscalar opera? tions， except Lines 2 and 9， which are implemented with FFT.SothecomplexityoftheUAMPdetectorisMNlog （MN） + MN||per OTFS block per iteration， which is independent of S.

Compared with the UAMP detector， the MP and VB de? tectors have a complexity of （MNS||） per OTFS block per iteration， which can be considerably higher than that of the UAMP detector in the case of rich scattering environ ? ments and when fractional Doppler shifts have to be consid ? ered （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，theOTFSdetectorcanbeimplementeddirectly withthe AMP algorithm. However， due to the deviation of the chan? nel matrix from the i. i. d. Gaussian matrix， the AMP detec ? tor 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 re? alized in a way that the detector and decoder exchange infor? mation iteratively， i. e.， the turbo processing[30 –31]. The OTFS detectors can be incorporated into a turbo receiver by endow ? ing the OTFS detectors with the capabilities of taking the out? put 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 in? formation bits are encoded and interleaved before symbol map ? ping， where each symbol xj∈ A = { α 1 ，...，α |A| } in the DD domainismapped fromasub-sequenceof thecodedbitsesponds to a length-log|| binary sequence， which is denoted by α a（1） ，...，αloag|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.，

where La （ cqj） is the output extrinsic LLR of the decoder in the last iteration. The extrinsic LLR Le （ cqj） is passed to the decod? er. The extrinsic LLR Le （ cqj） can be expressed in terms of ex? trinsic mean and variance of the symbols[32]， i.e.，

where mejand vejare the extrinsic mean and variance of xj， and q0and q0represent the subsets of all α acorresponding to cqj= 0and cqj= 1，respectively. Theextrinsicvarianceand mean are defined in Ref. [32].

where mjand vjare the a priori mean and variance of xjcalculated based on the output LLRs of the SISO decoder[30] and mj（p） and vj（p） are a posteriori mean and variance of xj.

Taking the UAMP detector as an example ， we show theincorporation of the OTFS detector into a turbo receiver. Ac ?cordingtothederivationof theUAMPalgorithm ， wecanfind that q and ν qconsist of the extrinsic means and varianc ?es of the symbols in % as they are the messages passed fromthe observation side and do not contain the immediate a pri ?ori information about %. Hence we have mej= qjand vej= ν q. Then Eq. （40） can be readily used to compute the extrinsicLLRsof thecodedbits. WiththeLLRsprovidedbytheSISOdecoder， one cancompute the probability p （ xj= α a ）for each xj， which is no longer the “non-informative prior ” in Algorithm 2. Therefore， ξj，ain Line 7 of the algorithm ischanged to

In addition， the iteration of the UAMP detector can be com ? bined with the iteration between the SISO decoder and detec ? tor， which leads to a single loop iteration （i. e.， inner iterations are not required）.

Thecomputationalcomplexityof thedetectorsissumma? rized 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].

5 Simulation Results

In this section， we compare the performance of the mes ? sage passing based detectors. The low complexity MRC de ? tector 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 TFdomain. Bothquadraturephaseshiftkeying（QPSK） modulationand16-quadratureamplitudemodulation （QAM） are considered. The carrier frequency is 3 GHz， and the subcarrier spacing is 2 kHz. The speed of the mobile us ? er is set to v = 135 km/h， leading to a maximum Doppler fre ? quency shift index kmax= 6. We assume that the maximum delay index is lmax=14. The Doppler index of the i-th path is uniformly drawn from the set [ -kmax ，kmax] and the delay in? dexisintherangeof[ 1，lmax]excludingthefirstpath （l1= 0）.Weassumethatthe fractionalDopplerκ iisuni? formly distributed within [ - 1/2， 1/2 ]， and the channel coeffi? cients hiare independently drawn from a complex Gaussian distribution with mean 0 and variance ηli ， where the normal? izedpowerdelayprofileηi= exp（ -αli ）/exp（ -αli ） with α being 0 or 0. 1. The maximum number of iterations is set to15 for all iterative detectors. We note that， all detectorsexcepttheMRCdetectorrequirethenoisevariance. 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 in ? cludingthebi-orthogonalandrectangular waveformswith integer or fractional Doppler shifts ， and QPSK or16-QAM for modulations. In addition， both uncoded and coded sys ? tems are evaluated.

Fig. 5 shows the BER performance of various detectors inthecaseofthebi-orthogonalwaveformwithdifferent numbers of paths， where we assume no fractional Doppler shifts，i. e.，S = P.Wealsoassumeα = 0，andQPSKis used. Fromthis figure， wecanseethat，theMPdetector 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 VBdetectorswhenP=6anddeliversbetterperformance than the MP and VB detectors with larger P. The AMP and UAMP detectors perform well ， where we can see that they enjoythediversitygainandachievebetterperformance with the increase of P. In all cases， the UAMP based detec ? tor delivers the best performance and significantly outper? forms other detectors.

With the rectangular waveform and factional Doppler shifts， we compare the bit error ratio （BER） performance of the AMP， UAMPandMRCdetectorsinFig.6，wherethenumberof 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 modulation16-QAM， compared with QPSK.

We then evaluate the performance of the detectors in a cod ? edOTFSsystem， where the turbo receiver inFig. 4isem? ployed. The number of paths P=14， and a rectangular wave ? form is used. In Fig. 7（a）， we show the performance of the un? coded 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 MN. The BCJR algorithm is used for the SISO decoder. We can find that the performance gaps be ? tween the AMP detector and the UAMP detector become larg? er in the coded system. The turbo receiver can achieve much betterperformance（about3.5 - 4dBattheBERof10-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.Asexpected，thesystemperformanceisimproved considerably when the LDPC is used. From Fig. 7（c）， we can see that the use of theLDPCcodecanimprove the perfor? mance of the UAMP based detector significantly and the per? formance gap between AMPandUAMPincreases when the LDPC is used.

6 Conclusions and Potential Future Work

In this paper， we reviewandcompare the recently pro ? posedmessagepassingbasedOTFSdetectors ，whichex? ploit the structures of the OTFS channel matrices ， such as sparsityandBCCB. According to the results， theMPand VBdetectorsaremoresuitableinthescenariosthatthe number of paths is relatively small and the modulation or? der is low， where they deliver good performance while with relatively low complexity. TheUAMP detector seems very promising especially in the case of rich-scattering environ? ments and/or when fractional Doppler shifts have to be con ? sidered， where the UAMP detector is attractive in both com ? putationalcomplexityandperformance. Theresultsalso show that the OTFS system with a turbo receiver can pro ? vide significant performance gain.

The message passing techniques seem promising in the de ? sign 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 chan? nel 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 superiorsystemperformanceand/orsignificantreductionof the training overhead. This is because the data symbols can be usedtoserveasavirtualtrainingsequenceandtheguard band between the trainingsymbolsanddatasymbolsisnot necessary.

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

Themessage passing techniquescould be used toimple ? ment sophisticated receivers in more complex systems， such as multi-user OTFS systems， grant-free multiple access with OTFS， multiple-output-multiple-input （MIMO）-OTFS， integrat? ed sensing and communication with OTFS.

References

[ 1] HADANI R， RAKIB S， TSATSANIS M， et al. Orthogonal time frequency space modulation [C]//2017 IEEE Wireless Communications and Networking Confer? ence（WCNC）.SanFrancisco，USA：IEEE，2017：1– 6.DOI：10. 1109/WCNC.2017.7925924

[2] RAVITEJA P， PHAN K T， HONG Y， et al. Interference cancellation and itera? tive detection for orthogonal time frequency space modulation [J]. IEEE transac? tions on wireless communications， 2018，17（ 10）： 6501 – 6515. DOI：10. 1109/TWC.2018.2860011

[3] SURABHI G D， AUGUSTINE R M， CHOCKALINGAM A. On the diversity of uncoded OTFS modulation in doubly-dispersive channels [J]. IEEE transactions onwirelesscommunications，2019，18（6）：3049–3063.DOI：10. 1109/TWC.2019.2909205

[4] HADANI R， MONK A. OTFS： A new generation of modulation addressing the challenges of 5G [EB/OL]. [2021-10-01]. https： //arxiv.org/abs/1802.02623

[5] LI S Y， YUAN J H， YUAN W J， et al. Performance analysis of coded OTFS sys ? tems over high-mobility channels [J]. IEEE transactions on wireless communica? tions， 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 modula? tion： a promising next-generation waveform [J]. IEEE wireless communications， 2021， 28（4）： 136 – 144. DOI： 10. 1109/MWC.001.2000408

[7] FARHANG A， REZAZADEHREYHANI A， 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] LI L， WEI H， HUANG Y， et al. A simple two-stage equalizer with simplified or? thogonal time frequency space modulation over rapidly time-varying channels [EB/OL]. [2021-10-10]. https：//arxiv.org/abs/1709.02505

[9] LONGF，NIUK，DONGC，etal. LowcomplexityiterativeLMMSE-PIC equalizer for OTFS [C]//2019 IEEE International Conference on Communica? tions（ICC）.Shanghai，China：IEEE，2019：1–6. DOI ：10. 1109/ICC.2019.8761635

[ 10] ZEMEN T， HOFER M， LOESCHENBRAND D. Low-complexity equalization fororthogonaltimeand frequencysignaling（OTFS）[EB/OL].[2021- 10- 10]. https：//arxiv.org/abs/1710.09916v1

[ 11] SURABHI G D， CHOCKALINGAM A. Low-complexity linear equalization for OTFS modulation [J]. IEEE communications letters， 2020， 24（2）： 330 – 334. DOI： 10. 1109/LCOMM.2019.2956709

[ 12] SINGH P， MISHRA H B， BUDHIRAJA R. Low-complexity linear MIMO-OT? FSreceivers[C]//2021IEEEInternationalConferenceonCommunications Workshops（ICCWorkshops）.Montreal，Canada：IEEE，2021：1– 6.DOI： 10. 1109/ICCWorkshops50388.2021.9473839

[ 13] LI S Y， YUAN W J， WEI Z Q， et al. Cross domain iterative detection for or? thogonal time frequency space modulation [J]. IEEE transactions on wireless communications， 2021， （99）： 1. DOI： 10. 1109/TWC.2021.3110125

[ 14] THAJ T， VITERBO E. Low complexity iterative rake decision feedback equal ? izer for zero-padded OTFS systems [J]. IEEE transactions on vehicular technol? ogy， 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] LI H， 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 onvehiculartechnology，2020，69（7）：7976–7980.DOI：10. 1109/TVT.2020.2991443

[ 18] ZHANG H J， ZHANG T T. A low-complexity message passing detector for OT? FS modulation with probability clipping [J]. IEEE wireless communications let? ters， 2021， 10（6）： 1271 – 1275. DOI： 10. 1109/LWC.2021.3063904

[ 19] TIWARI S， DAS S S， RANGAMGARI V. Low complexity LMMSE Receiver for OTFS [J]. IEEE communications letters， 2019， 23（ 12）： 2205 – 2209. DOI：10. 1109/LCOMM.2019.2945564

[20] RAVITEJA P， VITERBO E， HONG Y. OTFS performance on static multipath channels[J]. IEEE wirelesscommunications letters， 2019，8（3）： 745– 748. DOI： 10. 1109/LWC.2018.2890643ZTE COMMUNICATIONS December 2021 Vol. 19 No. 443Special Topic Message Passing Based Detection for Orthogonal Time Frequency Space ModulationYUAN Zhengdao， LIU Fei， GUO Qinghua， WANG Zhongyong

[21] DONOHO D L， MALEKI A， MONTANARI A. Message passing algorithms forcompressed sensing： motivation and construction [C]//2010 IEEE InformationTheoryWorkshoponInformationTheory（ITW2010，Cairo）.Cairo，Egypt：IEEE， 2010： 1 –5. DOI： 10. 1109/ITWKSPS.2010.5503193

[22] DONOHO D L， MALEKI A， MONTANARI A. Message passing algorithms forcompressed 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 J， BISHOP C M. Variational message passing [J]. Journal of machinelearning research， 2005， 6（4）： 661 –694.

[24] MONK A， HADANI R， TSATSANIS M， et al. OTFS - Orthogonal Time Frequency Space [EB-OL]. [2021-10-10]. https：//arxiv.org/abs/1608.02993v1.

[25] YUAN Z D， LIU F， YUAN W J， et al. Iterative detection for orthogonal timefrequencyspacemodulationwithunitaryapproximatemessagepassing[J].IEEEtransactionsonwirelesscommunications，2021.DOI：10. 1109/TWC.2021.3097173

[26] LIU F， YUAN Z D， GUO Q H， WANG Z Y， et al. Multi-block UAMP based detection forOTFS withrectangular waveform[J].IEEE wirelesscommunications 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]. https：//arxiv.org/abs/1504.04799

[28] YUAN Z D， GUO Q H， LUO M. Approximate message passing with unitarytransformation for robust bilinear recovery [J]. IEEE transactions on signal processing， 2021， 69： 617 –630. DOI： 10. 1109/TSP.2020.3044847

[29] LUOM，GUOQH， JINM， et al. Unitary approximate message passing forsparseBayesian learning[J].IEEE transactionsonsignal processing， 2021，69： 6023 –6039. DOI： 10. 1109/TSP.2021.3114985

[30] TUCHLERM，SINGERAC，KOETTERR.Minimummeansquarederrorequalization using a priori information [J]. IEEE transactions on signal processing， 2002， 50（3）： 673 –683. DOI： 10. 1109/78.984761

[31] GUOQH， PINGL.LMMSE turboequalizationbasedon factor graphs[J].IEEE journal on selected areas in communications， 2008， 26（2）： 311 – 319.DOI： 10. 1109/JSAC.2008.080208

[32] GUOQH，HUANGDD.Aconciserepresentationforthesoft-insoft-outLMMSE detector [J]. IEEE communications letters， 2011，15（5）： 566– 568.DOI： 10. 1109/LCOMM.2011.032811. 102073

[33] LIU F， YUAN Z D， GUO Q H， et al. Message passing based structured sparsesignal recovery for estimation of OTFS channels with fractional Doppler shifts[J].IEEEtransactionsonwirelesscommunications，2021.DOI：10. 1109/TWC.2021.3087501

Biographies

YUAN Zhengdao received the B.E. degree in communication and information system from Henan University of Science and Technology， China in 2006， the M.E. degree in communication engineering from Soochow University， China in 2009， and the Ph.D. degree in information and communication engineering from the National Digital Switching System Engineering and Technological Research Center， China in 2018. He is currently an associate professor with the Open University of Henan. He was a visiting scholar with the University of Wollon? gong， Australia in 2019. His research interests are mainly in massive MIMO， sparse channel estimation， message passing algorithm， and iterative receiver.

LIU Fei received the B.E. and M.E. degrees in information and communication engineering from Zhengzhou University， China in 2015 and 2017， respectively. He is currently working toward the Ph.D. degree with the School of Information and Engineering， Zhengzhou University， China. His research interests are mes? sage passing algorithm， sparse signal recovery， and OTFS.

GUO Qinghua （qguo@uow.edu.au） received the B.E. degree in electronic engi?neering and the M.E. degree in signal and information processing from Xidian University， China in 2001 and 2004， respectively， and the Ph.D. degree in elec?tronic engineering from the City University of Hong Kong， China in 2008. He is currently an associate professor with the School of Electrical， Computer and Telecommunications Engineering， University of Wollongong， Australia and an adjunct associate professor with the School of Engineering， The University of Western Australia. His research interests include signal processing， machine learning and telecommunications. He was a recipient of the Australian Re? search Councils inaugural Discovery Early Career Researcher Award in 2012.

WANG Zhongyong received the B.S. and M.S. degrees in automatic control from Harbin Shipbuilding Engineering Institute， China in 1986 and 1988， re?spectively， and the Ph. D. degree in automatic control theory and application from Xian Jiaotong University， China in 1998. From 1988 to 2002， he has been with the Department of Electronics， Zhengzhou University， China. Now he is a professor with the Department of Communication Engineering， Zhengzhou University. His research interests include numerous aspects within embedded systems， signal processing， and communication theory.