# comm.SphereDecoder

Decode input using sphere decoder

## Description

The `comm.SphereDecoder`

System object™ decodes the symbols sent over *N*_{T}
antennas using the sphere decoding algorithm.

To decode symbols using the sphere decoding algorithm:

Create the

`comm.SphereDecoder`

object and set its properties.Call the object with arguments, as if it were a function.

To learn more about how System objects work, see What Are System Objects?

## Creation

### Syntax

### Description

creates a
sphere decoder System object, `spheredecod`

= comm.SphereDecoder`spheredecod`

. This object decodes the
symbols using the sphere decoding algorithm.

sets the `spheredecod`

= comm.SphereDecoder(const,bitTab)`Constellation`

property to `const`

and the
`BitTable`

property to `bitTab`

.

sets properties using one or more optional name-value arguments in addition to any of the
input argument combinations in the previous syntaxes. For example,
`spheredecod`

= comm.SphereDecoder(___,`Name=Value`

)`spheredecod(InitialRadius="ZF solution")`

sets the initial search
radius of the decoding algorithm to `"ZF solution"`

.

## Properties

## Usage

### Syntax

### Description

### Input Arguments

### Output Arguments

## Object Functions

To use an object function, specify the
System object as the first input argument. For
example, to release system resources of a System object named `obj`

, use
this syntax:

release(obj)

## Examples

## Limitations

The output LLR values are not scaled by the noise variance. For coded links employing iterative coding (LDPC or turbo) or MIMO OFDM with Viterbi decoding, scale the output LLR values by the channel state information to achieve better performance.

## Algorithms

This object uses a soft-output Schnorr-Euchner sphere decoder (SESD), executed as a single tree search (STS) for tree traversal, to implement a soft-output max-log a posteriori probability (APP) detector for MIMO systems. The algorithm operates under the assumption that all transmit antennas use the same constellation and bit table. It takes the received symbol vector and the estimated channel matrix as inputs and outputs the log-likelihood ratios (LLRs) of the transmitted bits.

The algorithm models a MIMO system with *N*_{T}
transmit antennas and *N*_{R} receive antennas. It
assumes the system simultaneously transmits *N*_{T}
symbols, described by the equation *y* = *Hs* +
*n*, where *y* is the received symbols,
*H* is the MIMO channel matrix, *s* is the transmitted
symbol vector, and *n* is the thermal noise.

The MIMO detector seeks the maximum-likelihood (ML) solution, $${\widehat{s}}_{ML}$$, such that:

$${\widehat{s}}_{{}_{ML}}=\underset{s\in o}{{\displaystyle {}_{\mathrm{arg}\mathrm{min}}}}{\Vert y-Hs\Vert}^{2}$$

where *O* is the complex-valued constellation from which
the detector selects the *N*_{T} elements of
*s*.

Soft detection also computes a log-likelihood ratio (LLR) for each bit that serves as a measure of the reliability of the estimate for each bit. The calculation of the LLR employs the max-log approximation:

$$L\left({x}_{j,b}\right)=\underset{{\lambda}^{ML}}{\underbrace{\underset{s\in {x}_{j,b}^{(0)}}{\mathrm{min}}{\Vert y-Hs\Vert}^{2}}}-\underset{{\lambda}_{j,b}^{\overline{ML}}}{\underbrace{\underset{s\in {x}_{j,b}^{(1)}}{\mathrm{min}}{\Vert y-Hs\Vert}^{2}}}$$

where,

*L*(*x*_{j,b}) is the LLR estimate for each bit.$${x}_{j,b}$$ is each sent bit, the

*b*th bit of the*j*th symbol.$${x}_{j,b}^{(0)}$$ and $${x}_{j,b}^{(1)}$$ are the disjoint sets of vector symbols that have the

*b*th bit in the label of the*j*th scalar symbol equal to 0 and 1, respectively. The two λ symbols denote the distance calculated as norm squared, specifically:$${\lambda}^{ML}$$ is the distance $${\widehat{s}}_{ML}$$.

$${\lambda}_{j,b}^{{}^{\overline{ML}}}$$ is the distance to the counter-hypothesis, which denotes the binary complement of the

*b*th bit in the binary label of the*j*th entry of $${\widehat{s}}_{ML}$$, specifically the minimum of the symbol set $${x}_{j,b}^{\left({x}_{j,b}^{\overline{ML}}\right)}$$, which contains all of the possible vectors for which the*b*th bit of the*j*th entry is flipped compared to the same entry of $${\widehat{s}}_{ML}$$.

The equation for calculating the LLR estimate of bit $${x}_{j,b}$$ varies depending on whether $${x}_{j,b}^{\left({x}_{j,b}^{ML}\right)}$$ is `0`

or `1`

:

$$L({x}_{j,b})=\{\begin{array}{cc}{\lambda}^{ML}-{\lambda}_{j,b}^{\overline{ML}},\text{\hspace{0.17em}}& {x}_{j,b}^{ML}=\text{\hspace{0.17em}}0\\ {\lambda}_{j,b}^{\overline{ML}}-{\lambda}^{ML},& {x}_{j,b}^{ML}=\text{\hspace{0.17em}}1\end{array}$$

The design of a decoder strives to efficiently find $${\widehat{s}}_{ML}$$, $${\lambda}^{ML}$$, and $${\lambda}_{j,b}^{\overline{ML}}$$.

The search can transform into a tree search through the sphere decoding algorithm. This
involves decomposing the channel matrix into $$H=QR$$ by means of a *QR* decomposition. Then, by left-multiplying
*y* by *Q*^{H}, the problem
reformulates as:

$$\begin{array}{l}{\lambda}^{ML}=\underset{s\in o}{{\displaystyle \text{\hspace{0.17em}}\mathrm{arg}\text{\hspace{0.17em}}\mathrm{min}}}{\Vert \overline{y}-Rs\Vert}^{2}\\ {\lambda}_{j,b}^{\overline{ML}}{=}_{s\in {x}_{j,b}^{\left({x}_{j,b}^{\overline{ML}}\right)}}^{\mathrm{arg}\mathrm{min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\Vert \overline{y}-Rs\Vert}^{2}}\end{array}$$

Using this reformulated problem statement, the triangular structure of
*R* can be exploited to arrange a tree structure such that each of the leaf
nodes corresponds to a possible *s* vector and the partial distances to the
nodes in the tree can be calculated cumulatively adding to the partial distance of the parent
node.

The STS algorithm searches the $${\lambda}^{ML}$$ and $${\lambda}_{j,b}^{\overline{ML}}$$ metrics concurrently. The goal is to have a list containing the metric $${\lambda}^{ML}$$, along with the corresponding bit sequence $${x}^{ML}$$ and the metrics $${x}_{j,b}^{\left({x}_{j,b}^{ML}\right)}$$ of all counter-hypotheses. The subtree originating from a given node is searched only if the result can lead to an update of either $${\lambda}^{ML}$$ or $${\lambda}_{j,b}^{\overline{ML}}$$.

The STS algorithm essentially involves these steps:

If when reaching a leaf node, a new ML hypothesis is found $$\left(d\left(x\right)<{\lambda}^{ML}\right)$$, all $${\lambda}_{j,b}^{\overline{ML}}$$ for which $${x}_{j,b}={x}_{j,b}^{\overline{ML}}$$ are set to $${\lambda}^{ML}$$ which now turns into a valued counter-hypothesis. Then, $${\lambda}^{ML}$$ is set to the current distance,

*d*(*x*).If $$d(x)\ge {\lambda}^{ML}$$, only the counter-hypotheses have to be checked. For all

*j*and*b*for which $$\left(d\left(x\right)<{\lambda}^{ML}\right)$$ and $${x}_{j,b}={x}_{j,b}^{\overline{ML}}$$, the decoder updates $${\lambda}_{j,b}^{\overline{ML}}$$ to be*d*(*x*).When a node's partial distance surpasses the current $${\lambda}_{j,b}^{\overline{ML}}$$ value—a value subject to change during subtree traversal—the algorithm decides to prune that sub-tree.

The STS algorithm stops when it has either visited each tree node once or pruned them.

## References

[1] Studer, C., A. Burg, and H.
Bolcskei. “Soft-Output Sphere Decoding: Algorithms and VLSI Implementation.” *IEEE Journal on Selected Areas in Communications* 26, no. 2
(February 2008): 290–300. https://doi.org/10.1109/JSAC.2008.080206.

[2] Cho, Yong Soo, ed. *MIMO-OFDM Wireless Communications with MATLAB*. Singapore ; Hoboken,
NJ: IEEE Press : J. Wiley & Sons (Asia), 2010.

[3] Hochwald, B.M., and S. Ten Brink.
“Achieving Near-Capacity on a Multiple-Antenna Channel.” *IEEE
Transactions on Communications* 51, no. 3 (March 2003): 389–99.
https://doi.org/10.1109/TCOMM.2003.809789.

[4] Agrell, E., T. Eriksson, A. Vardy,
and K. Zeger. “Closest Point Search in Lattices.” *IEEE Transactions on
Information Theory* 48, no. 8 (August 2002): 2201–14.
https://doi.org/10.1109/TIT.2002.800499.

## Extended Capabilities

## Version History

**Introduced in R2013a**