# Adaptive Threshold-Aided K-Best Sphere Decoding for Large MIMO Systems
## 3 K-Best SD Algorithm
### Adaptive Threshold for KSD  
To reduce the computational complexity of the KSD, which can eventually lead to an improved trade-off between the complexity and performance, we consider dynamically adjusting the number of retained nodes at each layer rather than retaining a fixed number of nodes. In the AKSD scheme, the number of retained nodes at each layer is adaptively determined. Specifically, in AKSD, we first select \(K\) contender paths associated with the \(K\) smallest path metrics at each layer of the tree. In addition to those \(K\) paths, we choose additional paths whose path metric is close to that of the \(K\)th path, \(\tau_{i}^{(K)}\), within a threshold \(\Delta_{i}\). Specifically, if the difference between \(\tau_{i}^{(K+m)}\) and \(\tau_{i}^{(K)}\) is less than \(\Delta_{i}\), i.e.,  
\[\tau_{i}^{(K+m)}\leq\Delta_{i}+\tau_{i}^{(K)}, \tag{7}\]  
the node corresponding to \(\tau_{i}^{(K+m)}\) is retained. When only \(\tau_{i}^{(l)}\), \(l=1,2,\ldots,m\), satisfies (7), then \((K+m)\) nodes corresponding to \(\tau_{i}^{(1)},\tau_{i}^{(2)},\ldots,\tau_{i}^{(K+m)}\) are retained, whereas those associated with \(\tau_{i}^{(m+1)},\cdots,\tau_{i}^{(K|\Omega|)}\) are discarded. Let \(K_{v}\) and \(K_{p}\) be the numbers of visited and survival nodes at a layer, respectively. Then, the number of survival nodes becomes \(K_{p}=K+m\) under the assumption that all the survival nodes satisfy the sphere constraint (5). In the \((i-1)\)th layer, \(K_{v}\) is updated to \(K_{v}=K_{p}|\Omega|\). The threshold at layer \(i\) is given by  
\[\Delta_{i}=\alpha\frac{i}{\rho\eta}, \tag{8}\]  
where \(\alpha\) is a constant value to control the threshold, which can be used to optimize the trade-off between performance and complexity, and \(\rho\) is the SNR. Furthermore, \(\eta=\tau_{i}^{(2)}/\tau_{i}^{(1)}\) is the ratio between the second smallest path metric \(\tau_{i}^{(2)}\) and the smallest path metric \(\tau_{i}^{(1)}\) at the \(i\)th layer. In the low-SNR region, a relatively large number of nodes need to be retained to obtain the optimal solution, whereas a small number of retained nodes can be enough at high SNRs. Therefore, in (8), \(\Delta_{i}\) is chosen to be inversely proportional to \(\rho\). Furthermore, to reduce the effect of error propagation, especially in large MIMO systems, where the tree search processes a large number of layers, more nodes should be kept in the higher layers and fewer in the bottom layers. Therefore, \(\Delta_{i}\) is chosen to be proportional to the layer index \(i\), as shown in (8). Intuitively, as the difference between the paths with the first and second smallest path metrics becomes larger, the path with the first smallest path metric becomes more likely to be the true solution [14]. In other words, the node corresponding to the first minimum path metric could lead to the final optimal solution. Therefore, the threshold \(\Delta_{i}\) decreases with the ratio between \(\tau_{i}^{(2)}\) and \(\tau_{i}^{(1)}\), as shown in (8). Algorithm 1 summarizes the procedure of the proposed AKSD scheme. In Algorithm 1, steps 1-7 are used to find the path metrics at each layer of the tree. In step 8, the path metrics are ordered to generate \(\{\tau_{i}^{(l)}\}\). Step 9 computes the threshold \(\Delta_{i}\), which is then used to determine the paths to retain in step 10. ```
0:\(\mathbf{R},\mathbf{z},K,\rho,C_{0},\alpha\)
0:\(\mathbf{\hat{s}}\). 1:for\(i=N\)to 1 do
2:if\(i=N\)then
3: Calculate the path metric of each path \(\mathbf{s}^{(i)}\):
4:\(T(\mathbf{s}^{(i)})=\left|z_{i}-r_{i,i}s_{i}^{(i)}\right|^{2},s_{i}^{(i)}\in\Omega\),
5:else
6: Expand all the surviving \(K_{p}\) nodes at the \(i\)th layer
7: to all \(|\Omega|\) children nodes to generate \(\{\mathbf{s}^{(i)}\}\). 8: For each path \(\mathbf{s}^{(i)}\), compute the path metric:
9:\(T(\mathbf{s}^{(i)})=\sum_{k=i}^{N}\left|z_{k}-\sum_{j=k}^{N}r_{k,j}s_{j}^{(i) }\right|^{2}\),
10:endif
11: Find \(\tau_{i}^{(l)}\), \(l=1,2,\ldots,K_{p}|\Omega|\), by sorting the elements in \(\{T(\mathbf{s}^{(l)})\}\) in ascending order.