Logo der Uni Stuttgart
Sphere Detector - Description
Due to the upper triangular structure of $\mathbf{R}$, not every element of the vector $\mathbf{R} \!\cdot\! \left( \mathbf{s} \!-\! \mathbf{z}_{\mathrm{ZF}} \right)$ depends on every element of $\mathbf{s}$. Based on $\sum_{\mu=1}^{N_{\mathrm{tx}}} \left| \left[\mathbf{R} \!\cdot\! \left( \mathbf{s} \!-\! \mathbf{z}_{\mathrm{ZF}} \right)\right]_{\mu} \right|^2 \leq r_{\mathrm{sphere}}^2$ implying $$\sum_{\mu=1}^{\mathrm{n}} \left| \left[\mathbf{R} \!\cdot\! \left( \tilde{\mathbf{s}} \!-\! \mathbf{z}_{\mathrm{ZF}} \right)\right]_{N_{\mathrm{tx}}-\mu} \right|^2 \leq r_{\mathrm{sphere}}^2 \quad \forall \mathrm{n} = 1,\ldots,N_{\mathrm{tx}}, $$ where the result of the sum depends only on the last $\mathrm{n}$ elements of $\tilde{\mathbf{s}}$. Thus, the search for $\hat{\mathbf{s}}_{\mathrm{SD}}$ can be carried out efficiently as a tree search. The vectors $\tilde{\mathbf{s}}$, that are represented by the tree nodes, are successively filled with all possible QAM-symbols. Hence, the underlying search tree consists of $\frac{2^{M_{\mathrm{b}} \left(N_{\mathrm{tx}}+1\right)} - 1}{2^{M_{\mathrm{b}}} - 1}$ nodes, i.e. one root node and all possible transmit vectors of lengths $1$ to $N_{\mathrm{tx}}$.

Originating from the root node in each node in the $N_{\mathrm{tx}}$ levels one element of $\tilde{\mathbf{s}}$ is added to the parent node's $\tilde{\mathbf{s}}$. Each non-leaf node has $2^{M_{\mathrm{b}}}$ children - one corresponding each possible QAM-symbol. The leafs finally represent the possible transmit vectors $\mathbf{s}.$
A successive element-wise calculation enables the elimination many hypothesis $\mathbf{s}$. Therfore, if for any node $\tilde{\mathbf{s}}$ it is $\sum_{\mu=1}^{\mathrm{n}} \left| \left[\mathbf{R} \!\cdot\! \left( \tilde{\mathbf{s}} \!-\! \mathbf{z}_{\mathrm{ZF}} \right)\right]_{\mu} \right|^2 > r_{\mathrm{sphere}}^2$ all its $2^{M_b} \!\! \cdot \! \frac{2^{M_{\mathrm{b}} \left(N_{\mathrm{tx}}-\mathrm{n}\right)}-1}{2^{M_b}-1}$ descendants can be omitted (all outside of the search sphere).
Note that a suitable choice of the initial search radius can reduce the amount of visited nodes tremendously, especially for higher SNR.