# Early Neighbor Rejection-Aided Tabu Search Detection for Large MIMO Systems
## 3 Proposed Low Complexity TS Algorithms  
### ENR with QR-TS  
In each iteration of the conventional TS algorithm, the best neighbor \(\mathbf{x}^{(b)}\) is determined after all neighbors are examined. One drawback of this approach is that the ML metric in (13) must be computed even for unpromising neighbors. To exclude unlikely neighbors as early as possible, we propose an ENR-QR-TS, which performs a layer-by-layer search and excludes unpromising neighbor vectors from examination.  
In the ENR-QR-TS, the neighbor examination starts from the \(N\)th layer and proceeds to the final layer. At the \(N\)th layer, each neighbor's cumulative metric \(\phi_{N}(\mathbf{x})\), which considers only the \(N\)th layer, is computed. We then sort \(L\) neighbors, where \(L\) denotes the number of neighbors, in ascending order of their cumulative metrics and exclude \(k\) neighbors associated with the \(k\) largest cumulative metrics. Hence, in the \((N-1)\)th layer, we consider only \((L-k)\) retained neighbors. Similarly to the \(N\)th layer, the cumulative metrics of the retained \((L-k)\) neighbors are updated for the \((N-1)\)th layer to determine which \(k\) neighbors will be excluded from the remaining procedure. The process to update the cumulative metric and exclude \(k\) neighbors is iterative. Specifically, at layer \(i\), the cumulative metric \(\phi_{i}(\mathbf{x})\) is calculated as  
\[\phi_{i}(\mathbf{x})=\left\{\begin{array}{ll}\phi_{i+1}(\mathbf{x})+|z_{i}+ r_{i,d}\delta_{d}|^{2},&i\leq d\\ \phi_{i+1}(\mathbf{x})+|z_{i}|^{2},&i>d\end{array}\right.. \tag{14}\]  
We sort the cumulative metrics \(\phi_{i}(\mathbf{x})\) in ascending order and exclude the \(k\) neighbors corresponding to the \(k\) largest cumulative metrics. Thus, a larger \(k\) leads to lower complexity but also poor BER performance because it increases the risk of excluding the best neighbor. This means that the value of \(k\) determines the trade-off between complexity and performance.  
Figure 1 illustrates the operation of the proposed ENR scheme for \(k=1\) when there are eight neighbors \((l_{1},\ldots,l_{8})\) and eight layers \((1,\ldots,8)\). To more easily illustrate the operation, it is assumed that the neighbors are excluded in the order of \((l_{8},\ldots,l_{1})\). Figure 1 shows that at layer 8, all the neighbors are examined, i.e., all their cumulative metrics are computed. Assuming that neighbor \(l_{8}\) has the largest cumulative metric, it is excluded from the rest of the process. At layer 7, the remaining seven neighbors' metrics are computed, and neighbor \(l_{7}\) is chosen for exclusion. This process continues to layer 1 until only one neighbor is left to be determined the best neighbor. In Figure 1, it can be observed that the complexity of this process is approximately half the complexity of the conventional TS because, on average, the cumulative metrics are computed for only half the neighbors in an iteration. However, this means there is a risk of excluding the best neighbor. This can happen in early layers when the cumulative metric of the best neighbor is larger than those of other neighbors even though its complete metric \(\phi(\mathbf{x}^{(b)})\) is the smallest among all neighbors. To mitigate this risk, we propose applying a layer ordering scheme to the ENR-QR-TS.