Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English version of the page.

# comm.SphereDecoder

Decode input using sphere decoder

## Description

The `Sphere Decoder` System object™ decodes the symbols sent over NT antennas using the sphere decoding algorithm.

To decode input symbols using a sphere decoder:

1. Define and set up your sphere decoder object. See Construction.

2. Call `step` to decode input symbols according to the properties of `comm.SphereDecoder`. The behavior of `step` is specific to each object in the toolbox.

### Note

Starting in R2016b, instead of using the `step` method to perform the operation defined by the System object, you can call the object with arguments, as if it were a function. For example, ```y = step(obj,x)``` and `y = obj(x)` perform equivalent operations.

## Construction

`H = comm.SphereDecoder` creates a System object, `H`. This object uses the sphere decoding algorithm to find the maximum-likelihood solution for a set of received symbols over a MIMO channel with NT transmit antennas and NR receive antennas.

`H = comm.SphereDecoder(Name,Value)` creates a sphere decoder object, `H`, with the specified property name set to the specified value. Name must appear inside single quotes (''). You can specify several name-value pair arguments in any order as Name1,Value1,…,NameN,ValueN.

`H = comm.SphereDecoder(CONSTELLATION,BITTABLE)` creates a sphere decoder object, `H`, with the Constellation property set to `CONSTELLATION`, and the `BitTable` property set to `BITTABLE`.

## Properties

 `Constellation` Signal constellation per transmit antenna Specify the constellation as a complex column vector containing the constellation points to which the transmitted bits are mapped. The default setting is a QPSK constellation with an average power of `1`. The length of the vector must be a power of two. The object assumes that each transmit antenna uses the same constellation. `BitTable` Bit mapping used for each constellation point. Specify the bit mapping for the symbols that the `Constellation` property specifies as a numerical matrix. The default is `[0 0; 0 1; 1 0; 1 1]`, which matches the default `Constellation` property value. The matrix size must be `[ConstellationLength bitsPerSymbol]`. `ConstellationLength` represents the length of the `Constellation` property. `bitsPerSymbol` represents the number of bits that each symbol encodes. `InitialRadius` Initial search radius of the decoding algorithm. Specify the initial search radius for the decoding algorithm as either `Infinity` | `ZF Solution`. The default is `Infinity`. When you set this property to `Infinity`, the object sets the initial search radius to `Inf`. When you set this property to `ZF Solution`, the object sets the initial search radius to the zero-forcing solution. This calculation uses the pseudo-inverse of the input channel when decoding. Large constellations and/or antenna counts can benefit from the initial reduction in the search radius. In most cases, however, the extra computation of the `ZF Solution` will not provide a benefit. `DecisionType` Specify the decoding decision method as either `Soft` | `Hard`. The default is `Soft`. When you set this property to `Soft`, the decoder outputs log-likelihood ratios (LLRs), or soft bits. When you set this property to `Hard`, the decoder converts the soft LLRs to bits. The hard-decision output logical array follows the mapping of a zero for a negative LLR and one for all other values.

## Methods

 step Decode received symbols using sphere decoding algorithm
Common to All System Objects
`release`

Allow System object property value changes

## Examples

expand all

Modulate a set of bits using 16-QAM constellation. Transmit the signal as two parallel streams over a MIMO channel. Decode using a sphere decoder with perfect channel knowledge.

Specify the modulation order, the number of transmitted bits, the Eb/No ratio, and the symbol mapping.

```bps = 4; % Bits per symbol M = 2^bps; % Modulation order nBits = 1e3*bps; ebno = 10; symMap = [11 10 14 15 9 8 12 13 1 0 4 5 3 2 6 7];```

Generate and display the symbol mapping of the 16-QAM modulator by using the `qammod` function and the custom symbol map.

`sym = qammod(symMap(1:M)',M,symMap,'UnitAveragePower',true,'PlotConstellation',true);`

Convert the decimal value of the symbol map to binary bits using the left bit as the most significant bit (msb). The `M`-by-`bps` matrix `bitTable` is used by the sphere decoder.

`bitTable = de2bi(symMap,bps,'left-msb');`

Create a 2x2 MIMO Channel System object with `PathGainsOutputPort` set to `true` to use the path gains as a channel estimate. To ensure the repeatability of results, set the object to use the global random number stream.

```mimo = comm.MIMOChannel( ... 'PathGainsOutputPort',true, ... 'RandomStream','Global stream');```

Create an AWGN Channel System object.

`awgnChan = comm.AWGNChannel('EbNo',ebno,'BitsPerSymbol',bps);`

Create a Sphere Decoder System object that processes bits using hard-decision decoding. Configure using the custom bit table and symbol map.

```sphDec = comm.SphereDecoder('Constellation',sym, ... 'BitTable',bitTable,'DecisionType','Hard');```

Create an error rate System object.

`berRate = comm.ErrorRate;`

Set the global random number generator seed.

`rng(37)`

Generate a random data stream.

`data = randi([0 1],nBits,1);`

Modulate the data and reshape it into two streams to be used with the 2x2 MIMO channel.

```modData = qammod(data,M,symMap,'InputType','bit','UnitAveragePower',true); modData = reshape(modData,[],2);```

Pass the modulated data through the MIMO fading channel and add AWGN.

```[fadedSig,pathGains] = mimo(modData); rxSig = awgnChan(fadedSig);```

Decode the received signal using `pathGains` as a perfect channel estimate.

`decodedData = sphDec(rxSig,squeeze(pathGains));`

Convert the decoded hard-decision data, which is a logical matrix, into a double column vector to enable the calculation of error statistics. Calculate and display the bit error rate and the number of errors.

```dataOut = double(decodedData(:)); errorStats = berRate(data,dataOut); errorStats(1:2)```
```ans = 2×1 0.0380 152.0000 ```

## Algorithm

This object implements a soft-output max-log a posteriori probability (APP) MIMO detector by means of a soft-output Schnorr-Euchner sphere decoder (SESD), implemented as single tree search (STS) tree traversal. The algorithm assumes the same constellation and bit table on all of the transmit antennas. Given as inputs, the received symbol vector and the estimated channel matrix, the algorithm outputs the log-likelihood ratios (LLRs) of the transmitted bits.

The algorithm assumes a MIMO system model with NT transmit antennas and NR receive antennas where NT symbols are simultaneously sent, expressed as:

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, , such that:

`${\stackrel{^}{s}}_{{}_{ML}}=\underset{s\in o}{{}_{\mathrm{arg}\mathrm{min}}}{‖y-Hs‖}^{2}$`

where O is the complex-valued constellation from which the NT elements of s are chosen.

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 LLR is calculated as using the max-log approximation:

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

where

• L(xj,b) is the LLR estimate for each bit.

• ${x}_{j,b}$ is each sent bit, the bth bit of the jth symbol.

• ${x}_{j,b}^{\left(0\right)}$ and ${x}_{j,b}^{\left(1\right)}$ are the disjoint sets of vector symbols that have the bth bit in the label of the jth scalar symbol equal to 0 and 1, respectively. The two λ symbols denotes the distance calculated as norm squared., specifically:

• ${\lambda }^{ML}$ is the distance ${\stackrel{^}{s}}_{ML}$.

• ${\lambda }_{j,b}^{{}^{\overline{ML}}}$ is the distance to the counter-hypothesis, which denotes the binary complement of the bth bit in the binary label of the jth entry of ${\stackrel{^}{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 bth bit of the jth entry is flipped compared to the same entry of ${\stackrel{^}{s}}_{ML}$.

Based on whether ${x}_{j,b}^{\left({x}_{j,b}^{ML}\right)}$ is `0` or `1`, the LLR estimate for bit ${x}_{j,b}$ is computed as follows:

`$L\left({x}_{j,b}\right)=\left\{\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 ${\stackrel{^}{s}}_{ML}$, ${\lambda }^{ML}$, and ${\lambda }_{j,b}^{\overline{ML}}$.

This search can be converted into a tree search by means of the sphere decoding algorithms. To this end, the channel matrix is decomposed into $H=QR$ by means of a QR decomposition. Left-multiplying y by QH, the problem can be reformulated as:

`$\begin{array}{l}{\lambda }^{ML}=\underset{s\in o}{\text{\hspace{0.17em}}\mathrm{arg}\text{\hspace{0.17em}}\mathrm{min}}{‖\overline{y}-Rs‖}^{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}}{‖\overline{y}-Rs‖}^{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.

In the STS algorithm, the ${\lambda }^{ML}$ and ${\lambda }_{j,b}^{\overline{ML}}$ metrics are searched 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 sub-tree 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 flow can be summarized as:

1. 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).

2. If $d\left(x\right)\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).

3. A sub-tree is pruned if the partial distance of the node is bigger than the current ${\lambda }_{j,b}^{\overline{ML}}$ which may be affected when traversing the subtree.

4. The STS concludes once all of the tree nodes have been visited once or pruned.

## 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, the output LLR values should be scaled by the channel state information to achieve better performance.

## Selected Bibliography

[1] Studer, C., A. Burg, and H. Bölcskei. “Soft-Output Sphere Decoding: Algorithms and VLSI Implementation”. IEEE Journal of Selected Areas in Communications. Vol. 26, No. 2, February 2008, pp. 290–300.

[2] Cho, Y. S., et.al. "MIMO-OFDM Wireless communications with MATLAB," IEEE Press, 2011.

[3] Hochwald, B.M., S. ten Brink. “Achieving near-capacity on a multiple-antenna channel”, IEEE Transactions on Communications, Vol. 51, No. 3, Mar 2003, pp. 389-399.

[4] Agrell, E., T. Eriksson, A. Vardy, K. Zeger. “Closest point search in lattices”, IEEE Transactions on Information Theory, Vol. 48, No. 8, Aug 2002, pp. 2201-2214.