# Complexity Reduction of MLSE and MAP Equalizers Using Modified Prolate Basis Expansion
## 1 Introduction  
Reflection, refraction, and diffraction are propagation phenomena that cause many delayed replicas of the transmitted signal to reach the receiver. If the maximum delay of these replicas \(\tau_{max}\) is close to or greater than the symbol period \(T\), then each received symbol possesses energy from its neighbors. This impairment is known as intersymbol interference (ISI), and it greatly degrades system performance. A common approach to counteracting ISI is the use of orthogonal frequency division modulation (OFDM), which permits low-complexity frequency-domain equalization in low-mobility environments. However, OFDM has two major drawbacks: high sensitivity to Doppler spread, dependent on the system's mobility, and a high peak-to-average power ratio (PAPR), proportional to the length of the Fourier transform. In high carrier frequency bands (e.g., 60-70 GHz), even a small movement in the transceivers can cause a high Doppler spread, provoking intercarrier interference and long transmission latencies [1]. To avoid excessive PAPR while complexity equalization remains low in the frequency domain, the discrete-Fourier-transform (DFT)-Spread OFDM has been employed. Unfortunately, as noted in [2; 3], frequency-domain equalization is not a computationally advantageous strategy when the channel is rapidly time-varying. Hence, single carrier transmission remains as an alternative considered in standards such as IEEE 802.11 ad wireless local area networks (WLAN) [4], IEEE 802.15.3 high data rate wireless multi-media networks [5], IEEE 802.16 air interface for broadband wireless access systems [6], and the proposed standard IEEE 802.11 ay [7]. Focusing on single carrier transmission, a common approach for dealing with ISI is a channel equalizer, and they can be classified according to linearity. Linear equalizers, such as the minimum mean square error (MMSE) and zero-forcing (ZF), present low computational complexity, but they perform poorly when the channel presents deep notches in frequency. In contrast, non-linear equalizers, such as the decision feedback equalizer (DFE), the maximum likelihood sequence estimation (MMSE), and the maximum a posteriori probability (MAP), are computationally intensive algorithms; however, they significantly outperform the linear equalizers [8]. The MLSE equalizer finds the sequence of data symbols with the highest probability of being transmitted given the received signal, usually using the Viterbi algorithm. The MAP equalizer, meanwhile, is a symbol-by-symbol estimator, usually based on the Bahl, Cocke, Jelinek, and Raviv algorithm (BCJR) [9]. Although MLSE and MAP are the most effective equalizers, their implementation becomes infeasible due to excessive computational complexity when the channel impulse response (CIR) lasts several symbol periods or the data symbol alphabet is large. Recent works that use variations of these equalization techniques can be found in [10; 11; 12]. In [10] the authors compared the performance of detecting quadrature phase shift keying (QPSK) in a super-Nyquist wavelength division multiplexing system as a QPSK and quadrature duobinary (QDB) signal using MLSE and MAP equalizers with different detection schemes, and they concluded that QDB had the better performance. The authors in [11] reduced the complexity of faster-than-Nyquist (FTN) system receivers designing an MMSE-based channel shortening before the MLSE detection. Exact closed-form asymptotic expressions for symbol and bit error probability for arbitrary constellations and input distributions are presented in [12]. In order to reduce the computational complexity, sub-optimal algorithms [8] have been used, such as reduced state sequence estimation (RSSE), delayed decision feedback sequence estimation (DDFSE), the M-algorithm, Max-Log-MAP, Log-MAP, and other recent ideas including the reduced-state soft-output Viterbi equalizer [13] and the estimation of channel sparsity to assist in the detection of the transmitted sequence [14].