## 4 Low Complexity Non-Linear Detection
### Two Approaches for Non-Linear Data Detection
#### 4.2.2 Near ML Detection  
The ML detection using QR decomposition can be reformulated in the following way:  
\[\hat{\chi}=\operatorname*{argmin}_{\chi\in\Omega^{N_{D}}}\|\tilde{\mathbf{v}} -\mathbf{R}\chi\|^{2}. \tag{43}\]The search for the ML solution of the \(\mathbf{\hat{\chi}}\) vector based on the criterion established in Equation (43) can be reflected graphically in the construction of the tree shown in Figure 4. At the \(n\)-th level there are \(q=N_{c}^{N_{D}-n+1}\) possible candidates for \([\mathbf{\hat{\chi}}]_{n}\), where \(n=\{N_{D},N_{D}-1,\cdots,1\}\). The total minimum metric needed to determine the vector with the minimum distance in accordance to Equation (43) is defined as:  
\[d(\mathbf{\hat{\chi}})=\Big{\{}\sum_{j=1}^{N_{D}}\Big{\|}[\mathbf{\hat{v}}]_{j}-\sum_{ i=j}^{N_{D}}[\mathbf{\mathbf{R}}]_{j;i}[\mathbf{\hat{\chi}}]_{i}\Big{\|}^{2}\Big{\}}, \tag{44}\]  
where:  
\[\mathbf{\hat{\chi}}=\big{\{}\mathbf{\hat{\chi}}_{1}.\mathbf{\hat{\chi}}_{2},\cdots,\mathbf{ \hat{\chi}}_{N_{D}}\big{\}}, \tag{45}\]  
corresponds to the trajectory that forms the nodes at the \(n\) levels of the tree. The trajectory minimizes the distance calculated in the Equation (44). The symbol vector \(\mathbf{\chi}\) is defined to the \(n\)-th level as:  
\[\mathbf{\chi}=\big{\{}\mathbf{\chi}_{N_{D}},\cdots,\mathbf{\chi}_{n}\big{\}}, \tag{46}\]  
with \(N_{D}-n+1\) length. Adjusting the Equation (44) to calculate the partial metric for the \(\mathbf{\chi}\) vector, the modification is defined as:  
\[d_{n}(\mathbf{\chi})=\Big{\{}\sum_{j=n}^{N_{D}}\Big{\|}[\mathbf{\hat{v}}]_{j}-\sum_{i= j}^{N_{D}}[\mathbf{\mathbf{R}}]_{j;i}[\mathbf{\chi}]_{i}\Big{\|}^{2}\Big{\}}, \tag{47}\]  
where \(d_{n}(\mathbf{\chi})\) is the value obtained from the accumulated branch metric of the \([\mathbf{\chi}]_{n}\) node that has a \([\mathbf{\chi}]_{N_{D}}\cdots,[\mathbf{\chi}]_{n+1}\) as its predecessor nodes. This distance represents the addition of all of the branch metrics from the root (\(N_{D}\) node) to the node indicated at the \(n\)-th level. The QRD-M algorithm based on the QR decomposition reaches a performance in terms of BER, similar to the ML detector [27]. The QRD-M algorithm is a transversal tree search algorithm. At the \(n\)-th level, the algorithm maintains \(M\) possible candidates before selecting the symbol. Subsequently, the decision of the \(\mathbf{\hat{\chi}}\) vector is performed once the \(N_{D}\) levels have been processed. The search process in the QRD-M algorithm, used to detect the symbols, is run sequentially and is initiated at the last level (\(n=N_{D}\)). The algorithm calculates the metric \(d_{n}(\mathbf{\chi})\), defined in Equation (47), for all the possible values of \(\mathbf{\chi}_{i}\in\Omega\). The distances and the nodes are then arranged in ascending order, and only the \(M\) nodes with the least distance are maintained while the rest are discarded. The same procedure is used for the next level and continues until the first level (\(n=1\)) is processed. The performance of the QRD-M algorithm depends on the established value of \(M\leq N_{c}\); a higher value makes it more probable that the optimal branch is included in the branches selected at the \(n\)-th level. In the search process at each one of the \(n\)-th levels, the tree extends to \(p=MN_{c}\) branches, and their corresponding Euclidean distance is calculated in order to select the surviving \(M\) branches at the \(n\)-th level, as illustrated in Figure 5. This value is much lower than the number of branches \(q=N_{c}^{N_{D}-k+1}\) that are required in the ML algorithm. Additionally, in our proposal, we introduce heuristics so that the number of surviving \(M\) branches per level can be adapted. This value is adjusted during the search process run at each level of the tree. With this modification, the detector complexity is variable, and for a high signal to noise ratio the savings in computational complexity of the detector are significant, maintaining the detector's performance close to that of the ML detector in terms of BER.