# Complexity Reduction of MLSE and MAP Equalizers Using Modified Prolate Basis Expansion
## 2 Materials and Methods
### Proposed MLSE and MAP Equalizers  
From the description presented of the MLSE and MAP algorithms, it can be seen that both require calculating the parameter \(\hat{y}_{l}|\mathbf{b}_{l}\) in order to obtain the estimated data. Such a parameter corresponds to the noiseless received signal when a specific \(\mathbf{b}_{l}\) is transmitted through the channel \(\mathbf{h}\). Note that \(\tilde{y}_{l}|\mathbf{b}_{l}\) is highly dependent on the current communication channel. Moreover, the iterative computation of the objective functions Equations (13) and (16) leads to a highly demanding computational problem, which increases with the cardinality M of the transmitted alphabet and the length of the CIR. In order to deal with the latter, the use of BEM is proposed for representing \(\mathbf{h}\) employing MPFs. Thus, using Equations (2) and (3), \(\tilde{y}|\mathbf{b}_{l}\) is approximated by  
\[\hat{y}_{l}|\mathbf{b}_{l}\approx\sum_{k=0}^{K-1}w_{l,k}\left[\sum_{p=0}^{P-1}h_{p }^{(k)}b_{l-p}\right]=\sum_{k=0}^{K-1}w_{l,k}\left[g_{l}^{(k)}|\mathbf{b}_{l} \right], \tag{17}\]  
where \(g_{l}^{(k)}|\mathbf{b}_{l}=\sum_{p=0}^{P-1}h_{p}^{(k)}b_{l-p}\) is the response of the \(k\)-th sub-channel \(\mathbf{h}^{(k)}\) when the sequence \(\mathbf{b}_{l}\) is transmitted.  
Equation (17) shows that \(\hat{y}_{l}|\mathbf{b}_{l}\) is the weighted sum of the data signal \(\mathbf{b}_{l}\) filtered by each function of the basis \(\{\mathbf{h}^{(k)}\}\). It is important to note that such a basis can expand any channel realization that satisfies the conditions of maximum spread delay and the particular shape of the filters, while the weights \(w_{l,k}\) are the dependent values of each CIR. Therefore, it is possible to precompute and store \(g_{l}^{(k)}|\mathbf{b}_{l}\) for each function and each combination of data symbols. The desired \(\tilde{y}_{l}\) can be obtained by weighting \(g_{l}^{(k)}|\mathbf{b}_{l}\) with the \(w_{l,k}\) that corresponds to the current channel realization. For that reason, all the \(M^{P}\) possible outputs must be saved in a read-only memory for each of the \(K\) functions in the basis, resulting in \(KM^{P}\) memory locations.  
The equalizers based on orthogonal functions, hereafter referred to as orthogonal MLSE and orthogonal MAP, can be implemented using a methodology split into two stages. The first stage consists of computing a priori information, which will be calculated only once, throughout the following steps:  
* Obtain the kernel of the required expansion \(\mathbf{C}_{h}\) according to [17; 18].
* Solve Equation (4) to find the eigenfunctions \(\mathbf{h}^{(k)}\) and eigenvalues \(\lambda_{k}\) associated with the kernel.
* Sort the eigenvalues in descending order.
* Select the \(K\) eigenfunctions corresponding to the eigenvalues with higher energy while maintaining a determined modeling error energy, Equation (7).
* Compute \(g_{l}^{(k)}|\mathbf{b}_{l}\) for all possible transmitted sequences and store the results in memory. The second stage is the runtime implementation of the algorithms, which is carried out as follows:
* Obtain the weights \(w_{l,k}\).
* Use the weights for calculating \(\tilde{y}_{l}|\mathbf{b}_{l}\) as needed in Equation (13) for the MAP case or Equation (16) for the MLSE case.