Orthogonal Time Sequency Multiplexing Modulation: Analysis and Low-Complexity Receiver Design

Orthogonal frequency division multiplexing (OFDM) is the physical-layer modulation scheme deployed in 4G and 5G mobile systems, where the wireless channel typically exhibits time-varying multipath fading due to mobility. OFDM is known to achieve a near-capacity performance over such channels when the Doppler effect is limited [1, 2, 3], but suffers from severe performance degradation in high-mobility environments [4]. Hence, new modulation techniques that are robust in both slow and fast time-varying channels are needed.

Recently, orthogonal time frequency space (OTFS) modulation has been proposed in [4], showing significant advantages over OFDM in high-mobility environments. OTFS places information symbols in the delay-Doppler (DD) domain to capture the channel geometry that models mobile terminals and reflectors in a high mobility scene. Leveraging on this representation, the OTFS modulator multiplexes each information symbol over 2D orthogonal basis functions (IFFT along Doppler and FFT along delay), which span across the entire time–frequency domain required to transmit a frame. The set of basis functions is designed to combat the dynamics of the time-varying multipath channel¹¹1A similar scheme to OTFS was independently proposed in [25] for underwater acoustic communications.. Further, it was shown in [5] that any 2-D orthogonal transformation (precoding) with constant modulus basis functions operating on the time-frequency domain enables the receiver to exploit maximum time-frequency diversity. Since the Fourier basis are constant modulus, OTFS guarantees that the information symbols experience the same signal-to-noise ratio (SNR). In the recent few years, there has been a number of efforts dedicated to the development of OTFS (e.g. [6, 7, 8, 9, 10, 5, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21] and references therein).

In this paper, we propose a novel single-carrier modulation scheme: orthogonal time sequency multiplexing (OTSM). The key idea is to multiplex information symbols in the delay-sequency domain, rather than the DD domain of OTFS, where sequency is defined as the number of zero-crossings per unit time interval²²2In the case of discrete Walsh functions, sequency denotes the number of sign changes per unit time. [22, 23]. Specifically, OTSM transforms the information symbols placed in the delay-sequency domain into the delay-time domain, followed by time-domain signal transmission and reception. Such domain transformation is realised by using the inverse Walsh-Hadamard transform (IWHT) along the sequency domain, instead of IFFT along the Doppler domain in OTFS, as shown in Fig. 1. In such a way, OTSM allows channel delay spread and Doppler spread to cause inter-symbol interference (ISI) along the delay and sequency dimensions, respectively, while remaining separable at the receiver, like in OTFS [4, 17]. Note that this separability cannot be achieved by OFDM, since channel delay spread and Doppler spread jointly cause interference in OFDM along the frequency dimension. Hence, single-tap equalization fails due to the loss of orthogonality between the OFDM sub-carriers. Our single carrier OTSM scheme uses only 1-D orthogonal WHT transform and is different from the multi-carrier OTFS schemes in [5], where arbitrary 2-D unitary transform (such as DFT, WHT, discrete prolate spheroidal sequences) is applied to the time-frequency domain.

For the proposed OTSM modulation, we derive its delay-sequency domain input-output relation and present a low complexity detection scheme³³3A preliminary version of the detection scheme was presented in [26].. Similar to OTFS, we find that OTSM’s information symbols experience approximately the same SNR at the receiver, thanks to the constant modulus WHT. As a result, OTSM offers similar performance to OTFS in both static and high mobility channels, but at lower complexity, since WHT only requires addition and subtraction operations.

Further, we introduce the use of zero-padding (ZP) between every block in the time domain to avoid inter-block interference to reduce the detection complexity and to simultaneously allow for the insertion of pilots for channel estimation. Then we propose a low complexity time-domain channel estimation method based on reconstruction of the delay-time channel from the time domain pilots⁴⁴4Note that the proposed channel estimation can also be employed for OTFS systems.. We compare the performance of OTFS and OTSM using the delay-time channel reconstruction method and observe that they offer similar performance. Finally, we show how an outer error-correcting code can be used to improve the error performance and reduce the pilot power required for accurate detection.

Overall, the proposed OTSM modulation offers the following advantages. The OTSM transceiver has low complexity (appealing for hardware implementation), but achieves the advantages of a multi-carrier system without sacrificing performance. Similar to OTFS, OTSM can be easily overlaid on top of existing OFDM based systems, where time-frequency samples can be generated using the relations given in Fig. 1 (IWHT and FFT) and then transmitted as an OFDM signal. Different from other single carrier and OFDM systems, OTSM has excellent performance in the presence of multiple Doppler paths, making it suitable for high mobility and under-water acoustic wireless communications.

Due to the use of WHTs, the time domain samples take integer values if the information symbols are integer. Hence, a smaller number of bits may be used to represent the transmit signal without incurring any quantization error. Thanks to this feature, OTSM is suitable for integer forcing linear receivers with significantly reduced complexity [27].

Channel estimation benefits from using a sparse representation of the channel. In OTFS, the delay-Doppler domain offers such sparse representation, when the channel Doppler shifts are integer multiples of the receiver Doppler resolution. However, the sparsity reduces significantly with fractional Doppler shifts, which are commonly present in the channel. The sequency domain may offer a sparsity similar to the one of OTFS with fractional Doppler in all cases.

The rest of the paper is organized as follows. In Section II, we discuss the basic OTSM concepts. In Section III, we present the OTSM system model followed by comparison with the OTFS scheme in Section IV. In Section V, we present a low complexity detection scheme. In Section VI, we propose a time-domain channel estimation algorithm for OTSM. We further propose a turbo decoder for OTSM in Section VII. Section VIII presents the simulation results and discussions followed by our concluding remarks in Section IX.

Notations: The following notations are used: $a$, $\bf{a}$, ${\bf A}$ represent a scalar, vector, and matrix, respectively; ${\bf a}(n)$ and ${\bf A}(m,n)$ represent the $n$-th and $(m,n)$-th element of ${\bf a}$ and ${\bf A}$, respectively; ${\bf A}^{\dagger}$, ${\bf A}^{*}$ and ${\bf A}^{n}$ represent the Hermitian transpose, complex conjugate and $n$-th power of ${\bf A}$. The set of $M\times N$ dimensional matrices with complex entries are denoted by ${\mathbb{C}}^{N\times M}$. Let $\circledast$ represent circular convolution, $\otimes$, the Kronecker product, $\circ$, the Hadamard product (i.e., the element wise multiplication) and, $\oslash$, the Hadamard division (i.e., the element wise division). Let $[.]_{M}$ denote the modulo-$M$ operation, $|\mathcal{S}|$ the cardinality of the set $\mathcal{S}$, $\mathrm{tr}(A)$, the trace of the square matrix ${\bf A}$, vec$({\bf A})$, the column-wise vectorization of the matrix ${\bf A}$ and ${\rm vec}_{N,M}^{-1}({\bf a})$ is the matrix formed by folding a vector ${\bf a}$ into a $N\times M$ matrix by filling it column wise. Let ${\bf F}_{N}$ and ${\bf W}_{N}$ be the normalized $N$ point discrete Fourier transform (DFT) matrix and the normalized $N$-point WHT matrix, respectively.

Traditionally the communication theory has been based on the complete orthogonal set of sine and cosine functions. The concept of frequency is a consequence of these basis functions being periodic and hence characterized by distinct frequencies. Even though frequency domain representation of signals offers several advantages including close resemblance to the physical channel models, there are other basis functions which can equally be used to represent a signal. The Walsh functions, introduced by Joseph L. Walsh in 1923, constitute another complete set of orthogonal functions, which assume only the values ‘+1’ and ‘-1’. This means that almost any waveform can be uniquely synthesized to any desired degree of accuracy by a linear combination of Walsh functions, [22, 23]. There are a number of formal definitions of Walsh functions in the literature. In this paper, we are primarily concerned with the sequency-ordered Walsh functions.

Consider the ZP-OTFS system, with the 2-D information symbols ${\bf X}^{\rm OTFS}\in\mathbb{C}^{M\times N}$ split as symbol vectors ${\bf x}_{m}^{\rm OTFS}\in\mathbb{C}^{N\times 1}$, similar to the delay-sequency domain symbol vectors ${\bf x}_{m}^{\rm OTSM}$. Following [29], the vector input-output relation for ZP-OTFS can be written as

where ${\bf V}_{m,l}$ and ${\boldsymbol{\nu}}_{m,l}$ (first column of ${\bf V}_{m,l}$) are the circulant Doppler spread matrix and Doppler spread vector, respectively, at the $l$-th delay tap experienced by ${\bf x}^{\rm OTFS}_{m-l}$, i.e.,

Recall from Fig. 1, the delay-sequency domain information symbols are related to the delay-Doppler domain symbols as

From (39) and Fig. 1, OTSM can also be interpreted as a 1-D orthogonal precoding, given by a cascade of IFFT and WHT, along the Doppler domain. Combining (37) and (39), we get

where the sequency spread matrix

and the sequency spread vector

The Doppler spread matrix ${\bf V}_{m,l}$ is a circulant matrix where as the sequency spread matrix ${\bf U}_{m,l}$ is a symmetric matrix. Moreover, the circular convolution along the Doppler domain in OTFS is converted to dyadic convolution in the sequency domain. In other words, the ordering of delay-Doppler channel coefficients is independent of the location of the information symbols in the delay-Doppler grid. However, in the case of delay-sequency channel coefficients, the ordering depends on the sequency index of the information symbol in the delay-sequency grid.

OTSM retains the key property of OTFS: all the information symbols experience approximately the same channel gain. The received signal energy $E^{\rm OTFS}(n,m)$ of each OTFS information symbol ${\bf X}^{\rm OTFS}(m,n)$ (assuming unit symbol energy at the transmitter) can be expressed in terms of the Doppler spread vectors as

where $||\cdot||$ represent the Euclidean vector norm. Similarly, the received signal power of each OTSM information symbol ${\bf X}^{\rm OTSM}(m,n)$ can be written as

From (42), it can be seen that the Doppler spread ${\boldsymbol{\nu}}_{m,l}$ and sequency spread ${\bf u}_{m,l}$ are related using unitary transformations. This means that the Euclidean norm of both these vectors are equal

From (43), (44) and (45), it can be concluded that $E^{\rm OTFS}(n,m)=E^{\rm OTSM}(n,m)$. Since DFT and WHT are both unitary transformations, the noise power remains the same in both Doppler and sequency domains, which means that the received information symbols in OTFS and OTSM have the same SNR. This shows that OTSM has the potential to offer similar error performance to OTFS but at much lower modulation/demodulation complexity.

Remark – In [31], the OTFS transmitter was interpreted as the inverse Zak transform on the delay-Doppler domain, which is based on $N$-point DFTs across the Doppler domain. Similarly, the OTSM transmitter can be interpreted as an inverse Walsh Zak transform on the delay-sequency domain, where the DFT in the traditional Zak is replaced by WHT.

For completeness, we summarize here the low complexity detection method proposed in [26]. As illustrated in Fig. 3, due to the time-domain ZP, the interference between the time domain blocks is prevented. As shown in Fig. 4, this allows the time-domain input-output relation in (10) to be split and independently processed as

where ${\bf s}=[{\bf s}_{0}^{\text{T}},\cdots,{\bf s}_{N-1}^{\text{T}}]^{\text{T}}$ and ${\bf r}=[{\bf r}_{0}^{\text{T}},\cdots,{\bf r}_{N-1}^{\text{T}}]^{\text{T}}$ and ${\bf G}_{n}$ is the time-domain channel at the $n$-th time-domain block. Note that all the $N$ time-domain blocks have an equal component of each delay-sequency domain information symbol due to the Walsh-Hadamard precoding. In this section, we use the well known Gauss Seidel (GS) method available in the literature [35, 36], for low complexity detection.

In the proposed detector, GS iteration is done on the matched filtered channel matrix blocks ${\bf R}_{n}={\bf G}^{{\dagger}}_{n}\cdot{\bf G}_{n}$. The matrix input-output relation in (46) after the matched filtering operation can be written as

where ${\bf R}_{n}={\bf G}^{{\dagger}}_{n}\cdot{\bf G}_{n}$, ${\bf z}_{n}={\bf G}^{{\dagger}}_{n}\cdot{\bf r}_{n}$ and $\mathbf{\bar{\text{$\bf w$}}}_{n}={\bf G}^{{\dagger}}_{n}\cdot{\bf w}_{n}$. The GS method is used to iteratively find the least squares solution

of the $M$-dimensional linear system of equations in (47).

Let ${\bf D}_{n}$ and ${\bf L}_{n}$ be the matrix containing the diagonal elements and the strictly lower triangular elements of the matched filter matrix ${\bf R}_{n}$. From [35, 36], the GS iterative method for finding the estimate of ${\bf s}_{n}$ in each iteration is then given as

where ${\bf T}_{n}\in\mathbb{C}^{M\times M}$ is the GS iteration matrix. The vector $\hat{\bf s}_{n}^{(i)}\in\mathbb{C}^{M\times 1}$ represents the estimate of the transmitted time-domain samples of the $n$-th block in the $i$-th iteration. The delay-sequency domain information symbols in the $i$-th iteration is then given as

where $\mathcal{D}(.)$ denotes the decision making function replacing all the elements of the input with the nearest QAM symbol (in terms of the Euclidean distance). The hard decision estimates are transformed back to the time domain to update the time domain estimate to be used in the next iteration.

where $\delta$ is the relaxation parameter to improve the detector convergence for higher modulation schemes like 64-QAM, [35, 36, 29]. As initial estimates to the iterative detection, we chose ${\bf X}^{(0)}={\bf 0}_{M\times N}$ or the MMSE solution presented in [26] yielding faster convergence.

In this section, we propose a low complexity OTSM channel estimation algorithm. Due to the interleaved time-domain pilots, the time domain channel responses in (29) for the $l$-th delay tap at time instants $mT/M+nT$, are directly estimated in delay-time domain. A linear or spline interpolation is performed to reconstruct the time domain channel coefficients for the entire frame for each delay tap $l$. We note that, a similar scheme was proposed in [32] for OTFS by estimating channel coefficients in delay-time domain using spline interpolation. However, we show that for OTSM, linear interpolation is sufficient. Moreover, the proposed channel estimation differs from the single pilot scheme for OTFS in [14], since our channel estimation is performed in the delay-time domain rather than the DD domain in OTFS. This is because our OTSM delay-time detection algorithm does not use the delay-sequency channel coefficients.

In this section, we propose a turbo decoder for coded OTSM systems. At the transmitter, the delay-sequency domain information bits are randomly interleaved before converting them to QAM symbols, which is then OTSM modulated to generate the time domain signal. At the receiver, we use the low complexity iterative time domain detector summarized in Section V to obtain the time domain estimates in each iteration followed by a turbo iteration where a LDPC decoder is used to improve the current symbol estimates. One turbo iteration includes at least one detector and decoder iteration each. The number of detector and decoder iterations per turbo iteration can be set according to required BER and complexity requirements.

Fig. 8 shows the operation principle of the proposed turbo decoder. The information symbols estimates at the output of the detector is soft demodulated to obtain the bit LLRs, which are then de-interleaved and passed to a LDPC decoder. The LDPC decoder outputs the the coded bits, which are then interleaved, and converted to QAM symbols, and OTSM modulated to get back an improved estimate of the time-domain sample. The improved estimate ${\bf s}^{(i-1)}$ is used to generate the estimate of the time-domain samples to be used for the next iteration ${\bf s}^{(i)}$, where the superscript $i\geq 0$ represents the $i$-th turbo iteration. The initial time-domain estimate is initialized as ${\bf s}^{(0)}={\bf 0}_{NM\times 1}$.

In the following simulations, we generate OTFS frames for $N=64$ and $M=64$. The sub-carrier spacing $\Delta f$ is 15 kHz and the carrier frequency is 4 GHz. The maximum delay spread (in terms of integer taps) is set to be 4 ($l_{\max}=3$), which is approximately 4 ${\mu}s$, thereby the maximum number of delay taps as seen by the discrete receiver is $L=4$. The channel delay model is generated according to the standard EVA model (with a speed of 120 km/h) in [37] with the Doppler shift for the $i$-th path generated from a uniform distribution $U(0,\nu_{max})$, where $\nu_{max}$ is the maximum Doppler shift. For BER plots, $10^{5}$ frames are send for every point in the BER curve. For FER plots, all simulations run for a minimum of $10^{4}$ frames or until 100 frame errors are encountered. BER is plotted to show uncoded performance, while FER is used when an outer coding scheme is applied. We use the standard LDPC codes with parity check matrices from the 3GPP BG1 scheme of 5G NR [38], with code lengths 672, 3840, 8192.

Fig. 9 compares the OTSM uncoded BER performance with perfect CSI with OFDM and OTFS using the two low complexity equalizers (single tap and iterative) presented in Section V. The OTSM offers better performance than OFDM and a similar performance to OTFS, but with lower transmission and detection complexity. The concatenation with a long code reduces the performance gap between uncoded OTSM and uncoded OFDM as illustrated in Fig. 10. We plot the FER performance of OTSM compared with bit interleaved coded (BIC) OFDM for different codeword sizes of rate $=1/2$. For fair comparison in terms of detection complexity with OFDM, we use the single tap equalizer for both OTSM and OFDM. As seen in Fig. 10, for a FER of $10^{-2}$, coded OTSM has $4$ dB gain over OFDM when using the short code ( $L_{\rm LDPC}=672$ and rate $1/2$), and a $2$ dB gain when using the long code ( $L_{\rm LDPC}=8192$ and rate $1/2$).

In [26] we showed that uncoded OTSM and OTFS significantly outperform the uncoded single carrier (SC) scheme due to the time-domain precoding. In Fig. 11, we show the same comparison for the coded case. As expected, the use of a channel code reduces their performance gap, since the code can help SC to recover some diversity from the channel, while uncoded OTSM already achieves a high diversity gain, and coding provides slightly smaller returns, as demonstrated in Fig. 11 for both rates 1/2 and 3/4 with a codeword length $L_{\rm LDPC}=3840$ bits and turbo decoding with 4-QAM. Overall, the coded OTSM outperforms the coded SC.

Fig. 12 and Fig. 13 shows the OTSM uncoded BER and coded FER performance for 4, 16 and 64 QAM with the proposed channel estimation (with linear interpolation) for different excess pilot power $\beta$ (dB). We use an LDPC codeword of length $L_{\rm LDPC}=672$ to encode the information bits at the transmitter. The turbo iterations for the coded case are stopped either when all the $\lfloor\frac{NM^{\prime}Q}{L_{\rm LDPC}}\rfloor$ LDPC codewords satisfy the parity check condition or when a maximum of 5 turbo iterations is reached.

It can be noted that, for coded OTSM, similar performance to the perfect CSI case is achieved for 16 and 64 QAM with less pilot power as compared to the un-coded case. The required pilot power can be further reduced with longer codewords.

We proposed OTSM as a new modulation scheme that multiplexes the information symbols on the time and sequency shifted versions of a basic rectangular pulse and derived its input-output relation in the delay-sequency domain. By inserting zero padding between every block in the time domain, we proposed a low complexity channel estimation and detection for OTSM. It was shown in simulations that OTSM provides a significantly better performance than OFDM and SC transmission and a similar performance to OTFS, but at much lower complexity thanks to the WHT. This makes OTSM a promising solution for future high mobility communication systems requiring low complexity transceivers. Further analysis of channel representation, low complexity channel estimation and detection in the delay-sequency domain will be explored in future work.