Probabilistic Sorting Memory Constrained Tree Search Algorithm for MIMO System

Abstract

Considering the shortcomings of large storage space requirements and high complexity in multiple-symbol differential detection algorithm in current Multiple Input Multiple Output (MIMO) system, this paper proposes a probabilistic sorting memory constrained tree search algorithm (PSMCTS) by using performance advantage of sorting algorithm and storage advantage of memory constrained tree search (MCTS). Based on PSMCTS, a pruning PSMCTS named PPSMCTS is put forward. Simulation results show that the performance of PSMCTS is approach to that of ML algorithm under fixed memory situations, while the computational complexity is lower than that of MCTS algorithm in small storage capacity conditions under low signal noise ratio (SNR) region. PPSMCTS has more prominent advantages on reduction of computational complexity than PSMCTS algorithm. Theoretical analysis and simulation demonstrate that the two proposed algorithms can effectively inherit the good feature of MCTS algorithm, which are suitable for hardware implementation.

Appendices

Appendix A

On the basis of the signal model given in Sect. 2, we define an additional $2(N + 1) \times 2(N + 1)$ information matrix as ${\mathbf{S}} = diag\left\{ {S_{k} ,S_{k - 1} , \ldots ,S_{k - N} } \right\}$. Within one observation window, the received matrix R conditioned on the message matrix S has a multivariate Gaussian conditional Probability Density Function (PDF)

$$ p({\mathbf{R}}|{\mathbf{S}}) = \frac{1}{{\pi^{4(N + 1)} \det\Lambda }}\exp \{ - tr({\mathbf{R}}^{H}\Lambda ^{ - 1} {\mathbf{R}})\} $$

(A.1)

where $\Lambda= {\mathbf{S}}({\mathbf{C}}_{R} \otimes {\mathbf{I}}_{{N_{T} }} ){\mathbf{S}}^{H}$. Here, ${\mathbf{C}}_{R} = \sigma_{n}^{2} {\mathbf{I}}_{N + 1} + {\mathbf{C}}_{h}$ is the covariance matrix of R [18], $\otimes$ denotes the Kronecker product of two matrices or vectors and ${\mathbf{C}}_{h}$ denotes the autocorrelation matrix of the channel which can be expressed as

$$ {\mathbf{C}}_{h} = \left[ {\begin{array}{*{20}c} {C_{h} (0)} & \cdots & {C_{h} (N)} \\ \vdots & \ddots & \vdots \\ {C_{h} ( - N)} & \cdots & {C_{h} (0)} \\ \end{array} } \right]. $$

Thus, the ML decision metric within the observation window can be written as

$$ S_{ML} = \arg \hbox{min} \left\{ {tr({\mathbf{R}}^{H}\Lambda ^{ - 1} {\mathbf{R}}) + \ln \,\det (\Lambda )} \right\} $$

(A.2)

Considering that $\det (\Lambda )$ can be ignored because it is independence with the transmitted information, (A.2) becomes

$$ S_{ML} = \arg \hbox{min} \left\{ {tr({\mathbf{R}}^{H}\Lambda ^{ - 1} {\mathbf{R}})} \right\} $$

(A.3)

Using the results of the literature [19], (A.3) can be simplified to (A.4).

$$ \begin{aligned} \hat{V}_{ML} & = \mathop {\arg \hbox{min} }\limits_{{V_{t + 1} , \ldots ,V_{t + N} }} \sum\limits_{i = 1}^{N} {\sum\limits_{l = i + 1}^{N + 1} { - \tilde{c}_{i,l} ||R[i + t - 1]} } (\prod\limits_{m = i + t}^{l + t - 1} {V[m]} )^{H} \times R[l + t - 1]||_{F}^{2} \\ & = \mathop {\arg \hbox{min} }\limits_{{V_{t + 1} , \ldots ,V_{t + N} }} \sum\limits_{i = 1}^{N} {\sum\limits_{l = i + 1}^{N + 1} {||R[l + t - 1]} } - \tilde{c}_{i,l} (\prod\limits_{m = i + t}^{l + t - 1} {V[m]} ) \times R[i + t - 1]||_{F}^{2} \\ \end{aligned} $$

(A.4)

In formula (A.4), $c_{i,l}$ is the entity element of $\Lambda$ [15]. Normalize $c_{i,l}$ as follows, $c_{m} = \hbox{max} |c_{k,k + 1} |,k = 1, \ldots ,N$ or $c_{m} = c_{{\left\lfloor {N/2} \right\rfloor ,\left\lfloor {N/2} \right\rfloor + 1}}$, $\tilde{c}_{i,l} = {{c_{i,l} } \mathord{\left/ {\vphantom {{c_{i,l} } {c_{m} }}} \right. \kern-0pt} {c_{m} }}$, where $\left\lfloor \cdot \right\rfloor$ denotes the floor operation, $| \bullet |$ denotes the absolute value. When the channel condition remains within an observation window, $C_{h} (n) = 1$. Therefore $\tilde{c}_{i,l} = 1\left( {i = 1,2, \ldots ,N,l = 2, \ldots ,N + 1\,{\text{and}}\,i \ne l} \right)$. So (A.4) can be simplified to (A.5).

$$ \hat{V}_{ML} = \mathop {\arg \hbox{min} }\limits_{{V_{t + 1} , \ldots ,V_{t + N} }} \sum\limits_{i = 1}^{N} {\sum\limits_{l = i + 1}^{N + 1} {||R[l + t - 1]} } - (\prod\limits_{m = i + t}^{l + t - 1} {V[m]} ) \times R[i + t - 1]||_{F}^{2} $$

(A.5)

When N = 1, (A.5) can be simplified to (A.6)

$$ \hat{V} = \mathop {\arg \hbox{min} }\limits_{{V_{t + 1} , \ldots ,V_{t + N} }} ||R[t + 1] - V[t + 1] \times R[t]||_{F}^{2} $$

(A.6)

Appendix B

When observation window N = 1, from formula (A.6), we obtain

$$ \begin{aligned} D & = ||R[t + 1] - V[t + 1]R[t]||_{F}^{2} \\ & = ||C[t + 1]H[t + 1] + W[t + 1] - V[t + 1](C[k]H[t] + W[t])||_{F}^{2} \\ & = ||C[t + 1]H[t + 1] + W[t + 1] - C[k + 1]H[t] - V[t + 1]W[t]||_{F}^{2} \\ \end{aligned} $$

(B.1)

Since it is assumed that the channel remains unchanged at an adjacent interval, i.e. $H[t + 1] = H[t]$, so

$$ D = ||W[t + 1] - V[t + 1]W[t]||_{F}^{2} $$

(B.2)

In this paper, the $W[n],n = t,t + 1, \ldots ,t + N$ is a matrix with NT rows and NR columns, each element follows Gauss distribution with 0 mean and variance $\sigma_{W}^{2}$. It can be seen that $D/2\sigma_{w}^{2}$ is a chi-square random variable with a degree of freedom of $N_{R} N_{T}$. Thus, from formula (A.5), it can be deduced to (B.3) and (B.4) when the length of the observation window is N + 1 in the multi-symbol differential detection system.

$$ \begin{aligned} D & = ||C[t + N]H[t + N] + W[t + N] - V[t + N]C[t + N - 1]H[t + N - 1] - V[t + N]W[t + N - 1]||_{F}^{2} + \ldots \\ & + \,||C[t + N]H[t + N] + W[t + N] - V[t + N - 1]V[t + N]C[t + N - 2]H[t + N - 2] - V[t + N - 1]V[t + N]W[t + N - 2]||_{F}^{2} + \ldots \\ & + \,||C[t + N]H[t + N] + W[t + N] - V[t + 1] \ldots V[t + N - 1]V[t + N]C[t]H[t] - V[t + 1] \ldots V[t + N - 1]V[t + N]W[t]||_{F}^{2} \\ & = \,||C[t + N]H[t + N] + W[t + N] - C[t + N]H[t + N - 1] - V[t + N]W[t + N - 1]||_{F}^{2} + \ldots \\ & + \,||C[t + N]H[t + N] + W[t + N] - C[t + N - 1]H[t + N - 2] - V[t + N - 1]V[t + N]W[t + N - 2]||_{F}^{2} + \ldots \\ & + \,||C[t + N]H[t + N] + W[t + N] - C[t + 1]H[t] - V[t + 1] \ldots V[t + N - 1]V[t + N]W[t]||_{F}^{2} \\ & = \,||W[t + N] - V[t + N]W[t + N - 1]||_{F}^{2} + \ldots + ||W[t + N] - V[t + N - 1]V[t + N]W[t + N - 2]||_{F}^{2} + \ldots \\ & + \,||W[t + N] - V[t + 1] \ldots V[t + N - 1]V[t + N]W[t]||_{F}^{2} \\ \end{aligned} $$

(B.3)

In the derivation of (B.3), the third equal sign assumes that the channel remains constant within an observation interval, resulting in the formula (B.4)

$$ D = \sum\limits_{i = 1}^{N} {\sum\limits_{l = i + 1}^{N + 1} {||W[l + t - 1]} } - (\prod\limits_{m = i + t}^{l + t - 1} {V[m} ]) \times W[i + t - 1]||_{F}^{2} $$

(B.4)

At this point, according to the chi-square random variable degrees of freedom of the nature of the cumulative, $D/2\sigma_{w}^{2}$ is a chi-square random variable with a degree of freedom of $N(N + 1)N_{R} N_{T}$. So, the decision metrics distributed according to the chi-square distribution with $k = 2N(N + 1)N_{R} N_{T} \sigma_{w}^{2}$ degrees of freedom [13]. Its cumulative distribution function (cdf) is given by

$$ F(D;k) = \frac{{\gamma (k/2,D/\sigma^{2} )}}{{\Gamma (k/2)}} $$

(B.5)

where $\sigma^{2}$ is variance of $W[l + t - 1] - (\prod\limits_{m = i + t}^{l + t - 1} {V[m} ]) \times W[i + t - 1]$ in formula (B.4). According to formulas (2) and (3), and the distribution character of channel and noise, $\sigma^{2}$ is equal to $2\sigma_{W}^{2}$. Both $\gamma (.)$ and $\Gamma (.)$ are Gamma functions and show as

$$ \gamma \left( {s,x} \right) = \int_{0}^{x} {t^{s - 1} e^{ - t} dt} $$

(B.6)

$$ \Gamma (x) = \int_{0}^{ + \infty } {t^{x - 1} e^{ - 1} } dt $$

(B.7)