# Energy-Efficient Hardware Implementation of an LR-Aided K-Best MIMO Decoder for 5G Networks
## 2 Sphere Decoding and the K-Best Algorithm  
In this paper, we consider a MIMO system with \(\mathrm{N_{t}}\) transmit antennas and \(\mathrm{N_{r}}\) receive antennas. The maximum likelihood (ML) detector offers the best achievable BER performance; however, its complexity makes it impractical in terms of hardware implementation. On the other hand, the SDtries to decrease the complexity of ML and to achieve a sub-optimal performance by searching only through those points that fall inside a sphere of radius r, where the SD transforms the ML problem to a tree search [18]. There are many approaches to perform a tree search, where in this work we focus on Breadth-First Search (BFS) using the K-Best algorithm [8; 9]. In the following we describe the original SD algorithm [18] in order to provide some background explanation of the idea of SD, then we describe the LR-aided SD algorithm in the next section, which forms the basis for our implementation.  
The MIMO system is normally modeled using the following equation: \(\mathbf{y}=\mathbf{H}\mathbf{x}+\mathbf{n}\), where \(\mathbf{y}\) represents the received MIMO signal, \(\mathbf{H}\) represents the MIMO channel matrix, \(\mathbf{x}\) represents the transmitted MIMO signal and \(\mathbf{n}\) represents the additive white gaussian noise (AWGN). The ML algorithm for detecting the transmitted signal given the MIMO received signal model can be expressed as:  
\[\hat{\mathbf{x}}=\underset{\mathbf{x}\in\mathcal{X}^{\mathrm{N_{t}}}}{\arg \min}\,||\,\mathbf{y}-\mathrm{H}\mathbf{x}\,||^{2}, \tag{1}\]  
Using the K-Best detector, the ML problem shown in Equation (1) is transformed to Equation (2) as:  
\[\hat{\mathbf{x}}=\underset{\mathbf{x}\in\mathcal{X}^{\mathrm{2N_{t}}}}{\arg \min}\,||\,\hat{\mathbf{y}}-\mathrm{R}\mathbf{x}\,||^{2}. \tag{2}\]  
The operation in Equation (2) is performed after performing QR-decomposition on the channel matrix \(\mathbf{H}\), which results in \(\mathbf{H}=\mathbf{Q}\mathbf{R}\) with \(\mathbf{R}\) being an upper triangular matrix and \(\mathbf{Q}\) a unitary matrix. In (2), \(\tilde{\mathbf{y}}=\mathbf{Q}^{\mathrm{T}}\mathbf{y}\), and \(\mathbf{x}\in\mathcal{X}^{\mathrm{2N_{t}}}\) represents the symbol vector of size \(2\mathrm{N_{t}}\times 1\), where the complex vector of size \(\mathrm{N_{t}}\times 1\) is transformed to a real vector of size \(2\mathrm{N_{t}}\times 1\). Equation (2) refers to a tree search due to the nature of \(\mathbf{R}\), where it normally starts from the last row towards the first row in the \(\mathbf{R}\) matrix. In each layer the K-Best algorithm will select the K candidates having the lowest partial Euclidean distance (PED) from \(\tilde{\mathbf{y}}\). The K-Best algorithm can be summarized as follows:  
1. Initialize the first layer \(\mathrm{i}=2\mathrm{N_{t}}\);
2. Find the PEDs of all expanded nodes at layer \(\mathrm{i}\) and select the K minimum PEDs;
3. Expand the surviving nodes to their \(\sqrt{\mathrm{M}}\) children and set \(\mathrm{i}=\mathrm{i}-1\);
4. If \(\mathrm{i}\
eq 1\) go to step 2, otherwise continue;
5. Select the path with the lowest PEDs as the solution.