{'fraction_non_alphanumeric': 0.04184394992194435, 'fraction_numerical': 0.009948269001193792, 'mean_word_length': 4.262564432989691, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Iterative Detection for Orthogonal Time Frequency Space Modulation Using Approximate Message Passing with Unitary Transformation

The orthogonal time frequency space (OTFS) modulation has emerged as a promising modulation scheme for high mobility wireless communications. To harvest the time and frequency diversity promised by OTFS, some promising detectors, especially message passing based ones, have been developed by taking advantage of the sparsity of the channel in the delay-Doppler domain. However, when the number of channel paths is relatively large or fractional Doppler shift has to be considered, the complexity of existing detectors is a concern, and the message passing based detectors may suffer from performance loss due to the short loops involved in message passing. In this work, we investigate the design of OTFS detectors based on the approximate message passing (AMP) algorithm. In particular, AMP with unitary transformation (UTAMP) based detectors are developed, which enjoy the structure of the channel matrix and allow efficient implementation, e.g., by exploiting the property of block circulant matrix with circulant block (BCCB), the complexity of the UTAMP-based detector per symbol is in the order of the logarithm of OTFS block length. In addition, the estimation of noise variance is incorporated into the UTAMP-based detectors (while existing detectors assume perfect noise variance). Thanks to the robustness of UTAMP relative to AMP, the UTAMP-based detectors are able to deliver much better performance, and outperform state-of-the-art detectors significantly. The investigations are also extended to iterative joint detection and decoding in a coded OTFS system, where the OTFS detectors are integrated into a powerful turbo receiver, leading to a considerable performance gain.


I. INTRODUCTION
Recently the orthogonal time frequency space (OTFS) modulation has attracted much attention due to its capability of achieving reliable communications for high mobility applications [1], [2], [3], [4], [5]. OTFS offers both time and frequency diversity as each symbol is spread over the time and frequency domains through the two dimensional (2D) inverse symplectic finite Fourier transform (ISFFT) [1], [2]. Compared with orthogonal frequency division multiplexing (OFDM), OTFS can achieve significant performance gains in high mobility scenarios [6]. In addition, when the number of channel paths is small, the effective channel in the delay-Doppler (DD) domain is sparse, which allows efficient channel estimation and data detection using message passing techniques [2].
A practical and powerful detector is essential to harvest the full time and frequency diversity promised by OTFS. The optimal maximum a posteriori (MAP) detector is impractical due to its complexity growing exponentially with the length of the OFTS block. In [7], an effective channel matrix in the DD domain was derived, based on which a low-complexity two-stage detector was proposed. The authors in [8] proposed a detection scheme, which uses minimum mean squared error (MMSE) equalization in the first iteration, followed by parallel interference cancellation with a soft-output sphere decoder in subsequent iterations. The design of low-complexity detectors were also investigated based on the message passing techniques [2], [9], [10] and promising performance has been demonstrated. A variational Bayes (VB) based detector was proposed in [11] to achieve better convergence compared with the existing message passing based detectors. The detectors in [2], [11], and [12] take advantage of the sparsity of the channel matrix in the DD domain, and their complexity depends on the number of nonzero elements 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 is able to provide sufficient delay resolution, however, the Doppler resolution depends on the time duration of the OTFS block. To fulfill the low latency requirement in future wireless communications, the time duration should be relatively small, where it is necessary to consider fractional Doppler shifts [2], [9]. In this case, the value of S is proportional to the number of paths and it can be significantly larger than the number of channel paths, which leads to two issues: the complexity of the existing detectors is a concern especially in the case of rich scattering environments, and the message passing based detectors may suffer from performance loss due to the presence of short loops in the corresponding system graph model. This work aims to address the above issues by designing efficient detectors based on the approximate message passing (AMP) algorithm [13], [14]. The use of AMP in this work is due to two facts: AMP was developed based on loopy belief propagation in dense factor graphs, i.e., short loops can be handled by AMP, and AMP has a low complexity. It is known that AMP works well for i.i.d. (sub-)Gaussian system transfer matrix, but it may suffer from performance loss or even diverge for a general system transfer matrix [15]. Inspired by [16], the work in [17] discovered that AMP can still work well for a general system transfer matrix when a unitary transform of the original model is used, where the unitary transformation is used to diagonalize the system transfer matrix, e.g., the unitary matrix for transformation can be the conjugate transpose of the left singular matrix of a general system transfer matrix, or it can be simply a discrete Fourier transform (DFT) matrix for a circulant system transfer matrix. This variant to AMP is called UTAMP for convenience, which has been developed for low complexity robust sparse Bayesian learning [18], low complexity robust bilinear recovery [19], low complexity robust inverse synthetic aperture radar (ISAR) imaging with high Doppler resolution [20], low complexity direction of arrival (DOA) estimation [21], etc. It will be shown in this paper that UTAMP is well suitable for OTFS because the channel matrix in the DD domain is a block circulant matrix with circulant block (BCCB), which can be efficiently diagonalized using the 2D fast Fourier transform (FFT) algorithm. This leads to a very attractive UTAMP-based detector in two aspects. First, the complexity of the UTAMP-based detector is in the order of the logarithm of the OTFS block length per symbol, which is independent of S. Second, thanks to the robustness of UTAMP, the UTAMP-based detector delivers significantly better performance. In addition, as the noise variance is normally unknown in practice, the noise variance estimation is incorporated in the design of the UTAMP-based detector in this work. In contrast, existing OTFS detectors often assume a perfect knowledge of the noise variance. It is shown that, even with estimated noise variance, the UTAMP-based detector can significantly outperform the AMP-based detector and other state-of-the-art detectors [2], [11]. In this paper, we also extend our investigations to coded OTFS systems, and we integrate (UT)AMP-based detectors into a powerful turbo receiver to achieve joint iterative detection and decoding.
The remainder of the paper is organized as follows. In Section II, the OTFS system model is introduced. We design (UT)AMP based detectors with bi-orthogonal waveform in Section III, and rectangular waveform in Section IV. The discussion is extended to iterative joint detection and decoding in a coded OFTS system in Section V. The performance prediction of the OTFS system with the proposed detectors is discussed in Section VI. Simulations results are provided in Section VII, followed by conclusions in Section VIII.
Notations-Boldface lower-case and upper-case letters de-note vectors and matrices, respectively. The superscripts (·) H and (·) T represent conjugate transpose and transpose operations, respectively. The superscript * is used to denote the conjugate operation. We define [·] M as the mod M operation. The probability density function of a complex Gaussian variable with meanx and variance ν x is represented by N (x|x, ν x ). The notation f (x) q(x) denotes the expectation of the function f (x) with respect to probability density q(x). The relation f (x) = cg(x) for some positive constant c is written as f (x) ∝ g(x). Notation ⊗ represents the Kronecker product, and a · b and a · /b represent the component-wise product and division between vectors a and b, respectively. The notation X = reshape M (x) represents that the vector x is reshaped as an M × N matrix X column by column, where the length of vector x is M N . We use x = vec (X) to represent vectorization of matrix X column 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 magnitude squared operation for matrix A. We use 1 and 0 to denote an all-one vector and an all-zero vector with proper length, respectively. We use q j to denoted the jth entry of q. The superscript t of s t denotes the iteration index in an iterative algorithm.
II. SYSTEM MODEL The OTFS modulation and demodulation are shown in Fig.  1, which are implemented with 2D inverse SFFT (ISFFT) and SFFT at the transmitter and receiver, respectively [1], [22]. 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| } with |A| being the cardinality of A, l and k denote the indices of delay and Doppler shifts, respectively, and N and M are the number of grids of the DD plane. As shown in Fig. 1, ISFFT is performed to convert the symbols to signals in the time-frequency (TF) domain, i.e., Then the signals {X tf [m, n]} in the TF domain are converted to a continuous-time waveform s(t) using the Heisenberg transform with a transmit waveform g tx (t), i.e., where ∆f is subcarrier spacing and T = 1/∆f . The signal s(t) is then transmitted through a time-varying channel and the received signal in the time domain can be expressed as with h(τ, ν) being the channel impulse response in the (continuous) DD domain. The channel impulse response can be expressed as Fig. 1: OTFS modulation and demodulation [2].
where δ(·) is the Dirac delta function, P is the number of resolvable propagation paths, and h i , τ i and ν i represent the gain, delay and Doppler shift associated with the ith path, respectively. The delay and Doppler-shift taps for the ith path are given by where l i and k i are the delay index and Doppler index of the ith path, and κ i ∈ [− 1 2 , 1 2 ] is a fractional Doppler associated with the ith path. Here, M ∆f is the total bandwidth of the system and N T is the duration of an OTFS block.
At the receiver side, a receive waveform g rx (t) is used to transform the received signal r(t) to the TF domain i.e., Assume that the transmit waveform and receive waveform satisfy the bi-orthogonal property [1], then the channel inputoutput relationship in the DD domain can be written as [2], [23] 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 reshape can also be constructed based on {y[k, l]}. Then the channel input-output relationship in (9) can be rewritten in a vector form as where H ∈ C M N ×M N is the effective channel in the DD domain, and ω denotes a white Gaussian noise with mean 0 and variance −1 (or precision ).

B. AMP Based Detector
Based on (10), we aim to recover the discrete-valued symbols in the vector x. Motivated by the capability of dealing with short loops and low complexity of AMP, we estimate x using the AMP algorithm [13], [24]. The AMP-based detection algorithm is derived in the following and summarized in Algorithm 1.
The AMP algorithm decouples the estimation of vector x. Lines 1-6 of Algorithm 1 follow the AMP algorithm directly, and q computed in Line 6 can be regarded as pseudo observations with the following decoupled pseudo observation model where j denotes a Gaussian noise with mean zero and variance ν qj , which is computed in Line 5 of the algorithm. Lines 7-10 are used to compute the a posteriori mean and variance of each x j based on the above pseudo observation model and the prior of x j , which is a uniform discrete distribution, i.e., It is not hard to show that the a posteriori meanx j and variance ν xj of x j are given bŷ where with Algorithm 1 AMP based OTFS Detector

Until terminated
In Algorithm 1, the resultsx j and ν xj in the last iteration can be used for de-mapping, which can be performed based on the pseudo model where w j is a Gaussian noise with mean zero and variance ν xj . There are two issues we need to point out. First, in the above algorithm the noise variance −1 is assumed to be known, which, however, is often unknown in practice. Second, it is noted that the deviation of the channel matrix H from an i.i.d. (sub-)Gaussian matrix may lead to performance loss of the AMP algorithm, which motivates us to employ a robust variant to AMP, e.g., UTAMP. In the next sub-section, we address both issues and develop a UTAMP-based detection algorithm, where the estimation of the noise variance is incorporated. In particular, we will show how the UTAMP algorithm can take advantage of the structure of the channel matrix and implemented with the 2D FFT algorithm, which is much more efficient than the AMP-based algorithm.

C. UTAMP Based Detector with 2D FFT
We first examine the property of the channel matrix H in (10), which can be represented as where I N (−[q − k i ] N ) denotes an N × N matrix obtained by circularly shifting the rows of the identity matrix by It is noted that H in both (18) and (19) with A useful property of the BCCB matrix H is that, it can be diagonalized using 2D DFT matrix, i.e., where F = F N ⊗ F M with F N and F M denoting respectively the normalized N -point and M -point DFT matrices, and matrix Λ in (22) is a diagonal matrix, i.e., with d being a length-M N vector. The vector d can be computed as where FFT2 (·) represents the 2D FFT operation, C = reshape M (H(:, 1)) is an M × N matrix, and H(:, 1) with length-M N is the first column of matrix H.
The above property can be exploited by UTAMP, leading to a more efficient detection algorithm while with significantly enhanced performance, compared to the AMP-based detector. Instead of using model (10) directly, the UTAMP algorithm [17] works with the unitary transform of the model. Because the channel matrix H admits the diagonaliztion in (22), we have the following unitary transform of the OTFS system model (10) where r F y, ω F ω, and the noise ω has the same distribution as ω since F is an unitary matrix. The precision of the noise is still denoted by , which is unknown and needs to be estimated. By defining Φ ΛF and an auxiliary vector z Φx, we can factorize the joint probability density function of the unknown variables x, z, and given r as To facilitate the factor graph representation of the factorization in (26), we introduce the notations in Table I, showing the correspondence between the factor labels and the underlying distributions they represent, and the specific functional form assumed by each factor. In Table I, Φ j denotes the jth row of matrix Φ. The factor graph representation for the factorization in (26) is depicted in Fig. 2, where squares and circles represent function nodes and variable nodes, respectively.  (26) Factor Distribution Functional Form Following the UTAMP algoritm, we can derive a UTAMP based iterative detector, which is summarized in Algorithm 2. It is noted that the noise precision is unknown, and its estimation needs to be included in the UTAMP-based detector. According to the derivation of (UT)AMP using the loopy belief propagation, UTAMP provides the message from variable node z j to function node f rj , which is Gaussian and denoted by m zj →fr j (z j ) = N (z j |p j , ν pj ). Here, the mean p j and the variance ν pj are given in Lines 1 and 2 of Algorithm 2 in a vector form. Based on the mean field rule [25] at the function node f rj , we can compute the message passed from function node f rj to variable node , i.e., Algorithm 2 UTAMP Based OTFS Detector (with noise precision estimation) Unitary transform: r = F y = ΛF x+ω, with F = F N ⊗F M .

Until terminated
where b(z j ) is the belief of z j . It turns out that b(z j ) is also Gaussian with variance and mean given by respectively, whereˆ in the estimate of in last iteration. They can be expressed in a vector form shown in Line 3 and Line 4 of Algorithm 2. The estimation of can be performed based on the belief b( ) at the variable node shown in Fig. 2 Then the estimate of can be expressed aŝ which can be rewritten in a vector form shown in Line 5 of Algorithm 2. By using the mean field rule at the function node f rj again, we have the message passed from the function node f rj to the variable node z j , i.e., Then the UTAMP algorithm with known noise can be used as if the true noise precision isˆ , leading to Lines 6-15 and Lines 1 and 2 of Algorithm 2. The derivations of Lines 10-13 are the same as those for the AMP-based detector. There is an extra operation in Line 14, which averages the variances of {x j }. It is note that the special form of the unitary matrix F leads to the implementation with the 2D FFT algorithm in Line 2 and Line 9 of Algorithm 2.

D. Computational Complexity Analysis
We first look at the complexity of the AMP based-detector. From Algorithm 1, we can find that the complexity of AMPbased detector is dominated by the matrix-vector products in Lines 1, 2, 5 and 6, e.g., Hx t and |H| 2 ν t x . Note that, each row of the matrix H has S = P i=1 N i non-zero elements [2], so the complexity is O (M N S) + O (M N |A|) per OTFS block per iteration.
Comparing Algorithm 2 for the UTAMP-based detector with Algorithm 1, we can find that the UTAMP-based detector does not require any matrix-vector products, and all lines of the algorithm involve only element-wise vector operations or scalar operations, except Line 2 and Line 9. It is noted that Line 2 and Line 9 can be implemented with the FFT algorithm. So the the complexity of Algorithm 2 is O (M N log(M N )) + O (M N |A|) per OTFS block per iteration, which is independent of S.
In comparison with the (UT)AMP-based detectors, the detectors proposed in [2] and [11] have a complexity of O(M N S|A|) per OTFS block per iteration, which can be much higher than that of the (UT)AMP-based detectors in the case of rich scattering environments and when fractional Doppler shifts have to be considered (leading to a large S). Moreover, the (UT)AMP-based detectors can deliver much better performance when the number of paths is relatively large, as shown in Section VI. In particular, the UTAMP-based detector with estimated noise precision can even significantly outperform other detectors with perfect noise precision.

IV. OTFS DETECTION WITH RECTANGULAR WAVEFORM
The rectangular waveform has been used in the literature as a more practical waveform. When a length-T rectangular waveform is used as the transmitter and receiver filters, as in [26], [27], [28], we append a cyclic prefix (CP) to each length-M sub-block of the signal s in the time domain before transmitting over the time-varying channel.
After removing CPs at the receiver side, the received signal in the time domain can be expressed as [26], [27], [28] where ω is an additive Gaussian white noise vector, and H T is an N M × N M block diagonal matrix where H n ∈ C M ×M is the channel matrix corresponding to the n-th sub-block of the transmitted signal. Then the received signal in the DD domain is obtained by performing block-wise DFTs, followed by the SFFT operation, i.e., Finally, the channel input-output relationship in the DD domain can be expressed as where H represents the effective channel matrix in the DD domain.
Based on model (35), we can directly apply Algorithm 1 to detect x, leading to an AMP-based OTFS detector. However, Algorithm 2 cannot be directly applied. Next, we design a detector based on the UTAMP algorithm.
Since the channel matrix H T is a block diagonal matrix, it can be diagonalized using the singular value decomposition (SVD) in a block-by-block manner, i.e., and each Λ n is an M × M diagonal matrix (so does Λ itself).

By applying the unitary transformation with the unitary matrix
whereX reshape M (x), andXF * N can be computed Fig. 3: Iterative joint detection and decoding in a coded OTFS system, where II and II −1 represent interleaver and deinterleaver, respectively.
using the FFT algorithm. c. The computation of q in Line 9 of Algorithm 2 is replaced by where S reshape M (V H (d * · s)), and SF N can be computed using the FFT algorithm. The UTAMP-based detector with rectangular waveform only involves element-wise product (division) except (41) and (42). Note that V is a block diagonal matrix, so the computational complexity of the detector is O M 2 N + O(M N |A|) per OTFS block. It is noted that the complexity of the UTAMPbased detector is independent of S, and as shown in Section VI, the detector can achieve a significant performance gain, compared to other detectors.

V. EXTENSION TO CODED TURBO SYSTEM
In this section, we consider a coded OFTS system and investigate the design of a turbo receiver for joint detection and decoding, which can be much powerful than a non-iterative receiver.
The turbo system is shown in Fig. 3, where the information bits are firstly encoded and then interleaved before mapping. Each symbol x j ∈ A = {α 1 , ..., α |A| } in the DD domain is mapped from a sub-sequence of the coded bit sequence, which is denoted by ]. Each α a corresponds to a length-log|A| binary sequence denoted by {α 1 a , ..., α log|A| a }. The turbo receiver consists of a soft-insoft-out (SISO) detector and a SISO decoder, which exchange information in an iterative manner. Based on the log-likelihood ratios (LLRs) provided the SISO decoder and the output of the OTFS demodulator as shown in Fig. 3, the task of the SISO detector is to compute the extrinsic LLR for each coded bit, i.e., L e (c q j ) = ln where L a (c q j ) is the ouput extrinsic LLR of the decoder in last iteration. The extrinsic LLR L e (c q j ) is passed to the decoder. The derivation for L e (c q j ) in terms of extrinsic mean and variance can be find in [29], and the result is shown here where m e j and v e j are the extrinsic mean and variance of x j , and A 0 q and A 0 q represent the subsets of all α a corresponding to c q j = 0 and c q j = 1, respectively. The extrinsic variance and mean are defined as [29] v e 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], [31], [32] and m p j and v p j are the a posteriori mean and variance of x j . By examining the derivation of the (UT)AMP algorithm, we can find that q and ν q consists of the extrinsic means and extrinsic variances of the symbols in vector x as they are the messages passed from the observation side and do not contain the immediate a priori information about x. Therefore, we have in Algorithm 1 and in Algorithm 2. Then (44) can be readily used to compute the extrinsic LLRs of the coded bits. It is noted that, with the LLRs provided by the SISO decoder, we can compute the probability p(x j = α a ) for each x j , which is no longer 1/|A| in Algorithm 1 and Algorithm 2. Therefore, ξ j,a in Line 7 of Algorithm 1 is amended to and Line 10 of Algorithm 2 is changed to In addition, we note that the iteration of the (UT)AMPbased detector can be incorporated into the iteration between the SISO decoder and detector, leading to a single loop iteration (i.e., inner iterations are not required).

VI. BER PERFORMANCE PREDICTION WITH STATE EVOLUTION
In this section, we investigate how to predict the performance of the (UT)AMP-based OTFS detector based on the state evolution (SE). As (UT)AMP decouples the estimation of vector x, so that, in the tth iteration, we have the following pseudo observation model where j = 1, ..., J with J = M N , and { t j } denote an additive white Gaussian noise (AWGN) with mean 0 and variance τ t . In UTAMP, the variance of the AWGN τ t is given as where v t x is the (average) variance of {x j } in the tth iteration. In the case of large i.i.d. Gaussian matrix with a size of J ×J, where the entries of the matrix are independently drawn from a Gaussian distribution with mean zero and variance 1/J, λ (consisting of the squared singular value of the matrix) approaches a length-J all one vector 1. In this case, (52) for UTAMP is reduced to which is exactly the SE equation for AMP (noting that in the scenario of the OTFS system considered in this work, the system transfer matrix, i.e., the channel matrix, is a square one with size J × J). Based on the above, the coded OTFS system can be regarded as a pseudo coded system with a simple AWGN channel give in (51), where {x j } are mapped from a coded bit sequence. In the pseudo coded system, {q t j } are the received signal, and the noise variance is τ t , i.e., the SNR is 1/τ t , where we assume that the power of the signal is 1. Then the signal is demapped with (44) and the LLRs are input to the SISO decoder. Based on the output of the decoder, the variance v t+1 x can be obtained as shown in Line 10 of Algorithm 1 and Line 14 of Algorithm 2. Clearly, v t+1 x depends on the SNR or τ t of the pseudo AWGN channel, i.e., v t+1 where g(·) is a function. It is noted that the function normally does not have an analytical form. However, it can be established (in the form of a table) through simulation as in [33], i.e., simulate the code (with the mapper used) in AWGN channels with different SNRs. At the same time the bit error rate (BER) can also be obtained. Hence, we can establish the 'function' It is noted that the 'function' does not depend on the OTFS channel, and it is only related to the code, the symbol mapper used and the SNR of the AWGN channel. Therefore the BER performance of the coded OTFS system with iterations can be predicated with the following simple iterative process with initialization t = 0 and v t x = 1. Repeat As we will see in Section VII that the BER performance of the coded OTFS system with the UTAMP-based detector can be predicted fairly well. In contrast, for the system with AMP-based detector, there is a huge difference between the simulated performance and predicted performance as the AMP SE equation (53) is no longer valid because the channel matrix deviates from the i.i.d. Gaussian matrix.

VII. SIMULATION RESULTS
In this section, we evaluate the performance of the proposed detectors and compare them with the state-of-the-art low complexity detectors in [2] and [11]. We set M = 256 and N = 32, i.e., there are 32 time slots and 256 subcarriers in the TF domain. The carrier frequency is 3 GHz, the subcarrier spacing is 2 kHz, and Quadrature phase shift keying (QPSK) modulation is adopted. The speed of the mobile user is set to be v = 135km/h, leading to a maximum Doppler frequency shift index k max = 6. We assume that the maximum delay index is l max = 14. The Doppler index of the ith path is uniformly drawn from the set [−k max , k max ] and the delay index belongs to [1, l max ] excluding the first path (l i = 0). We assume that the fractional Doppler κ i is uniformly distributed within [−1/2, 1/2], and the channel path gains {h j } are independently drawn from the complex Gaussian distribution N (0, 1/P ). The maximum number of iterations is set to be 15 for the iterative algorithms.
Here, we note that, all the detectors require the precision (or variance) of the noise. The UTAMP-based detectors developed in this work have the capability of noise precision estimation. However, all the other detectors including the AMP-based detectors assume that the noise precision is perfectly known.
We first examine the performance of various detectors in the  case of bi-orthogonal waveform. We assume that no fractional Doppler shifts exist, i.e., κ i = 0 and S = P , and the results are shown in Fig. 4, where VB and MP represent the variational Bayesian based detector [11] and the conventional message passing based detector [9], respectively. By comparing the results in Fig. 4 (a), (b), (c) and (d), we can see that, MP performs well when P = 6, but, with the increase of P , its performance degrades. This is because, with P increasing, the channel matrix becomes denser, which leads to the presence of short loops with a higher probability, significantly affecting the performance of the conventional MP algorithm. The VBbased detector has the similar trend. In contrast, the AMP and UTAMP-based detectors perform well, and they enjoy the diversity gain and achieve better performance with the increase of P . In all cases, the UTAMP-based detector delivers the best performance. To illustrate the convergence behaviors, we plot the BER performance of various detectors versus the number of iterations in Fig. 5 with P = 10 and SNR= 15dB. It can be seen that the UTAMP-based detection algorithm converges faster than others. With the assumption of factional Doppler shifts, we compare the BER performance of the AMP-based detector and the UTAMP-based detector versus SNR in Fig. 6. As channel matrix is not i.i.d. (sub-) Gaussian, UTAMP is more robust than AMP, which leads to a significantly better performance for the UTAMP-based detector, as demonstrated in Fig. 6. It can also be seen that, when P = 14, the performance of the AMP-based detector gets worse, and there is a huge performance gap between the AMP and the UTAMP-based detectors.
Next, we consider the rectangular waveform, and show the BER performance of the AMP and UTAMP based detectors versus SNR in Fig. 7. From Fig. 7, we can see that the UTAMP-based detector can still deliver significantly better performance than the AMP-based one, and their performance gap become larger when P = 14.
We then evaluate the performance of the detectors in a coded OTFS system, where the turbo receiver shown in Fig.  3 is employed. We use a rate-1/2 convolutional code with 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. Fig. 8 shows the BER performance of the AMP and UTAMP-based detectors, where the parameters are the same as those in Fig. 7. By comparing Fig. 7. with Fig. 8, it is interesting to find that the performance gaps between the AMP-based detector and the UTAMP-based detector become larger in the coded turbo system. It can also be seen that the turbo receiver can achieve much better performance (about 3.5−4dB at the BER of 10 −4 ) thanks to the iteration between the SISO detector and the SISO decoder.
Last, we examine the effectiveness of the SE-based BER performance prediction in Section VI. The coded OTFS system has exactly the same settings as those in Fig. 8 (a). The SE performance and the simulated performance versus SNR is shown in Fig. 9, where we can see that the predicted performance matches well with the simulated performance for the UTAMP-based detector. However, for the AMP-based detector, the predicated performance is no longer accurate, and the SE overestimated the performance severely. This is because the SE equation for AMP is no longer valid when the channel matrix deviates from the i.i.d. Gaussian matrix. Figure. 10 shows the predicated performance and simulated performance of the (UT)AMP-based receiver versus iteration number at SNR=8dB and 9dB, where it can be seen that the predicted performance matches well with the simulated performance for the UTAMP-based detector.

VIII. CONCLUSIONS
In this paper, to address the issues of OFTS detection when the number of channel paths is relatively large and the fractional Doppler shifts have to be considered, we have investigated the design of OTFS detectors based on (UT)AMP. In particular, the UTAMP-based detectors enjoy the structure of the channel matrix, allowing more efficient implementation while with enhanced performance due to the robustness of UTAMP. The investigations have also been extended to joint detection and decoding in a coded OTFS system with a turbo receiver. It has been demonstrated that the UTAMPbased detector can outperform the state-of-the-art detectors significantly, and the performance of the system with the UTAMP-based detector can be predicted well with the state evolution.