  Orthogonal time frequency space (OTFS) modulation can effectively convert a
doubly dispersive channel into an almost non-fading channel in the
delay-Doppler domain. However, one critical issue for OTFS is the very high
complexity of equalizers. In this letter, we first reveal the doubly block
circulant feature of OTFS channel represented in the delay-Doppler domain. By
exploiting this unique feature, we further propose zero-forcing (ZF) and
minimum mean squared error (MMSE) equalizers that can be efficiently
implemented with the two-dimensional fast Fourier transform. The complexity of
our proposed equalizers is gracefully reduced from
$\mathcal{O}\left(\left(NM\right)^{3}\right)$ to
$\mathcal{O}\left(NM\mathrm{log_{2}}\left(NM\right)\right)$, where $N$ and $M$
are the number of OTFS symbols and subcarriers, respectively. Analysis and
simulation results show that compared with other existing linear equalizers for
OTFS, our proposed linear equalizers enjoy a much lower computational
complexity without any performance loss.
