1

Low Complexity Modem Structure for OFDM-based
Orthogonal Time Frequency Space Modulation

arXiv:1710.00655v1 [] 2 Oct 2017

Arman Farhang, Ahmad RezazadehReyhani, Linda E. Doyle, and Behrouz Farhang-Boroujeny
Abstract—Orthogonal time frequency space (OTFS) modulation is a two-dimensional signaling technique that has recently
emerged in the literature to tackle the time-varying (TV) wireless
channels. OTFS deploys the Doppler-delay plane to multiplex the
transmit data where the time variations of the TV channel are
integrated over time and hence the equivalent channel relating
the input and output of the system boils down to a time-invariant
one. This signaling technique can be implemented on the top of
a given multicarrier waveform with the addition of precoding
and post-processing units to the modulator and demodulator. In
this paper, we present discrete-time formulation of an OFDMbased OTFS system. We argue against deployment of window
functions at the OTFS transmitter in realistic scenarios and
thus limit any sort of windowing to the receiver side. We study
the channel impact in discrete-time providing deeper insights
into OTFS systems. Moreover, our derivations lead to simplified
modulator and demodulator structures that are far simpler than
those in the literature.

I. I NTRODUCTION

W

HILE orthogonal frequency division multiplexing
(OFDM) modulation scheme achieves a performance
near the capacity limits in linear time-invariant channels, it
leads to a poor performance in doubly dispersive channels.
This is due to the large amount of interference that is imposed
by the channel Doppler spread. The common approach to cope
with this issue in the existing wireless standards such as IEEE
802.11a and digital video broadcasting systems is to shorten
OFDM symbol duration in time so that the channel variations
over each OFDM symbol are negligible. However, this reduces
the spectral efficiency of transmission since the cyclic prefix
(CP) length should remain constant. A thorough analysis of
OFDM in such channels is conducted in [1]. Another classical
approach for handling the time-varying (TV) channels is to
utilize filtered multicarrier systems that are optimized for a
balanced performance in doubly dispersive channels, [2].
Recently, new signaling techniques have emerged in the
literature to tackle the TV channels, [3], [4]. In [3], the
authors introduce a new waveform called frequency-division
multiplexing with a frequency-domain cyclic prefix (FDMFDCP). This waveform, at its current stage, outperforms
OFDM in channels with high Doppler and low delay spread.
However, its performance in channels with high Doppler and
medium to high delay spread is yet to be understood, [3].
Orthogonal time frequency space (OTFS) modulation,
which is the main focus of this paper, is another emerging
This publication has emanated from research conducted with the financial
support of Science Foundation Ireland (SFI) and is co-funded under the
European Regional Development Fund under Grant Number 13/RC/2077.
A. Farhang and L. E. Doyle are with Trinity College Dublin, Dublin 2,
Ireland (e-mail: {farhanga, ledoyle}@tcd.ie).
A. RezazadehReyhani and B. Farhang-Boroujeny are with the University
of Utah, USA (e-mail: {Ahmad.Rezazadeh, farhang}@ece.utah.edu).

signaling technique that is capable of handling the TV channels. OTFS was first introduced in the pioneering work of
Handani et al., [5], where the two dimensional (2D) Dopplerdelay domain was proposed for multiplexing the transmit data.
OTFS modulation is a generalized signaling framework where
precoding and post-processing units are added to the modulator and demodulator of a multicarrier waveform allowing
for taking advantage of full time and frequency diversity gain
of doubly dispersive channels. This process also coverts the
TV channel to a time-invariant one. This modulation scheme
has two stages. First, a set of complex data symbols in the
Doppler-delay domain are converted to the time-frequency
domain through an inverse symplectic finite Fourier transform (SFFT−1 ), [5]. In the second stage, the resulting timefrequency samples are fed into a multicarrier modulator to
form the time domain transmit signal. The reverse operations
are performed at the receiver to map the received signal back
to the Doppler-delay domain. In addition, to further improve
the channel sparsity in the Doppler-delay space, application of
proper window functions to the 2D signals, after the SFFT−1
at the transmitter and before the SFFT block at the receiver,
is proposed in [5]. However, very little is said on the choice
of such windows. Moreover, although the OTFS formulations
presented in [5] are kept general, the numerical results presented there seem to be limited to the case where OFDM is
used for transmission of the generated time-frequency signals.
In this paper, we present a discrete-time formulation of
OTFS modulation while limiting ourselves to the case where
OFDM is used for time-frequency signal modulation. This
study reveals that in realistic scenarios this formulation leads to
highly simplified transmitter and receiver structures compared
with the existing ones in [5]–[8]. We note that window
functions (at the transmitter and receiver) that may be effective
in converting the channel to a sparse one in the Doppler-delay
space require knowledge of channel variations on a given data
packet at the transmitter which obviously is unknown. Hence,
it is hard to say any effective window in this sense could be
applied at the transmitter. On this basis, we will ignore the
windowing step of the OTFS at the transmitter side. At the
receiver side, on the other hand, an iterative channel estimation
and equalization may allow the use of an effective window that
leads to a sparse channel, e.g. [9], [10]. This is an interesting
topic that falls out of the scope of this paper and may be left
for future studies. In this paper, we include the windowing of
the time-frequency signal at the receiver side, but limit our
discussion to the case where this is a separable window along
the time and frequency dimensions and emphasise on channel
independent window functions with some reasonable impact.
The rest of this paper is organized as follows. In Section II,
we present OFDM-based OTFS system model in its general

2

OFDM
OFDM-based OTFS Transmitter
xk,l

SFFT−1

OFDM
Modulator

ym,n

OFDM-based OTFS Receiver
LTV Channel

OFDM
Demodulator

zm,n

Windowing
+

x̃k,l

SFFT

Fig. 1. OTFS transmitter and receiver structure.

form. Section III presents the channel impact in the Dopplerdelay domain. In Section IV, we present our proposed OFDMbased OTFS modem structure. We analyze the computational
complexity of our proposed structure in Section V and finally,
conclude the paper in Section VI.
Notations: Throughout the paper, matrices, vectors and
scalar quantities are denoted by boldface uppercase, boldface
lowercase and normal letters, respectively. [A]mn , and A−1
represent the mnth element, and the inverse of A, respectively.
The function vec{A} vectorizes A by stacking its columns
on the top of one another in a column vector. The functions
circ{a}, and diag{a} form a circulant matrix whose first
column is the vector a and a diagonal matrix with the diagonal
elements in a, respectively. Im and 0m×n are the identity
matrix of size m and an all zero m×n matrix, respectively. The
superscripts (·)T , (·)H and (·)∗ indicate transpose, conjugate
transpose and conjugate operations, respectively. Finally, the
operators ⊙, ⊗, ⊛, and ((·))N represent elementwise multiplication, Kronecker product, 2D circular convolution, and
modulo-N operations, respectively.
II. OFDM- BASED OTFS S YSTEM
We consider an OTFS system transmitting a block of M ×N
Doppler-delay quadrature amplitude modulated (QAM) data
symbols xk,l where k = 0, . . . , M − 1 and l = 0, . . . , N − 1.
In OTFS modulation, the data symbols, xk,l , are first converted
to the time-frequency domain through the SFFT−1 operation,
ym,n =

M−1
−1
X NX

xk,l bk,l (m, n),

(1)

k=0 l=0
mk

nl

1
e−j2π( M − N ) . Due to the discuswhere bk,l (m, n) = √MN
sion in Section I, we ignore transmit windowing step of OTFS.
Hence, the time-frequency samples ym,n are directly fed into
the OFDM transmitter to form the OTFS transmit signal,

S = ACP FH
M Y,

(2)

where Y is the M × N matrix containing the time-frequency
samples ym,n on its mnth elements. FM is the normalized
M -point discrete Fourier transform (DFT) matrix with the
−j2πpq
elements [FM ]pq = √1M e M , for p, q = 0, . . . , M − 1.
T T
ACP = [GT
CP , IM ] is the cyclic prefix (CP) addition matrix
where the MCP × M matrix GCP is formed by taking the
last MCP rows of the identity matrix IM and MCP is the CP
length. Finally, the (M + MCP ) × N matrix S includes the
OFDM time domain transmit signals on its columns. After
parallel to serial conversion of S, the OTFS transmit signal at
the baseband can be formed as s = vec{S}.

The received signal samples after transmission over a linear
L−1
time varying (LTV) channel with the length L, {h(κ, ℓ)}ℓ=0
,
can be obtained as
L−1
X
r(κ) =
h(κ, ℓ)s(κ − ℓ) + ν(κ),
(3)
ℓ=0

where ν(κ) ∼ CN (0, σν2 ) is the channel noise. Assuming
MCP ≥ L, the received OFDM symbols are free of intersymbol interference. Thus, the received OFDM symbol n at
the output of the OFDM demodulator can be written as
zn = FM Hn FH
M yn + ν n ,

(4)

th

where yn is the n column of Y, Hn = RCP H̆n ACP ,
RCP = [0M×MCP , IM ] is the CP removal matrix, and H̆n
is the LTV channel matrix realizing the linear convolution
operation, (3), on the samples of the nth OFDM symbol.
The vector ν n contains the noise samples at the OFDM
demodulator output and zn = [z0,n , . . . , zM−1,n ]T . As the
second step of the OTFS demodulator, the time-frequency
samples, zm,n , are windowed using a receive window function
wm,n , and then the result is converted back to the Dopplerdelay domain through a SFFT operation. This process can be
represented as
x̃k,l =

M−1
−1
X NX

wm,n zm,n b∗k,l (m, n),

(5)

m=0 n=0

where k = 0, . . . , M − 1, and l = 0, . . . , N − 1. It is shown
in [5] that the OTFS receiver output samples, x̃k,l s, can be
obtained as the 2D circular convolution of the QAM data symbols xk,l and a time-invariant channel impulse response in the
Doppler-delay domain. The OFDM-based OTFS modulation
and demodulation process is shown in Fig. 1. More details and
derivations on the baseband channel response in the Dopplerdelay domain are presented in the following section.
III. C HANNEL I MPACT
To study the channel impact, in this section, we expand the
formulation presented in Section II. In addition to providing a
deeper insight into OTFS, this paves the way for the derivation
of a novel modem structure in Section IV. The SFFT−1
operation in (1) can be represented as
Y = FM XFH
N,

(6)

where X is an M ×N matrix containing the data symbols xk,l
∗
∗
on its klth elements. From (6), yn = FM XfN,n
where fN,n
th
is the n column of the N -point DFT matrix. Consequently,
(4) can be expanded as
zn

=

∗
FM Hn FH
M FM XfN,n + ν n

=

∗
FM Hn XfN,n
+ ν n.

(7)

3

Forming an M × N matrix Z = [z0 , . . . , zN −1 ], the receiver
PSfrag replacementsdκ
windowing as well as the SFFT operation shown in (5) can
be rearranged as
X̃ = FH
M (W ⊙ Z)FN ,

c
r
X̃ = FH
M (W ZW )FN ,

(9)

c
diag{[w0c , . . . , wM−1
]},

r

where W
=
and W
=
r
diag{[w0r , . . . , wN
]}.
−1
To derive a clearcut representation of the channel effect on
the transmit data symbols xk,l s, we expand the nth column of
the matrix X̃ as
x̃n

=
=

c
r
FH
M (W ZW )fN,n
N
−1
X
j2πni
1
c
√ FH
zi wir e− N ,
W
M
N
i=0

(10)

N −1
j2πni
1
c X
∗
Hi XfN,i
wir e− N + ν̃ n
x̃n = √ W
N
i=0
N −1 N −1
j2π(n−k)i
1
c X X
W
Hi xk wir e− N
+ ν̃ n
N
i=0
k=0

=W

c

N
−1
X

H((n−k))N xk + ν̃ n ,

k=0

where ν̃ n =
c
FH
M W FM , and

√1 FH Wc
N M

Hk =

PN −1
i=0

ν i wir e−

N −1
j2πki
1 X
Hi wir e− N .
N i=0

(11)
j2πni
N

, W

c

=

(12)

Next, defining an M N × M N block circulant matrix HBC =
T
T
circ{[HT
0 , . . . , HN −1 ] }, the M N × M N block diagonal
c
c
windowing matrix W = IN ⊗ W , the set of equations (11),
for n = 0, 1, . . . , N − 1, can be combined together to obtain
c

d̃ = (W HBC )d + vec{Ṽ},

(13)

where d̃ = vec{X̃}, d = vec{X}, and Ṽ = [ν̃ 0 , . . . , ν̃ N −1 ].
From (13), one may realize that if the submatrices Hn in HBC
are circulant, i.e. the channel can be assumed time-invariant
c
over each OFDM symbol, the multiplication of W HBC
to d realizes the 2D circular convolution of the windowed
Doppler-delay channel impulse response HDD,w with the data
c
matrix X. This is due to the fact that the matrices W ,
and HBC are block circulant with circulant submatrices and
their multiplication result in a matrix preserving their circulant
property. Consequently, X̃ can be written as
X̃ = HDD,w ⊛ X + Ṽ,

IDFT

P/S

M

Z −1

.
.
.
M

N -point
IDFT

P/S

N -point
IDFT

CP

.
.

.
.
.

s
Addition

.

P/S

Fig. 2. Our proposed OFDM-based OTFS modulator structure.

where the columns of the M × N matrix HDD,w include
the first columns of the matrices Hn that are windowed by
c
the window function wm
in the delay domain. In particuc
lar, the elements kl of HDD,w are equal to [W Hl ]k0 for
k = 0, . . . , M − 1 and l = 0, . . . , N − 1.
As a final note here, we note that (13) is a linear system
of equations that relates d̃ to d. It, thus, may be used as a
basis to derive linear detectors such as zero-forcing (ZF) and
minimum mean square error (MMSE) ones or to develop soft
detectors/equalizers.
IV. P ROPOSED M ODEM S TRUCTURE

Substituting zi from (7) into (10), we have

=

N -point

Z −1

(8)

where the M × N matrix X̃ contains the samples x̃k,l at the
OTFS receiver output and the 2D window matrix W includes
wm,n on its mnth elements. As mentioned in Section I, here,
we consider the general class of separable receiver window
c
c
functions, i.e. wm,n = wm
wnr , where the functions wm
and
r
wn window the columns and rows of Z, respectively. In this
case, (8) can be written as

c

M

(14)

As discussed in the previous sections, our focus in this paper
is on the general class of channel independent and separable
window functions that are only applied at the receiver. In practical systems, without application of a window, the Dopplerdelay channel impulse response along the delay dimension
remains sparse and has the support of L ≪ M . Any channel
independent window along the frequency dimension, before
application of the SFFT, translates into a circular convolution
along the delay dimension. Most likely, this increases the
support of the channel impulse response, and hence, degrades
the channel sparsity. In contrast, abrupt start and end of
the subcarrier signals along the time dimension in the timefrequency signal matrix Z translates to a non-sparse impulse
response along the Doppler dimension. On these bases, we
propose utilization of a rectangular window along the frequency domain, while using a window with smooth corners
along the consecutive OFDM symbols in time.
Next, we recall that the SFFT−1 operation in (1) can be
represented as Y = FM XFH
N . Inserting this into (2), one
may realize that the IDFT operation at OFDM modulator
and the M -point DFT operation in SFFT−1 block cancel out.
Consequently, (2) boils down to
S = ACP XFH
N.
FH
N

(15)

In (15), the operation X times
can be implemented
through a set of M IDFT operations of size N that are applied
to the rows of X. CPs are then added to the columns of the
resulting matrix. Fig. 2 presents a system structure that takes
the QAM symbol elements of X (denoted by the sequence dκ ),
distributes them as inputs to the M IDFT blocks, serializes and
interleaves the results, and finally adds a CP prior to each block
of M samples at the output. The output here is the vectorized
form of the matrix S.

4

TABLE I
C OMPUTATIONAL C OMPLEXITY OF D IFFERENT M ODEM S TRUCTURES
Structure

Number of modulator CMs
M N log2 M +

OTFS mod./demod. in [5]

MN
2
MN
2

OFDM mod./demod.
Our proposed mod./demod.

MN
2

log2 M
log2 N

r
wn

replacements
CP

M

r
Removal
Z

N -point
DFT

P/S

−1

M

Z −1

.
.
.
M

N -point
DFT

P/S

.
.

.
.
.
N -point
DFT

d˜κ

.

Fig. 3. Our proposed OFDM-based OTFS demodulator structure.

To derive our proposed OTFS demodulator structure, we
expand Z as
∗
∗
= FM [H0 XfN,0
, . . . , HN −1 XfN,0
] + V,

M N log2 M +
MN
2
MN
(1
2

MN
2

(1 + log2 N )

log2 M
+ log2 N )

the complexity by combining the inverse SFFT and SFFT
blocks with the OFDM modulator and demodulator blocks,
respectively. Moreover, noting that in practical systems the
number of OFDM symbols, N , in each data packet is much
smaller than the FFT size, M , one will observe that our
proposed OTFS modulator and demodulator blocks may have a
significantly lower complexity than their OFDM counterparts.
VI. C ONCLUSION

P/S

∗
∗
, . . . , FM HN −1 XfN,N
Z = [FM H0 XfN,0
−1 ] + V

log2 N

Number of demodulator CMs

(16)

c

where V = [ν 0 , . . . , ν N −1 ]. Replacing W with IM in (9),
while using (16), one realizes that similar to the transmitter,
the DFT operation at the OFDM demodulator and the IDFT in
the SFFT block cancel out. As a result, (9) can be expanded
as
∗
r
∗
X̃ = [w0r H0 XfN,0
, . . . , wN
−1 HN −1 XfN,N −1 ]FN + Ṽ, (17)
∗
where the M ×1 vectors wnr Hn XfN,n
are the OFDM received
symbols after the CP removal and application of the window
coefficients wnr . Also, Ṽ = FH
M V̄FN . Equation (17) shows
that after CP removal, OTFS demodulator only requires scaling
the OFDM symbols with the scalar wnr and application of
DFTs (of size N ) to the rows of the result. This leads to the
OTFS demodulator structure that is presented in Fig. 3. Here,
the output sequence d˜κ is the serialized elements of X̃.

V. C OMPLEXITY A NALYSIS
This section focuses on the computational complexity of
the modulator and demodulator structures that were presented
above and compares them with their counterparts in [5] as
well as those of OFDM. Table. I presents a summary of the
computational complexity of different modulator/demodulator
structures in terms of the respective number of complex
multiplications (CMs). Clearly, the original OTFS structures
that have been presented in [5] and elsewhere, [6]–[8], are significantly more complex than their OFDM counterparts. This is
because of the separation of the inverse SFFT and SFFT blocks
from the modulator and demodulator blocks, respectively. The
OTFS structure proposed in this paper substantially reduces

In this paper, we studied OFDM-based OTFS modulation
scheme. We presented the discrete-time formulation of such
systems while investigating the channel impact on the transmit
data symbols. An interesting finding of our study is that the
SFFT−1 /SFFT and OFDM modulator/demodulator blocks in
OTFS systems can be combined. This led us to a design of
low complexity modulator and demodulator structures. Our
complexity analysis revealed that our proposed OTFS modem
structure offers a great amount of savings in computational
complexity compared to the existing structures.
R EFERENCES
[1] T. Wang, J. G. Proakis, E. Masry, and J. R. Zeidler, “Performance degradation of OFDM systems due to Doppler spreading,” IEEE Transactions
on Wireless Communications, vol. 5, no. 6, pp. 1422–1432, June 2006.
[2] B. Farhang-Boroujeny, “Filter bank multicarrier modulation: A waveform candidate for 5G and beyond,” Advances in Electrical Engineering,
pp. 1–25, 2014.
[3] T. Dean, M. Chowdhury, and A. Goldsmith, “A new modulation technique for Doppler compensation in frequency-dispersive channels,” in
Submitted to IEEE PIMRC, 2017.
[4] A. Monk, R. Hadani, M. Tsatsanis, and S. Rakib, “OTFS - Orthogonal
time frequency space,” arXiv preprint arXiv:1608.02993, 2016.
[5] R. Hadani, S. Rakib, M. Tsatsanis, A. Monk, A. J. Goldsmith, A. F.
Molisch, and R. Calderbank, “Orthogonal time frequency space modulation,” in IEEE Wireless Communications and Networking Conference
(WCNC), March 2017, pp. 1–6.
[6] S. Rakib and R. Hadani, “Orthogonal time frequency space
communication system compatible with OFDM,” Jan. 5 2017,
WO Patent App. PCT/US2016/039,662. [Online]. Available:
http://www.google.com/patents/WO2017003952A1?cl=en
[7] ——, “Orthogonal time frequency space modulation system for the
Internet of Things,” Feb. 2 2017, US Patent App. 15/143,323. [Online].
Available: https://www.google.com/patents/US20170033899
[8] R. Hadani and S. Rakib, “Compatible use of orthogonal time frequency
space modulation within an LTE communication system,” Mar. 23
2017, WO Patent App. PCT/US2016/052,524. [Online]. Available:
https://www.google.com/patents/WO2017049303A1?cl=en
[9] P. Raviteja, K. T. Phan, Q. Jin, Y. Hong, and E. Viterbo, “Lowcomplexity iterative detection for orthogonal time frequency space
modulation,” arXiv preprint arXiv:1709.09402, 2017.
[10] L. A. Li, H. Wei, Y. Huang, Y. Yao, W. Ling, G. Chen, P. Li, and
Y. Cai, “A simple two-stage equalizer with simplified orthogonal time
frequency space modulation over rapidly time-varying channels,” arXiv
preprint arXiv:1709.02505, 2017.

