# A Low Complexity Reactive Tabu Search Based Constellation Constraints in Signal Detection
## 3 CC-RTS Algorithm  
**Maximum Likelihood (ML)**: Maximum likelihood detection algorithm calculates the Euclidean distance between the received signal vector and the product of all possible transmitted signal vectors multiplied by channel \(\mathbf{H}\) and searching for the one with the minimum distance. Let \(\mathbf{A}\) denote the whole ML search space with a number of combination candidates which increases exponentially with a raising number of spatial multiplexed transmit antennas modulation level. ML algorithm determines the estimated transmitted signal vector \(\widehat{\mathbf{s}}\) as:  
\[\widehat{\mathbf{s}}_{ML}=\underset{\widehat{\mathbf{s}}\in\mathbf{\mathrm{A}}^{N _{t}}}{\arg\min}\ ||\mathbf{r}-\mathbf{H}\widehat{\mathbf{s}}||^{2} \tag{2}\]  
where \(||\mathbf{r}-\mathbf{H}\widehat{\mathbf{s}}||^{2}\) corresponds to the ML metric of the candidate \(\widehat{\mathbf{s}}\). **Traditional RTS Algorithm**: The implementation of RTS algorithm in massive MIMO [10, 11, 12] is introduced in the following. With sufficient number of receiving antennas, the RTS algorithm has a performance closes to the ML algorithm, but with significant lower detection complexity. This algorithm use the MMSE output as the initial solution vector, and find the neighborhood candidates of the initial solution vector; Then, the algorithm computes the respective ML cost with these candidates and searching for the one with the minimum cost. If it is the case that the selected candidate does not appear in the tabu list (Tabu list is used to hold the initial solution of the next iterative process. The elements in the list follow first in first out FIFO rules. The tabu length indicates that the element will not be used again as the initial solution vector in the next few iterations. The length of tabu is divided into variable and immutable. If the tabu length is fixed, then the algorithm is called fixed tabu search. If the length is a variable, then the algorithm is termed reactive tabu search), the selected candidate is used as the initial value for the next iteration of searching, meanwhile the algorithm includes this selected candidate into the tabu list; On the other hand, if the candidate is already included in the tabu list, a suboptimal solution outside the tabu list is selected as the initial value for the next iteration of searching, and the suboptimal solution is added to the tabu list. After several iterations, the candidate with the minimum ML cost can be selected as the final output of the RTS algorithm. **RTS neighborhood**: The selection criteria of neighborhood candidates in [9] is the metric of Euclidean distance, that is, to find the nearest constellation candidates from a given point. For example: If we use \(\widehat{\mathbf{s}}\) to indicate a transmitting signal symbol, and \(\mathbf{N}\mathbf{e}\mathbf{b}(\widehat{\mathbf{s}})\) denotes the neighborhood candidates of \(\widehat{\mathbf{s}}\). For QPSK modulation, if we consider a \(2\times 2\) MIMO model and the initial value is considered to be \(\widehat{\mathbf{s}}_{i}=\frac{1}{\sqrt{2}}\{-1-j\}\), the number of candidates for \(\widehat{\mathbf{s}}_{i}\) is 2, by finding the nearest two candidates, we have \(\mathbf{N}\mathbf{e}\mathbf{b}(\widehat{\mathbf{s}}_{i})=\frac{1}{\sqrt{2}}\{ -1+j,1-j\}\). For the RTS algorithm, the most expensive step is to find the nearest constellation candidates by measuring Euclidean distance and calculate their respective ML costs [14, 15, 16, 17]. Table 1 shows the number of nearest candidates in different modulation modes. With the increased number of antennas, the number of candidates for the RTS algorithm is raising. The main contribution of the proposed algorithm is to reduce the computational complexity of the conventional RTS by shorten the candidates list. In below, we will introduce in detail of the proposed CC algorithm, and how the CC algorithm can be used for reducing the number of candidates in each iteration of searching.